Popis piškvorkového algoritmu

Článek popisuje algoritmus umělé inteligence hrající piškvorky. Popsaný algoritmus si můžete vyzkoušet na stránce hratky.nenapadnymajak.cz.

Algoritmus by se dal rozdělit na tři hlavní části:

1. Procházení stromu hry -  používá se v deskových hrách velmi často používaný algoritmus alfabeta s iterativním zvětšováním hloubky stromu. Kromě alfabety se používá i podobný algoritmus MTD(f) - ten se zapojuje náhodně – aby celý algoritmus nehrál pořád stejně.
2. Ohodnocovací funkce – jádro celého algoritmu – používá se pro ohodnocení koncových uzlů stromu (tzv. “listů”). Ohodnocuje kvalitu rozehrané hry z pohledu jednoho hráče. Používané ohodnocovací funkci bude věnována většina zbytku článku.
3. Optimalizační techniky – protože webové piškvorky běží v javascriptu, který je dost pomalý, bylo k základní kostře (alfabeta+ohodnocovací funkce) přidáno několik optimalizací:
   • Transpoziční tabulky – Zapamatování si výsledku ohodnocovací funkce. Pokud je potřeba znova ohodnotit stav hrací plochy, který už byl hodnocen, použije se uložené ohodnocení.
   • Řazení tahů – Snaha o to, aby se v každém uzlu stromu hry, zkoušely nejdříve ty nejlepší tahy.
   • Hlídání trojek a čtyřek – Pokud má nějaký hráč souvislou trojku nebo čtyřku, nelze už hrát nikde jinde, než právě kolem trojky nebo čtyřky.

Ohodnocovací funkce

Cílem ohodnocovací funkce je ohodnotit stav hrací plochy z pohledu jednoho hráče nějakým reálným číslem, které bude co nejlépe vystihovat šanci hráče na výhru – nejde o to stanovit nějakou procentuální pravděpodobnost, ale o to, že ohodnocení reálným číslem umožňuje porovnání různých stavů hrací plochy.

Základním stavebním kamenem popisované ohodnocovací funkce je ohodnocení pětice sousedících políček. Ohodnocení hrací plochy je pak součtem ohodnocení všech pětic, které na hrací ploše jsou.

Na obrázku je jeden řádek z hrací plochy s rozměry 11×11. V tomto řádku je 7 pětic políček (první pětice je 1A-1E, druhá je 1B-1F,…, sedmá je 1G-1K).

Pro ohodnocení jedné pětice se používá následující algoritmus:

• Pokud jsou všechna políčka prázdná, je ohodnocení 0
• Pokud mají v dané pětce oba hráči alespoň jednu značku, je ohodnocení 0
• Pokud má v dané pětce značky jen jeden hráč, získává tento hráč za tuto pětici
  • 1 bod, pokud má v dané pětici jednu značku
  • 73 bodů, pokud má v dané pětici dvě značky
  • 511 bodů, pokud má v dané pětici tři značky
  • 1751 bodů, pokud má v daní pětici čtyři značky

Pokud je v nějaké pětici pět značek, znamená to vítězství a konec hry, což musí algoritmus nějak zachytit – aby neprozkoumával následující tahy, které dle pravidel nedávají smysl. Ohodnocení pěti značek musí být takové, aby ohodnocení hrací plochy s vítěznou pětkou bylo vždy vyšší než stav hrací plochy bez vítězné pětice. Stačí použít nějaké hodně vysoké číslo.

V následujícím příkladu si ukážeme ohodnocení jednoho řádku z hrací plochy.

Ohodnocení jednoho řádku se skládá ze součtu ohodnocení jednotlivých pětic:

• 1A-1E – v této pětici je jeden křížek, hráč s křížky získává 1 bod
• 1B-1F – v této pětici jsou dva křížky, hráč s křížky získává 73 bodů
• 1C-1G – tato pětice je obsazena oběma hráči, žádný nezískává bod
• 1D-1H - tato pětice je obsazena oběma hráči, žádný nezískává bod
• 1E-1I - tato pětice je obsazena oběma hráči, žádný nezískává bod
• 1F-1J - tato pětice je obsazena oběma hráči, žádný nezískává bod
• 1G-1K - v této pětici je jedno kolečko, hráč s kolečky získává 1 bod

Z pohledu hráče s křížky je ohodnocení tohoto řádku: (1+73) – 1 = 73 bodů (z pohledu hráče s kolečky minus 73 bodů).

Takovýmto způsobem se ohodnotí všechny řádky, všechny sloupce a oba diagonální směry.

Samozřejmě není nutné pokaždé počítat celou hrací plochu – po jednom tahu se vždy změní v každém směru nejvýše 5 pětic, celkem tedy stačí přepočítat 20 pětic po každém tahu.

Posted in programming