Teaching Computers the Game of go

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

John S. Rogers Science Research Program

In 2003, Amanda Venghaus and Heather Cook were 2 of 37 Lewis & Clark students engaged in the John S. Rogers Science Research Program, which promotes collaborative research in the mathematical and natural sciences by providing the framework and financing for more than a dozen student-faculty projects each summer.

The program, which began in 1999 after a multiyear pilot grant from the M.J. Murdock Charitable Trust, gives science majors a taste of real-world scientific investigation and helps them acquire skills they need to further their education and pursue a career in the sciences.

Faculty members lead research teams of one to three students who work together, full time, for 10 weeks in the summer. The students are selected through a competitive application process (about 60 percent of applicants are selected) and matched to a project based on their interests. To hone their writing and speaking skills, students are required to give a half-hour lunchtime talk and present a poster about their project.

“Rogers fellows are treated as fledgling scientists who have a responsibility to communicate the purpose and results of their work to a general audience,” says Michael Broide, associate professor of physics and director of the program. “And when they go to graduate school,” he adds, “they hit the ground running.”