The grand challenge of computer go: Monte carlo tree search and extensions

The ancient oriental game of Go has long been considered a grand challenge for artificial intelligence. For decades, com-puter Go has defied the classical methods in game tree search that worked so successfully for chess and checkers. How-ever, recent play in computer Go has been transformed by a new paradigm for tree search based on Monte-Carlo meth-ods. Programs based on Monte-Carlo tree search now play at human-master levels and are beginning to challenge top professional players. In this paper we describe the leading algorithms for Monte-Carlo tree search and explain how they have advanced the state of the art in computer Go. 1