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.
When people advance through the game, they’ll be able to play on 13x13 and 19x19 boards, and the AI still works.
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.
Avatar support is unusually charming in The Path of Go.
"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."
A tricky enough challenge, but that's only half the story. Remember how easy it is to evaluate who's winning in Chess? You can often do it with just a quick glance at the board – a very quick glance if I happen to be playing – but that doesn't work for Go.
"So the size aspect of Go is a problem," says Graepel, "but there's also this evaluation problem to take into account. The computer has to work out whose position is better in order to choose the right moves to make next, and with no difference between knights and pawns, this gets very hard.
"Each of the Go stones is the same: they only take their value from their position on the board and how they inter-relate to all the other stones on the board. That means it's almost impossible to look at the board the same way and come up with the same kind of evaluation."
So how have computer Go researchers tackled these two issues? This is where the science behind The Path of Go gets brilliant – and where the game's modest loading bar comes into its own.
"Let's talk about the evaluation problem first," Graepel says. "Something called Monte Carlo sampling has proved very useful. It's quite an amazing fact, but if you take a Go position in which Black is in a better position than White, how can the computer find out about that?
"A way that appears to work is this: you take that position and you play randomly to the end of the game. By that, I mean that Black and White still make legal moves, but those legal moves are determined by just throwing a die or using a random number generator.
"Do that once and the outcome will be random, of course. But it turns out that if you do that often enough – you always start from the same position, and then you play the game to completion with random moves, say, 10,000 times, you'll find that if Black has an advantage in that position, even through random play, Black will win slightly more often than White.
A quirk of the AI system is that your rivals will often beat you by half a point. That's because the computer is only seeking to win.
"This is a very weak statistical signal which is hard to pick up," admits Graepel. "But people in the Go community have advanced this, and discovered that if the computer simulations make moves which have done better in earlier samples – if you effectively bias your random games towards good moves – then the signal gets much stronger.
"That way, you are randomly exploring the game tree, but putting more of your attention on promising moves, and it allows you to evaluate who is winning much more successfully."
Cripes. So every time that little loading bar pops up – every time the computer makes a move in The Path of Go – it's first playing a series of games randomly through to their completion?
"Exactly," laughs Graepel. "That's exactly right. It's a technique called UCT: Upper Confidence Intervals in Trees, and it's become one of the very exciting research areas. Although we use it, we didn't invent, so I don't want to take credit.
"So that's problem number one," he continues. "Now we know how to evaluate a position, the second problem is the size of the tree: there are too many different moves available at each turn. We get around this in part by cutting down the board size for much of the campaign in The Path of Go.
"The original game is played on a 19x19 board, which allows for 361 different points. We've cut that down to a 9x9 board, which allows for only 81 points. It's roughly as complex as Chess, but it makes it less intimidating for players and allows the AI to work much better.
"On 9x9 boards, Go programmes are almost competitive with the best human players now, while on bigger boards they're still very much away from that."
This smaller board is then interpreted using a different technique using pattern recognition, explains Graepel. "Here, the idea is to train a machine learning system that learns to imitate a professional Go player.
"As training examples, we have a quarter million game records from professional players. What this has given us is a large number of training examples with each position, and then the next move that actually got made by a professional.
"Of course, not all the possible Go positions will turn up in these quarter million game records, so we have to be able to interpolate. So what happens is that the computer tries to learn the value of each move in each position.
"When a professional player makes a move, he's effectively telling the computer that the move he made is better than any of the other 200 or so moves he could have made. If we get enough of this kind of information, we can start to evaluate different moves, and learn what good moves are."
According to Graepel, it's essentially about data-mining. "The way we then use this is not to make the decision of which move to make, but to prune down the tree. Say there's 200 moves we can make in our specific scenario: we use our machine learning to prune down our options, because most of these moves, a professional player wouldn't even consider, right?
"Our system predicts that, prunes them out of the tree, and then suddenly only 20 moves are left, which makes it a lot easier for the computer to search through."
So how does Graepel, who characterises himself as an advanced Go player, rate The Path of Go as a an opponent? "I think it's getting closer to the human Go experience," he says. "But we're building on a lot of research from the computer Go community – stuff that's already been published and written about – so it's not the case that we've made a huge AI breakthrough here, where only we have contributed to it.
"I think it's actually quite amazing at times, though. When you've been involved in building something, and it makes a move that you didn't expect, or that defeats you, you get this funny feeling about having created something that can in turn surprise you."
Once the computer is confident of triumph, it's happy to grind out a victory with minimal extra effort.
What Graepel and his colleagues can take sole credit for, however, is solving the third and oft-forgotten social problem facing Go: the fact its ancient take on deep simplicity can make it a terrifying prospect for new players used to games in which the goal is far more obvious, and the tactics are a little more comprehensible.
With a surprisingly engaging single-player story mode tucked in alongside online and local multiplayer, The Path of Go will both teach the you the basic game from scratch, and key you into just a few of its hidden depths along the way.
And with a lovely tactile method of stone placement, a range of grand masters to play against, and the option to switch to larger board sizes, it's as complete a package as you could hope for. Achievements? Check. Avatar support? Check. Picture of a pagoda on the start screen? Check.
If that's still not enough to intrigue you, I asked Graepel for a few starter tips for anyone looking to get into this ancient and intoxicating game. "You mean other than getting yourself a copy of The Path of Go on the Xbox 360?" he replied, proving once and for all that having a doctorate in Physics doesn't mean you can't make it as a door-to-door brush salesman too.
"There are a few things. Firstly, play on a small board. Maybe even 7x7. That will reduce the complexity and really help you get your footing. The second thing is, it's good to have a good player explain it to you, but then to explore the game with another beginner. It's too frustrating to play against a strong beginner early on.
"Finally, there's a variant of the game called Capture Go, that's often taught to players first. It's a more fast-paced game, where the winner is the first to capture an opponent's stone. It reduces the complexity of the game much clearer and it allows you to focus on a simple goal. That's my favourite tool for teaching people to play."
Or, as Graepel puts it with a chuckle: "My favourite tool for teaching them the flow of the stones."
