Hledání stromu v Monte Carlu - Monte Carlo tree search

Hledání stromu v Monte Carlu
TřídaVyhledávací algoritmus
Graf a strom
vyhledávací algoritmy
Výpisy
související témata

v počítačová věda, Hledání stromu v Monte Carlu (MCTS) je heuristický vyhledávací algoritmus pro některé druhy rozhodovací procesy, zejména ti, kteří byli zaměstnáni v software který hraje stolní hry. V této souvislosti se MCTS používá k řešení herní strom.

MCTS byl představen v roce 2006 pro počítač Go.[1] To bylo použito v jiných deskových hrách jako šachy a shogi,[2] hry s neúplnými informacemi, jako např most[3] a poker,[4] stejně jako v tahových strategických videohrách (např Total War: Rome II Implementace v kampani AI na vysoké úrovni[5]).

Dějiny

Metoda Monte Carlo

The Metoda Monte Carlo, která používá náhodnost pro deterministické problémy, které je obtížné nebo nemožné vyřešit pomocí jiných přístupů, sahá až do 40. let 20. století. Ve své disertační práci z roku 1987 Bruce Abramson spojil hledání minimax s model očekávaného výsledku na základě náhodných her až do konce, místo obvyklých funkce statického vyhodnocení. Abramson uvedl, že model očekávaných výsledků „se ukazuje jako přesný, přesný, snadno odhadnutelný, efektivně vypočítatelný a nezávislý na doméně“.[6] Do hloubky experimentoval Piškvorky a poté pomocí strojově generovaných vyhodnocovacích funkcí pro Othello a Šachy.

Tyto metody byly poté prozkoumány a úspěšně aplikovány na heuristické vyhledávání v oblasti automatizované dokazování věty W. Ertel, J. Schumann a C. Suttner v roce 1989,[7][8][9] čímž se zlepší časy exponenciálního vyhledávání neinformovaných vyhledávacích algoritmů, jako je např. prohledávání do šířky, prohledávání do hloubky nebo iterativní prohlubování.

V roce 1992 jej B. Brügmann poprvé použil v a Go-playing program.[10] Chang a kol.[11] ve svém algoritmu Adaptive Multi-stage Sampling (AMS) pro model Markovových rozhodovacích procesů navrhl myšlenku „rekurzivního rozvinutí a zpětného sledování“ s „adaptivním“ výběrem vzorků. AMS byla první prací, která prozkoumala myšlenku UCB - průzkum a využití při konstrukci vzorkovaných / simulovaných stromů (Monte Carlo) a bylo hlavním semenem UCT (Upper Confidence Trees).[12]

Hledání stromu Monte Carlo (MCTS)

Hodnocení nejlepších Go-playing programů na serveru KGS od roku 2007. Od roku 2006 používají všechny nejlepší programy stromové vyhledávání Monte Carlo.[13]

V roce 2006, inspirovaný těmito předchůdci,[14] Rémi Coulom popsal aplikaci metody Monte Carlo na vyhledávání stromů her a vytvořil název vyhledávání stromů Monte Carlo,[15] L. Kocsis a Čs. Szepesvári vyvinul algoritmus UCT (Upper Confidence bounds applied to Trees),[16] a S. Gelly a kol. implementovali UCT do svého programu MoGo.[17] V roce 2008 dosáhlo MoGo dan (hlavní) úroveň v režimu 9 × 9 Go,[18] a program Fuego začal vyhrávat proti silným amatérským hráčům na 9 × 9 Go.[19]

V lednu 2012 program Zen zvítězil 3: 1 v zápase Go na desce 19 × 19 s amatér 2 dan hráč.[20] Google Deepmind vytvořil program AlphaGo, který se v říjnu 2015 stal prvním programem Computer Go, který bez profesionálního hráče Go porazil znevýhodnění na desce 19x19 plné velikosti.[1][21][22] V březnu 2016 byla AlphaGo udělena čestná úroveň 9 dan (mistr) v 19 × 19 Go za porážku Lee Sedol v zápas pěti her s konečným skóre čtyři hry k jedné.[23] AlphaGo představuje významné zlepšení oproti předchozím programům Go a také milník v roce strojové učení protože používá vyhledávání stromu Monte Carlo s umělé neuronové sítě (A hluboké učení metoda) pro politiku (výběr přesunu) a hodnotu, což jí dává efektivitu, která daleko předčí předchozí programy.[24]

Algoritmus MCTS byl také použit v programech, které hrají jiné stolní hry (například Hex,[25] Havannah,[26] Hra Amazonek,[27] a Arimaa[28]), videohry v reálném čase (například Paní Pac-Man[29][30] a Fable Legends[31]) a nedeterministické hry (např skat,[32] poker,[4] Magic: The Gathering,[33] nebo Osadníci z Catanu[34]).

Princip činnosti

MCTS se zaměřuje na analýzu nejslibnějších tahů a rozšiřování vyhledávací strom na základě náhodný výběr Aplikace prohledávání stromů Monte Carlo ve hrách je založena na mnoha playouty, také zvaný roll-out. V každém play-off se hra odehrává až do samého konce náhodným výběrem tahů. Konečný výsledek hry každého playoutu se poté použije k vážení uzlů ve stromu hry, takže v budoucích playoutech je pravděpodobnější, že budou vybrány lepší uzly.

Nejzákladnějším způsobem použití playoutů je použití stejného počtu playoutů po každém legálním tahu aktuálního hráče, poté vyberte tah, který vedl k největšímu počtu vítězství.[10] Účinnost této metody - tzv Pure Monte Carlo Game Search—Často se časem zvyšuje, protože tahům, které často vedly k vítězství aktuálního hráče podle předchozích her, je přiřazeno více her. Každé kolo vyhledávání stromu Monte Carlo se skládá ze čtyř kroků:[35]

  • Výběr: Začít od root R a vyberte po sobě jdoucí podřízené uzly až do uzlu listu L je dosaženo. Kořen je aktuální stav hry a list je jakýkoli uzel, který má potenciální dítě, ze kterého ještě nebyla zahájena žádná simulace (přehrávání). V následující části se dozvíte více o způsobu ovlivnění výběru podřízených uzlů, který umožňuje, aby se strom hry rozšiřoval směrem k nejslibnějším tahům, což je podstatou vyhledávání stromu Monte Carlo.
  • Expanze: Pokud L ukončí hru rozhodně (např. výhra / prohra / remíza) pro jednoho hráče, vytvoří jeden (nebo více) podřízených uzlů a zvolí uzel C od jednoho z nich. Podřízené uzly jsou jakékoli platné tahy z pozice hry definované pomocí L.
  • Simulace: Dokončete jedno náhodné přehrávání z uzlu C. Tento krok se někdy také nazývá playout nebo zavádění. Playout může být stejně jednoduché jako výběr uniforma náhodná tahy, dokud není rozhodnuto o hře (například v šachu je hra vyhrána, ztracena nebo vylosována).
  • Zpětná propagace: Výsledek přehrávání použijte k aktualizaci informací v uzlech na cestě z C na R.
Krok vyhledávání stromu Monte Carlo.

Tento graf ukazuje kroky spojené s jedním rozhodnutím, přičemž každý uzel ukazuje poměr výher k celkovému počtu odehraných zápasů od tohoto bodu ve stromu hry pro hráče, kterého uzel představuje.[36] V diagramu výběru se černá pohybuje. Kořenový uzel ukazuje, že z této pozice zatím zbývá 11 výher z 21 play-off. Doplňuje celkem 10/21 černých výher zobrazených podél tří černých uzlů pod ním, z nichž každý představuje možný černý tah.

Pokud bílá ztratí simulaci, všechny uzly ve výběru zvýšily počet simulací (jmenovatel), ale mezi nimi byly připsány pouze černé uzly (čitatel). Pokud místo toho vyhraje bílá, všechny uzly ve výběru by stále zvyšovaly počet simulací, ale mezi nimi by byly připsány pouze bílé uzly. Ve hrách, kde jsou možné remízy, remíza způsobí, že se čitatel pro černou i bílou zvýší o 0,5 a jmenovatel o 1. Tím se zajistí, že během výběru se možnosti každého hráče rozšíří směrem k nejslibnějším tahům daného hráče, což odráží Cílem každého hráče je maximalizovat hodnotu svého tahu.

Kola vyhledávání se opakují, dokud zbývá čas přidělený pohybu. Poté je jako konečná odpověď zvolen tah s největším počtem provedených simulací (tj. Nejvyšší jmenovatel).

Čisté hledání her v Monte Carlu

Tento základní postup lze použít na jakoukoli hru, jejíž pozice nutně mají konečný počet tahů a konečnou délku. Pro každou pozici jsou určeny všechny proveditelné pohyby: k náhodné hry se hrají až do samého konce a skóre se zaznamenávají. Je vybrán tah vedoucí k nejlepšímu skóre. Kravaty jsou rozbité spravedlivými převráceními mincí. Výsledkem hry Pure Monte Carlo Game Search je silná hra v několika hrách s náhodnými prvky, jako ve hře EinStein würfelt nicht!. Konverguje k optimálnímu přehrávání (jako k inklinuje k nekonečnu) v deskových hrách s náhodným pořadí tahů, například v Hex s náhodným pořadí tahů.[37] DeepMind AlphaZero nahrazuje krok simulace hodnocením založeným na neuronové síti.[2]

Průzkum a těžba

Hlavním problémem při výběru podřízených uzlů je udržování určité rovnováhy mezi vykořisťování hlubokých variant po tahech s vysokou průměrnou mírou výhry a průzkum tahů s několika simulacemi. První vzorec pro vyvažování vykořisťování a průzkumu ve hrách, nazvaný UCT (Horní hranice důvěryhodnosti 1 aplikováno na stromy), byl představen Levente Kocsis a Csaba Szepesvári.[16] UCT je založen na vzorci UCB1 odvozeném od Auera, Cesa-Bianchiho a Fischera[38] a prokazatelně konvergentní algoritmus AMS (Adaptive Multi-stage Sampling) nejprve aplikovaný na vícestupňové modely rozhodování (konkrétně Markovské rozhodovací procesy ) Chang, Fu, Hu a Marcus.[11] Kocsis a Szepesvári doporučují zvolit v každém uzlu herního stromu tah, pro který je výraz má nejvyšší hodnotu. V tomto vzorci:

  • wi znamená počet výher pro uzel uvažovaný po i-th tah
  • ni znamená počet simulací pro uzel uvažovaný po i-tý tah
  • Ni znamená celkový počet simulací po i-tý tah spuštěný nadřazeným uzlem uvažovaného
  • C je parametr průzkumu - teoreticky stejný jako √2; v praxi se obvykle volí empiricky

První složka výše uvedeného vzorce odpovídá vykořisťování; je vysoká u tahů s vysokým průměrným poměrem výher. Druhá složka odpovídá průzkumu; je vysoká pro pohyby s několika simulacemi.

Většina současných implementací vyhledávání stromů Monte Carlo je založena na nějaké variantě UCT, která sleduje její kořeny zpět k algoritmu optimalizace simulace AMS pro odhad hodnotové funkce v konečném horizontu Markovské rozhodovací procesy (MDP) zavedené Changem a kol.[11] (2005) v Operační výzkum. (AMS byla první prací, která prozkoumala myšlenku průzkumu a vykořisťování založeného na UCB při konstrukci vzorkovaných / simulovaných (Monte Carlo) stromů a byla hlavním semenem pro UCT.[12])

Výhody a nevýhody

Ačkoli bylo prokázáno, že hodnocení pohybů ve stromovém vyhledávání Monte Carlo konverguje k minimax,[39] základní verze stromového vyhledávání Monte Carlo konverguje pouze v takzvaných „Monte Carlo Perfect“ hrách[40]. Hledání stromů v Monte Carlu však oproti tomu nabízí značné výhody prořezávání alfa – beta a podobné algoritmy, které minimalizují prostor pro vyhledávání.

Čisté hledání stromu Monte Carlo zejména nevyžaduje explicitní vyhodnocovací funkce. Pouhá implementace mechaniky hry je dostatečná k prozkoumání prostoru pro vyhledávání (tj. Generování povolených tahů v dané pozici a podmínky na konci hry). Vyhledávání stromů Monte Carlo lze tedy použít ve hrách bez rozvinuté teorie nebo v obecné hraní her.

Strom hry ve vyhledávání stromů v Monte Carlu roste asymetricky, jak se metoda soustředí na slibnější podstromy. Tím pádem[pochybný – diskutovat] dosahuje lepších výsledků než klasické algoritmy ve hrách s vysokou úrovní větvící faktor.

Vyhledávání stromů Monte Carlo lze navíc přerušit v kdykoli což přináší nejslibnější již nalezený krok.

Nevýhodou je, že v kritické pozici proti zkušenému hráči může existovat jediná větev, která vede ke ztrátě. Vzhledem k tomu, že to není snadné najít náhodně, hledání to nemusí „vidět“ a nebude to brát v úvahu. Předpokládá se, že to mohlo být jedním z důvodů Ztráta AlphaGo ve čtvrtém zápase proti Lee Sedol. Hledání se v podstatě pokouší ořezat sekvence, které jsou méně relevantní. V některých případech může hra vést k velmi specifické linii hry, která je významná, ale která je při prořezávání stromu přehlížena, a tento výsledek je proto „mimo vyhledávací radar“.[41]

Vylepšení

Byly navrženy různé modifikace základní metody hledání stromu Monte Carlo, aby se zkrátila doba hledání. Některé využívají odborné znalosti specifické pro doménu, jiné nikoli.

Hledání stromu Monte Carlo lze použít buď světlo nebo těžký playouty. Lehké playouty se skládají z náhodných tahů, zatímco těžké playouty používají různé heuristiky, aby ovlivnily výběr tahů.[42] Tyto heuristiky mohou využívat výsledky předchozích playoutů (např. Heuristika Last Good Reply)[43]) nebo odborné znalosti dané hry. Například v mnoha programech pro hraní Go ovlivňují určité kamenné vzory v části hracího plánu pravděpodobnost přesunu do této oblasti.[17] Paradoxně, díky neoptimálnímu hraní v simulacích je program vyhledávání stromů Monte Carlo někdy celkově silnější.[44]

Vzory hane (okolní soupeřovy kameny) používané v playoutech programem MoGo. Pro černou i bílou je výhodné umístit na prostřední čtverec kámen, kromě vzoru zcela vpravo, kde upřednostňuje pouze černou.[17]

Při vytváření herního stromu mohou být využity znalosti specifické pro doménu, které pomohou využít některé varianty. Jedna taková metoda přiřadí nenulovou hodnotu předchůdci k počtu vyhraných a hraných simulací při vytváření každého podřízeného uzlu, což vede k uměle zvýšenému nebo sníženému průměrnému výhernímu poměru, který způsobí, že uzel bude v kroku výběru vybrán více či méně často.[45] Související metoda, tzv progresivní zkreslení, spočívá v přidání do vzorce UCB1 a prvek, kde bi je heuristické skóre i-th tah.[35]

Základní vyhledávání stromu Monte Carlo sbírá dostatek informací k nalezení nejslibnějších tahů až po mnoha kolech; do té doby jsou jeho pohyby v zásadě náhodné. Tuto průzkumnou fázi lze u určité třídy her pomocí RAVE významně snížit (Rychlý odhad hodnoty akce).[45] V těchto hrách vedou permutace řady tahů do stejné polohy. Typicky se jedná o deskové hry, ve kterých tah zahrnuje umístění kousku nebo kamene na hrací plochu. V takových hrách je hodnota každého tahu často jen mírně ovlivněna jinými tahy.

V RAVE pro daný uzel herního stromu N, jeho podřízené uzly Ci ukládat nejen statistiky vítězství v playoutech spuštěných v uzlu N ale také statistiky výher ve všech playoutech spuštěných v uzlu N a pod ním, pokud obsahují tah i (také když byl tah přehráván ve stromu, mezi uzly N a playout). Tímto způsobem je obsah uzlů stromu ovlivněn nejen tahy hranými okamžitě na dané pozici, ale také stejnými tahy hranými později.

RAVE na příkladu tic-tac-toe. V červených uzlech budou statistiky RAVE aktualizovány po simulaci b1-a2-b3.

Pokud používáte RAVE, krok výběru vybere uzel, pro který je upravený vzorec UCB1 má nejvyšší hodnotu. V tomto vzorci a stojí za počet vyhraných zápasů obsahujících tah i a počet všech her, které obsahují tah ia funkce by měla být blízká jedné a nule pro relativně malé a relativně velké ni a , resp. Jeden z mnoha vzorců pro , navrhl D. Silver,[46] říká, že ve vyvážených pozicích se dá zaujmout , kde b je empiricky zvolená konstanta.

Heuristika používaná při vyhledávání stromů v Monte Carlu často vyžaduje mnoho parametrů. Existují automatizované metody pro vyladění parametrů k maximalizaci míry výhry.[47]

Hledání stromů v Monte Carlu může současně provádět mnoho lidí vlákna nebo procesy. Existuje několik zásadně odlišných metod paralelní provedení:[48]

  • Paralelizace listů, tj. paralelní provedení mnoha playoutů z jednoho listu herního stromu.
  • Kořenová paralelizace, tj. Budování nezávislých herních stromů paralelně a provádění tahu založeného na kořenových větvích všech těchto stromů.
  • Paralelizace stromů, tj. paralelní budování stejného stromu hry, ochrana dat před současným zápisem buď s jedním globálním mutex, s více mutexy nebo s neblokující synchronizace.[49]

Viz také

Reference

  1. ^ A b Stříbro, Davide; Huang, Aja; Maddison, Chris J .; Guez, Arthur; Sifre, Laurent; Driessche, George van den; Schrittwieser, Julian; Antonoglou, Ioannis; Panneershelvam, Veda; Lanctot, Marc; Dieleman, Sander; Grewe, Dominik; Nham, John; Kalchbrenner, Nal; Sutskever, Ilyo; Lillicrap, Timothy; Leach, Madeleine; Kavukcuoglu, Koray; Graepel, Thore; Hassabis, Demis (28. ledna 2016). "Zvládnutí hry Go pomocí hlubokých neuronových sítí a vyhledávání stromů". Příroda. 529 (7587): 484–489. Bibcode:2016Natur.529..484S. doi:10.1038 / příroda16961. ISSN  0028-0836. PMID  26819042. S2CID  515925.uzavřený přístup
  2. ^ A b Silver, David (2017). „Zvládnutí šachu a šógi hraním sebe sama s algoritmem učení se všeobecnou výzvou“. arXiv:1712.01815v1 [cs.AI ].
  3. ^ Stuart J. Russell, Peter Norvig (2009). Umělá inteligence: moderní přístup (3. vyd.). Prentice Hall.CS1 maint: používá parametr autoři (odkaz)
  4. ^ A b Jonathan Rubin; Ian Watson (duben 2011). „Počítačový poker: recenze“ (PDF). Umělá inteligence. 175 (5–6): 958–987. doi:10.1016 / j.artint.2010.12.005. Archivovány od originál (PDF) dne 2012-08-13.
  5. ^ „Hledání stromu Monte-Carlo ve hře TOTAL WAR: ROME II's Campaign AI“. AI Game Dev. Archivovány od originál dne 13. března 2017. Citováno 25. února 2017.
  6. ^ Abramson, Bruce (1987). Model očekávaných výsledků her pro dva hráče (PDF). Technická zpráva, Katedra informatiky, Columbia University. Citováno 23. prosince 2013.
  7. ^ Wolfgang Ertel; Johann Schumann; Christian Suttner (1989). „Učit se heuristiku pro poskytovatele věty pomocí zpětného šíření.“. V J. Retti; K. Leidlmair (eds.). 5. Österreichische Artificial-Intelligence-Tagung. Informatik-Fachberichte 208, pp. 87-95. Springer.
  8. ^ Christian Suttner; Wolfgang Ertel (1990). „Automatické získávání heuristiky s průvodcem vyhledáváním.“. CADE90, 10. Int. Konf. na Automated Deduction.pp. 470-484. LNAI 449. Springer.
  9. ^ Christian Suttner; Wolfgang Ertel (1991). „Použití sítí zpětného šíření k vedení hledání poskytovatele věty“. Journal of Neural Networks Research & Applications. 2 (1): 3–16.
  10. ^ A b Brügmann, Bernd (1993). Monte Carlo Go (PDF). Technická zpráva, Katedra fyziky, Syracuse University.
  11. ^ A b C Chang, Hyeong Soo; Fu, Michael C .; Hu, Jiaqiao; Marcus, Steven I. (2005). „Adaptivní vzorkovací algoritmus pro řešení Markovových rozhodovacích procesů“ (PDF). Operační výzkum. 53: 126–139. doi:10.1287 / opre.1040.0145. hdl:1903/6264.
  12. ^ A b Hyeong Soo Chang; Michael Fu; Jiaqiao Hu; Steven I. Marcus (2016). „Google DeepMind's Alphago: O.R. je neohlášená role v úspěchu průlomové cesty“. NEBO MS dnes. 45 (5): 24–29.
  13. ^ "Sensei's Library: KGSBotRatings". Citováno 2012-05-03.
  14. ^ Rémi Coulom (2008). „Revoluce Monte-Carlo v pohybu“ (PDF). Sympózium japonsko-francouzských hranic vědy.
  15. ^ Rémi Coulom (2007). "Efektivní operátory selektivity a zálohování ve vyhledávání stromů Monte-Carlo". Počítače a hry, 5. mezinárodní konference, CG 2006, Turín, Itálie, 29. – 31. Května 2006. Revidované příspěvky. H. Jaap van den Herik, Paolo Ciancarini, H. H. L. M. Donkers (eds.). Springer. 72–83. CiteSeerX  10.1.1.81.6817. ISBN  978-3-540-75537-1.
  16. ^ A b Kocsis, Levente; Szepesvári, Csaba (2006). „Plánování Monte Carla na základě banditů“. Ve Fürnkranz, Johannes; Scheffer, Tobias; Spiliopoulou, Myra (eds.). Strojové učení: ECML 2006, 17. evropská konference o strojovém učení, Berlín, Německo, 18. – 22. Září 2006, sborník. Přednášky z informatiky. 4212. Springer. str. 282–293. CiteSeerX  10.1.1.102.1296. doi:10.1007/11871842_29. ISBN  3-540-45375-X.
  17. ^ A b C Sylvain Gelly; Yizao Wang; Rémi Munos; Olivier Teytaud (listopad 2006). Úprava UCT se vzory v Monte Carlu Go (PDF). Technická zpráva, INRIA.
  18. ^ Chang-Shing Lee; Mei-Hui Wang; Guillaume Chaslot; Jean-Baptiste Hoock; Arpad Rimmel; Olivier Teytaud; Shang-Rong Tsai; Shun-Chin Hsu; Tzung-Pei Hong (2009). „Výpočetní inteligence MoGo odhalena na tchajwanských počítačových turnajech Go“ (PDF). Transakce IEEE na výpočetní inteligenci a AI ve hrách. 1 (1): 73–89. CiteSeerX  10.1.1.470.6018. doi:10.1109 / tciaig.2009.2018703. S2CID  15266518.
  19. ^ Markus Enzenberger; Martin Mūller (2008). Fuego - otevřený rámec pro deskové hry a Go Engine založený na vyhledávání stromů v Monte Carlu (PDF). Technická zpráva, University of Alberta.
  20. ^ „Shodan Go Bet“. Citováno 2012-05-02.
  21. ^ „Research Blog: AlphaGo: Mastering the ancient game of Go with Machine Learning“. Výzkumný blog Google. 27. ledna 2016.
  22. ^ „Google dosáhl„ průlomu “AI tím, že porazil Go šampiona“. BBC novinky. 27. ledna 2016.
  23. ^ „Match 1 - Google DeepMind Challenge Match: Lee Sedol vs AlphaGo“. Youtube. 9. března 2016.
  24. ^ „Google AlphaGo AI clean zametá evropského šampiona Go“. ZDNet. 28. ledna 2016.
  25. ^ Broderick Arneson; Ryan Hayward; Philip Henderson (červen 2009). „MoHex vyhrává Hex turnaj“ (PDF). ICGA Journal. 32 (2): 114–116. doi:10.3233 / ICG-2009-32218.
  26. ^ Timo Ewalds (2011). Hraní a řešení Havannah (PDF). Diplomová práce, University of Alberta.
  27. ^ Richard J. Lorentz (2008). „Amazonky objevují Monte Carlo“. Počítače a hry, 6. mezinárodní konference, CG 2008, Peking, Čína, 29. září - 1. října 2008. Sborník. H. Jaap van den Herik, Xinhe Xu, Zongmin Ma, Mark H. M. Winands (eds.). Springer. s. 13–24. ISBN  978-3-540-87607-6.
  28. ^ Tomáš Kozelek (2009). Metody MCTS a hra Arimaa (PDF). Diplomová práce, Univerzita Karlova v Praze.
  29. ^ Xiaocong Gan; Yun Bao; Zhangang Han (prosinec 2011). „Metoda vyhledávání v reálném čase v nedeterministické hře - paní Pac-Man“. ICGA Journal. 34 (4): 209–222. doi:10.3233 / ICG-2011-34404.
  30. ^ Tom Pepels; Mark H. M. Winands; Marc Lanctot (září 2014). „Hledání stromu Monte Carlo v reálném čase v paní Pac-Manové“. Transakce IEEE na výpočetní inteligenci a AI ve hrách. 6 (3): 245–257. doi:10.1109 / tciaig.2013.2291577.
  31. ^ Mountain, Gwaredd (2015). „Taktické plánování a MCTS v reálném čase v legendách Fable“. Citováno 2019-06-08. .. implementovali jsme přístup založený na simulaci, který zahrnoval modelování hry a použití MCTS k prohledání potenciálního prostoru plánu. Celkově to fungovalo dobře, ...
  32. ^ Michael Buro; Jeffrey Richard Long; Timothy Furtak; Nathan R. Sturtevant (2009). „Zlepšení hodnocení stavu, odvozování a vyhledávání v trikových karetních hrách“. IJCAI 2009, Proceedings of the 21st International Joint Conference on Artificial Intelligence, Pasadena, California, USA, 11. – 17. Července 2009. Craig Boutilier (vyd.). 1407–1413. CiteSeerX  10.1.1.150.3077.
  33. ^ CD. Ward; P.I. Cowling (2009). „Hledání Monte Carlo aplikováno na výběr karet v Magic: The Gathering“ (PDF). CIG'09 Sborník z 5. mezinárodní konference o výpočetní inteligenci a hrách. Tisk IEEE. Archivovány od originál (PDF) dne 2016-05-28.
  34. ^ István Szita; Guillaume Chaslot; Pieter Spronck (2010). „Hledání stromu Monte-Carlo u osadníků z Catanu“ (PDF). V Jaap Van Den Herik; Pieter Spronck (eds.). Pokroky v počítačových hrách, 12. mezinárodní konference, ACG 2009, Pamplona, ​​Španělsko, 11. – 13. Května 2009. Revised Papers. Springer. 21–32. ISBN  978-3-642-12992-6.
  35. ^ A b G.M.J.B. Chaslot; M.H.M. Winands; J.W.H.M. Uiterwijk; H. J. van den Herik; B. Bouzy (2008). „Progresivní strategie pro vyhledávání stromů v Monte Carlu“ (PDF). Nová matematika a přírodní výpočty. 4 (3): 343–359. doi:10,1142 / s1793005708001094.
  36. ^ Bradberry, Jeff (07.09.2015). „Úvod do vyhledávání stromu Monte Carlo“.
  37. ^ Peres, Yuval; Schramm, Oded; Sheffield, Scott; Wilson, David B. (2006). "Hex s náhodným tahem a další výběrové hry". arXiv:matematika / 0508580.
  38. ^ Auer, Peter; Cesa-Bianchi, Nicolò; Fischer, Paul (2002). „Analýza problému s více pásmy v banditech v konečném čase“ (PDF). Strojové učení. 47 (2/3): 235–256. doi:10.1023 / a: 1013689704352. S2CID  207609497. Archivovány od originál (PDF) dne 2014-05-12.
  39. ^ Bouzy, Bruno. „Staromódní počítač Go vs Monte Carlo Go“ (PDF). Sympozium IEEE o výpočetní inteligenci a hrách, 1. – 5. Dubna 2007, Hilton Hawaiian Village, Honolulu, Havaj.
  40. ^ Althöfer, Ingo (2012). „Hry na palubě s náhodným pořadí a perfektní Monte Carlo“. Pokroky v počítačových hrách. Přednášky z informatiky. 7168. str. 258–269. doi:10.1007/978-3-642-31866-5_22. ISBN  978-3-642-31865-8.
  41. ^ „Lee Sedol porazil AlphaGo v mistrovském návratu - hra 4“. Go Game Guru. Archivovány od originál dne 16. 11. 2016. Citováno 2017-07-04.
  42. ^ Świechowski, M .; Mańdziuk, J., „Adaptace herních strategií při obecném hraní her“ (2010), Transakce IEEE na výpočetní inteligenci a AI ve hrách, svazek: 6 (4), str. 367-381, doi: 10.1109 / TCIAIG.2013.2275163, http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6571225&isnumber=4804729
  43. ^ Drake, Peter (prosinec 2009). „Zásada poslední dobré odpovědi pro Monte Carlo Go“. ICGA Journal. 32 (4): 221–227. doi:10.3233 / ICG-2009-32404.
  44. ^ Seth Pellegrino; Peter Drake (2010). "Zkoumání účinků síly hry v Monte Carlu Go". Sborník příspěvků z Mezinárodní konference o umělé inteligenci 2010, ICAI 2010, 12. – 15. Července 2010, Las Vegas, Nevada, USA. Hamid R. Arabnia, David de la Fuente, Elena B. Kozerenko, José Angel Olivas, Rui Chang, Peter M. LaMonica, Raymond A. Liuzzi, Ashu M. G. Solo (eds.). CSREA Stiskněte. str. 1015–1018. ISBN  978-1-60132-148-0.
  45. ^ A b Sylvain Gelly; David Silver (2007). „Kombinace online a offline znalostí v UCT“ (PDF). Machine Learning, Proceedings of the Twenty-Fourth International Conference (ICML 2007), Corvallis, Oregon, USA, 20. – 24. Června 2007. Zoubin Ghahramani (ed.). ACM. str. 273–280. ISBN  978-1-59593-793-3.
  46. ^ David Silver (2009). Posílení učení a vyhledávání založené na simulaci v počítači Go (PDF). Disertační práce, University of Alberta.
  47. ^ Rémi Coulom. „CLOP: Spolehlivá místní optimalizace pro hlučné ladění parametrů černé skříňky“. ACG 2011: Advances in Computer Games 13 Conference, Tilburg, Nizozemsko, 20. – 22. Listopadu.
  48. ^ Guillaume M.J-B. Chaslot, Mark H.M. Winands, Jaap van den Herik (2008). „Parallel Monte-Carlo Tree Search“ (PDF). Počítače a hry, 6. mezinárodní konference, CG 2008, Peking, Čína, 29. září - 1. října 2008. Sborník. H. Jaap van den Herik, Xinhe Xu, Zongmin Ma, Mark H. M. Winands (eds.). Springer. str. 60–71. ISBN  978-3-540-87607-6.CS1 maint: více jmen: seznam autorů (odkaz)
  49. ^ Markus Enzenberger; Martin Müller (2010). "Vícezávitový algoritmus pro vyhledávání stromů Monte Carlo bez zámků". V Jaap Van Den Herik; Pieter Spronck (eds.). Pokroky v počítačových hrách: 12. mezinárodní konference, ACG 2009, Pamplona, ​​Španělsko, 11. – 13. Května 2009, revidované příspěvky. Springer. str.14 –20. CiteSeerX  10.1.1.161.1984. ISBN  978-3-642-12992-6.

Bibliografie

  • Cameron Browne; Edward Powley; Daniel Whitehouse; Simon Lucas; Peter I. Kryt motoru; Philipp Rohlfshagen; Stephen Tavener; Diego Perez; Spyridon Samothrakis; Simon Colton (březen 2012). "Průzkum metod vyhledávání stromů v Monte Carlu". Transakce IEEE na výpočetní inteligenci a AI ve hrách. 4 (1): 1–43. CiteSeerX  10.1.1.297.3086. doi:10.1109 / tciaig.2012.2186810. S2CID  9316331.

externí odkazy