Designing The Path of Go

What's your favourite loading bar? One of PopCap's, perhaps? You know, the ones with those cute little jokes. Or how about that one that popped up way back in the first 3D Indiana Jones game - the one that riffed, wittily, on the movies' map sequences?

I've got a new favourite. OK, it's more of a thinking bar than a loading bar. It's the little gauge that pops up in Microsoft's downloadable game The Path of Go whenever your AI opponent is selecting their next move.

It's not particularly pretty and it's not accompanied by clever jokes or transmedia references. It doesn't even go "ker-ching" when it's finished, which is just courtesy, really. I love it, though, because of what's going on behind its quiet façade.

Let's go back a bit. Actually, let's go back more than just a bit.

Go is a very old board game. It's been around for about 2500 years, meaning that it's older than the Great Wall of China, John the Baptist and certain parts of Cher. It's been back in fashion in Europe for the last decade or so. In the unlikely event you've never heard of the game, you've almost certainly have seen a wise old man or a pretentious British villain playing it in an upmarket action movie.

Clichéd as it may sound, but Go is a deceptively simple game. It's played on a board covered with a 19x19 grid – although there are, as we'll see, variations.

Two players take turns to place black or white stones at the intersection points of the horizontal and vertical lines.The overall aim is to control more of the territory on the board than your opponent. It's easier to play than it is to describe, but here's the interesting thing: that's not true if you're a computer.

Computers aren't very good at Go. Not historically, anyway, which brings us to The Path of Go – a fairly wonderful XBLA version of the game that's just become available on Marketplace.

Dr. Thore Graepel is one of the members of the small team behind the title. A senior researcher at Microsoft Research Cambridge, he's also the co-creator of the Xbox's TrueSkill ranking system.

On top of that, Graepel is a lifetime Go fan with over ten years' research experience of computer versions. All of which makes him the perfect person to explain the difficulties inherent in creating a satisfying programme based on the ancient game.

"The problems computers have with Go is best explained if you first understand how chess programmes work," he begins.

"Think of the structure of the game as a tree: you have a starting position, and then lines emerge from that which are all the possible moves you can make, and then they lead to new positions, with new possible moves. At the bottom of the game tree, the game is over and somebody's won.

"The way computer programs work is by evaluating the positions within that tree, and making moves based on that.

"So in Chess, you evaluate your position by looking at how many pieces each player has left, and how safe the king is, for example. From that, you can work out who's winning. The computer can then use that knowledge to work out which decisions to make for the next move."

This is strategy works brilliantly for Chess. But when it comes to Go, says Graepel, things are a little more tricky.

"The first thing is that in Go, there are vastly more moves you can make at any time than in chess," he sighs. "At the start of Chess there's 20 possible moves for White, for example, and throughout the game it tends to hover at about 20 or 30 moves.

"But in Go, from the first move, there are 361 possible moves. As you play on, they become less, but there's still generally around 200 moves for the computer or the player to consider.

"Alongside that the game tree is incredibly deep, which means that the games last for a long time. Go may last 200 moves whereas Chess may last 30 or 40. So the tree's not only wider in terms of the possible moves, it's also deeper."