is Íslenska en English

Lokaverkefni (Meistara)

Háskólinn í Reykjavík > Tæknisvið / School of Technology > MSc Tölvunarfræðideild / Department of Computer Science >

Vinsamlegast notið þetta auðkenni þegar þið vitnið til verksins eða tengið í það: http://hdl.handle.net/1946/7478

Titill: 
  • Titill er á ensku CADIA-Player : a general game playing agent
  • CADIA-Player: alhliða leikjaspilari
Námsstig: 
  • Meistara
Leiðbeinandi: 
Útdráttur: 
  • Útdráttur er á ensku

    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 naïve 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ð búa til greind forrit sem ekki eru einskorðuð við einn leik, heldur fá sem inntak leikreglur og þurfa að geta lært að spila leikinn sem þær lýsa. Þetta neyðir forritið til að mynda herkænsku sína á eigin spýtur án þess að styðjast við upplýsingar um leikinn sem hönnuður þess hefur sett inn í það. Hingað til hafa þau forrit sem notið hafa mestrar velgengni í alhliða leikjaspilun notað hina hefðbundnu aðferð að leita í leiktrénu með sjálfvirkri uppgötvun gildisákvörðunarfalls til að hjúpa þekkingu út frá lýsingu leiksins. Í þessari ritgerð lýsum við CADIA-Player, alhliða leikjaspilara sem notar hermanir til að draga ályktanir um leiki. Nánar tiltekið notar hann Monte Carlo útspilun með UCT (Upper Confidence Bound fyrir tré) sem aðal leitaraðferð sína. CADIA-Player hefur þegar, með því að vinna þriðju árlegu keppni slíkra forrita sannað hversu áhrifaríkar aðferðir byggðar á hermun geta verið í alhliða leikjaspilun. Við lýsum útfærslu spilarans auk þess að sýna nokkrar betrumbætur á algríminu sem auka afköst þess. Niðurstöður tilrauna eru gefnar sem sýna að CADIA-Player hefur mikla yfirburði yfir einfaldan Monte Carlo spilara, eða rétt undir 90% vinningshlutfall að meðaltali í hinum ýmsu leikjum, þ.m.t. Checkers og Othello. Við rannsökum enn fremur tölfræðilegt mikilvægi þess hvernig UCT velur aðgerðir, minnislíkans hans og hinna ýmsu viðbóta við að ná þessum árangri.

Samþykkt: 
  • 1.2.2011
URI: 
  • http://hdl.handle.net/1946/7478


Skrár
Skráarnafn Stærð AðgangurLýsingSkráartegund 
MSc_Hilmar-Finnsson.pdf560.5 kBOpinnHeildartextiPDFSkoða/Opna