I've been fascinated by the ancient board game of
Go
(Weiqi, Baduk) for a while. It's an incredibly deep game emerging from a
simple set of
rules.
You can read more about it at
Sensei's Library.
Unlike
chess, human players are
still stronger than the best
computer programs.
GOFAI techniques have
not been successful at tackling the problem of creating a strong Go AI
player. The high branching factor, long game length, lack of a strong
evaluation function
and global nature of the game make this a very tough
problem to solve. Recently, there has been a major breakthrough in
AI strength through a new algorithm called
Monte Carlo Tree Search (MCTS).
Having a
Monte Carlo
background through my work in
computer graphics,
this family of techniques seemed immediately appealing.
MCTS combines the precision of
minmax searching with
random simulations
(sometimes called playouts, or rollouts) for an evaluation function. Further,
UCT
(also see
Sensei's Library on UCT)
adapts the UCB algorithm (Upper Confidence Bounds as applied to the
Multi-armed Bandit Problem)
to trees. This basically combines
stochastic tree search, the exploitation vs exploration balance of a
bandit problem and the random-simulations-as-evaluation-function idea into a
powerful algorithm that forms the basis for most
top Go programs today.
See
A Survey of Monte Carlo Tree Search Methods
for a comprehensive overview. This is a very active area of research,
with many publications on improving the general tree search method and
incorporating domain specific knowledge into the playouts. The
RAVE
(Rapid Action Value Estimation) algorithm being an important example of the former, and the addition of
3x3 patterns
in the playouts an important example of the later.
Research problems
include finding automatic ways to acquire domain
specific knowledge without relying on external experts (See
Computing Elo Ratings of Move Patterns in the Game of Go), parallelization of
the MCTS algorithm and fixing weaknesses of current programs (such as dealing
with situations where the move order is of great importance).
The MCTS algorithm is now being used for applications other than Go such as
GGP (General
Game Playing) and other planning and decision making problems. My own Go
program, Gopher, is a heavy work-in-progress also based on UCT. It features
a largely
lock-free
tree representation and scales nicely on SMP machines.
The data structures used during playouts have been optimized for little state to
facilitate an eventual GPU port.
