The Monte-Carlo Revolution in Go

Rmi Coulom e

Universit Charles de Gaulle, INRIA, CNRS, Lille, France e

January, 2009

JFFoS2008: Japanese-French Frontiers of Science Symposium
Introduction Monte-Carlo Tree Search History Conclusion
Game Complexity How can we deal with complexity ?

Game Complexity

Game Tic-tac-toe Connect 4 Checkers Chess Go

Complexity 10171

Status Solved manually Solved in 1988 Solved in 2007 Programs > best humans Programs best humans

Complexity:

number of board congurations
The Monte Carlo Revolution in Go

2 / 12

How can we deal with complexity ?
Some formal methods Use symmetries Use transpositions Combinatorial game theory

3 / 12

Some formal methods Use symmetries Use transpositions Combinatorial game theory When formal methods fail Approximate evaluation Reasoning with uncertainty

Dealing with Huge Trees

Full tree

4 / 12

Classical approach = depth limit + pos. evaluation (E) (chess, shogi,. ) Full tree
Monte-Carlo approach = random playouts
Rmi Coulom e The Monte Carlo Revolution in Go 4 / 12
Principle of Monte-Carlo Evaluation Monte-Carlo Tree Search Patterns

A Random Playout

5 / 12
Principle of Monte-Carlo Evaluation

Root Position

Random Playouts MC Evaluation + + =

6 / 12

Basic Monte-Carlo Move Selection
Algorithm N playouts for every move Pick the best winning rate 5,000 playouts/s on 19x19
Rmi Coulom e The Monte Carlo Revolution in Go 7 / 12
Algorithm N playouts for every move Pick the best winning rate 5,000 playouts/s on 19x19 Problems Evaluation may be wrong For instance, if all moves lose immediately, except one that wins immediately.

7 / 12

Monte-Carlo Tree Search
Principle More playouts to best moves Apply recursively Under some simple conditions: proven convergence to optimal move when #playouts 9/15 2/6 3/9
Rmi Coulom e The Monte Carlo Revolution in Go 8 / 12
Incorporating Domain Knowledge with Patterns
Patterns Library of local shapes Automatically generated Used for playouts Cut branches in the tree Examples (out of 30k)

Good to move

Rmi Coulom e The Monte Carlo Revolution in Go

9 / 12

History (1/2)
Pioneers 1993: Brgmann: rst MC program, not taken seriously u 2000: The Paris School: Bouzy, Cazenave, Helmstetter

10 / 12

Pioneers 1993: Brgmann: rst MC program, not taken seriously u 2000: The Paris School: Bouzy, Cazenave, Helmstetter Victories against classical programs 2006: Crazy Stone (Coulom) wins Computer Olympiad 2007: MoGo (Wang, Gelly, Munos,. ) wins 19 19

History (2/2)

Victories against professional players 2008-03: 2008-08: 2008-09: 2008-12: MoGo beats Catalin Taranu (5p) on MoGo beats Kim Myungwan (9p) at H9 Crazy Stone beats Kaori Aoba (4p) at H8 Crazy Stone beats Kaori Aoba (4p) at H7

11 / 12

Conclusion
Summary of Monte-Carlo Tree Search A major breakthrough for computer Go Works similar games (Hex, Amazons) and automated planning

12 / 12

Summary of Monte-Carlo Tree Search A major breakthrough for computer Go Works similar games (Hex, Amazons) and automated planning Perspectives Path to top-level human Go ? Adaptive playouts (far from the root) ?
Summary of Monte-Carlo Tree Search A major breakthrough for computer Go Works similar games (Hex, Amazons) and automated planning Perspectives Path to top-level human Go ? Adaptive playouts (far from the root) ? More information: http://remi.coulom.free.fr/CrazyStone/ Slides, papers, and game records Demo version of Crazy Stone (soon)
Rmi Coulom e The Monte Carlo Revolution in Go 12 / 12