Simulation-Based General Game Playing

Abstract

The aim of General Game Playing (GGP) is to create intelligent agents that automatically learn how to play many different games at an expert level without any human intervention. One of the main challenges such agents face is to automatically learn knowledge-based heuristics in real-time, whether for evaluating game positions or for search guidance. In this thesis we approach this challenge with Monte-Carlo Tree Search (MCTS), which in recent years has become a popular and effective search method in games. For competitive play such an approach requires an effective search-control mechanism for guiding the simulation playouts. In here we describe our GGP agent, CADIAPLAYER, and introduce several schemes for automatically learning search guidance based on both statistical and reinforcement learning techniques. Providing GGP agents with the knowledge relevant to the game at hand in real time is, however, a challenging task. This thesis furthermore proposes two extensions for MCTS in the context of GGP, aimed at improving the effectiveness of the simulations in real time based on in-game statistical feedback. Also we present a way to extend MCTS solvers to handle simultaneous move games. Finally, we study how various game-tree properties affect MCTS performance.

Markmið Alhliða Leikjaspilunar (General Game Playing, GGP) er að búa til forrit sem geta á sjálfstæðan hátt lært að spila marga mismunandi leiki og náð getu sérfræðings án þess að mannshöndin komi þar nærri. Ein aðal áskorunin við gerð slíkra forrita að geta á sjálfvirkann hátt búið til þekkingu í rauntíma sem hjálpar til við að meta stöður og leiðbeina leitarrekniritum. Hér er reynt að nálgast þetta vandmál með leitaraðferð byggðri á hermunum sem nefnist Monte-Carlo Trjá Leit (Monte-Carlo Tree Search, MCTS). MCTS hefur á undanförnum árum náð miklum vinsældum vegna góðs árangur í spilun margs konar leikja. Til að vera keppnishæft þarf forrit sem beitir MCTS að hafa yfir að ráða öflugum aðferðum til að stýra útspilun hermana sinna. Það að sjá GGP forriti fyrir þekkingu er hentar þeim leik sem verið er að spila hverju sinni er mikil áskorun. Við kynnum forrit okkar í Alhliða Leikjaspilun, CADIAPLAYER, og ýmsar aðferðir sem við höfum þróað fyrir það sem læra að stýra leit sjálfvirkt með notkun tölfræði og styrkingarnáms. Að auki eru kynntar tvær nýjar viðbætur við MCTS í GGP sem nýta tölfræðilega endurgjöf við spilun leikja á árangursríkan hátt. Einnig er sýnd viðbót við MCTS sem gerir kleift að leysa leiki þar sem spilarar leika á sama tíma. Að lokum er kannað hvernig nokkur eigindi leikjatrjáa hafa áhrif á getu MCTS til að spila leiki.