Kružić i križić

Kružić pobjeđuje s 3 kružića u dijagonali

Križić-kružić igra se na praznom polju 3x3 na papiru. Igrač O postavlja kružiće, a igrač X križiće. Počevši od igrača s križićem, igrači naizmjenično odabiru prazna polja i unutar njih crtaju svoj znak. Igrač pobjeđuje kada ostvari 3 svoja znaka uzastopno u nekom redu, stupcu, glavnoj ili sporednoj dijagonali. Ako to ne uspije niti jednom igraču, igra završava neriješeno.

Optimalna strategija za igrača X. U svakoj tablici, osjenčani crveni X predstavlja optimalan potez, a lokacija O u sljedećem protivničkom potezu daje sljedeću podtablicu za razmatranje. Primijetite da samo dva niza poteza igrača O (svaki počevši od sredine, gornji desni kut, lijevo u sredinu) vodi u neriješeno, dok svi ostali nizovi poteza igrača O vode u pobjedu igrača X.

Optimalna strategija za igrača O. Igrač O uvijek može forsirati pobjedu ili neriješeno ako ode u sredinu. Ako je igrač X već zauzeo sredinu, O mora u neki kut

U sljedećoj igri pobjeđuje igrač X:

Lako se vidi da ako oba igrača igraju optimalno, igra završava neriješeno. Zato igru najčešće igraju mala djeca.

Prva dva poteza igre. Nakon eliminacije rotacije i simetrija, postoje samo tri prva poteza – kut, središte stranice i sredina.

Kombinatorika

Zanimljivi su broj mogućih stanja igre i broj različitih završenih igara.

Broj konačnih stanja

Ako zanemarimo rotacije i simetrije, postoji samo 138 različitih završnih stanja igre. Ako pretpostavimo da igrač X igra prvi tada je 91 puta pobijedio igrač X, 44 puta je pobijedio igrač O; a 3 igre završile su neriješeno:

OXO  OOX  OOX
XXO  XXO  XOO
OOX  OOX  OXX

Strategija

Igrač može odigrati optimalnu igru kružić-križić (da barem bude neriješeno) ako uvijek svoj potez bira kao prvi moguć na sljedećem popisu, kao što su koristili Newell i Simon u programu iz 1972. koji igra kružić i križić:

1. Pobijedi: ako igrač ima dva za redom, može staviti treći da dobije tri za redom.
2. Spriječi: ako protivnik ima dva za redom, igrač mora sam staviti treći da bi spriječio neposrednu pobjedu protivnika.
3. Račva: stvori situaciju u kojoj igrač u sljedećem potezu može na dva načina pobijediti.
4. Spriječi račvanje protivnika:
   • Prvi način: igrač treba napraviti dva za redom kako bi spriječio neprijatelja da se brani, ukoliko time neprijatelj ne račva. Na primjer, ako igrač X ima dva nasuprotna kuta, a igrač O ima središnje polje, igrač O ne smije igrati u neki kut ako ne želi izgubiti. (Ako bi igrao u kut, igrač X imao bi račvanje.)
   • Drugi način: ako protivnik u sljedećem potezu može račvati, igrač to treba spriječiti tako da igra u ono polje u koje bi protivnik trebao igrati da bi račvao.
5. Sredina: igrač igra u središnje polje. (Ako se radi o prvom potezu u igri, igranje u kut daje neoptimalnom protivniku više mogućnosti da učini pogrešku; međutim ovo ništa ne znači ako je protivnik optimalan.)
6. Suprotan kut: ako protivnik igra u kut, igrač igra u suprotan kut.
7. Kut: igrač igra u proizvoljan kut.
8. Brid: igrač igra u proizvoljno polje koje je središte neke stranice (gore u sredinu, lijevo u sredinu, dolje u sredinu ili desno u sredinu).

Rigorozni detalji

Označimo polja kao u sljedećoj tablici:

1	2	3
4	5	6
7	8	9

Kada X igra u 1 kao prvi potez, O treba u 5. Zatim X u 9 (u ovoj situaciji, O ne smije u 3 ni u 7, O treba u 2, 4, 6 ili 8):

• X1 → O5 → X9 → O2 → X8 → O7 → X3 → O6 → X4, ova igra završava neriješeno.

ili 6 (u ovoj situaciji, O ne smije ni u 4 niti u 7, O treba u 2, 3, 8 or 9. Ustvari, igranje u 9 je najbolji potez, jer će neoptimalan igrač X možda igrati u 4 pa O može u 7 da pobijedi).

• X1 → O5 → X6 → O2 → X8, tada O ne smije u 3, ili X može u 7 da pobijedi, te O ne smije igrati u 4, ili će X moći u 9 i pobijediti, dakle O treba igrati u 7 ili 9.
  • X1 → O5 → X6 → O2 → X8 → O7 → X3 → O9 → X4, ova igra završava neriješeno.
  • X1 → O5 → X6 → O2 → X8 → O9 → X4 (7) → O7 (4) → X3, ova igra završava neriješeno.
• X1 → O5 → X6 → O3 → X7 → O4 → X8 (9) → O9 (8) → X2, ova igra završava neriješeno.
• X1 → O5 → X6 → O8 → X2 → O3 → X7 → O4 → X9, ova igra završava neriješeno.
• X1 → O5 → X6 → O9, pa X ne smije u 4, ili će O moći u 7 i pobijediti, X mora u 2, 3, 7 ili 8.
  • X1 → O5 → X6 → O9 → X2 → O3 → X7 → O4 → X8, ova igra završava neriješeno.
  • X1 → O5 → X6 → O9 → X3 → O2 → X8 → O4 (7) → X7 (4), ova igra završava neriješeno.
  • X1 → O5 → X6 → O9 → X7 → O4 → X2 (3) → O3 (2) → X8, ova igra završava neriješeno.
  • X1 → O5 → X6 → O9 → X8 → O2 (3, 4, 7) → X4/7 (4/7, 2/3, 2/3) → O7/4 (7/4, 3/2, 3/2) → X3 (2, 7, 4), ova igra završava neriješeno.

U obje situacije (X igra u 6 ili 9 na drugom potezu), X ima [math]\displaystyle{ \frac{1}{3} }[/math] vjerojatnost da pobijedi.

Ako X ne igra optimalno, X može igrati 2 ili 3 na drugom potezu. Tada će igra završiti neriješeno, a X ne može pobijediti.

• X1 → O5 → X2 → O3 → X7 → O4 → X6 → O8 (9) → X9 (8), ova igra završava neriješeno.
• X1 → O5 → X3 → O2 → X8 → O4 (6) → X6 (4) → O9 (7) → X7 (9), ova igra završava neriješeno.

Ako X prvo igra 1, a O ne igra optimalno, može se dogoditi nešto od sljedećeg:

Iako O igra jedino dobro polje (5) na prvom potezu, ako O griješi na drugom potezu:

• X1 → O5 → X9 → O3 → X7, tada X može igrati u 4 ili 8 da bi pobijedio.
• X1 → O5 → X6 → O4 → X3, tada X može igrati u 2 ili 9 da bi pobijedio.
• X1 → O5 → X6 → O7 → X3, tada X može igrati u 2 ili 9 da bi pobijedio.

Iako O zauzima dobru poziciju nakon i prvog i drugog poteza, ako O griješi na trećem potezu:

• X1 → O5 → X6 → O2 → X8 → O3 → X7, tada X može igrati u 4 ili 9 da bi pobijedio.
• X1 → O5 → X6 → O2 → X8 → O4 → X9, tada X može igrati u 3 ili 7 da bi pobijedio.

Ako pak O zauzima lošu poziciju već nakon prvog poteza (to su svi potezi osim onog u 5):

• X1 → O3 → X7 → O4 → X9, tada X može igrati u 5 ili 8 da bi pobijedio.
• X1 → O9 → X3 → O2 → X7, tada X može igrati u 4 ili 5 da bi pobijedio.
• X1 → O2 → X5 → O9 → X7, tada X može igrati u 3 ili 4 da bi pobijedio.
• X1 → O6 → X5 → O9 → X3, tada X može igrati u 2 ili 7 da bi pobijedio.

Varijacije na igru i poopćenja

Neke varijacije su en:Notakto, en:Number Scrabble, en:Misère tic tac toe (gdje je cilj izgubiti), en:Quantum tic-tac-toe, en:Treblecross, en:Ultimate tic-tac-toe, en:Wild tic-tac-toe i dr. Igra se može poopćiti u en:m,n,k-game, ili još jače u en:Harary's generalized tic-tac-toe ili pak još jače u en:n^d game (gdje je [math]\displaystyle{ n=3 }[/math] i [math]\displaystyle{ d=2 }[/math]).

Kružić i križić u popularnoj kulturi

• Ratne igre (1983.) (izvorno War Games) - film u kojem mladi hacker slučajno upada u računalo koje upravlja američkim nuklearnim arsenalom, u potrazi za novim videoigrama. Na kraju filma dječak i računalo imaju igru križića i kružića o čijem ishodu ovisi hoće li započeti termonuklearni rat.
• U filmu 12 gnjevnih ljudi (1957.) ima scena u kojoj dva člana porote igraju križić-kružić.