Monte Carlo metoda ve hře Scrabble

PA026 Projekt z umělé inteligence (jaro 2004)
Jan Pomikálek <xpomikal@fi.muni.cz>

Obsah

Úvod

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.

Monte Carlo metoda

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.

Konec hry

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].

Implementace

Generování tahů

Velmi efektivní Appel-Jacobsonův algoritmus. Viz [3].

Počáteční a střední část hry

Metoda Monte Carlo spojená s algoritmem MinMax. Nastavitelný počet simulací (počet běhů MinMaxu), nastavitelná hloubka vyhledávacího stromu, nastavitelná redukce větvení (viz níže).

Koncová část hry

Algoritmus MinMax. Nastavitelná hloubka vyhledávacího stromu a redukce větvení.

Redukce větvení

Používají se jednoduché heuristiky. Nastavení hodnot X a Y je volitelné (zvlášť pro střední a koncovou část hry).
  1. Seřaď přípustné tahy sestupně podle okamžitého bodového zisku.
  2. Vezmi prvních X tahů, ostatní zahoď.
  3. Ze zbylých tahů odstraň ty, které se od prvního liší o více než Y bodů.
Smysl těchto heuristik spočívá v tom, že pro danou pozici je obvykle nejlepším tahem ten s maximálním okamžitým ziskem, nebo ten, který se maximálnímu okamžitému zisku blíží. Toto pravidlo platí méně spolehlivě v koncové fázi hry. Je tedy vhodné pro tuto fázi nastavit X a Y na vyšší hodnoty, než pro střední fázi.

Vhodné konfigurace

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.

Výsledky simulací

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.

Simulace 1 - MinMax vs. Greedy

Použitý stroj: leto.fi.muni.cz, Pentium III, 500MHz

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í 112256.10% 86443.20%
Prohry 86443.20% 112256.10%
Remízy 140.70% 140.70%
Ukončení hry 109154.55% 46323.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.

Simulace 2 - Monte Carlo vs. Greedy

Použitý stroj: daphne.fi.muni.cz, Pentium III, 900MHz

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í 13467.00% 6633.00%
Prohry 6633.00% 13467.00%
Remízy 00.00% 00.00%
Ukončení hry 12060.00% 4120.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.

Simulace 3 - Monte Carlo vs. MinMax

Použitý stroj: ceryx.fi.muni.cz, Pentium 4, 2GHz

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í 12964.50% 7035.00%
Prohry 7035.00% 12964.50%
Remízy 10.50% 10.50%
Ukončení hry 9246.00% 8040.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.

Simulace 4 - Monte Carlo (50sims, 2ply) vs. Monte Carlo (300sims, 1ply)

Použitý stroj: ceyx.fi.muni.cz, Pentium 4, 2GHz

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í 12763.50% 7236.00%
Prohry 7236.00% 12763.50%
Remízy 10.50% 10.50%
Ukončení hry 7839.00% 6231.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ů.

Simulace 5 - Monte Carlo (300sims) vs. Monte Carlo (50sims)

Použitý stroj: helena.fi.muni.cz, Pentium 4, 1.6GHz

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í 11859.00% 7939.50%
Prohry 7939.50% 11859.00%
Remízy 31.50% 31.50%
Ukončení hry 8241.00% 8241.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ů.

Simulace 6 - Monte Carlo (silná konfigurace) vs. Greedy

Použitý stroj: fobos.fi.muni.cz, Pentium 4, 1.7GHz

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í 15678.00% 4321.50%
Prohry 4321.50% 15678.00%
Remízy 10.50% 10.50%
Ukončení hry 14271.00% 3618.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.

Download

scrbsim-1.10.tar.bz2 - zdrojové kódy (827 kB)
sim-1.tar.gz - průběh partií ze simulace 1 (2000 her, 2424 kB)
sim-2.tar.gz - průběh partií ze simulace 2 (200 her, 250 kB)
sim-3.tar.gz - průběh partií ze simulace 3 (200 her, 247 kB)
sim-4.tar.gz - průběh partií ze simulace 4 (200 her, 268 kB)
sim-5.tar.gz - průběh partií ze simulace 5 (200 her, 261 kB)
sim-6.tar.gz - průběh partií ze simulace 6 (200 her, 254 kB)

Literatura

[1] Pravidla Scrabble podle České asociace Scrabble
[2] Scrabble - diplomová práce Víta Hotárka
[3] Appel, A. W. - Jacobson, G. J. -- The world's fastest Scrabble program
[4] Sheppard, B. -- World-championship-caliber Scrabble