Monte-Carlo tree search and rapid action value estimation in computer Go

A new paradigm for search, based on Monte-Carlo simulation, has revolutionised the performance of computer Go programs. In this article we describe two extensions to the Monte-Carlo tree search algorithm, which significantly improve the effectiveness of the basic algorithm. When we applied these two extensions to the Go program MoGo, it became the first program to achieve dan (master) level in 9 x 9 Go. In this article we survey the Monte-Carlo revolution in computer Go, outline the key ideas that led to the success of MoGo and subsequent Go programs, and provide for the first time a comprehensive description, in theory and in practice, of this extended framework for Monte-Carlo tree search. (C) 2011 Elsevier B.V. All rights reserved.