Advertising

Monday, August 28, 2006 - Page updated at 12:00 AM

E-mail article     Print

What's black, white and can stump computers?

Newhouse News Service

Go facts


Go originated in China more than 2,000 years ago and is considered the oldest board game in play today.

The objective of the two-player game is to control the most territory on the board.

A typical game on a 19-by-19 grid lasts for 200 to 250 moves.

The number of possible games is so great it has been said that no game has ever been played twice. This is one reason it has been so difficult to program computers to play Go.

The game reportedly has been played by such luminaries as Albert Einstein, Bill Gates and Rod Stewart.

In 1996, U.S. astronaut Daniel Barry was the first person to play Go in space.

Nobel Prize-winning author Yasunari Kawabata published the novel "The Master of Go" in 1951, based on an epic game that took place over several months.

PORTLAND — He told his wife he would be home around midnight. But as the sun gleamed through the upper windows of the math department at Lewis & Clark College, Peter Drake was still in his office watching a game being played on a small grid on his computer screen. It was 9:30 in the morning.

The gangly professor finally stood up and went downstairs where two of his students had just started working in the computer lab. "We're beating Jacqueline," Drake announced, explaining he had spent the past 12 hours reworking a key algorithm in their Go-playing computer program, Orego.

For the past four years, Drake and his students have tried nearly every novel approach out there: neural networks, cellular automata and genetic algorithms. Their victory with this ingenious algorithm marked a turning point for Orego and was the latest application of a promising new strategy in artificial intelligence.

"I'm going to take a nap now," Drake said.

Go is a board game that originated in China more than 2,000 years ago. It still has a huge following in Asia, where children play it in school and expert players receive salaries rivaling those of sports stars.

Stone challenge

Players take turns laying stones in a struggle to capture the most territory. There are no pawns or rooks or knights in the game, just black stones versus white stones. It is one of the simplest games to learn and the most difficult to master.

The best chess programs can beat the best chess players, but the best Go program would hardly impress an amateur. Drake and his students share their programming secrets with users of an international Computer Go mailing list. Then their programs duke it out on the Computer Go Ladder.

Orego had not beat a human being named Jacqueline, but another program called JacquelineGo.

A key problem for computers is determining which side is actually winning. "A skilled human player could figure it out at a glance, but a computer can't," Drake said. "That seems to have something to do with our ability to do pattern matching. Go combines the intuitive aspect — when you say, 'Ahh, this seems like a good move' — with the more rigorous logical reading that is a bigger part of chess."

In chess, game play revolves around the capture of a single piece, the king, whereas Go involves domination of the entire board. Elwyn Berlekamp, a mathematician who studies Go at the University of California, Berkeley, said, "My own view, which is pretty radical, is that it's not Go that's exceptional, it's chess and checkers."

The challenges of Go are more representative of the real-world problems humans face: The pieces may be black and white, but the solutions never are.

Drake said solving this class of problems will help in designing electronic circuits, controlling flows in a sewage plant, or building cars that can drive themselves. "It's considered an open question in artificial intelligence," he added.

The night that Orego beat JacquelineGo, Drake, 35, was using a new strategy pioneered by Remi Coulom at Université Charles de Gaulle in Lille, France.

Drake said: "Rather than trying to come up with some special rules that are specific to Go and require lots of time and an expert player to come up with, you just say, 'Well, I'm at this position, and I will play the rest of this game out randomly a hundred times or a thousand times, and if black usually wins, then this is a good position for black.' "

Mathematicians call this a Monte Carlo method because it resembles games of chance found in that city's casinos. One pull on a slot machine may not tell you much. But if you repeat the experiment a thousand times, you'll be able to estimate the probability of victory on your next pull.

Orego uses this method to compare probabilities of victory among possible board moves. Because the number of possible games is astronomical, Orego must concentrate its searches on the most likely games. For each move in the game, the most likely move is the best move for each player.

After beating JacquelineGo on the Computer Go Ladder, Orego went on to beat Godot, Gogo and GoLife, climbing four rungs in less than a week. With 12 programs ahead, Orego still had a long way to go.

"Some of the strongest programs are written by pretty good Go players, who are also good programmers and have been working on them for many years and carefully tweaking all the expert knowledge that's built into the program," Drake said.

By contrast, his program lacks nearly all that expert knowledge. Mathematician Berlekamp was surprised to hear the Monte Carlo method was working so well, and even Drake admitted, "You wouldn't expect it to work for complicated problems in general."

Earlier this month, Orego faced Viking, written by Swedish programmer Magnus Persson. For the first move, Orego played in the center — one of its only pieces of "expert knowledge." The next couple of moves were decent, then Orego made a couple of blunders. As Orego struggled, Viking was sketching out its own territory. Viking triumphed.

In an instant message to Persson, Drake wrote: "I find it somewhat satisfying that the first program able to stop Orego was another Monte Carlo program. It seems a very promising line of research."

Copyright © 2006 The Seattle Times Company

advertising


Get home delivery today!

Advertising

Advertising