Monte Carlo tree search with neural network-based opponent modeling in the hidden information card game Moska

Abstract

When playing a game, humans often think ahead about the potential effect of their actions on the current game state, often doing so subconsciously. In our minds, we are creating a tree-like structure of allowed moves and the possible responses of our opponents. This look-ahead reasoning is straightforward in games, where all the information is visible, such as chess. But what happens when some of the information is hidden, like in many card games?

This study researches the question in the context of a hidden information multiplayer card game Moska. We create an application of the Monte Carlo Tree Search (MCTS) algorithm within this environment to develop an agent capable of beating a human player. The hidden information was handled with a determinization approach, using random and neural network-based methods. We trained the neural network with 50,000 games of data from self-play to model opponents hand cards, which was then used in the determinization process.

Our experiments showed that while a chance based random approach performed well in this environment, our neural network was able to model opponents’ hands with around 89% accuracy and significantly increase our agent’s playing strength. These results indicate that while a tree search algorithm like MCTS is applicable to hidden information environments, the quality of the information given is key to better performance.

Pelejä pelatessaan ihmiset monesti yrittävät ennakoida, miten heidän toimintansa vaikuttaa tulevaan pelitilanteeseen, usein täysin tiedostamatta. Luomme mielessämme hakupuulle ominaisen rakenteen, kun mietimme pelin nykytilanteen salittuja siirtoja ja vastustajien mahdollisia reaktioita eteenpäin. Tämä ajatteluprosessi on luontaista peleissä, joissa kaikki tieto on näkyvissä, kuten shakissa. Mutta mitä tapahtuu, kun osa tiedosta ei olekaan saatavilla?

Tässä tutkimuksessa kysymystä tarkastellaan piilotetun tiedon moninpelikorttipelissä, Moskassa. Tavoitteena oli kehittää ihmisen päihittävä Monte Carlo -puuhakualgoritmi pohjainen agentti Moska-korttipeliin. Monte Carlo -hakupuu ei ole suoraan hyödynnettävissä piilotetun informaation ympäristöissä, joten tätä ongelmaa lähestyttiin determinisointimenetelmällä, käyttäen sekä satunnaista että neuroverkkopohjaista lähestymistapaa. Tutkimuksen neuroverkko koulutettiin mallintamaan vastustajien käsikortteja pelitilanteen pohjalta ja malli koulutettiin 50 000 pelitilanteen sisältävällä itse kerätyllä aineistolla.

Työn tulokset osoittavat, että satunnaiseen determinisointiin pohjautuva lähestymistapa suoriutui hyvin työn piilotetun informaation ympäristössä. Neuroverkkopohjainen lähestymistapa kuitenkin paransi merkittävästi agentin pelitehoa ja malli pystyi luokittelemaan vastustajien käsikortit noin 89% tarkkuudella. Tutkimus osoitti, että Monte Carlo -puuhakualgoritmi on sovellettavissa piilotetun tiedon ympäristöihin, mutta algoritmin saama tiedon laatu ja tarkkuus ovat keskeisessä osassa pelaajien suorituskyvyn parantamisessa.