A játék
Tic-tac-toe egy nagyon népszerű játék két játékos, X és O, akik felváltva jelölés a terek egy 3×3 rács. Az a játékos, akinek sikerül három jelölését függőleges, vízszintes vagy átlós sorba helyezni, megnyeri a játékot.,
matematikai tulajdonságok
matematikai szempontból a játéknak két nagyon fontos tulajdonsága van:
1.tulajdonság:
a játék elismeri, hogy az optimális stratégiát használó játékos nyer vagy rajzol, de nem fog veszíteni.
2. tulajdonság:
a lehetséges különböző mérkőzések száma viszonylag kicsi.
az elején az első játékos megjelölheti a 9 szóköz egyikét. A következő fordulóban a második játékos megjelölheti a fennmaradó 8 szóköz egyikét stb., A játék addig folytatódik, amíg az összes szóköz meg nem jelenik, vagy az egyik játékos nyer.
ezután könnyű megérteni, hogy a különböző mérkőzések teljes száma alacsonyabb, mint:
987….1 = 9! = 362880
Ez egy meglehetősen kis szám a számítógép számára.
az algoritmus
az 1. és 2. tulajdonságokból következik, hogy a játék megnyeréséhez/rajzolásához egy gyakorlati és általános algoritmus az alfa béta keresés használata.,
minden fordulóban az algoritmus kiértékeli az egyes lépések összes lehetséges következményét (a 2. tulajdonság miatt lehetséges), és kiválasztja azt, amely biztosítja a győzelmet vagy a döntetlent (az 1.tulajdonság miatt lehetséges).
egy AI-lejátszó, amely minden egyes lépést az alfa-béta Keresési algoritmussal választ, soha nem veszít. Annak érdekében, hogy a játék reálisabb legyen, jó bevezetni egy sztochasztikus tényezőt úgy, hogy minden alkalommal előre meghatározott valószínűséggel az AI játékos véletlenszerűen mozog, nem pedig az alfa béta algoritmust követve., Ez realisztikusabbá teszi a játékot, mivel az AI-lejátszót emberibbé teszi, néha elveszíti.