Scrabble je desková hra oblíbená zejména v anglicky mluvících zemích, která prověřuje především jazykové a strategické schopnosti hráčů. Podrobné informace o hře včetně pravidel lze nalézt v [1].
Ve světě počítačů se v souvislosti se Scrabble můžeme často setka s tzv. hladovou strategií. Dobře napsaný program dokáže v libovolné fázi hry nalézt všechny přípustné tahy během zlomku sekundy (i na velmi pomalém stroji). Je přirozené zvolit z těchto tahů ten s nejvyšším bodovým ohodnocením. Takový postup nazýváme hladovou strategií.
Počítač používající hladovou strategii je pro běžného hráče téměř neporazitelným soupeřem. V případě expertních hráčů je však hladová strategie nedostatečná. Cílem tohoto projektu bylo vytvořit strategicky dokonalejší program, který volí tah nejen s ohledem na okamžitý bodový zisk, ale i s ohledem na možnosti, které sobě i soupeři svým tahem přinese.
Scrabble patří do kategorie her s neúplnou informací. Hráči během hry losují z váčku hrací kameny do svých přihrádek, jejichž obsah před soupeřem skrývají. Narozdíl od deskových her jako jsou šachy nebo dáma, kde jsou možnosti obou stran jednoznačně předvídatelné, ve Scrabble lze tahy, které budou následovat, jen odhadovat.
Z výše uvedených důvodů nelze k volbě tahu využít obvyklých algoritmů jako např. MinMax. Lze však použít různé heuristiky. Jednou z možností je metoda Monte Carlo.
Představme si, že bychom pro výběr tahu ve Scrabble použili jeden z algoritmů pro hry s úplnou informací, např. výše zmíněný MinMax. Vzhledem k tomu, že ve hře hraje roli náhoda (v okamžiku, kdy hráči losují kameny z váčku), je zřejmé, že spustíme-li MinMax opakovaně, získáme různé výsledky. Jinými slovy MinMax se v případě hry s neúplnou informací nechová deterministicky. Výsledek jednoho běhu MinMaxu tedy žádnou zásadní informaci nepřinese. V případě dostatečného počtu běhů však můžeme výsledky statisticky vyhodnotit a zjistit, který z přípustných tahů pravděpodobně přinese nejvyšší bodový zisk. Tento postup nazýváme metodou Monte Carlo. MinMax zde samozřejmě můžeme nahradit libovolným jiným příbuzným algoritmem.
Jak již bylo řečeno, Scrabble je hrou s neúplnou informací. V okamžiku, kdy je váček s písmeny prázdný, se však stává hrou s úplnou informací, neboť počet všech druhů kamenů ve hře je vždy stejný a z kamenů umístěných na desce a těch ve vlastní přihrádce lze přesně odvodid, jaké kameny drží soupeř.
V konečné fázi hry je tedy vhodné nahradit metodu Monte Carlo například již zmiňovaným algoritmem MinMax. Problémem však je faktor větvení, který v této fázi hry činí zhruba 200 (v extrémním případě však až 8000). Nelze tedy očekávat, že se vyhledávací strom vždy podaří v rozumném čase projít až do konce, a to i přesto, že koncová fáze hry může mít i velmi malý počet tahů. Bylo dokázáno, že ani obvyklé techniky prořezávání (např. alfa-beta metoda) tento problém nevyřeší. S úspěchem zde lze využít techniky dynamického programování. To je však nad rámec této práce. Detaily se lze dočíst např. v [4].
Dalším z mnoha problémů ve hře Scrabble je velmi náročné generování tahů. I s efektivním Appel-Jacobsonovým algoritmem na 1 GHz stroji trvá vygenerování všech přípustných tahů pro danou pozici zhruba 2 ms. Je nutné si uvědomit, že tahy jsou generovány pro každý uzel vyhledávacího stromu s výjimkou listů.
Při nastavení konstant pro redukci větvení na X=20, Y=10 (tyto hodnoty se ukázaly jako vhodné pro střední fázi hry), dosáhneme průměrného faktoru větvení cca 6. Při hloubce vyhledávacího stromu odpovídající 2 ply, procházíme zhruba 200 uzlů (6^3), které nejsou listy. Čas jedné simulace bude tedy přibližně 0,4 sekundy (200 * 2 ms) a při 50-ti simulacích potrvá jeden tah asi 20 sekund.
Cílem simulací bylo porovnat úspěšnost Monte Carlo metody s hladovou strategií a zároveň otestovat výsledky Monte Carlo metody v různých konfiguracích.
V následujícím textu budou v souvislosti s konfigurací Monte Carlo metody použita následující označení.
Ve všech simulacích byl odehrán sudý počet partií, přičemž každý z "hráčů" zahajoval právě jednu polovinu.
Cílem bylo prověřit, do jaké míry může ovlivnit výsledek hry dobré zvládnutí závěrečné fáze. Monte Carlo metoda (zde bychom ji měli nazývat spíše MinMax algoritmem) se ve střední části hry chovala stejně jako hladová metoda, ovšem v koncové fázi zapojila algoritmus MinMax.
MinMax | Greedy | |||
---|---|---|---|---|
Konfigurace |
end-ply = 3 end-cut-x = 20 end-cut-y = 15 |
|||
Vítězství | 1122 | 56.10% | 864 | 43.20% |
Prohry | 864 | 43.20% | 1122 | 56.10% |
Remízy | 14 | 0.70% | 14 | 0.70% |
Ukončení hry | 1091 | 54.55% | 463 | 23.15% |
Průměrné skóre na hru | 340.274 | 331.897 | ||
Průměrný počet tahů na hru | 15.662 | 15.470 | ||
Průměrný počet BINGO na hru | 0.318 | 0.340 | ||
Průměrná hodnota tahu | 21.725 | 21.454 | ||
Průměrný čas tahu | 0.824s | 0.004s | ||
Tahy s lokálně maximálním skóre | 93.820% | 100.000% |
Z výsledků simulace je patrné, že použití algoritmu MinMax v závěrečné fázi hry, výrazně zvyšuje šanci na ukončení hry a získání bonusu. Vliv na výsledek hry však není výrazný, neboť počet bodů, které lze získat v konečné fázi, je mnohem nižší než počet bodů dosažitelných ve střední části hry.
V této simulaci byla použita Monte Carlo metoda v nastavení, které umožnilo provedení tahu v průměru během 20 sekund.
Monte Carlo | Greedy | |||
---|---|---|---|---|
Konfigurace |
sim = 50 mid-ply = 2 mid-cut-x = 20 mid-cut-y = 10 end-ply = 3 end-cut-x = 20 end-cut-y = 15 |
|||
Vítězství | 134 | 67.00% | 66 | 33.00% |
Prohry | 66 | 33.00% | 134 | 67.00% |
Remízy | 0 | 0.00% | 0 | 0.00% |
Ukončení hry | 120 | 60.00% | 41 | 20.50% |
Průměrné skóre na hru | 348.865 | 319.595 | ||
Průměrný počet tahů na hru | 15.385 | 15.140 | ||
Průměrný počet BINGO na hru | 0.455 | 0.280 | ||
Průměrná hodnota tahu | 22.676 | 21.109 | ||
Průměrný čas tahu | 20.798s | 0.003s | ||
Tahy s lokálně maximálním skóre | 62.561% | 100.000% |
Výsledky ukazují, že hladová strategie byla poražena mnohem větším rozdílem, než v přechozí simulaci.
Zde byly proti sobě postaveny metoda Monte Carlo ze simulace 2 a algoritmus MinMax ze simulace 1.
Monte Carlo | MinMax | |||
---|---|---|---|---|
Konfigurace |
sim = 50 mid-ply = 2 mid-cut-x = 20 mid-cut-y = 10 end-ply = 3 end-cut-x = 20 end-cut-y = 15 |
end-ply = 3 end-cut-x = 20 end-cut-y = 15 |
||
Vítězství | 129 | 64.50% | 70 | 35.00% |
Prohry | 70 | 35.00% | 129 | 64.50% |
Remízy | 1 | 0.50% | 1 | 0.50% |
Ukončení hry | 92 | 46.00% | 80 | 40.00% |
Průměrné skóre na hru | 342.995 | 326.260 | ||
Průměrný počet tahů na hru | 14.935 | 14.910 | ||
Průměrný počet BINGO na hru | 0.490 | 0.380 | ||
Průměrná hodnota tahu | 22.966 | 21.882 | ||
Průměrný čas tahu | 11.310s | 0.199s | ||
Tahy s lokálně maximálním skóre | 60.830% | 94.802% |
Monte Carlo metoda porazila algoritmus MinMax téměř stejně výrazným rozdílem jako hladový algoritmus. Kromě střední části byl MinMax poražen (i když nepatrným rozdílem) i v koncové fázi hry. To lze přisuzovat lepší přípravě koncovky v případě metody Monte Carlo.
Cílem této simulace bylo zjistit, zda má na sílu Monte Carlo metody větší vliv počet simulací nebo hloubka vyhledávacího stromu.
Monte Carlo 1 | Monte Carlo 2 | |||
---|---|---|---|---|
Konfigurace |
sim = 50 mid-ply = 2 mid-cut-x = 20 mid-cut-y = 10 end-ply = 3 end-cut-x = 20 end-cut-y = 15 |
sim = 300 mid-ply = 1 mid-cut-x = 20 mid-cut-y = 10 end-ply = 3 end-cut-x = 20 end-cut-y = 15 |
||
Vítězství | 127 | 63.50% | 72 | 36.00% |
Prohry | 72 | 36.00% | 127 | 63.50% |
Remízy | 1 | 0.50% | 1 | 0.50% |
Ukončení hry | 78 | 39.00% | 62 | 31.00% |
Průměrné skóre na hru | 326.635 | 311.630 | ||
Průměrný počet tahů na hru | 16.170 | 16.115 | ||
Průměrný počet BINGO na hru | 0.390 | 0.300 | ||
Průměrná hodnota tahu | 20.200 | 19.338 | ||
Průměrný čas tahu | 11.123s | 36.696s | ||
Tahy s lokálně maximálním skóre | 59.709% | 73.999% |
Výsledky jednoznačně ukazují, že hloubka vyhledávacího stromu je oproti počtu simulací mnohem důležitějším faktorem. V této simulaci si lze rovněž povšimout nízké průměrné hodnoty tahu. To lze připsat tomu, že oba "hráči" (zejména Monte Carlo 2) se snaží hrát takovým způsobem, aby soupeři zabránili ve zisku vysokého počtu bodů.
Tato simulace proti sobě postavila dvě Monte Carlo metody s ekvivalentní konfigurací, až na počet simulací.
Monte Carlo 1 | Monte Carlo 2 | |||
---|---|---|---|---|
Konfigurace |
sim = 300 mid-ply = 2 mid-cut-x = 20 mid-cut-y = 10 end-ply = 3 end-cut-x = 20 end-cut-y = 15 |
sim = 50 mid-ply = 2 mid-cut-x = 20 mid-cut-y = 10 end-ply = 3 end-cut-x = 20 end-cut-y = 15 |
||
Vítězství | 118 | 59.00% | 79 | 39.50% |
Prohry | 79 | 39.50% | 118 | 59.00% |
Remízy | 3 | 1.50% | 3 | 1.50% |
Ukončení hry | 82 | 41.00% | 82 | 41.00% |
Průměrné skóre na hru | 334.060 | 327.820 | ||
Průměrný počet tahů na hru | 15.360 | 15.365 | ||
Průměrný počet BINGO na hru | 0.400 | 0.405 | ||
Průměrná hodnota tahu | 21.749 | 21.336 | ||
Průměrný čas tahu | 81.563s | 13.284s | ||
Tahy s lokálně maximálním skóre | 64.844% | 59.421% |
Je vidět, že vyšší počet simulací umožňuje při volbě tahu dosáhnout statisticky významnějších a tedy lepších výsledků.
Cílem bylo zjistit, o kolik se zlepší výsledky silné konfigurace metody Monte Carlo oproti konfiguraci ze simulace 2.
Monte Carlo | Greedy | |||
---|---|---|---|---|
Konfigurace |
sim = 300 mid-ply = 2 mid-cut-x = 30 mid-cut-y = 15 end-ply = 4 end-cut-x = 20 end-cut-y = 15 |
|||
Vítězství | 156 | 78.00% | 43 | 21.50% |
Prohry | 43 | 21.50% | 156 | 78.00% |
Remízy | 1 | 0.50% | 1 | 0.50% |
Ukončení hry | 142 | 71.00% | 36 | 18.00% |
Průměrné skóre na hru | 360.805 | 315.205 | ||
Průměrný počet tahů na hru | 15.445 | 15.230 | ||
Průměrný počet BINGO na hru | 0.620 | 0.300 | ||
Průměrná hodnota tahu | 23.361 | 20.696 | ||
Průměrný čas tahu | 145.389s | 0.001s | ||
Tahy s lokálně maximálním skóre | 63.548% | 100.000% |
Zesílení konfigurace se projevilo významných způsobem. Hladová strategie zde byla zcela deklasována.