IEEE Spectrum October, 2007 - 42

all the way up to the World Champion level-
about 2900 on the Chess Federation's scale. In
the end, this conjecture proved to be partly
true. That is, the program did continue to play
better as search depth increased, but additional gains in rating could also be achieved
by improving the evaluation function and the
selectivity of its search.

DeaD or alive?
to play any board game well you have
to assess the situation on the board
astutely, over and over again. For go,
doing this involves determining whether
a group of connected, like-colored
stones (yours or your opponent's) is
"alive" or "dead." Stones that cannot
be captured are alive; spaces that are
surrounded by living groups of the first
side that cannot sustain living groups of
the second side belong to the first side.
the game ends when both sides agree
on the final disposition of territory.
the challenge of go comes from the
fact that analyzing whether a group
of like-colored stones is likely to live
or die can be a hugely tricky affair. In
the figure below, the black stones are

group is alive or dead the program must
search many moves ahead. In the figure
below, if black places a stone on C, then

D
go is played on a board crisscrossed by
19 vertical and 19 horizontal lines whose
361 points of intersection constitute the playing field. The object is to conquer those intersection points.
A player makes a move by placing a lozengeC
shaped "stone" on an intersection, then the
other player counters, and the two alternate moves. Players capture enemy stones
by surrounding them, that is, by removing
the black stones will live, but not uncontheir "liberties," which consist of either the
ditionally. that is, black may have to make
vacant points adjacent to a stone itself or to
additional moves to keep the stones alive
friendly stones to which it is itself connected
if white plays nearby. For instance, if
(see illustration, "The Goal of Go"). When no
white plays on any of the points marked
more moves are possible, the players count up
in red, then black will have to respond
the intersection points they control, and the
appropriately-and immediately-to keep
player with the most points wins.
the black group alive.
A
All the leading Go programmers today belitConsider the black stone labeled D.
tle brute force. In this they resemble the comIf the nearby green spaces are occupied
puter chess experts of 40 years ago. Selective
by white and black doesn't react right
B
search dominated thinking on computer chess
away, then white can kill black by playfrom the late 1940s to the late 1970s, and that
ing on the space to the right of stone D.
mind-set prevented any program from advancIf black captures the new stone, then
ing beyond the level of a Class C player.
white plays on the space above stone D
Go does, however, present two real probunconditionally alive as they have
and destroys the eye. If black connects
lems, both having to do with the amount of
two "eyes," indicated by A and B. the
by playing on the space above stone D,
searching the program must perform.
liberties A and B cannot be occupied
then white captures the four newly conThe first problem is the tree of analysis.
by white (for a white stone placed in
nected stones, killing the entire group.
Because Go offers more possibilities at every
either spot would itself be dead), and
A program would have to follow these
turn, the tree is far bigger for Go than for chess.
therefore black stones cannot be capbranching possibilities to see whether the
At the start of the game, the first player can place
tured no matter what.
black stones are alive or dead, a far more
a stone on any one of 361 positions, the second
however, the situation is usually more arduous job than simply counting up men
player has 360 choices, and so on. A typical game
complicated, and to judge whether a
and positional features, as in chess. -F.H.
lasts about 200 moves, so it averages at least
200 move choices per turn-nearly 10 times as
many as in the average chess position.
alpha-beta pruning, and it works by curtailing the examination of a
The second problem is the evaluation of the end positions. move the moment it becomes clear that another move must be betIn Go you can't just count up stones, because you have to know ter. Let's say the program is comparing move A with move B, and
which stones are worth counting. Conquered territory is defined as it already knows that A leads to an advantage. If it finds, early on,
board space occupied or surrounded by "living" stones-stones the that move B allows the other side to obtain a draw at the very least,
opponent cannot capture by removing their liberties. Before you then the program can cut off its analysis, saving a lot of time.
can count a stone as live, you have to calculate several moves ahead
Alpha-beta pruning reduces the effective branching factor
just to satisfy yourself that it is really there in the first place.
to about the square root of the number of move choices. For
Put these two problems together and you get a computational example, to look ahead 12 plies in pure brute-force mode, you
problem that at first glance seems intractable. But there are would need to search only about 4 billion positions, or 4 x 10 9,
ways to engineer around it.
instead of 3812-or 1019-positions.
A newer way to cut back the overgrowth-null-move pruning-
let's start with the problem of the exploding tree of analysis. was not implemented in Deep Blue, even though one of its invenIf we assume that the program must consider every possible tors, Murray Campbell, was a key member of the Deep Blue team.
continuation that could arise 12 plies into the future, as Deep The algorithm performs a kind of thought experiment, asking how
Blue did in chess, you might expect to have to search a million the position would look if you were to give up the right to move
times as fast. But we don't really need to pay that high a price, for one turn, thus allowing your opponent to make two moves in
because there are ways to prune the tree of analysis.
a row. If after that enormous sacrifice you still have a good posiOne old standby, implemented in all chess programs, is called tion after a relatively shallow search, then the algorithm can stop
www.spectrum.ieee.org

October 2007 | IEEE Spectrum | NA 53

http://www.spectrum.ieee.org

Table of Contents for the Digital Edition of IEEE Spectrum October, 2007