Sun, Aug 06, 2006 - Page 9 News List

An old Oriental game of strategy still confounds programmers

By Charles Arthur  /  THE GUARDIAN , LONDON

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 center in Cambridge, England, 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 gameplaying territory?

While simple to explain and to learn, Go has subtle gradations of ability. There are hundreds of professionals, mainly in Japan, Korea and China, 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.

Go rankings: kyu to dan

40 kyu: Child beginner

25 kyu: Adult learner

15 kyu: Top-level social player

10 kyu: Weak club player

4-5 kyu: Average club player

1 kyu/1 dan: Transition to expert

2 dan: Competent, well-informed amateur

3-4 dan: Good amateur

5-6 dan: Strong amateur (top 100 in Europe, top 10,000 in South Korea)

7 dan: Amateur good enough to be professional 1 dan; can play world's best without embarrassment

Pro 4 dan: can make a living at Go in East Asia (akin to golf tour professional)

Pro 9 dan: among top 100 in world; can win pro tournaments

Source: The Guardian, Charles Matthews


Even the best Go-playing program is presently only ranked at about 9 kyu (see sidebar).

Why are computers so bad at Go? First, 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.

"It is very difficult to produce an efficient `static evaluation' function to compute the value of board positions in Go for a particular player," Stern says.

"The reason is that the stones on the Go board influence each other's value in complex ways. The value of a particular stone to a player is derived from its relationships with the surrounding stones, not from itself," he says.

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 showing up.

This story has been viewed 5437 times.
TOP top