Applying AlphaZero Algorithm to an Imperfect Information Card Game

Abstract

Reinforcement learning is a machine learning paradigm where the learning system does not require labelled training data, it learns by experimentation and environment feedback. Google DeepMind’s AlphaGo demonstrated that reinforcement learning can beat a human champion in Go. It used recorded human expert games for supervised learning. DeepMind’s AlphaZero was trained tabula rasa, without human knowledge. The method used self-play with Monte Carlo Tree Search to improve the suggestions from network. AlphaZero's differentiating property compared to AlphaGo is bootstrapping from games played without domain understanding. This thesis studies the possibility to apply AlphaZero-inspired approach to learn to play games of imperfect information. An important part of the approach is to evaluate model goodness without human intelligence. In this work I created an evaluation system using classic minimax, fixed strategy baselines and games against older versions of the model. Results were promising and surprisingly clear. Firstly, the system was shown to learn and to beat trivial strategies and to beat older versions of the model. Secondly, it was shown and measured how much the imperfect information affected the learning potential. It was shown that 73% learning from the absolute maximum was reached and only 7% of the learning potential was left undone. The rest 20% is considered to be behind so called "information barrier", caused by the imperfect information. Learning that 20% would require more advanced methods and those are discussed in the thesis. Thirdly, a methodological approach for decomposition of learning progress was created. Fourth, the created learning and evaluation system is adaptable to other games or to measuring the effect of different amount of hidden information. The covered theoretical background includes reinforcement learning and AlphaZero, probability-related search methods, Markov Decision Process and exploration-exploitation trade-off. Further study, applications and approach limitations were considered, showing interesting directions for future work.

Vahvistusoppiminen on koneoppimisen paradigma, jossa oppiva järjestelmä ei tarvitse leimattua opetusdataa, vaan se oppii kokeilemalla ja ympäristöltä saatavan palautteen avulla. Google DeepMindin AlphaGo osoitti, että vahvistusoppivalla järjestelmällä voidaan voittaa mestaritason ihmispelaaja Go-pelissä. AlphaGo käytti tallennettuja ihmisasiantuntijoiden pelejä ohjattuun oppimiseen. DeepMindin AlphaZero koulutettiin tabula rasa -periaatteella, ilman ihmisen tuottamaa tietoa. Menetelmä käytti pelejä itseään vastaan yhdessä Monte Carlo -puuhaun kanssa parantaakseen neuroverkon ennusteita. AlphaZeron ero verrattuna AlphaGo:hon on ”bootstrappaus” eli oppiminen peleistä, joissa ei vielä ole minkäänlaista aihepiirin ymmärrystä. Tämä opinnäytetyö tutkii mahdollisuutta soveltaa AlphaZero -henkistä lähestymistapaa pelien oppimiseen tilanteissa, joissa pelitila ei ole täysin tiedossa, eli epätäydellisen informaation peleissä. Tärkeä osa kokeilun onnistumisessa on mallin hyvyyden arviointi ilman ihmisälyä. Tässä työssä loin arviointijärjestelmän, joka hyödyntää klassista minimax-hakua, kiinteitä vertailustrategioita sekä pelejä mallin vanhempia versioita vastaan. Tulokset olivat lupaavia ja yllättävän selkeitä. Ensinnäkin järjestelmän osoitettiin oppivan ja voittavan triviaalit strategiat sekä selvästi voittavan mallin vanhemmat versiot. Toiseksi mitattiin, kuinka paljon epätäydellinen informaatio vaikutti oppimispotentiaaliin. Osoitettiin, että 73 % teoreettisesta maksimioppimisesta saavutettiin ja vain 7 % oppimispotentiaalista jäi käyttämättä. Loput 20 % katsotaan johtuvan niin kutsutusta informaatiomuurista, jonka epätäydellinen informaatio aiheuttaa. Tämän 20 %:n oppiminen vaatisi kehittyneempiä menetelmiä ja niitä käsitellään työn keskusteluosuudessa. Kolmanneksi luotiin havainnollinen oppimisen komponenttien seuranta. Toteutettu kokeellinen järjestelmä ja arviointimenetelmä on sovellettavissa muihin peleihin tai kun piilotetun informaation määrän vaikutusta halutaan tarkastella. Työn teoreettinen tausta kattaa vahvistusoppimisen ja AlphaZeron, todennäköisyyspohjaiset hakumenetelmät, Markovin päätösprosessin sekä ”exploration-exploitation” -tasapainon. Jatkotutkimusta, sovelluksia ja valitun lähestymistavan rajoituksia pohdittiin ja näiden perusteella löytyi useita kiinnostavia suuntia jatkotyölle.