杏吧原创

MICHAEL REISS鈥檚 basement office in north-west London doesn鈥檛 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鈥檚 workshop. Coffins are stacked casually against one wall 鈥� the carpenter shares the space with an undertaker. And everything in Reiss鈥檚 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鈥檚 already a favourite in Japan for example, and millions will soon be able to play it on Sony鈥檚 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鈥檚 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?

The problem is that, as yet, there isn鈥檛 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鈥檚 gone into developing them over the past three decades. 鈥淥f 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鈥檚 pieces and they are 鈥渃aptured鈥� 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鈥檚 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鈥檚 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 鈥渨hat 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鈥檛 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鈥檚 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鈥檛 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 鈥渋nstinctive鈥� 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. 鈥淧rofessionals 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鈥檚 difficult for computers. The patterns that humans recognise are somehow much more than just arrangements of stones and empty spaces. It鈥檚 like the problem of face recognition. A child can look at a photograph of a group of people and pick out its mother鈥檚 face, but software designed to do the same often struggles even to determine which parts of the picture represent faces. We don鈥檛 know how to design efficient algorithms that get anywhere near mimicking the human brain鈥檚 ability to process visual information. 鈥淕o 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鈥檚 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鈥檚 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鈥檚 chances of winning. 鈥淔rom 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鈥檚 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. 鈥淎I is developing, step by step, from low-complexity applications up to high-complexity, real-world applications,鈥� Bouzy says. 鈥淭he 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鈥檚 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. 鈥淭he 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鈥檚 computers, Schaeffer suggests. 鈥淚t illustrates that there are two architectures for intelligence,鈥� he says. Chess plays towards the strength of the computer鈥檚 architecture and the weakness of the brain鈥檚. Go is just the reverse. So we might find that there鈥檚 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鈥檛 be for lack of trying. The worldwide Go community is growing steadily, with about 200 programmers currently involved. And there鈥檚 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 鈥淓ternity鈥� puzzle, is now planning to write a Go-playing program. As yet, he admits, he doesn鈥檛 know how he鈥檚 going to do it.

Reiss, meanwhile, is beavering away on the next generation of his program, but he鈥檚 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鈥檚 willing to help the cause. In fact, he鈥檚 quite disappointed no one in the scientific community has yet approached him for help to develop Go programming. 鈥淵ou see all these things saying Go is a great test bed for artificial intelligence, it鈥檚 going to help science progress and so on,鈥� he says. 鈥淗ere I am, I鈥檝e won a whole bunch of these competitions, and I鈥檓 waiting for the phone to ring, for Bill Gates or IBM to ask for some tips on AI programming. But it hasn鈥檛 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.