Dizertace

Monte Carlo Tree Search in Imperfect-Information Games

(Monte Carlo prohledávaní v hrách s neúplnou informací)

Abstrakt

Monte Carlo Tree Search (MCTS) je v poslední době velmi populární algoritmus pro hraní her v extenzivní formě s úplnou informací. Jeho adaptace vedla například k programům hrajícím hru Go na úrovni lidských expertů nebo podstatnému zlepšení algoritmů pro doménově nezávislé automatické plánování. Inspirováni těmito úspěchy začali výzkumníci přizpůsobovat tuto techniku i pro hry s neúplnou informací. Neúplná informace způsobuje v těchto hrách několik komplikací, které se u her s úplnou informací neobjevují. Příkladem je třeba nutnost používání randomizovaných strategií pro zajištění optimálního hraní. I když vlastnosti optimálních strategií v těchto hrách jsou dobře prozkoumány, předchozí výzkum v oblasti MCTS v hrách s neúplnou informací na těchto znalostech nestaví dostatečně. Žádný z existujících MCTS algoritmů u těchto her nekonverguje k optimální strategii, i při neomezeném času na výpočet.

V této práci studujeme MCTS v hrách dvou hráčů s nulovým součtem v extenzivní formě s neúplnou informací a zaměřujeme se na herně teoretické vlastnosti produkovaných strategií. Postupujeme ve dvou krocích. Nejprve detailně analyzujeme jednu z nejjednodušších tříd her s neúplnou informací: hry se současnými tahy. Poté přistoupíme k plně generickým hrám s neúplnou informací. Zkoumáme stávající MCTS algoritmy pro tyto druhy her a zařazujeme je do několika principiálně odlišných tříd. Dále prezentujeme následující přínosy:

Za prvé se zaměřujeme na návrh nových MCTS algoritmů, které prokazatelně konvergují k Nashově rovnováze hry s rostoucím výpočetním časem. Navrhujeme tři takové algoritmy. Jeden je založený na menší modifikaci standardní MCTS šablony pro hry se současnými tahy a další dva na adaptaci úspěšného algoritmu Monte Carlo Counterfactual Regret Minimization (MCCRF) pro online hraní her jak v hrách se současnými tahy tak v obecných hrách s neúplnou informací.

Za druhé jsme se zaměřili na zlepšení výkonu MCTS algoritmů a to především tím, že navrhujeme a vyhodnocujeme nové funkce pro výběr akcí, které určují takové akce, které mají být vzorkovány v pozdějších iteracích na základě statistických údajů získaných z předchozích iterací. V obecných hrách s neúplnou informací navrhujeme explicitní modelování hráčových odhadů pravděpodobnosti, že se nachází v konkrétním herním stavu během hry.

Za třetí provádíme rozsáhlé vyhodnocení navržených a existujících MCTS metod na pěti hrách se současnými tahy a čtyřech hrách s neúplnou informací, které mají proměnnou velikost a zásadně odlišné vlastnosti. Hodnotíme schopnost algoritmů rychle konvergovat k Nashově rovnováze a jejich výkony srovnáváme ve vzájemných turnajích. Ukazujeme, že algoritmy založené na MCCFR mají velmi rychlou konvergenci k rovnováze, ale klasické MCTS s novými funkcemi pro výběr akcí vynikají při turnajích ve velkých hrách.

Závěrem prezentujeme případovou studii využití MCTS pro vytváření inteligentních agentů pro robotické hry pronásledování cílů. Navrhujeme doménově specifické varianty navržených algoritmů a vyhodnocujeme jejich úspěšnost ve složitém simulovaném prostředí. Ukazujeme, že algoritmy založené na MCTS překonávají nejlepší známý algoritmus pro tento problém.

Plný text (PDF)

Hry s neúplnou informací

Hráči v hrách s neúplnou informací přesně znají pravidla hry, ale při jednotivých rozhodnutích mohou částečně nebo úplně neznat nekteré minulé (nebo současné) akce ostatních hráčů nebo výsledky náhodných jevů. Typickým příkladem jsou hry jako poker, ale také problémy ze skutečného světa, jako například pronásledování inteligentních cílů ve fyzickém prostoru.

Malé varianty těchto her mohou být graficky znázorněné jako herní stromy. Neúplná informace je zachycena množinami uzlů, které hráč nedokáže rozlišit. Jednoduchá varianta pokeru s jednou kartou sa dá reprezentovat následovně.

Hra začína v kořeni stromu náhodnou volbou, která určuje možné karty rozdané Ann a Beth. Ann ví jakou kartu dostala, ale neví jakou kartu má Beth. Proto například nerozezná náhodné volby (1,2) a (1,3) spojené čárkovaně v levé horní části stromu. Když hráči dosáhou listů hry, dostanou odpovídajíci odměnu.

Realistické hry, které hrají lidé, jako i modely problému z reálneho světa mají typicky miliardy uzlů. Metody online prohledávání stavového prostoru, jako je MCTS, se pokoušejí nalézt dobrou strategii v těchto hrách ve velmi omezeném čase. V mé práci jsem se soustředil na tento typ algoritmů jak z praktického tak teoretického pohledu. Vyvíjel jsem praktické algoritmy které vyhrávají nad většinou jiných algoritmů ve vzájemné hře a z teoretického pohledu jsem k těmto algoritmům odvodil záruky dobrého chováni i proti nejhorším možným oponentům.

Možné aplikace

Navrhnuté metody jsem experimentálně ověřil ve velkém množství rozmanitých her. Tyto hry zahrnovaly jednoduché teoretické hry na vyhodnocování chování v nejhorším případě, hry běžne hrané lidmi, jako i komplikovanou simulaci taktických vojenských operací s bezpilotními robotickými prostředky.

Následuje krátké video demonstrující nejpokročilejší aplikaci.

Vybrané související publikace