Monte-Carlo strategies for computer Go

Abstract

The game of Go is one of the games that still withstand classical Artificial Intelligence approaches. Hence, it is a good testbed for new AI methods. Amongst them, Monte-Carlo led to promising results. This method consists of building an evaluation function by averaging the outcome of several randomized games. The paper introduces a new strategy, which we call Objective Monte-Carlo, to improve this evaluation. Objective Monte-Carlo is composed of two parts. The first one is a move-selection strategy that adjusts the amount of exploration and exploitation automatically. We show experimentally that it outperforms the two classical strategies previously proposed for Monte-Carlo Go: Simulated Annealing and Progressive Pruning. The second part of our algorithm is a new backpropagation strategy. We show that it gives better results than Minimax in this context. Finally we discuss the extension of this method to other problems. 1