IEEE Spectrum July, 2014 - 53

probability of leading to a win. But this is usually too risky.
For example, a move with 7 wins out of 10 trials may have
the highest odds of winning (70 percent), but because this
number comes from only 10 trials, the uncertainty is high.
A move with 65,000 wins out of 100,000 trials (65 percent)
is a safer bet. This suggests a different strategy: Choose the
move with the largest number of wins. And this is indeed the
standard approach.

to refine our programs, enhancing the power of randomness
with a dash of knowledge, we believe our AIs will eventually
perform as well as Go's human grand masters.
in The early days of developing chess-playing programs,

researchers tried to get computers to play chess the way people
do. Very quickly, it became clear that chess AIs couldn't efficiently
learn and apply enough strategic knowledge to be successful.
Programmers then adopted a search-intensive approach that
required only enough knowledge to understand the rules and
since meThods based on mcTs replaced The TradiTional
to evaluate the strength of a given board configuration. MCTS
knowledge-based approaches, we have seen amazing improvetakes this one step further by questioning the need for making
ments in the playing strength of Go programs. On the 9-by-9
any such evaluations. It may seem paradoxical, but we're already
board, top programs are on a par with the best human playseeing the benefits of such intelligence-free artificial intelligence
ers. On the standard 19-by-19 board, a program called Crazy
in the game of Go-and that may be just the beginning.
Stone has convincingly defeated a top professional while playIn recent years, AI researchers have
ing with a handicap of only four stones,
120 plays as
been trying to develop a program that
indicating that the program
can learn to play any game well-Go, ticwell as a very strong amateur.
tac-toe, chess, whatever-given only the
The most basic Go-playing
100program
TOP HUMAN
rules of the game as input. historically,
using MCTS would employ only miniGRAND MASTER
all the strong game-playing programs
mal knowledge of the game-namely,
80
have been able to play only one specific
which moves are legal and who wins
MASTER
CHESS-PLAYING
game. They were "idiot savants" that
at the end of the game. This60produces
PROGRAM
could do one thing very well, but nothsurprisingly successful Go-playing
prog rams. But the latest research
ing else. If AI researchers can develop a
40
indicates that a little bit more knowlprogram
capable of more general learnAVERAGE CLUB PLAYER
edge can boost the performance of
ing, however, we might create a more
GO-PLAYING
20
PROGRAM
MCTS programs.
flexible kind of computer intelligence.
At the University of Alberta, we are
This would be a big step toward the real
0
1997
1967
2011
finding ways to include some gamegoal of artificial intelligence research:
specific knowledge to give the profashioning a general-purpose learner.
going For it: Chess-playing programs bested
The AI community has been able to
gram certain tendencies as it chooses
human grand masters more than a decade ago,
gauge progress in this area at the Genits random moves. For example, a probut Go-playing programs weren't contenders until
their coders embraced Monte Carlo tree search
gram can be biased so that its random
eral Game Playing (GGP) competition,
techniques in the late 2000s.
move sequences aren't really so ranheld at the annual conference of the
Association for the Advancement of Artidom. Instead, they often incorporate
moves that would naturally follow from the opponent's previous
ficial Intelligence. There, programs are given only the rules of a
move. Such obvious actions would include a move that would
game and then have to play it in a tournament. From the rules,
defend the program's stones from immediate capture, and a
a GGP program can usually infer the appropriate search algomove that would seize an immediate opportunity to capture
rithm to find suitable moves. But these programs quickly run
an opponent's stones.
into trouble as they try to learn the game-specific knowledge
The program can also be given some pieces of knowledge
that will allow them to make evaluations. One program might
that can be applied without requiring it to perform true evalutry to make deductions based on the rules of the game. Another
might learn by playing against itself and making inferences. Yet
ations of game positions. For example, a program may have a
neither strategy has proven effective. To date, there have been no
database of simple patterns of stones that can occur within a
truly successful approaches to machine learning in this sphere.
3-by-3 region of lines. After an opponent's move, the program
Instead, in recent tournaments virtually all the GGP prochecks the areas around that stone to see whether the resultant
configurations match any of the stored patterns. If it does find
grams have used a variation of MCTS to avoid the knowledgea match, it plays the next move associated with that pattern in
acquisition problem altogether. These programs still have a
its database. If it finds several matching patterns, it chooses
long way to go. But there may come a day soon when an AI will
among the associated next moves at random.
be able to conquer any game we set it to, without a bit of knowlWhen AI researchers first applied Monte Carlo methods to Go
edge to its name. If that day comes, we will raise a wry cheer for
around 2005, computer Go programs improved dramatically
the triumph of ignorance. n
and rapidly. Over the past few years, progress has been slower,
but the research community is still optimistic. If we continue
poSt your coMMentS at http://spectrum.ieee.org/go0714
SPECTRUM.IEEE.ORG

nORTh aMERICan

jUl 2014

http://spectrum.ieee.org/go0714 http://SPECTRUM.IEEE.ORG

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