Kapcsolatok

GDEV BLOG
PlanetX Horrorszkóp

Blogszemle

Blogok fórum

A lehetséges Tic-Tac-Toe játszmák száma

Cikkek / Tic-Tac-Toe (573 katt) Kapitány
  2014.02.17.

A Tic-Tac-Toe játék vizsgálata során felvetődik a kérdés, hogy hányféle játszmát lehet végigjátszani. Ez azért fontos kérdés, mert ezzel támpontot kaphatunk azzal kapcsolatban, hogy van-e lehetőségünk a teljes játékfa felépítésére és az ennek segítségével történő lépésválasztásra.

Ha úgy fogjuk fel a játékot, hogy a játékosoknak lépéseik során a következő ábrán látható pozíciók közül kell választaniuk, akkor egy játszma például lehet a következő: 1, 2, 3, 4, 5, 6, 7, 8, 9. Az összes elképzelhető játszmát így az 1-9 számok permutációinak előállításával kaphatnánk meg, melyeknek száma 9! = 362 880.



Ez a szám egy felső becslés a lehetséges játszmák számára, ui. nem minden esetben jutunk el 9 lépésig. Az X játékos már az ötödik lépésben is győzhet, mint az a következő ábrán látható.



Egy programmal megvizsgáltam a Tic-Tac-Toe teljes játékfáját, és a következő eredményt kaptam:



A programnak az eredmény meghatározásához – a kiinduló üres táblával együtt – összesen 549 946 játékállást kellett legenerálnia és megvizsgálnia.

Előző oldal Kapitány