The ancient Chinese game of Go presents an ideal challenge for computer scientists studying artificial intelligence.

The 4,000-year-old board game with "simple, elegant rules and complex consequences" has captivated and confounded researchers who’ve tried to construct a program that can compete against the world’s top human players, says Peter Drake, assistant professor of computer science.

Nevertheless, Drake is drawn to the problem—partly because its solution is likely to aid the quest to make computers think like people. "Go is considered one of the grand problems of artificial intelligence," Drake explains. "It’s a problem that seems like it would be easy to crack, but it’s not."

In fall 2002, the challenge’s broader implications won over Amanda Venghaus ’04 and Heather Cook ’03, students in Drake’s artificial intelligence class who answered his call for research volunteers.

"I thought: Research? Game? Sounds like a good thing," says Venghaus. "I’m interested in the idea of trying to get computers to think more like the brain." For her part, Cook became intrigued by "the unforeseen complexities of the game," both on the board and on the computer screen in terms of programming.

Last summer, the duo clocked ten 40-hour weeks working with Drake as part of the John S. Rogers Science Research Program (see related article on next page). They learned a programming language, Java, and schooled themselves in neural networks, a promising field that has spawned applications in economic forecasting, industrial-process control, and credit-card fraud detection. But they, too, were baffled by Go’s resistance to computer mastery.

The game involves two players who alternate placing black and white stones on the intersections of a 19-by-19-inch grid. The object is to capture the most territory by placing stones in such a way that they cannot be surrounded by your opponent.

Sounds simple enough. But the strategy is profoundly complex.

Programs that play games, such as chess, generally work by considering sequences of possible moves—what can I do, how can my opponent respond, and so on. In both chess and Go, considering all possible moves until the end of the game is impossible: It would take even the fastest computer processor longer than the expected lifetime of the universe. Instead, programs are relegated to looking a few moves ahead and estimating the values of the resulting positions. This approach works in computer chess, but it fails in computer Go. There are too many moves to consider at every turn, and determining the value of a position is very difficult because large groups of doomed stones may remain on the board for a long time.

Skilled human players can rapidly determine which moves are worth considering and which stones are likely to survive. But translating this knowledge into a computer program has so far thwarted researchers. The game’s subtleties, Venghaus says, "are lost to computers."

The challenge that Drake, Venghaus, and Cook faced was to develop a self-teaching program that would eventually grasp those subtleties. To do this, they built computer systems called artificial neural networks. These systems, rather than processing information sequentially, try to emulate the human brain’s complex web of neurons and synapses by processing lots of information simultaneously.

Drake and his students fed into their neural network several thousand recorded Go games, played by experts, in an attempt to teach the program to recognize good moves and bad ones. "You train a neural network by saying, ‘If you see this, do that,’ and after a while it can generalize," Drake explains.

Their results were illuminating, but not ultimately successful. The trio found that the network’s best training regimen was to first watch 3,200 recorded games, then play against itself 3,000 times. But even after that workout, the program could triumph only over absolute beginners. "Computers are good at thinking in a precise, logical way," Drake explains. "Our brains are good at thinking about things in a vague, intuitional sort of way." The successful Go program, he has come to realize, must reflect both types of cognition.

Cook says the summerlong research taught her a valuable lesson: Things do not work always work out as planned. "You just have to step back—sometimes to the beginning—and try a new approach," says Cook, now a Peace Corps volunteer in South Africa. "This, luckily for me, applies to many areas of life." Eventually, Cook may become a computer-science teacher.

Venghaus, meanwhile, has continued her research by taking Drake’s neural networks class and a psychology course in cognitive science. She wants to pursue graduate work in cognitive science, a blend of artificial intelligence and psychology.

Their career intentions leave open the possibility that one of them may yet accomplish what eluded them last summer: to author the first computer program that plays Go better than any human alive.

—by Dan Sadowsky