IEEE Spectrum July, 2014 - 51

root
evaluation function adds up the material value of pieces (a queen,
for example, has a higher value than a pawn) and computes the
value of their locations on the board based on their potential to
attack or be attacked.
Compared with that of chess pieces, the value of individual Go
stones is much lower. Therefore the evaluation of a Go position
is based on all the stones' locations, and on judgments about
which of them will eventually be captured and which will stay
safe during the shifting course of a long game. To make this
assessment, human players rely on both a deep tactical understanding of the game and a clear-eyed appraisal of the overall
board situation. Go masters consider the strength of various
groups of stones and look at the potential to create, expand, or
conquer territories across the board.
Rather than try to teach a Go-playing program how to perform
this complex assessment, we've found that the best solution is to
skip the evaluation process entirely. Over the past decade, several research groups have pioneered a new search paradigm for
games, and the technique actually has a chance at cracking Go.
Surprisingly, it's based on sequences of random moves. In its simplest form, this approach, called Monte Carlo tree search (MCTS),
eschews all knowledge of the desirability of game positions.
A program that uses MCTS need only know the rules of the game.
From the current configuration of stones on the board, the
program simulates a random sequence of legal moves (playing
moves for both opponents) until the end of the game is reached,
resulting in a win or loss. It automatically does this over and over.
The magic comes from the use of statistics. The evaluation of a
position can be defined as the frequency with which random
move sequences originating in that position lead to a win. For
instance, the program might determine that when move A is
played, random sequences of moves result in a win 73 percent
of the time, while move B leads to a win only 54 percent of the
time. It's a shockingly simple metric.
It may seem counterintuitive to try to win a deeply strategic
game with a program that uses random moves to evaluate its
different choices. But there are lots of precedents that show
the efficacy of this statistical approach. For example, most
Internet search engines do not attempt to analyze a query to try
to understand the semantics of what is being asked for-they just
apply some simple numerical schemes to rank results. Monte
Carlo methods are also standard in disciplines such as particle
physics, weather forecasting, chemistry, and finance. They are
often the best approach for solving complex problems in which
problem-specific knowledge is hard to formalize.
a go-playing ai can repeaTedly apply iTs mcTs algoriThm

until resources-time or memory-run out. Like many other
search methods, MCTS constructs a game tree, in which
each possible move creates branches of new possible moves,
which are conventionally drawn pointing downward. For a
basic example of this algorithm, imagine that a Go program
is trying to decide on its next move. It would therefore repeat
these four steps:
1. Tree descent: From the existing board position (the root

2/4
Leaf node
2/3

0/1

Leaf node

1/1

0/1

1/1

GrowinG
the Tree
In these four simulations of a simple
Monte Carlo tree search, the program,
playing as black, evaluates the winning
potential of possible moves. Starting
from a position to be evaluated (the
leaf node), the program plays a random
sequence of legal moves, playing for
both black and white. It plays to the end
of the game and then determines if the
result is a win (1) or a loss (0). Then it
discards all the information about that
move sequence except for the result,
which it uses to update the winning ratio
for the leaf node and the nodes that
came before it, back to the root of the
game tree.
SPECTRUM.IEEE.ORG

nORTh aMERICan

jUl 2014

http://SPECTRUM.IEEE.ORG

Table of Contents for the Digital Edition of IEEE Spectrum July, 2014