CADIA-Player : a general game playing agent
Hilmar Finnsson · 2007
The aim of General Game Playing (GGP) is to create intelligent agents that can automatically learn how to play many different games well without any human intervention, given only a description of the game rules. This forces the agents to be able to learn a strategy without having any domain-specific knowledge provided by their developers. The most successful GGP agents have so far been based on the traditional approach of using game-tree search augmented with an automatically learned evaluation function for encapsulating the domain-specific knowledge. In this thesis we describe CADIAPlayer, a GGP agent that instead uses a simulation-based approach to reason about its actions. More specifically, it uses Monte Carlo rollouts with upper confidence bounds for trees (UCT) as its main search procedure. CADIAPlayer has already proven the effectiveness of this simulation-based approach in the context of GGP by winning the Third Annual GGP Competition. We describe its implementation as well as several algorithmic improvements for making the simulations more effective. Empirical data is presented showing that CADIA-Player outperforms naive Monte Carlo by close to 90% winning ratio on average on a wide range of games, including Checkers and Othello. We further investigate the relative importance of UCT’s actionselection rule, its memory model, and the various enhancements in achieving this result.; Markmið Alhliða Leikjaspilunar (e. General Game Playing) er að bua til greind forrit sem ekki eru einskorðuð við einn leik, heldur fa sem inntak leikreglur og þurfa að geta laert að spila leikinn sem þaer lýsa. Þetta neyðir forritið til að mynda herkaensku sina a eigin spýtur an þess að styðjast við upplýsingar um leikinn sem honnuður þess hefur sett inn i það. Hingað til hafa þau forrit sem notið hafa mestrar velgengni i alhliða leikjaspilun notað hina hefðbundnu aðferð að leita i leiktrenu með sjalfvirkri uppgotvun gildisakvorðunarfalls til að hjupa þekkingu ut fra lýsingu leiksins. I þessari ritgerð lýsum við CADIA-Player, alhliða leikjaspilara sem notar hermanir til að draga alyktanir um leiki. Nanar tiltekið notar hann Monte Carlo utspilun með UCT (Upper Confidence Bound fyrir tre) sem aðal leitaraðferð sina. CADIA-Player hefur þegar, með þvi að vinna þriðju arlegu keppni slikra forrita sannað hversu ahrifarikar aðferðir byggðar a hermun geta verið i alhliða leikjaspilun. Við lýsum utfaerslu spilarans auk þess að sýna nokkrar betrumbaetur a algriminu sem auka afkost þess. Niðurstoður tilrauna eru gefnar sem sýna að CADIA-Player hefur mikla yfirburði yfir einfaldan Monte Carlo spilara, eða rett undir 90% vinningshlutfall að meðaltali i hinum ýmsu leikjum, þ.m.t. Checkers og Othello. Við rannsokum enn fremur tolfraeðilegt mikilvaegi þess hvernig UCT velur aðgerðir, minnislikans hans og hinna ýmsu viðbota við að na þessum arangri.