Varianty Monte Carlo Tree Search ´ s Kuˇca Tomaˇ
[email protected] Hern´ı algoritmy MFF UK Praha
2011
´ s Kuˇca Tomaˇ
Monte Carlo tree search
´ Temata
ˇ ˇ O cem bude pˇredna´ ska? Monte Carlo Tree Search ´ ejˇ ˇ s´ım od her podobn´ych Go (bez Go) k vzdalen rozd´ıly a rozˇs´ırˇen´ı MTCS
´ s Kuˇca Tomaˇ
Monte Carlo tree search
Pˇripomenut´ı MCTS ´ ı hern´ıho stromu Postupne´ budovan´ ˇ ri faze: ´ Algoritmus opakuje ctyˇ Selekce ´ vybere list z hern´ıho stromu (nejdˇr´ıve nenavˇst´ıvene) Multi-armed bandit problem q typicky UCT algoritmus: Ui = vi + c
ln N ni
Expanze - pˇrida´ nov´y uzel ˇ ´ Simulace - odhad pravdepodobnosti v´yhry (bodoveho ´ uzlu na zaklad ´ zisku) v danem eˇ mnoha simulac´ı Backpropagation - informace o hodnoteˇ uzlu je ´ propagovana stromem na cesteˇ ke koˇreni
´ s Kuˇca Tomaˇ
Monte Carlo tree search
V´yhody MTCS
nepotˇrebuje nutneˇ evaluaˇcn´ı funkci ´ ´ lze pˇridavat domenov eˇ specificke´ heuristiky
´ s Kuˇca Tomaˇ
Monte Carlo tree search
Nev´yhody MTCS
´ ´ y” tah, ma´ problemy s pozicemi, kde je jen jeden ”spravn´ tzv. killer move ´ ze odhalit vyhrane´ (nebo prohrane´ pozice), cˇ asto nedokaˇ ´ sˇt ve hrach ´ s nahlou ´ obzvlaˇ smrt´ı (ˇsachy, hex, lines of action) ´ an´ ´ ı nebo proof number search davaj´ ´ ıv αβ-prohledav takov´ych situac´ıch lepˇs´ı v´ysledky ˇreˇs´ı tzv. MCTS solver
´ s Kuˇca Tomaˇ
Monte Carlo tree search
Lines of action
´ cu˚ s perfektn´ı informac´ı, hra dvou hraˇ nulov´ym souˇctem hrac´ı deska o velikosti 8 × 8 (obecneˇ n × n) ´ cn´ı pozice viz obr. poˇcateˇ ´ ci se stˇr´ıdaj´ı v taz´ıch hraˇ ´ c´ılem hry je uspoˇradat kameny tak, ´ ce aby se vˇsechny kameny hraˇ ´ e) ˇ dot´ykaly (staˇc´ı diagonaln
´ s Kuˇca Tomaˇ
Monte Carlo tree search
Tah v Lines of action
ˇ ´ ´ c pohne jedn´ım kamenem behem sveho tahu hraˇ ´ e, ˇ vertiakln ´ eˇ nebo diagonaln ´ eˇ horizontaln ´ ´ kamen se pohne o tolik pozic, kolik je v danem ˇradku/sloupci/diagon ´ ´ kamenu˚ ale ´ nesm´ı pˇreskoˇcit soupeˇruv ˚ kamen pokud skonˇc´ı pˇreesneˇ na pozici soupeˇrova kamene, ´ ˇ zakryje ho (soupeˇruv je ze hry odstranen) ˚ kamen
´ c nemuˇ ´ passuje pokud hraˇ ˚ ze hrat, ´ opakuje pozice → rem´ıza pokud se tˇrikrat pokud spojen´ı do jedne´ komponenty nastane souˇcasneˇ → rem´ıza
´ s Kuˇca Tomaˇ
Monte Carlo tree search
MTCS pro Lines of action pˇri selekci pouˇz´ıva´ ”progressive bias” q c Ui = vi + c lnnNi + Wni×P +1 W je konstanta (pouˇzita´ hodnota 100) ˇ Pc je pravdepodobnost tahu dane´ kategorie, z´ıskana´ na ´ zaklad eˇ pˇredchoz´ıch her ´ ı) a dle kategorie jsou urˇcene´ dle typu tahu (zajet´ı, blokovan´ ´ cn´ı a koncove´ pozice kamene (hrac´ı deska se poˇcateˇ ˇ ı na nekolik ˇ ´ ı - stˇred, rohy, okraje) rozdel´ cˇ ast´
´ ˇ ale teˇ ´z s pˇri simulaci nejsou tahy nahodn e, ˇ pravdepodobnost´ ı dle kategori´ı ´ pokud evaluaˇcn´ı funkce pˇresahne urˇcitou hranici, povaˇzuje ˇ ı (podobneˇ prohra) se hra za v´ıtestv´ pˇri backpropagation se propaguj´ı hodnoty 1, 0, −1 ´ s Kuˇca Tomaˇ
Monte Carlo tree search
´ a´ smrt Nahl
´ problem ´ s nahlou ´ tato varianta ma´ stale smrt´ı nalezen´ı v´yhern´ıho tahu trva´ dlouho
´ s Kuˇca Tomaˇ
Monte Carlo tree search
´ a´ smrt Nahl
´ problem ´ s nahlou ´ tato varianta ma´ stale smrt´ı nalezen´ı v´yhern´ıho tahu trva´ dlouho Backpropagation propaguj´ı se hodnoty {−∞, 0, ∞} propagace podobneˇ jako v MINIMAX ´ c a propaguji −∞: pokud je na tahu hraˇ propaguje −∞, pokud maj´ı vˇsichni sourozenci −∞ propaguje −1 jinak
obdobneˇ pro v´yhern´ı pozice jak to ovlivn´ı selekci?
´ s Kuˇca Tomaˇ
Monte Carlo tree search
Volba tahu
ˇ hodnota uzlu se muˇ proto nelze vz´ıt uzel s ˚ ze rychle menit, nejlepˇs´ı hodnotou ˇ a´ strategie, hraje se ta, jinak pokud je nalezena v´ıtezn v+
√A , n
kde
v je hodnota uzlu A je konstanta (napˇr. 1) ´ stev ˇ uzlu n je poˇcet navˇ
´ s Kuˇca Tomaˇ
Monte Carlo tree search
V´ysledky
MTCS-solver poraz´ı MTCS v 65 MTCS-solver poraz´ı starˇs´ı verze MIA 2000, 2002 ˇ (pravdepodobn eˇ nejlepˇs´ı program, zaloˇzen´y na αβ ´ an´ ´ ı) (z´ıska´ cca 60% bodu) prohledav ˚ ˇ s´ı verze MIA 2006 v´yrazneˇ poraz´ı i MTCS-solver nejnovejˇ (11%)
´ s Kuˇca Tomaˇ
Monte Carlo tree search
Hex
´ cu˚ s perfektn´ı informac´ı, hra dvou hraˇ nulov´ym souˇctem hrac´ı deska o velikosti 11 × 11 (obecneˇ n × n) ´ ci v kaˇzdem ´ tahu pˇridaj´ı jeden hraˇ ´ kamen sve´ barvy ´ ci se stˇr´ıdaj´ı v taz´ıch hraˇ c´ılem hry spojit protilehle´ strany ´ c ma´ ”sve” ´ dveˇ desky (kaˇzd´y hraˇ strany)
´ s Kuˇca Tomaˇ
Monte Carlo tree search
Mrtve´ oblasti
ˇ - nejsou zaj´ımave´ ani pro jednoho hraˇ ´ ce mrtve´ bunky ´ cu˚ nema´ smysl tam hrat ´ zajate´ uzem´ ı - pro jednoho z hraˇ ´
´ s Kuˇca Tomaˇ
Monte Carlo tree search
´ an´ ´ ı pol´ı Promazav
ˇ ´ v uvahu, nekter e´ tahy nemus´ım brat protoˇze jsou ´ ´ jin´ymi tahy dominovany
´ s Kuˇca Tomaˇ
Monte Carlo tree search
H-search
ˇ algoritmus pro nalezen´ı strategie pro spojen´ı dvou bunek ˇ trivialn´ ´ ı tahy neupln´ ´ y, obˇcas pˇrehl´ızˇ ´ı i pro cˇ loveka ale pokud existuje ˇreˇsen´ı, cˇ asto ho najde
´ s Kuˇca Tomaˇ
Monte Carlo tree search
MTCS
standartn´ı MTCS ˇ s´ı pokud pouˇz´ıva´ AMAF heuristiku, bez nejsilnejˇ ´ an´ ´ ı (exploration) prohledav ´ ´ simulace nahodn e´ (permutace prazdn´ ych pol´ı) ´ ı zlepˇsen´ı pouze ”bridge” pattern, ostatn´ı nepˇridavaj´ ´ poˇctu navˇst´ıven´ı uzlu z neho ˇ pˇri urˇcitem spust´ı H-search ´ ı stromu proˇrezan´
´ s Kuˇca Tomaˇ
Monte Carlo tree search
´ ı Hex - proˇrezan´
´ s Kuˇca Tomaˇ
Monte Carlo tree search
Hex - v´ysledky
MTCS + brdige pattern vs MTCS → 65% win rate MTCS + AMAF vs MTCS → 74% win rate ´ y program) → 49% win rate MTCS vs Wolve (nejlepˇs´ı znam´
´ s Kuˇca Tomaˇ
Monte Carlo tree search
Kriegspiel
´ pozici soupeˇrov´ych figur sˇ achy, kdy neznam ´ jen koncovka King + Rook vs King ma´ prohledavac´ ı prostor ´ jako dama rozd´ıly oproti Phantom Go dynamicke´ ´ a´ z´ıskana´ informace rychle zastarav hra nema´ omezen´y poˇcet tahu˚ ˇ podm´ınky pro v´ıtezstv´ ı ´ a´ standartn´ı MTCS selhav m´ısto simulace protivn´ıka simulovat jen kategorie tahu˚ omezit poˇcet tahu˚ pˇri simulaci
´ s Kuˇca Tomaˇ
Monte Carlo tree search
Dalˇs´ı hry
Scrabble, Poker, Game of Scotland Yard, Bridge, generick´y ´ c, evropske´ hry hraˇ cˇ asem moˇzna´ i RTS
´ s Kuˇca Tomaˇ
Monte Carlo tree search
