Enter the maze

Go, Go gadget: computers' biggest gaming challenge

a Go board

Computers have been outwitting humans for more than half a century. Since 1951 you’d have been hard pressed to beat a computer program at Nim (but you can still try), and even the world chess champion, Garry Kasparov, lost to a computer in 1997. In one game though, humans are still on top. That game is Go, an East Asian board game that’s been played for thousands of years. Its rules are much simpler than chess, but a game of Go can play out in many more ways. That’s what makes it such a headache for a computer to play.

Here’s the secret to outsmarting a human with a computer: don’t think like a human. When humans play chess or Go, they tend to analyse the board for patterns they’ve seen before. By plugging the problem into our brain’s tremendous talent for analysing and imagining things visually, a good player can feel the way the game is going. They see which parts of the board influence the others, and use the strategies they know to get the game going to their advantage. It’s a great way to play, but the problem is that computers would be terrible at it. They just don’t have much of a visual sense.

You vicious brute

a tree graph of branching moves

What computers are really good at, though, is crunching numbers. The way a computer beat Garry Kasparov at chess was by analysing every possible move it could make, followed by every countermove and so on, until it had examined every possible situation for twelve moves ahead. Then the computer would make the move that would get it to the best future. It’s not a particularly elegant strategy – in fact, the approach is called ‘brute force’, which should give you some idea of how smart it is. Brute force number crunching does play to a computer’s strengths, though, which is how Kasparov was defeated by a blue and black tower of microprocessors.

Computers still haven’t mastered Go because it’s a game where simple brute force just doesn’t work. It’s much too complicated to be wrapped up in a simulation of twelve moves in the future. For example, if you capture a piece in chess, it’s gone forever. In Go, one piece can change allegiances back and forth until the end of the game. In fact, there are many, many more ways for a game of Go to end than there are particles in the universe. And there are even more ways of getting to each possible ending. When humans play Go, our knack for patterns and visual thought helps us discard a huge number of unlikely moves so we don’t waste time considering them, but a computer using only brute force can’t do that.

Playing games with nuclear maths

Fortunately for the electronic competitors, some computer scientists at the University of California at Santa Cruz have made a Go program whose brute force is a little less brutish. Using maths previously confined to figuring out the random jiggling of atoms in a nuclear explosion, their program simulates entire games without thinking about which moves are best to make. What’s the point in that? The secret is that the computer keeps track of the statistics from all its random games too. After it’s played a few million games, those statistics give the computer a better sense of what might happen in a game. Then the computer can discard all the unlikely moves it would have wasted time analysing. It’s the best approximation we’ve got so far of what humans do when they look at a Go board. The Go-playing computer is starting to do what humans do, even if it’s not the same way we do it.

That doesn’t mean that computers are ready to start beating humanity’s best champions of Go, though. At the moment computers have only won two games against Go professionals. But the scientists reckon that in a couple of decades’ time, Go will be one more game at which humans used to be unbeatable.