tasodifiy tik-oyoq barmog'i

3*3 taxtada bitta o'yinchi tik-to-barmog'i bor deylik.

U har bir harakatda ehtimoli p bo'lgan X va q = 1-p ehtimollikdagi O ni oladi.

U ketma -ket/ustunli/diagonalli 3X ga ega bo'lishi bilan g'alaba qozonadi va

ketma -ket /kol/ diada 3Oda yutqazadi .

Aks holda, 9 ta harakatdan keyin chizilgan.

Uning eng yaxshi strategiyasi va g'alabani kutish (g'olib = 1, yutqazilgan = 0, durang = 0,5)

bu strategiya yordamida p = 0,5?

Jon Xovgand

Men bu erda hech qanday strategiyani ko'ra olmayapman. U

to'qqiz kvadratning har biriga biror narsa qo'yishga majbur bo'lgani uchun va agar u

sizni to'g'ri tushunsam , u tanlagan yagona tanlov - har bir kvadrat o'z belgisini oladi. Shunday qilib,

har bir kvadratga ketma

-ket ko'rsatma berish strategiyasi har qanday kabi yaxshi va muammo ketma -ket

3X yoki 3O ga yetmasdan taxtani to'ldirish ehtimolini topishga olib keladi . G'olib bo'lgan

xarajatlarni hisoblash juda ahamiyatsiz.

-

Jon Xovgand

, informatika kafedrasi, Univ. Oslo, Norvegiya, mailto: jon. @ifi.uio.no

http://www.ifi.uio.no/

Jon Xovgand

Tasodifiy ravishda

X yoki O ni 1/2 prob bilan ketma -ket uchta X olish ehtimoli , men 237/512 ni hisoblashim mumkin.

Jon Xovgand

Tasodifiy ravishda

X yoki O probini 1/2 bilan ketma -ket uchta X olish ehtimoli , men hisoblay oladigan bo'lsak, 239/512.

Risto Lankinen

Ishonch uchun oldin X ning bir juft bajarish uchun harakat qilish yaxshi

Ey ning bir juft bajarish mumkin maydonga o'ynab "

a uch. Shuning uchun, qolgan

kvadratlarning to'ldirish tartibi strategiyaning mazmunli omilidir.

Denni Kodicek

Savolni o'qish usulida u qaysi ramzdan foydalanayotganini aniqladi va

* keyin * uni taxtaga joylashtirdi. Bunday holda, men eng yaxshi

strategiya deb o'ylagan bo'lardim :

Har bir X ni ketma -ket diagonali

O bo'ylab boshqa kvadratchalarga joylashtiring, shunda barcha kvadratchalar to'lib ketguncha (shundan so'ng

siz diagonalli kvadratlardan birini o'ynashga majbur bo'lasiz, bu esa

yo'qotishga olib keladi ).

G'alaba qozonish ehtimoli- bu 9 burilishdan kamida

uchta uchta X- 1- (1-p)^7 * (1+9p+36p^2). P = 0,5 uchun bu

0,8867 ehtimollikdir

Bu usul hech qachon durangga olib kelmaydi, shuning

uchun durangga imkon beradigan boshqa strategiya yuqori ballga ega bo'lishi mumkin, lekin men bunga shubha qilaman.

Jon Xovgand

Oh, bu mantiqiy.

>Har bir X ni ketma -ket diagonal bo'ylab

joylashtiring>O ni boshqa kvadratchalarga qo'ying, bu kvadratchalar to'lmaguncha (shundan so'ng

siz diagonalli kvadratlardan birini o'ynashga majbur bo'lasiz, natijada

>yo'qotiladi).

>>

Keyin g'alaba qozonish ehtimoli- 9 burilishdan, kamida

>uchtasi X, ya'ni 1- (1-p)^7 * (1+9p+36p^2). P = 0.5 uchun bu

>0.8867 ehtimollikdir

Haqiqatan ham? Men bundan yaxshiroq olaman:

P [no X>= 3] = 1 - P [no X
1 - SUM (i = 0,2) ni tanlang (9, i) * p^i * (1 -p)^(9- i) =

1 - (1 -p)^7 * (28p^2+7p+1)

Va p = 0,5 uchun ->P = 466/512 = 0,91

>>

Bu usul hech qachon durangga olib kelmaydi, shuning

uchun durangga imkon beradigan boshqa strategiya yuqori ballga ega bo'lishi mumkin, lekin men bunga shubha qilaman.

Agar siz yaxshiroq ish qilsangiz, unda faqat ikkita X bilan durang o'ynashingiz kerak bo'ladi,

bu aniq emas.

Denni Kodicek

Mening noto'g'ri arifmetikani bajarish qobiliyatim afsonaviy, lekin

bu erda sizning koeffitsientlaringizni qaerdan olganingizni ko'rmayapman . 9C1 = 9 va 9C2 - 36, shuning uchun men olaman:

1- [(1-p)^9 + p*(1-p)^8*9 + p^2*(1-p)^7*36]

= 1- (1-p)^7 (1+) 9p + 36 p^2)

>>Bu usul hech qachon durangga olib kela olmaydi, shuning uchun durangga imkon beradigan

boshqa

strategiya yuqori ballga ega bo'lishi mumkin, lekin men bunga shubha

qilaman.

>>

Agar siz yaxshiroq ish qilsangiz, unda faqat ikkita X bilan durang o'ynashingiz kerak bo'ladi,

bu aniq emas.

Menimcha, bu ham imkonsiz, lekin "aniq" ekanligiga ishonchim komil emas -

isbotlangan har qanday matematik taklif ahamiyatsiz degan tamoyil bundan mustasno

. O'ylaymanki, har qanday

strategiyani rasman bayon qilish va isbotlash juda qiyin bo'ladi.

Denni Kodicek

>>>Bu usul hech qachon durangga olib kela olmaydi, shuning uchun durangga imkon beradigan

boshqa

>>>strategiyasi yuqori ballga ega bo'lishi mumkin, lekin men bunga

shubha

qilaman.

>>

Agar siz yaxshiroq olaman bo'lsa>>, keyin siz bilan durang qilish kerak faqat ikki Xs,

>>aniq imkonsiz bo'lgan.

>>

Menimcha, bu ham imkonsiz, lekin isbotlangan har qanday matematik taklifning arzimas ekanligi tamoyili

bundan mustasno . O'ylaymanki, har qanday strategiyani rasman bayon qilish va isbotlash juda qiyin bo'ladi.





Oh, men qaytaraman - siz haqsiz, bu aniq. Mening strategiyam

3 yoki undan ko'p X bo'lgan har qanday holat uchun 1 ball , aks holda 0 - va aniqki, har bir

strategiya 3dan kam X bo'lsa, 0 ball olishi kerak, shuning uchun bu

maksimal ball bo'lishi kerak .

Jon Xovgand

(1-p)^2 + 9*p*(1-p) + 36*p*p ga qarang,

bu (1-p)^7 faktorini chiqarib bo'lgandan keyin sizda qoladi .

Denni Kodicek

Buni bilgandim. Men sizga aytaman - mening arifmetika va algebra yomon. Va men hozir

la'nat kitobini yozishga harakat qilaman .

Sterten

ahh, chalkashliklar uchun uzr. Men buni aniq deb o'yladim, lekin hozir

unday emasligini tan olaman .

O'yinchi avval kvadrat tanlaydi, keyin tasodifiy

generator X yoki O chizadi.

yaxshi, agar siz boshqa versiya bilan ham zavqlansangiz!

Denni Kodicek

Bunday holda, men ko'rib turganimdek, yaxshi strategiya yo'q. Qaysi buyurtmani

tanlasangiz ham, g'alaba qozonish imkoniyati bir xil bo'lishi kerak. Chiziq yaratish uchun siz

har doim ikkita qatorni to'ldirish uchun kvadrat qo'yishingiz kerak, va

bu satrni yaratish yoki buzish ehtimoli bir xil bo'ladi.

Stiven Sousa

Majburiy emas. Tasavvur qiling -a, sizning birinchi tanlovingiz chap burchak. Siz "

O" ni olasiz. Sizning keyingi tanlovingiz - uning ostidagi kvadrat. Siz

yana "O" ga ega bo'lasiz. Siz darhol

chap pastki kvadratni tanlashingiz ahmoqlik bo'lardi , chunki yo'qotish

xavfi past bo'lgan boshqa yo'llar mavjud bo'lganda, O o'yinni yo'qotadi.

-

Stiven Sousa

Chris - "bir amerikalik bo'lib, men kasal va boshqa mamlakatlarning charchab olish qilyapman"

Piyoz keltirilgan bo'lib, Langston

bugun tashrifi www.badtasteadvertising.com!

Jon Xovgand

Bu to'g'ri. Men buni ko'rmadim. Men

bu erda hech qanday strategiya yo'q deb o'ylagan birinchi odamman .

Men bu haqda o'ylashim kerak.

Sasha Semenov

Men faqat qo'pol kuch echimini tasavvur qila olaman. Yaxshiyamki, o'yin juda

cheklangan. Quyida ko'rsatilgan oddiy min-max C dasturi quyidagi

natijani beradi:

Qaerdan boshlashingiz muhim emas. Har qanday holatda ham

g'alaba = 281, mag'lubiyat = 199, durang = 32 bo'ladi.

Agar siz markazdan boshlasangiz va X ni olsangiz, o'rta qatorda davom eting:

g'alaba = 187, yo'qotishlar = 53, durang = 16.

Agar siz markazdan boshlasangiz va O ni olsangiz, burchakda davom eting:

g'alaba = 94, mag'lubiyat = 146, chizadi = 16.

/ * mumkin bo'lgan uyali holatlar */

typedef enum CellState;

typedef CellState TTT [9];

int OneTwoThree (CellState *p_ttt, CellState st);

int FindBestCell (TTT ttt,

int *nWonGames, int *nLostGames, int *nDrawnGames);

int main (int argc, char* argv [])

<

TTT ttt = ;

int w = 0;

int l = 0;

int d = 0;

int bestCell;

bestCell = FindBestCell (ttt, & w, & l, & d);

printf ("hujayra =%d, g'alaba =%d, yo'qotishlar =%d, durang =%d", bestCell, w, l, d);

int FindBestCell (TTT ttt,

int *nWonGames, int *nLostGames, int *nDrawnGames)

<

int i;

int w, l, d;

int bestW, bestL, bestD;

int nEmptyCells;

int bestCell, bestScore;



/ * bo'sh hujayralarni sanash */

nEmptyCells = 0;

uchun (i = 0; i

/ *o'yin allaqachon yutilganligini tekshiring */

if (OneTwoThree (ttt, X))

<

*nWonGames += Pow2 [nEmptyCells];

NOCELL -ni qaytarish;

>

/ *o'yin yo'qolganligini tekshiring */

if (OneTwoThree (ttt, O))

<

*nLostGames += Pow2 [nEmptyCells];

NOCELL -ni qaytarish;

>

/ *o'yin chizilganligini tekshiring */

if (nEmptyCells == 0)

<

*nDrawnGames += Pow2 [nEmptyCells];

NOCELL -ni qaytarish;

>

/*agar o'yin hali yutmagan yoki

yutqazmagan bo'lsa, barcha bo'sh hujayralarni sinab ko'ring*/ bestScore = -1;

bestCell = -1;

uchun (i = 0; i
agar (ttt [i] == E)

<

w = l = d = 0;

ttt [i] = X;

FindBestCell (ttt, & w, & l, & d);

ttt [i] = O;

FindBestCell (ttt, & w, & l, & d);

ttt [i] = E;

/*ballni tekshiring*/

if (2*w + 0*l + 1*d>bestScore)

<

bestScore = 2*w + 0*l + 1*d;

bestCell = i;

eng yaxshi W = w; eng yaxshi L = l; eng yaxshiD = d;

>

>

* NWonGames + = bestW;

*nLostGames += eng yaxshi L;

*nDrawnGames += eng yaxshiD;

bestCell -ni qaytarish;

>

int OneTwoThree (CellState *p_ttt, CellState st)

<

if ((p_ttt [0] == st) && (p_ttt [1] == st) && (p_ttt [2] == st)) qaytish 1;

agar ((p_ttt [3] == st) && (p_ttt [4] == st) && (p_ttt [5] == st)) qaytish 1;

agar ((p_ttt [6] == st) && (p_ttt [7] == st) && (p_ttt [8] == st)) qaytish 1;

agar ((p_ttt [0] == st) && (p_ttt [3] == st) && (p_ttt [6] == st)) qaytish 1;

agar ((p_ttt [1] == st) && (p_ttt [4] == st) && (p_ttt [7] == st)) qaytish 1;

agar ((p_ttt [2] == st) && (p_ttt [5] == st) && (p_ttt [8] == st)) qaytish 1;

agar ((p_ttt [0] == st) && (p_ttt [4] == st) && (p_ttt [8] == st)) 1 qaytarish;

agar ((p_ttt [2] == st) && (p_ttt [4] == st) && (p_ttt [6] == st)) qaytish 1;

Erik Nilsen

Agar siz kengashni to'liq to'ldirsangiz, natijani nazorat qila olmaysiz.

Shu bilan birga, 3 ta X va 3 O qatorli to'liq taxtalar mavjud,

shuning uchun menimcha *

har bir belgidan keyin pozitsiyani qayta baholash orqali qaysi biri birinchi bo'lib paydo bo'lishiga ta'sir qilishi mumkin . OTOH, agar

siz haqiqatan ham nazorat qila olmasangiz, men ajablanmayman .

Den Xou

>3*3 taxtada bitta o'yinchi tik-to-barmog'i bor deylik. U

har bir

harakatda p ehtimoli bilan>X va ehtimolligi q = 1-p bo'lgan O ni oladi .

>U ketma

-ket /ustunli/diagonalli 3X ga ega bo'lishi bilan g'alaba qozonadi va >ketma -ket 3/0/mag'lubiyatda mag'lub bo'ladi. Aks holda, 9 ta harakatdan keyin chizilgan.

>Uning eng yaxshi strategiyasi va yutuqni kutishi

>(g'alaba = 1, yutqazilgan = 0, durang = 0,5) bu strategiya yordamida p = 0,5?

>Men bu erda hech qanday strategiyani ko'ra olmayapman. U

har bir to'qqiz kvadratchaga biror narsa qo'yishga majbur bo'lgani uchun

, agar u sizni to'g'ri tushunsam, har bir

kvadrat o'z belgisini olganida bo'ladi. Shunday qilib, ishora qilish strategiyasi

>ketma -ketlikdagi har bir kvadrat har qanday kabi yaxshi.

Risto Lankinen ta'kidlaganidek, kvadratlar qachon

belgilanishi to'g'risida qaror qabul qilish muhim, chunki agar X ham, O ham

ketma -ket uchtasini oladigan bo'lsa , g'olib birinchi bo'lib uchtasini oladi.

>Tasodifiy ketma -ket uchta X -ni olish ehtimoli

>1/2 yoki X bilan O ni olish, men hisoblay

oladigan bo'lsak>239/512.

Men ketma -ket uchta X -ning 282/512 - 198/512 ehtimolini olaman va

ketma -ket uchta Os yo'q , va X va O -ning ketma -ket uchta bo'lishining 84/512 ehtimolligi

. Bellashuv ehtimoli (ketma

-ket uchtasi yo'q) - 32/512.

Men yozgan dastur barcha natijalar jadvalini tuzdi:

.

: OOO qatorlar soni

:: | .

: | : XXX qatorlar soni

:: v: 0 1 2 3 4 5 6 8

::.

: 0: 32 74 66 34 13 6 4 1

: 1: 74 72 6

: 2: 66 6

: 3: 34

: 4: 13

: 5: 6

: 6: 4

: 8: 1

.

Har bir natijaning 1/512 ehtimolligi bo'lsa.

Denni Kodicek yozgan:

>Men savolni o'qiganimda, u qaysi ramz ekanligini aniqladi

>yordamida va * keyin * uni doskaga joylashtiradi.

Keyinchalik Guenter aniqlaganidek, bu maqsadli o'qish emas. Men buni

tekshirmaganman.

Jon Xogsandning tahlillari yordam beradi, chunki bizga

aytadiki, hech qanday ketma -ketlikning hech qanday foydasi yo'q, X va O

to'qqiz harakatdan keyin ketma -ket uchta bo'ladi . Agar ikkalasida ham ketma -ket uchta bo'lsa

, diagonal qator ham yo'q, shuning uchun diagonallar strategiyaga ta'sir qilmaydi.

Diagonallar g'alaba qozona olmaydigan o'yinni tahlil qilish

osonroq bo'lishi mumkin , chunki avtomorfizm guruhida

8 -o'rniga 72 -sonli buyurtma bor . Biroq, qo'pol kuch dasturiga bu

soddalashtirish kerak emas .

Uch o'lchovli tik-to-barmog'ini ko'rib chiqish qiziq bo'lishi mumkin

, bunda diagonal g'alabalar bir nechta g'alabalarga to'sqinlik qilmaydi, shuning uchun

diagonallar strategik ahamiyatga ega.

Mening dasturim

281/512 ehtimollik bilan g'alaba qozonib, quyidagi strategiyani optimal deb topdi:

1. Agar doskada bitta X bo'lsa va Os bo'lmasa, keyingi o'yinni

X o'z ichiga olgan gorizontal yoki vertikal chiziqlardan birida bajaring.

2. Agar doskada bitta O bo'lsa va X bo'lmasa, keyingi o'yinni O ni o'z ichiga olgan

gorizontal va vertikal chiziqlardan boshqa joyda bajaring.

3. Aks holda, agar

ikkita Osni o'z ichiga olgan chiziqda bo'lmagan bo'sh maydon bo'lsa , navbatdagi o'yinni shunday

maydonga o'tkazing.

4. Aks holda, har qanday mumkin bo'lgan harakatni qiling.

Birgalikda o'tkazilgan 32 ta o'yin bilan birga,

har bir o'yinga 297/512 ochko kutilmoqda .

E'tibor bering, bu 1/512 X

ketma -ket uchta pozitsiya sonidan kamroq . Ko'rinib turibdiki, bu vaziyatga bog'liq

unda 1/4 ehtimollik bilan birinchi kvadrat

O, ikkinchisi X bo'ladi.

Sterten

Kimda faqat p = 1/2 emas, balki har qanday p uchun ishlaydigan dastur bormi?

Sterten

>Uch o'lchovli tik-to-barmog'ini ko'rib chiqish qiziq bo'lishi mumkin

, bunda diagonal g'alabalar bir nechta g'alabalarga to'sqinlik qilmaydi, shuning uchun

diagonallar strategik ahamiyatga ega.

3 yoki undan ko'p o'lchamlarda bizda har xil diagonallar mavjud.

Va murakkablik tezda ko'tariladi, shuning uchun kompyuter dasturi

juda sekin bo'lishi mumkin.

>Mening dasturim quyidagi strategiyani eng maqbul deb topadi: g'alaba qozonish

ehtimoli 281/512:

>>

1. Agar bortda bitta X bo'lsa va Os bo'lmasa, keyingi o'yinni

>gorizontal yoki vertikal chiziqlardan birida bajaring . X.

>

>2. bor bir O va hech Xs bortida, keyingi o'yin qilish bo'lsa

gorizontal va vertikal chiziqlar ustida ortiq>qaerdadir boshqa

O. o'z ichiga>

>

bir bo'sh kvadrat deb bor bo'lsa, Aks holda>3.

Ikkita Osni o'z ichiga olgan chiziqda emas , keyingi o'yinni har qanday

kvadratda bajaring .

>>

4. Aks holda, mumkin bo'lgan harakatni qiling.

O'ylaymanki, bu 3x3 (?) Dan kattaroq kvadrat taxtalarni umumlashtiradi.

Strategiya 1/2 dan kattaroq yoki kichikroq uchun ham ishlaydimi?

Optimal strategiya shunga o'xshash muammolarga bog'liqmi?

(boshqa taxtalar, o'lchamlar, boshqa "diagonallar" va boshqalar.)

3 yoki undan ko'p o'lchovlarda

bu diagonallarning umumiy ko'rinishini ushlab turish oson emas, lekin umumiy strategiya

qatorda/col/diada ko'p sonli X-esli

hujayralarni tanlash va qatorida ko'p osli hujayralardan saqlanish bo'lishi kerak. /col/dia.

Ed Merfi

Mana mening qo'pol urinishim, faqat

kompilyatsiya qilinganida ko'rsatgichni aylantirish bo'yicha bir nechta ogohlantirishlar va bajarilganda segfault. Kimdir uni tuzatmoqchi?

float prob_win (int m [], float p) <

float result = 0.0, prob_sub;

int ox [9], b [9], i, win_lose_draw;

/ * bu aniq XO ketma -ketligi ehtimoli */

/* ushbu XO ketma -ketligini tartibda qo'llang;

bu bizga g'alaba, yutqazish yoki durang beradimi? */

/ * p = X * ehtimoli/

float p = 0,5, p_win, max_p_win = -1,0;

int m [9], maksimal_m [9], i;

/ * 1 2 3

4 5 6

7 8 9 */

/* simmetriya tufayli biz ba'zi m [1] qiymatlarni o'tkazib yuborishimiz mumkin;

3 dan 5 gacha bizga burchak (3), yon (4) va markaz (5) beradi */

p_win = prob_win (*m, p);

agar (p_win>max_p_win) <

max_p_win = p_win;

uchun (i = 1; i
>

printf (" %d %d %d %d %d %d %d %d \ n",

maksimal_m [1], maksimal_m [2], maksimal_m [3], maksimal_m [4], maksimal_m [5], maksimal_m [6], maksimal_m [7], maksimal_m [8], maksimal_m [9]);

printf ("%f \ n", max_p_win);

>

Sasha Semenov

Bu algoritm boshqa muammoni hal qiladi, ya'ni:

O'zingizning harakatlaringizning eng yaxshi ketma

-ketligini tuzing

va o'yin davomida X va O ko'rinishiga qaramay, oldindan belgilangan ketma-ketlikni saqlang .

(Men shubhalanamanki, bunday talqinda

ketma -ketlikni tanlash muhim emas)

Yaxshiyamki, men bir nechta ahamiyatsiz xatolarni tuzatishga ruxsat oldim:

float prob_win (int m [], float p) <

float result = 0.0, prob_sub;

int ox [10], b [10], i, win_lose_draw;

/ * bu aniq XO ketma -ketligi ehtimoli */

/* ushbu XO ketma -ketligini tartibda qo'llang;

bu bizga g'alaba, yutqazish yoki durang beradimi? */

/ * p = X * ehtimoli/

float p = 0,5, p_win, max_p_win = -1,0;

int m [10], maksimal_m [10], i;



agar (p_win>max_p_win) <

max_p_win = p_win;

uchun (i = 1; i
>

printf (" %d %d %d %d %d %d %d %d \ n",

maksimal_m [1], maksimal_m [2], maksimal_m [3], maksimal_m [4], maksimal_m [5], maksimal_m [6], maksimal_m [7],

maksimal_m [8], maksimal_m [9]);

printf ("%f \ n", max_p_win);

Charlz Bryant

Xo'sh, men

quyida keltirilgan dastur bilan 0,580078125 yoki 297/512 (ya'ni g'alaba + 0,5 * durang) yutuq kutaman . Ko'rinib turibdiki, ba'zi

hollarda strategiya farq qiladi. Bunda:

Agar siz burchakda o'ynasangiz, u "X" bo'lsa (p = 0,5) g'alaba qozonasiz, yoki

"O" bo'lsa (p = 0,5), kutilgan 0,5 ball uchun yutqazasiz.

Agar siz pastki chetining o'rtasini o'ynasangiz, u

"O" (p = 0,5) bo'lsa yutqazasiz, lekin "X" bo'lsa, endi burchakda o'ynashingiz kerak,

agar u ham "X" bo'lsa , g'alaba qozonasiz. (p = 0,5*0,5), agar u "O" bo'lsa, yo'qotish. Bu

kutilgan 0,25 ballni beradi.

Mening dasturim barcha mumkin bo'lgan lavozim pozitsiyalarini baholaydi va shuni aytadiki

, pozitsiya uchun kutilgan ball -

bu bo'sh maydonlardan birini tanlash uchun olishingiz mumkin bo'lgan eng yaxshi ball , bu esa o'z navbatida

"x" va "o" ni sinab ko'rish orqali baholanadi . kvadrat

yordamida va kutilgan ballarni birlashtirib, p yordamida.

Vaqtni tejash uchun, u har doim taxtani baholasa, natijani saqlaydi va

agar bu lavozim haqida yana so'ralsa, undan foydalanadi. Bu ko'p

vaqtni tejaydi, chunki bir xil pozitsiyaga har xil yo'llar bilan erishish mumkin.

Mana dastur:

# o'yin qoidalari: siz bo'sh maydonni ko'rsatasiz va

u erda "X" yoki "O" paydo bo'ladi. Agar siz "X" qatorga kirsa, 1 ball olasiz, agar "O"

# qatorga kirsa , hech narsa ; taxta bir chiziq oldin to'lgan bo'lsa va 0,5 hosil bo'ladi

#

$ g_probx = 0,5; # "O" ehtimoli

%g_expsco = (); # saqlangan natijalar har bir mumkin bo'lgan pozitsiya uchun

%g_best = (); Har bir pozitsiyada # eng yaxshi harakat



$ g_board = '' x 9 taxtasini ishga tushiring;

# qidiruvni ishga tushirish

& calcpos;

# hozir $ g_expsco chop etish "expsco =", $ g_expsco , "\ n";

#

($ i = 0; $ i
substr ($ g_board, $ i, 1) = 'x' har bir mumkin bo'lgan birinchi harakat uchun kutilgan ballarni chop etishga harakat qilaylik;

mening $ p = $ g_expsco * $ g_probx;

substr ($ g_board, $ i, 1) = 'o';

$ p += $ g_expsco * (1 - $ g_probx);

substr ($ g_board, $ i, 1) = '*';

chop etish "'$ g_board' ->", $ p, "\ n";

substr ($ g_board, $ i, 1) = '';

>

# va eng yaxshi birinchi harakatlar ro'yxatini ko'rsatish

"eng yaxshi birinchi harakat:", qo'shilish (',', @>), "\ n";

# find expected score from current position

# if we already calculated it, return the pre-calculated

# value, otherwise calculate and save the value

sub calcpos
my $p = $g_expsco;

return $p if defined $p;

return $g_expsco = &expsco;

>

sub expsco
# check for game ended

return 1 if $g_board =

/^xxx. $/; # rows

return 0 if $g_board =

/^ooo. $/;

return 1 if $g_board =

/^. xxx. $/;

return 0 if $g_board =

/^. ooo. $/;

return 1 if $g_board =

/^. xxx$/;

return 0 if $g_board =

/^. ooo$/;

return 1 if $g_board =

/^x..x..x..$/; # columns

return 0 if $g_board =

/^o..o..o..$/;

return 1 if $g_board =

/^.x..x..x.$/;

return 0 if $g_board =

/^.o..o..o.$/;

return 1 if $g_board =

/^..x..x..x$/;

return 0 if $g_board =

/^..o..o..o$/;

return 1 if $g_board =

/^x. x. x$/; # diagonals

return 0 if $g_board =

/^o. o. o$/;

return 1 if $g_board =

/^..x.x.x..$/;

return 0 if $g_board =

/^..o.o.o..$/;

return 0.5 unless $g_board =

/ /; # draw if no space

# game not over yet - make best possible move

my $best = 0;

my $i;

my @move = ();

for ($i=0; $i < 9; $i++) < # for each square

# check it's vacant

next unless substr($g_board, $i, 1) eq ' ';

# what if we get a 'o'

substr($g_board, $i, 1) = 'o';

my $po = &calcpos;

# what if we get a 'x'

substr($g_board, $i, 1) = 'x';

my $px = &calcpos;

# put it back the way we found it

substr($g_board, $i, 1) = ' ';

my $p = $px * $g_probx + $po * (1 - $g_probx);

if ($p >= $best)
@move = () if $p >$best;

$best = $p;

push(@move, $i);

>

>

$g_best = \@move;

return $best;

>

------------------------------------------------------------------------

Ed Murphy

>>>Who has a program which works for any p, not only p=1/2 ?

>>

>>Here's my rough attempt, except it gets a few pointer conversion warnings

>>when compiled, and a segfault when executed. Someone want to fix it up?

>

>

>This algorithm will solve a different problem, namely:

>

>Construct the best sequence of moves you can, and

>stick to this pre-defined sequence regardless of

>X's and O's appearance during the actual game.

>(I strongly suspect that in such interpretation the

>choice of sequence simply does not matter)

I have trouble forming an intuition on this one. Note that the

program didn't attempt to look for ties.

>Anyway I took the liberty to fix few insignificant bugs:

They're significant if they prevent the segfault! Yeah, I figured

it was some simple error of array-passing. My C is quite rusty.

So can someone solve the original generalized problem? i.e. the

sequence is not pre-defined, but is adjusted on the fly, based on

the X's and O's that have appeared so far.

e.g. let's say you get to this position:

1 2 O

4 O 6

7 8 9

you would be well-advised to avoid 7 for now, and instead pick

(say) 1 and 4, to see if you luck out and get a pair of X's.

Actually, intuition says that picking 3-and-5 first can be bested

by picking 3-and-2 first. If they both come up O, then you've

got three more winning lines to try (1-4-7 4-5-6 7-8-9), versus

only two (1-4-7 7-8-9).

Also note that, even if you get to a position where you can't win,

you still need to try for a draw rather than a loss.

Arthur J. O'Dwyer

>>>>Who has a program which works for any p, not only p=1/2 ?

>>>Here's my rough attempt, except it gets a few pointer conversion warnings

>>>when compiled, and a segfault when executed. Someone want to fix it up?

>>

>>This algorithm will solve a different problem, namely:

>>

>>Construct the best sequence of moves you can, and

>>stick to this pre-defined sequence regardless of

>>X's and O's appearance during the actual game.

>>(I strongly suspect that in such interpretation the

>>choice of sequence simply does not matter)

I think you (Sasha) are right about that variant of the puzzle,

although I'm not sure either.

>So can someone solve the original generalized problem? i.e. the

>sequence is not pre-defined, but is adjusted on the fly, based on

>the X's and O's that have appeared so far.

[snip strategy tidbit]

Here is a C++ program (tested on DJGPP; should be portable) that

calculates the expected outcome if the player plays as intelligently

as possible. It essentially plays minimax, except that it's more of

averagey-max, since we weight the "opponent's" two moves instead of

taking the minimum.

You can vary the P defined in main() in order to calculate different

P-values. The output number is the expected winnings of a player who

plays a series of games against the "opponent", betting SCALE dollars

each time. Thus, any positive number is a winning record. The number

for P=0.5 is about 0.16, or about 138:100 odds of winning. P has to

drop all the way to 0.4614. before the strategy breaks even.

If someone could come up with a way to see what the best strategy

really *is*, that would be pretty cool. Problem is, it probably branches

out pretty quickly, so it'd be hard to write down.

ObVariant: Does the optimal strategy change as a function of P? If so,

where are the point(s) at which the strategy changes? (I.e., does P=0.1

suggest a more conservative strategy than P=0.9?)

Very interesting puzzle, BTW!

#define _ 0

#define X 1

#define O 2

#define SCALE 1.0

struct Board


int bnum;

int B[9];

Board *Child[9][2];

double avg_score[9];

double best_score;

Board(int bignum): bnum(bignum)


for (int i=0; i < 9; ++i)
B[i] = bignum % 3; bignum /= 3;

Child[i][0] = Child[i][1] = NULL;

avg_score[i] = 0.0;

>

>

static int plus(int symbol, int square)


while (square--) symbol *= 3;

return symbol;

>

double eval(void)


if (B[0] != _ && B[0] == B[1] && B[1] == B[2]) return SCALE*(-1+2*(B[0]==X));

if (B[3] != _ && B[3] == B[4] && B[4] == B[5]) return SCALE*(-1+2*(B[3]==X));

if (B[6] != _ && B[6] == B[7] && B[7] == B[8]) return SCALE*(-1+2*(B[6]==X));

if (B[0] != _ && B[0] == B[3] && B[3] == B[6]) return SCALE*(-1+2*(B[0]==X));

if (B[1] != _ && B[1] == B[4] && B[4] == B[7]) return SCALE*(-1+2*(B[1]==X));

if (B[2] != _ && B[2] == B[5] && B[5] == B[8]) return SCALE*(-1+2*(B[2]==X));

if (B[0] != _ && B[0] == B[4] && B[4] == B[8]) return SCALE*(-1+2*(B[0]==X));

if (B[2] != _ && B[2] == B[4] && B[4] == B[6]) return SCALE*(-1+2*(B[2]==X));

return 0;

>

void deepify(double Prob_of_X);

>;

void Board::deepify(double P)


if ( fabs(eval()) >SCALE/2.0 || ( !has(_) ))
best_score = eval();

printf("Just finished board");

for (int i=0; i < 9; ++i)

printf(" %c", B[i]==_?'_':B[i]==X?'X':'O');

printf("\n");

return;

>

for (int i=0; i < 9; ++i)
if (Child[i][0] != NULL)


avg_score[i] = P * Child[i][0]->best_score

+ (1.-P) * Child[i][1]->best_score;

>

else if (B[i] == _)

Child[i][0] = all_possible_boards[bnum + plus(X,i)];

Child[i][1] = all_possible_boards[bnum + plus(O,i)];

Child[i][0]->deepify(P);

Child[i][1]->deepify(P);

avg_score[i] = P * Child[i][0]->best_score

+ (1-P) * Child[i][1]->best_score;

>

else avg_score[i] = -100.0*SCALE;

>

best_score = avg_score[0];

for (int i=1; i < 9; ++i)
if (avg_score[i] >best_score)

best_score = avg_score[i];

>

>

int main(void)


double P = 0.1;

for (int i=0; i < 19683; ++i)
all_possible_boards[i] = new Board(i);

>

printf("Starting calculations. \n");

all_possible_boards[0]->deepify(P);

printf("The best return is %g.\n", all_possible_boards[0]->best_score);

return 0;

>

Charles Bryant

Actually, no. The squares 1, 4, 7, 8, and 9 are all equally good. To

see why, consider how the game will end. If it's a draw, you must

have nominated every square and formed no lines. In that case it

doesn't matter in what order you chose the squares - you just

multiply the probabilities.

If you win, there are only two possible winning lines 1-4-7 and 7-8-9.

Since they both need an 'X' in 7, you're forced to nominate 7

eventually. When you do, there are obviously no lines (since the game

would have ended earlier if there were) so again it doesn't matter

in what order you chose the squares - the probability of the

configuration is the same.

Finally, consider what happens if you choose 2 or 6. If you get a

'x', you're no closer to winning, since it can't form part of a

winning line, hower you are closer to losing. With 2 empty, if you

nominate 8 and get a 'o', you try 4 instead; but if there's a 'o' on

2, you lose immediately.

I think, in general, if, in order to win, you need an 'x' on one of a

set of squares, then it is always better to nominate one from that set.

Dan Hoey

On 18 Jun, I presented a computer-calculated

strategy that I claimed was optimal for p=1/2.

It turns out that the strategy I reported was

incorrect. My program had found the correct

strategy (and optimal payoff) but there was an

error in printing out the results. Since then, I

have found some simplifications that enabled an

analysis by hand, which results in a strategy that

is optimal for any probability p.

Several people observed that in many cases there

is no strategy that can affect the outcome of the

game. This can be expressed by considering the

following game equivalent to Random Tic-Tac-Toe:

RT2: A fair umpire chooses one of the 512

configurations of Xes and Os according to

the defined probability. That is, any

configuration with k Xes and 9-k Os

occurs with probability p^k q^(1-k). The

umpire then takes a deck of cards, and places

nine cards face down in a 3-by-3 square, using

black for an X and red for an O. The

player then moves by turning the cards face up

one at a time. If a line of three blacks is

turned over before any line of three reds, the

player scores 1. If nine cards are turned

over with no three-in-line, the player scores

1/2.

We may take further advantage of our umpire by

having him circumvent play in games where the

outcome is not dependent on the play, in the

following equivalent game.

RT3: The fair umpire places cards as in RT2.

Then the umpire considers whether the

configuration includes a line of three Xes,

a line of three Os, both, or none. If there

are not both kinds of line, the umpire turns

all the cards over. Otherwise the player must

turn the cards over one at a time. Scoring is

as in RT2.

In RT3, let us call a configuration of nine Xes

and Os "playable" if the umpire gives the player

a chance to move. There are only 84 playable

configurations. No playable configuration has a

diagonal line of three, so the game is unchanged

by permuting the ranks and files or rotating the

board. Up to these equivalences, the only four

kinds of playable configurations are:

X | X | X X | X | X X | X | X X | X | X

---+---+--- ---+---+--- ---+---+--- ---+---+---

X | X | X X | X | O X | O | O O | O | O

---+---+--- ---+---+--- ---+---+--- ---+---+---

O | O | O O | O | O O | O | O O | O | O .

There are respectively 6, 36, 36, and 6

configurations of these types, occurring with

respective probabilities p^6 q^3, p^5 q^4,

p^4 q^5, and p^3 q^6. My analysis by hand

indicates that any strategy will lose at least one

of the configurations of the third kind, and that

there are strategies in which that is the only

playable configuration that is lost. One such

strategy is for the player to make the nth move

in the square containing the digit n in the

following diagram

until the exposed card does not match the X or

O marking in the diagram. If that failure to

match occurs, the player has a guaranteed win with

correct play. If the eighth move is made with a

match, the player loses.

To express the payoff for this game, define

9

f(x_1,x_2. x_9) = SUM x_k p^k q^(9-k) .

k=1

The probability that the game will have an

(unplayable) configuration in which there is a

guaranteed win for X is

f(0,0,0,2,12,62,76,36,9,1). The probability of a

draw is f(0,0,0,0,16,16,0,0,0,0), for an expected

payoff of f(0,0,0,0,8,8,0,0,0,0). The probability

of a playable configuration is

f(0,0,0,6,36,36,6,0,0,0), from which the optimal

expected payoff is f(0,0,0,6,36,35,6,0,0,0). So

the total expected payoff with optimal play is

f(0,0,0,8,56,105,82,36,9,1).