Yew Jin's Sometimes Blog

When a million monkeys play Go, they win.

Enter the Monte Carlo method, named by its Manhattan Project pioneers for the casinos where they gambled. It consists of random simulations repeated again and again until patterns and probabilities emerge: the characteristics of an atomic bomb explosion, phase states in quantum fields, the outcome of a Go game. Programs like MoGO and Many Faces simulate random games from start to finish, over and over and over again, with no concern for figuring out which of any given move is best.

A professional 8-dan player has been defeated by MoGo, a computer Go program that uses Monte Carlo tree search algorithms, in a 9-stone handicap game on a 19x19 board. [usgo.org] [slashdot.org]

This represents a major milestone in computer Go, and is also, evidence that the Monte Carlo tree search algorithm is a viable search technique that works in high branching factor domains. In my honest opinion, the budding graduate student in computer games research can easily find applications of this technique in emerging problems which are unsolvable by traditional techniques.

Think RTS, think war games, think huge risk mitigation situations like epidemic simulations. sigh I had a research proposal rejected a year ago based on this concept, and, as a result, made me switch from academic research to industry.

The papers for ICML 2007 are now available online. As a game AI researcher, interesting papers include:

1. Learning to Solve Game Trees. David Stern, Ralf Herbrich and Thore Graepel.

Formulating a probabilistic model for nodes in a game-tree and performing best-first AND/OR search. Interesting trend in integrating statistical machine learning techniques into game-tree search techniques. See also authors' prior paper on Bayesian pattern matching in computer Go.

2. Combining Online and Offline Knowledge in UCT. Sylvain Gelly and David Silver.

UCT - Upper confidence Tree search is a promising game-tree search technique for games with high branching factor. This paper sheds some light on what does and does not work when using UCT.