MICHAEL REISS’s basement office in north-west London doesn’t look like a launch pad for world-beating technology. To reach it, you negotiate a muddy alley strewn with cardboard boxes and then walk through a carpenter’s workshop. Coffins are stacked casually against one wall – the carpenter shares the space with an undertaker. And everything in Reiss’s office is covered in a fine layer of sawdust, even his three computers.
Yet beneath their dirty cases, these machines are spinning pure gold. Reiss has spent more than a decade developing a computer program that plays the ancient Asian game of Go. His carefully guarded software, called Go4++, is turning out to be a commercial winner in the Far East. It’s already a favourite in Japan for example, and millions will soon be able to play it on Sony’s PlayStation 2. And now the market in China – potentially more than a billion Go-obsessed people – is also opening up. For Reiss, business is booming.
But it’s not all fun and games. Go-playing programs may be just what artificial intelligence researchers have been looking for. Teach a computer to play Go well, and you could be on the way to mimicking the workings of the human mind. Computer Go could also lead to serious, everyday applications. Programming techniques originally developed to enhance software that plays games such as chess and draughts are already used in fields such as DNA sequencing, traffic planning, elevator control and task-planning for spacecraft. Who knows what a top-flight Go-playing computer could do for us?
Advertisement
The problem is that, as yet, there isn’t one. Chess, draughts and Othello programs can already beat human world champions. But even the best Go programs are not much better than rank amateurs, despite the huge effort that’s gone into developing them over the past three decades. “Of all games of skill, Go is only second to chess in terms of research and programming efforts spent,” says Martin Müller, an artificial intelligence and Go researcher at the University of Alberta in Edmonton. And yet the programmers are getting nowhere fast.
What makes this particularly galling is that Go seems so simple. Two players take turns to put counters on a board marked with a grid of lines. Surround your opponent’s pieces and they are “captured” and removed. The end comes when no more counters can be played: whoever dominates the board wins.
Admittedly there are a few other rules, but it’s certainly the kind of game you can teach a child. Yet while chess is a benchmark for the power of computers, Go seems only to highlight their weakness.
It’s fairly easy to build powerful chess programs because they rely on little more than brute force. Before each move, the program usually runs a series of “what if?” subroutines. Each one simply searches along a different branch of possible moves, and when it reaches a certain point – perhaps after 20 moves – it evaluates the success of this branch using straightforward criteria. Each chess piece is assigned a value depending on its power and importance and the program simply adds up the values of its own pieces and subtracts those of its opponent. This way it can tell immediately whether a particular strategy will pay off.
But a Go program can’t do that. For a start, there are many, many more possible moves to consider. There are 361 places you can put a piece on a Go board, compared to a mere 64 on a chessboard. The Go-playing equivalent of IBM’s computer chess champion Deep Blue would need to be unimaginably powerful to handle every possible permutation of moves. Worse, no one knows what criteria a Go program should use to judge whether a series of moves is good or bad. Simply adding up gains and losses doesn’t seem to be a good pointer to which player will eventually triumph.
And yet, somehow, humans can do it. So Reiss and other Go programmers want to mimic the way people play the game. In particular, good Go-playing seems to rely on “instinctive” responses to patterns in the arrangement of the counters. Subtle differences in these patterns can have a major effect on the tactics employed by an experienced player. “Professionals know by intuition whether a group [of counters] can be captured or not,” Müller says.
This kind of intuitive pattern recognition seems to be relatively easy for us, but it’s difficult for computers. The patterns that humans recognise are somehow much more than just arrangements of stones and empty spaces. It’s like the problem of face recognition. A child can look at a photograph of a group of people and pick out its mother’s face, but software designed to do the same often struggles even to determine which parts of the picture represent faces. We don’t know how to design efficient algorithms that get anywhere near mimicking the human brain’s ability to process visual information. “Go has many visual and intuitive components that seem to suit humans. And they are very hard to program,” Müller says.
What is clear is that many of the best players gain their strength by intensive studies of past professional games. And that’s why Reiss has equipped his program with a library of knowledge: a database of over 7000 patterns of counters. Attached to each one are instructions indicating what moves to play – and what moves to avoid – if such a pattern appears on the board. After each move, Reiss’s software looks at the current arrangement of counters, and if it spots matching patterns it finds an appropriate move more quickly than if there were no recognisable patterns. The routine is assisted by a statistical analysis of 300,000 patterns – logged with the help of a top Korean Go player – that have appeared in professional Go matches. This helps pin down what kind of moves are likely to improve a player’s chances of winning. “From these patterns and these statistics, it can get a guide to where to play,” Reiss says.
This approach has proved successful, but adding libraries of pattern data to a program can actually backfire: sometimes a particular arrangement of patterns on the board means that the best solution relies on making entirely new and unconventional moves. While human players can often find these solutions, Go programs that rely on libraries find it much harder to adapt. And it’s the challenge of programming this kind of response that is getting researchers so excited.
Artificial intelligence researchers Bruno Bouzy of the René Descartes University and Tristan Cazenave of the University of Paris VIII recently issued a call for their colleagues to look on Go as a fertile research area (Artificial Intelligence, vol 132, p 39). They believe that AI will have a huge impact on the way the world works, and that Go should be involved in its development. “AI is developing, step by step, from low-complexity applications up to high-complexity, real-world applications,” Bouzy says. “The complexity of Go lies between these two sets of applications.” In this respect, he says, developing software that can play a mean game of Go will provide an appropriate benchmark for progress in AI – just as chess did for computing power a few decades ago.
Jonathan Schaeffer, a colleague of Müller’s at the University of Alberta, believes that computer Go is certainly an important field for the future of science. Developing subtle ways to collate and manipulate information – both visual and numerical – could prove enormously useful in the knowledge-rich 21st century.
All systems go
Take the vast amounts of scientific data pouring forth from everything from satellite imagery and climate monitoring to huge studies of genetic information. Finding ways to gather and exploit them, automating intuitive leaps and reasonable responses to the unexpected, could lead to huge leaps in our understanding of the world. “The scientific community can watch the progress of computer Go to see where it goes, and then adopt the technology,” Schaeffer says.
But this may yet turn out to be impossible without a technological revolution. The difficulty of programming Go could be telling us something fundamental about the limitations of today’s computers, Schaeffer suggests. “It illustrates that there are two architectures for intelligence,” he says. Chess plays towards the strength of the computer’s architecture and the weakness of the brain’s. Go is just the reverse. So we might find that there’s such a fundamental difference between the way the human brain and computers work that only a completely different kind of machine will turn out to be a winner – perhaps more advanced neural networks that are capable of learning as they play.
If the quest for good Go-playing software does fail, it won’t be for lack of trying. The worldwide Go community is growing steadily, with about 200 programmers currently involved. And there’s certainly been no shortage of incentives. For two decades, a million-dollar prize was available to anyone who could use a computer to beat a professional player. Sadly, no one even came close before the competition expired in 2000.
But there are still annual computer Go tournaments, and cash prizes of tens of thousands of dollars mean that those who can afford it, like Reiss, are pursuing computer Go full-time. Anders Kierulf, for example, quit a high-powered programming job at Microsoft to become a full-time Go programmer. He hopes to catch up with the top programs in about three years’ time. And Alex Selby, a British mathematician who recently won himself a million pounds by solving the mathematical “Eternity” puzzle, is now planning to write a Go-playing program. As yet, he admits, he doesn’t know how he’s going to do it.
Reiss, meanwhile, is beavering away on the next generation of his program, but he’s not expecting a big breakthrough any time soon. Whatever the input from high-flyers, he believes the future of Go programming will be like its past: a slow and painful progression. And despite his financial interest in remaining the best, he’s willing to help the cause. In fact, he’s quite disappointed no one in the scientific community has yet approached him for help to develop Go programming. “You see all these things saying Go is a great test bed for artificial intelligence, it’s going to help science progress and so on,” he says. “Here I am, I’ve won a whole bunch of these competitions, and I’m waiting for the phone to ring, for Bill Gates or IBM to ask for some tips on AI programming. But it hasn’t ever happened.”
The key to our technological future could be sitting, waiting, under a thin coating of sawdust in a grubby London basement. Go on Bill, make that call.
- For more information on Go, see:
