Monte Carlo Tree Search applied to Go : reaching omega

Details

Supervisors

Deville, Yves

Faculty

Ecole polytechnique de Louvain

Degree label

Master [120] : ingénieur civil en informatique

Abstract

This thesis is about designing an artificial intelligence Go player based on Monte Carlo Tree Search, or MCTS, techniques, with the lower bound complexity. Go is a strategy board game with a high complexity, having 10 to the power of 600 possible games. For this reason, artificial intelligence applied to Go is a challenging field, where progress can still be done. Before the recent match of AlphaGo versus a worldwide champion of Go, MCTS was considered as the state of the art and performed better than other methods. As the quality of the results of MCTS is proportional to the number of iterations, it is important to have the fastest iteration possible, leading to a more exhaustive search for an amount of time. This is the main focus of this master thesis. It was a success by making use of specific data structures for the Go board representation, resulting in the end in an optimal model. These structures are detailed and explained in this master thesis, as well as the way their combination allows to reach an optimal complexity. In addition to giving an implementation that reached the lower bound Ω, we expose one flaw of the core basic technique of MCTS when used alone. Moreover, we find and examine some leads. On the one hand, some of them correct the mentioned flaw, and on the other hand, some could be used in general to improve MCTS.