28 June 2010
Go is a game so complex that raw computing power was never going to be enough to turn it into a competitive computer game. But two Cambridge researchers found a way – with a programming language used for analysing financial risks.
The best chess player in the world is a computer. But computers are no match for experts at Go, an ancient Chinese game which involves placing stones on the intersections of a 19 by 19 line grid with the aim of capturing more territory than your opponent.
That’s because Go, by many measures, is far more complex than chess and can’t yet be solved by simply applying raw computational power to calculate what would happen as a result of each possible move. The number of possible moves at any given point in a game of chess is typically less than 40, whereas in Go a player generally has a choice of around 200 moves.
So creating software that can play Go competitively with humans, while running on the five-year-old Xbox 360, is a real test of the progress of Microsoft Research in the field of artificial intelligence and machine learning, which is central to making computers more adaptable and human-like. A team from Microsoft Research’s Cambridge labs led by Joaquin Quiñonero Candela and Markus Jost took up the challenge of creating a competitive Go game in early 2008.
The two met when video game fan Jost and a friend won a games design competition run by Quiñonero Candela. The competition challenged entrants to build a game for Xbox 360 or the PC, paying particular attention to in-game artificial intelligence and pushing it to a new level. Dissatisfied with his job as a software engineer for banking giant UBS, Jost took up Quiñonero Candela’s offer of an internship at Microsoft Research.
After developing an impressive prototype of a Go game in just a few weeks, Jost was given the opportunity to become the technical lead on a project to produce a commercial Go game for the Xbox, to be called The Path of Go. Jost, the lead programmer, and Quiñonero Candela, the producer, built on the work of colleagues Thore Graepel, who had been doing research on Go for ten years, and David Stern, who wrote his PhD thesis on this topic and created the artificial intelligence engine on which the game is based.
Stern’s engine is written in the F# programming language, which was developed at Microsoft Research in Cambridge and is well suited to expressing mathematical concepts in a succinct way. Quiñonero Candela says F# has been widely adopted in the financial services industry, which uses complex mathematical models to analyse risk.
The artificial intelligence that underpins The Path of Go has two basic elements, according to Quiñonero Candela. The first involves simulations of what might happen if the software makes a particular move. The number of such simulations is constrained by the need to make a move within a short period of time, so the human opponent doesn’t get bored waiting. The second element involves matching the patterns of stones on the board to those in a database of 250,000 games played by expert humans.
The software then looks at the moves the expert humans made in similar positions to determine its next move. “It produces some surprising, very human-like moves,” says Quiñonero Candela. This machine learning approach emulates the approach of experienced Go players, who can recognise the kinds of patterns of stones that increase their chances of winning the game.
In the broader world of video games, Go, Chess and other grid-based games form a niche. The vast majority of video games tend to follow set scripts and don’t need to make use of the kind of state-of-the-art artificial intelligence and machine learning that underpins The Path of Go, according to Tim Rance, head of technology at Microsoft Lionhead Game Studios. “Most games have different branches in the script, which, if they are done well, can trick people into thinking the game is really responding to what they are doing,” he says.
Of course, to stand any chance of winning a game like Go, a computer has to genuinely respond to the moves made by its human opponent. The Path of Go is a breakthrough in the sense that the software can analyse its opponent’s moves without having to draw on a large amount of computing power, according to Quiñonero Candela. He claims the software beat 95 per cent of human challengers at a recent trade fair, while only 5 per cent defeated it. “It can give a hard time to almost any amateur,” he adds.
Embellished with rich three-dimensional graphics, in-game avatars, a scripted storyline and tutorials, The Path of Go, which is due for release soon, is designed to appeal to mainstream Xbox 360 owners as much as Go enthusiasts. As well as trying to beat the Xbox, The Path of Go players will be able to play matches online against other human players of similar ability, identified by Microsoft’s TrueSkill ranking and matching system, which was also developed at the Cambridge labs. Ralf Herbrich, who together with Thore Graepel created TrueSkill, actually wrote the code for that part of the game.
Still, Microsoft is only at the beginning of a long journey. Quiñonero Candela stresses that artificial intelligence and machine learning have a long way to progress before they will beat the best Go players. “We are not at the end of the road. We are not even in the middle of the road,” he says.
Of course, machine learning and artificial intelligence concepts are relevant in many other areas of computing. Quiñonero Candela, for example, is now applying machine learning techniques to help Microsoft improve the targeting and relevance of Internet advertising. Meanwhile, Jost is figuring out what his next project will be, while putting the finishing touches to The Path of Go. The 30-year-old is keen to continue developing games. “Whereas developing business applications is an organisational challenge, gaming combines multimedia, artificial intelligence, physics and maths,” he says.
Jost says he would also much prefer to continue working in small teams developing absorbing games, such as The Path of Go, rather than join a large team with a multi-million euro budget creating amazing graphics for a blockbuster title. For Jost, a game needs to be unpredictable, as well as pretty. “Why would I care what the water looks like, if there is no game play?” he asks.
You can also have a look at the "Path of Go" video: