Saturday, February 14, 2009
Tracking the Mathematics of Go
From ScienceNews.org Coupons help evaluate game of Go Game theory math might clarify complexity of chess By Laura Sanders Web edition : 8:03 pm (Image: Chinese Ladies playing Go [Weiqi]) CHICAGO—A new twist on the ancient board game Go may clarify the complicated mathematics behind games like chess, suggests research from the mathematical field known as combinatorial game theory. Using “coupons” to quantify the value of moves in the game allowed researchers to describe the math behind the game more precisely, mathematician Elwyn Berlekamp of the University of California, Berkeley reported February 14 at the annual meeting of the American Association for the Advancement of Science. Go is a popular game in Asia thought to originate 3,000 to 4,000 years ago. Using a board with 19 squares on each side, players put stones on the grid in an attempt to surround and capture an opponent’s stones. Although the rules of Go are simple, the strategy of the game is very complex. A chess board has more than 1040 legal configurations that the pieces can be in at one time. The Go board has about 10171. The complicated mathematical fallout of all those possibilities prevents computer programs from seriously challenging top-tier Go players. “For every move, you have to look at its impact on the whole board,” says Berlekamp. Without a significant handicap, no computer program has yet beaten a top-tier Go player, designated 9p. To understand the mathematical rules that govern Go, Berlekamp turned to some of the best Go players. He wanted to know why the players thought certain moves were good or bad, what Go players call bigger or smaller moves. But Berlekamp ran into a problem. “Go players don’t want to have mathematics discussions,” he says. “They want to play.” To get around this obstacle, Berlekamp created a version of Go called Coupon Go, in which players have the option of either putting a stone on the board or taking a coupon. The coupons, which have different point values, showed Berlekamp what the most valuable moves were. Using the resulting map of moves, Berlekamp developed a mathematical model to predict the most favorable moves near the end of a Go game, when move options are constrained. A large Go Coupon tournament among professional players is being organized to take place in China in 2009.