When Garry Kasparov was beaten, to his furious humiliation, by
IBM's Deep Blue chess computer in 1997, it left human players
pondering their future. Draughts, Othello, Backgammon, Scrabble: by
the start of this century, each had been all but conquered by
machines.???
But don't worry. Almost a decade later, with Moore's Law still
at work, there is still a board game in which humans reign
supreme.
???
The game is Go, an oriental game of strategy.
???
It sounds superficially easy. The board is a 19 by 19 grid of
intersecting lines. The pieces (called "stones") are black or
white, and identical.
???
Once placed on the board, they do not move (unless surrounded and
captured) or change color. The object is to use one's stones to
surround as many blank intersections (called "territory") as
possible. And that's about it.
???
Even the lure of a US$1 million prize for the first program to beat
a human professional went uncollected after the deadline passed in
2000. No program has yet come close to meeting the challenge.
???
Now, however, there may be a new attack on this outpost of
humanity. At Microsoft's research centre in Cambridge, scientists
are taking a simpler approach to working out how to beat the best
humans. They're telling their program what the best humans did
against each other in thousands of games, providing a vast
repertoire of millions of moves.
???
Are computers about to invade another piece of our game playing
territory?
???
A board of possibilities
???
While simple to explain and to learn, Go has subtle gradations of
ability. There are hundreds of professionals, mainly in China,
Japan and South Korea.
???
Yet even the best computer version is only as good as an average
European club player, who is as far from being professional as the
average tennis club player is from playing at Wimbledon. Even the
best Go-playing program is presently only ranked about 9kyu. Why
are computers so bad at Go? Firstly, playing Go plunges a computer
into a sea of possibilities in which most drown. A chess board,
with 64 squares, is comparatively tiny: each turn offers about 30
possible legal moves. In Go, with 361 points, few moves are
illegal, offering more possibilities on average, about 200 per
turn. Thus the total number of possible moves in chess is between
1,060 and 1,070; in Go it is about 10,250.
???
Secondly, according to David Stern of the Cavendish Laboratory in
Cambridge, who is working on a doctorate on computer Go with the
team at Microsoft, it is very hard to determine, for each move,
what its effects will be. Although the stones do not move, their
presence affects the value and "strength" of the others; adjacent
stones of the same color form "groups" which are harder to
capture.
???
That's unlike chess, where it is comparatively easy to determine
the "static value" of all the pieces at any time, because there are
only 32 at most, where a Go board constantly fills with new
pieces.
???
"The value of a particular stone to a player is derived from its
relationships with the surrounding stones, not from itself," Stern
said.
???
The effect is that in Go there are many non-ideal moves at any
point. But because games last longer typically about 200 moves (100
stones placed by each side) rather than 70 (35 by both sides) in
chess it's harder to look far ahead enough to see a non-ideal
move's defects show up.
???
David Fotland author of the Go-playing programme "Many Faces of
Go," still ranked one of the strongest available reckons that for
humans, reading ahead is actually easier in Go than in chess.
???
"People are visual, and the board configuration and relationships
change less from move to move than they do in chess," he
said.
???
It's the visual element of the game that nobody can quite put into
code. A high-good level player will reject a potential move because
its "visual shape" that is, the position of a stone move being
considered in relation to the stones already there "looks bad."
They're not intuitively obvious. Equally, good players also talk of
stones and groups having "influence" on other parts of the board,
or being "heavy" or "light" or "overextended."
???
But computer chess games don't understand chess; they just got
better at crunching moves. Won't brute force do the job on Go, as
it did in other games? No, says Bob Myers, who runs the Intelligent
Go website. "A very rough estimate might be that the evaluation
function (for computer Go) is, at best, 100 times slower than
chess, and the branching factor is four times greater at each
play," he explained.
???
"Taken together, the performance requirements for a chess-like
approach to Go can be estimated as 1,027 times greater than that
for computer chess.
???
Stern and the Microsoft team are trying a different tack. Instead
of wondering how to get a computer to beat a human, they are
showing the computer how humans beat each other by creating a huge
database of moves and positions from professional games.
???
So far they have fed in around 180,000 games.
???
Speed advantage
???
Thore Grapel, who is an amateur shodan (the Go equivalent of a
black belt) and is helping coordinate the Microsoft sponsored
project, says that the new program plays to about 10kyu
level.
???
Improvement will rely on getting better at recognizing when groups
of stones are at risk of being surrounded and captured. But one
thing it does have over rival programs, and humans, is speed. "It's
fast about 10 milliseconds per move," Grapel says. Other programs
can take minutes to consider any board layout. However, Charles
Matthews, a 3-dan Go player also based in Cambridge, is
unpersuaded.
???
"If you can't beat your computer Go opponent, you are going to be
one of the rabbits at the local Go club," Matthews said. "But
further progress has been by rather small increments.
???
Grapel thinks there may be a deeper reason why computers remain bad
at Go, and humans good.
???
"I believe Go requires certain human characteristics visual
recognition, matching shapes and logical reasoning," Grapel
explained.
???
"You have to do spatial reasoning about which direction should you
play. It's all about predator and prey, hunting and chasing, and
territory. All these are very basic yet complex human
facilities."
???
The implication is that computers are bad at Go because they're
still bad at being human. Which might come as some relief.
???
In 2002, David Levy, one of the earliest drivers of computer chess,
wrote (in "Do not pass Go," October 24, 2002): "Perhaps Go will be
the final bastion in man's attempts to stave off his inevitable
intellectual defeat at the hands of the machine."
(China Daily August 12, 2006)
