Umělá inteligence je založená na algoritmu Negamax, což je varianta klasického alfa-beta pruningu pro hry s nulovým součtem.
Alfa beta pruning je klasický algoritmus, který prohledává strom možných budoucích tahů a výsledky hodnotí na základě nějaké heuristiky. Alfa beta pruning neprohledává větve, které nemohou vézt k nalezení posloupnosti tahů, které by proti optimálně (vzhledem k heuristice) hrajícímu protivníkovi vedli k lepšímu výsledku dané heuristiky. Negamax využívá toho, že pokud při hře s nulovým součtem hráč A vítězí o X bodů, pak hráč B prohrává o X bodů. Tato znalost umožňuje redukovat množství výpočtů heuristiky.
Použitá heuristika je ta, že algoritmus pro každého hráče spočítá množství řad o 2,3,4,5 kamenech, které na ploše jsou (svisle, horizontálně i diagonálně). Řady také rozlišuje dle toho, jestli mají volno na krajích (Jdou dál prodlužovat) a nebo uprostřed (Jdou zničit jedním tahem). Tyto řady mají různá bodová ohodnocení. Heuristika sečte všechna ohodnocení všech řad pro oba hráče, hráč s vyšší sumou ohodnocení vyhrává o rozdíl oproti sumě ohodnocení druhého hráče. Algoritmus často zároveň blokuje druhého hráče( blokované řady mají menší ohodnocení) a prodlužuje svou řadu( delší řada = vyšši ohodnocení), také připravuje více příležitostí k útoku najednou(víc vzniklých dvojic/trojic jedním tahem = vyšši ohodnocení).
AI bylo otestováno jak proti lidem, tak proti dalším umělým inteligencím.
AI vyhrálo 10 her z 13 proti lidem. Nezdá se, že by dělalo nějaké zjevné chyby. V nějakou chvíli ho prostě hráč přehraje a dostane se k sekvenci, kdy je AI každým tahem donuceno blokovat, až dokud hráč eventuálně nezíská dvě volné trojice. Pokud člověk udělá proti AI zjevnou chybu, tak ji AI využije a zpravidla hned vyhraje.
Vzali jsme poslední 25 z 47 programů ze soutěže gomocup 2018 (http://gomocup.org/download-gomoku-ai/ )
a nechali je hrát proti naší AI. Proti každému protihráči jsme odehráli dvě hry, v každé hře začínal jiný hráč.
Naše AI porazilo 8 protihráčů, prohrálo proti 7 a remizovalo proti jednomu. Čtyři programy z gomocupu nešly spustit.
Výsledky jsou v tabulce níže.
| Pořadí v gomocup | Protihráč | Výhra:Prohra | Deska | Počet tahů (jednoho hráče)/hru | Poznámky |
|---|---|---|---|---|---|
| 23 | zetor2017 | 0 : 2 | 15X15 | 24 | --- |
| 24 | Eulring | 0 : 2 | 15X15 | 24 | --- |
| 25 | Pecuchet | X : X | 15X15 | XXX | -Nefunguje- |
| 26 | jude | X : X | 15X15 | XXX | -Nefunguje- |
| 27 | Sparkle | 0 : 2 | 15X15 | 24 | --- |
| 28 | djall18 | 0 : 2 | 15X15 | 24 | --- |
| 29 | QMENTAT6 | 0 : 2 | 15X15 | 24 | --- |
| 30 | Puskvorec | 2 : 0 | 15X15 | 15 | --- |
| 31 | Noesis | 0 : 2 | 20X20 | 25 | --- |
| 32 | imro15 | 1 : 1 | 15X15 | 38 | --- |
| 33 | licht14 | X : X | 20X20 | XXX | - Nefunguje- |
| 34 | fast-gomoku14 | 1 : 1 | 15X15 | 56 | --- |
| 35 | pisq7 | 1 : 1 | 15X15 | 32 | --- |
| 36 | LightBlue | 2 : 0 | 15X15 | 23 | --- |
| 37 | Stahlfaust | X : X | 15X15 | XXX | -Nefunguje- |
| 38 | PureRocky | 1 : 1 | 20X20 | 17 | --- |
| 39 | Benjamin | 0 : 0 | 20X20 | 187 | Vyplnili celou desku remíza |
| 40 | brain-Crusher2010 | 2 : 0 | 15X15 | 23 | --- |
| 41 | valkyrie | 1 : 1 | 20X20 | 17 | --- |
| 42 | fiverow | 2 : 0 | 20X20 | 30 | --- |
| 43 | prolog | 2 : 0 | 15X15 | 20 | --- |
| 44 | mushroom | 2 : 0 | 15X15 | 5 | --- |
| 45 | Whatateam | 2 : 0 | 15X15 | 13 | --- |
| 46 | alphagomoku | 0 : 2 | 20X20 | 18 | --- |
| 47 | GammaKu | 1 : 1 | 15X15 | 24 | --- |
| Total | 20 : 20 | 701/23 = 30.5 |