Hra
Tic-tac-toe je velmi populární hra pro dva hráče, X a O, kteří se střídají značení prostory v 3×3 sítě. Hráč, kterému se podaří umístit tři své značky do svislé, vodorovné nebo diagonální řady, vyhrává hru.,
Matematické Vlastnosti
Z matematického hlediska hra má dvě velmi důležité vlastnosti:
Majetek 1:
hra přiznává hráč, který používá tuto optimální strategii, vyhrát nebo remíza ale to se neztratí.
vlastnost 2:
počet možných různých zápasů je relativně malý.
na začátku může první hráč označit některý z 9 mezer. V následujícím otočení může druhý hráč označit jeden ze zbývajících 8 mezer a tak dále., Hra pokračuje, dokud nejsou označeny všechny mezery nebo jeden z hráčů vyhraje.
je pak snadné pochopit, že celkový počet různých zápasů je nižší než:
987….1 = 9! = 362880
to je poměrně malé číslo pro počítač.
algoritmus
z vlastností 1 a 2 vyplývá, že praktickým a obecným algoritmem pro výhru / kreslení hry je použití vyhledávání alfa Beta.,
při každém otočení algoritmus vyhodnotí všechny možné důsledky každého pohybu (možné kvůli majetku 2) a vybere ten, který zajistí vítězství nebo remízu (možné kvůli majetku 1).
AI hráč, který si vybere každý pohyb s alpha beta vyhledávací algoritmus se nikdy neztratí. Aby byla hra realističtější, je hezké zavést stochastický faktor, takže pokaždé s předdefinovanou pravděpodobností se hráč AI pohybuje náhodně spíše než podle algoritmu alfa beta., Díky tomu bude hra realističtější, protože učiní hráče AI lidštějším a někdy ztratí.