Sun, Aug 06, 2006 - Page 9 News List

An old Oriental game of strategy still confounds programmers

By Charles Arthur  /  THE GUARDIAN , LONDON

EASIER FOR HUMANS

David Fotland -- author of the Go-playing program Many Faces of Go, which is still ranked as 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 told the Intelligent Go Web site (www.intelligentgo.org).

It's the visual element of the game that nobody can quite put into code. Go has a visual element; a high-good level player will reject a potential move because its "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." More simply, "urgent" moves are those that will bolster the player's position; good players consistently choose the most urgent moves.

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 Web site.

"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; 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," he says. "Moore's Law holds that computing power doubles every 18 months, so that means we might have a computer that could play Go using these techniques sometime in the 22nd century."

Now, though, 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, adding them to a huge database so the program can pick the best available in any given situation.

ALL MOVES

Thore Grapel, of the Speech and Intelligent Systems research group at Microsoft Cambridge, who is helping coordinate the work, says that both the winner's and loser's moves are included.

"From the point of view of the computer, these pros are so much better that any variation in their skills is minimal, compared [with] the computer's playing strength," Grapel says.

In other words, it's better to play like a losing pro than the best computer.

And how well does it perform? Grapel, who is an amateur shodan (the Go equivalent of a black belt), says that the program plays to about the 10 kyu 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.

This story has been viewed 5418 times.
TOP top