Deep reinforcement Learning Using Monte-Carlo Tree Search for Hex and Othello

Abstract

Når Deepminds AlphaGo-program slo den menneskelige profesjonelle Go-spilleren Fan Hui i 2015 var dette et stort gjennombrudd for kunstig intelligens til spilling. Go hadde vist seg å motstå de teknikkene som lenge hadde slått mennesker i spill som sjakk. Gjennom en nyskapende kombinasjon av dype nevrale nettverk, forsterkende læring og Monte Carlo-tresøk ble Go endelig mestret. Kort tid etterpå kom AlphaGo Zero, som oppnådde det samme ved å lære utelukkende ved å spille mot seg selv, og AlphaZero, som generaliserte teknikken til andre spill.

Dette arbeidet inneholder en nøye gjennomgang av disse systemene og arbeidet i feltet som ledet opp mot dem. Det går gjennom min egen implementasjon av denne teknikken og dens bruk i spillene Hex og Othello. Ved hjelp av denne implementasjonen har jeg undersøkt rollen utrulling spiller i algoritmen. Dette var en sentral del av tidligere arbeid i feltet og fremdeles brukt i AlphaGo, men ikke i AlphaGo Zero og AlphaZero. Flere eksperimenter har blitt gjennomført for å få empiriske data for om utrulling fremdeles kan være en gunstig del av denne nyskapende kombinasjonen av teknikker, og hvordan disse i så fall bør gjennomføres.

Selv om det var noen indikasjoner i dataene på at utrulling har liten eller ingen positiv effect er disse resultatene stort sett ikke entydige. Noen svakheter i oppsettet har blitt identifisert og noen nye spørsmål har blitt oppdaget. Men arbeidet har resultert i et funksjonelt system som kan brukes til videre undersøkelser av problemområdet og enten gi mer entydige data eller innsikt i nye spørsmål.

When Deepmind's AlphaGo computer program beat the human professional Go player Fan Hui in 2015, it was a major breakthrough in AI game playing. Go had proved resilient to techniques that had long since beaten humans in games like chess. Through a novel combination of deep neural networks, reinforcement learning and Monte Carlo tree search, Go was finally mastered. Soon after came AlphaGo Zero, which accomplished even better results while learning completely from self-play, and AlphaZero, which generalized it to other games.

This work contains a thorough description of these systems and the work in the field which led up to them. It details my own implementation of this approach as applied to the games Hex and Othello. Using this implementation, the role rollouts play in the algorithm has been investigated. These were a core part of earlier work in the field and still used in AlphaGo, but then absent from AlphaGo Zero and AlphaZero. Several experiments have been conducted to gain empirical data on whether rollouts can still be a beneficial part of this novel combination of techniques, and how these rollouts should be performed.

Though there were some indications in the data that rollouts provide little or no benefit, the results were ultimately mostly inconclusive. Some weaknesses in the setup have been identified and some new questions have been raised. But the work has resulted in a functional system that could be used to further investigate the issue and produce more conclusive data or insight into new questions.