news
Science | DOI: 10.1145/1978542.1978548
Kirk L. Kroeker
a new Benchmark for
artificial intelligence
Computers are unable to defeat the world’s best Go players,
but that may change with the application of a new strategy
that promises to revolutionize artificial intelligence.
In 1997, when IBM’s Deep Blue beat world champion chess player Garry Kasparov in a five- game match, the media her- alded the beginning of a new
era in artificial intelligence. While the
event undeniably marked a noteworthy
milestone in the history of computers, and has served as an enduringly
fresh metaphor for the possibilities of
technology, what became clear in the
years following the event is that many
classical programming strategies for
AI do not work well when applied to
more complex applications. One such
application that has emerged as a new
benchmark for those conducting research in AI is the board game Go.
Images courtesy of martIN müller, uNIVersIty of alberta
Go has proved to be extremely difficult for computers to master. To date,
no computer has beaten a professional Go player on the 19× 19 board in an
even match. On the surface, Go might
appear to be much simpler than chess,
with players alternating placement
of black and white pieces on a square
board to capture more territory than
their opponent by game’s end. But
the simplicity of Go’s rules are deceiving. From a computer’s perspective,
Go is much more complex than chess.
Go boards showing a sample of how the fuego software calculates board positions using
monte Carlo tree search. the size of the black or white square on each point indicates
the percentage of how often that point belongs to each player at the end of a round of
simulated moves.
Instead of dozens of branching movement combinations to evaluate as in
chess, the branching search trees for
Go may consist of hundreds of options for each move. For the first two
Go moves alone, for example, more
than 100,000 lines of play are possible,
making options for each player’s turn
highly open-ended.
The approach that has proved in re-
cent years to be the most likely path to
victory for computers in Go is a meth-
od called Monte Carlo Tree Search, or
MCTS. Only a few years ago, computers
couldn’t compete well even with ama-
teur Go players, but the use of MCTS
has resulted in software that can play
near the level of the best professional
players on the 9×
9 Go board, and can
even provide a decent game for sea-
soned players on the 19×
19 board. The
demonstrated strength of MCTS ap-
plied to Go has drawn attention from
many areas of computer science, with
