When it comes to the ancient Chinese board game of Go, a certain cliché has gained near ubiquity. The game, the saying goes, takes just minutes to learn, but a lifetime to master.

Thats a shorthand way to describe the games deceptive simplicity. Go is played on a square grid of equidistant parallel lines overlaid with a second set oriented at a right angle to the first, creating a series of intersections. Competitors place playing pieces, called stones, onto the points of intersection in an attempt to surround and capture the opponents stones. At a glance, Go appears rudimentary, almost childlike, belying intricate strategies and tactics that can rivet ones imaginationand, in some cases, change ones life.

Markus Jost knows all about the latter. A few years back, he was a young developer, fresh out of the University of Zurichs computer-science program, writing Java enterprise applications for a major Swiss bank. But the financial world held few thrills for the young software engineer. In a word, he was bored.

Now, three years later, he finds himself the lead developer for The Path of Go, a computer-based, narrative-driven version of the venerable East Asian favorite. With the game, developed by Microsoft Research Cambridge, being released to the public Dec. 15 as an Xbox Live Arcade title, Jost has shaken his ennui.

I plan to continue developing games for years, Jost says. Its fun, its challenging, its creative, and customers are happy about what youre selling them. That makes me happy, too.

Go: minutes to learn, a lifetime transformed.

Joaquin Quiñonero Candela, senior applied researcher for Microsoft adCenter, is delighted, too. Quiñonero Candela, who leads a team embedded within Microsoft Research Cambridge, served as producer/project manager for The Path of Go, soon to be ported to Windows Phone 7.

Developing a broadly accessible computer version of Go was no trivial undertaking. More than a decade after computers demonstrated the ability to defeat chess world champions, Go remains one of the key challenges for the field of artificial intelligence. Chess, for example, can offer an initial set of 20 potential moves. On a standard, 19x19 board, Go offers 361. That complexity makes Go difficult to program efficiently.

In addition, the game has a unique history and ethos, one at odds with typical first-person shooter computer games whose raison dêtre is to destroy the enemy. The precise origin of Go is unknown, but the game was popular 2,500 years ago, and Chinese emperors are understood to have taught the fundamentals of Go to their children as part of their educational rigors.

In many western games, Quiñonero Candela says, theres a clear notion of the game is over because I have destroyed my opponent, whereas theres a notion of honor in Go. If I know Ive won a game, theres no need to humiliate my opponent.

That sort of thinking has guided the development of The Path of Go, in everything from research into artificial intelligence, which began years before Jost became involved, to the name of the Xbox Live Arcade game itself.

I suppose the reason why we chose The Path of Go, Quiñonero Candela told the video-game website Joystiq in March, was because we wanted a metaphor for the process of learning. It really feels like a journey.

That journey is enhanced by the story mode of the new titleand is reflected in the extensive effort it took to produce a welcoming challenge for prospective players.

Prior Work

Thore Graepel, senior researcher at Microsoft Research Cambridge, is a longtime Go enthusiast and has worked on Go artificial intelligence for years, along with Ralf Herbrich, Microsoft Research Cambridge-based director of FUSE Labs.

Graepel and Herbrich also were the masterminds behind TrueSkill, a skill-based ranking system for Xbox Live. TrueSkill, which is designed to identify and track the expertise of gamers for the purposes of placing them into competitive online matches, has been incorporated into The Path of Go.

Quiñonero Candela joined Microsoft Research Cambridge in 2007, reporting to Graepel, and quickly found himself entranced by Go and the artificial-intelligence work his predecessors had pursued. He also found himself fascinated by the then-new XNA Game Studio, a programming environment that uses Microsoft Visual Studio to create Xbox games. In an effort to heighten awareness of XNA in the academic community, he organized the Silicon Minds Challenge, a competition among aspiring game developers that required the use of XNA Game Studio.

Among those intrigued by the competition was avid gamer Remo Zehnder, who happened to work alongside Jost in Zurich.

I needed a change, Jost says, and a friend convinced me to enter the challenge in 2008.

Jost and Zehnder submitted a game called iSheep, in which a sheepdog must herd a flock of sheep into a pen. It opened some eyesand the two were named one of five winning teams in the competition.

They created a fantastic game, Quiñonero Candela says. They got a window into what they could achieve with XNA.

That made me realize that creating a game was not impossible. We had these brilliant guys who won the competition. I thought: This is feasible. It will be tough, but we can do it. Lets go for it!

As Silicon Minds winners, Jost and Zehnder became eligible to interview for internships at Microsoft Research Cambridge, which they did, successfully. It didnt take long for Quiñonero Candela to put them to work on a new project: to develop a game for Go aficionadosand newcomers.

Microsoft Research, Quiñonero Candela notes, is a place where you grab talented people and enable them to do wonderful things.

Developing a computer Go game was not novel; high-performance-computing games for expert players have been around for a while. But the game is hard to program for a broad audience, requiring extremely intricate artificial intelligence to make it challenging. The complexity of the gamegiven the larger number of potential moves and the difficulty of defining appropriate evaluation functions for those potential movesposed a significant hurdle.

A grand master poses a formidable challenge for a newcomer to The Path of Go.

Zehnder eventually returned to the financial world, although he did play an integral role in the development of 3-D graphics used in The Path of Gos user interface. But Jost stuck around, eventually becoming an agency contractor, based near Zurich, for Microsoft Research Cambridge and serving as lead developer on the project.

Markus always had a game developer inside, Quiñonero Candela says. Hes the kind of guy who has played every game he could since the early days.

David Stern, an applied researcher working for Herbrich, joined the effort to write the artificial-intelligence engine for The Path of Go. Under the supportive supervision of Graepel and Herbrich, the team went to work in earnest.

Microsoft Research, of course, isnt in the business of game creation. But this particular project offered intriguing research opportunities. It was a way to extend artificial intelligence to a new domain and to gain an abstract test bed to study key artificial-intelligence principles. The results of that research could be shared with the Xbox Live Arcade community, and the algorithms thus derived could be applied not only to other games, but also to large-scale machine-learning projects. For example, Quiñonero Candela says, the work could help to model consumer behavior in online services and could assist automated planning.

There is a continued effort in doing research in the field of artificial intelligence for Go, Quiñonero Candela says, noting that Graepel is a leader in that effort and that Stern wrote his Ph.D. thesis on such work.

Two key approaches helped drive the game development. One was the use of Monte Carlo machine learning, which calculates the expected game outcome for a given board position by playing simulated matches. But again, theres that complexity factor.

The number of different states of the board for Go by far exceeds the number of atoms in the universe, Quiñonero Candela chuckles. Given that, what do you do? You find clever ways of partially exploring that immense universe. How clever you are at exploring the parts will determine whether your artificial intelligence is good enough.

Theres an algorithm called Upper Confidence Intervals Applied to Trees that is an efficient way of exploring the game tree, of avoiding the exploration of branches that are not worth exploring because you can already predict whats going to happen.

The Monte Carlo technique was combined with pattern recognition.

We train the machine-learning program on a quarter-million game records of expert Go players, Quiñonero Candela explains. Go players will tell you that certain shapes you can form on the board are good. In fact, calling a move good shape is one of the biggest compliments you can give to another Go player. We thought we could learn those shapes from a massive collection of expert games. We built an automatic predictor for expert moves, a system that, trained on a wealth of past games, will map certain patterns to the moves an expert would play. It uses that to rank the patterns.

It gives a positive weight to a pattern in the sense that, if this pattern was present, the probability of an expert making that move is higher, and vice versa for lousy patterns. You combine that with the exploration of the game tree to prune away the stuff that was worthless, then focus on the patterns that are promising. The combination of these two systems gives us playable, fun artificial intelligence on a modest architecture.

Also playing a key role were several key technologies:

• Pioneering artificial intelligence, to produce software capable of playing Go.
• F#, a new, functional programming language developed by Microsoft Research Cambridge in collaboration with Microsofts Developer Division. Programming the artificial intelligence for the game in F#, which runs efficiently on Microsofts .NET Compact Framework, enabled the games creators to spend more time on the problem at hand and less time on programming.
• TrueSkill, to match online players of equal abilities.
• XNA, a set of tools offering a managed runtime environment, facilitating development and management of the game. The premade libraries offered by XNA made programming easier and the game quicker to develop, with fewer resources necessary.

The Path of Go features a set of environments in story mode: a collection of five 3-D scenes, lovingly rendered, during different times of the day. As the novice player advances from morning to night, he or she will meet a Go grand master at a temple in the morning, cross a lake guarded by a female guard, cross a hanging bridge at the top of a small mountain, enter a mysterious cave, and reach the top of a mountain at night. Each scene, naturally, involves a bit of Go playing and learning.

The Path of Go leads the player through a challenging day, culminated by mountaintop game play at night.

We created this whole story, Quiñonero Candela says, where you start with a basic tutorial that shows you the board and how to place stones and gives you some basic concepts about capturing stones. The exciting bit is the five stages.

He should know. He authored most of the text for the story.

One of the craziest things Ive done, Quiñonero Candela laughs. I had some long nights writing all those dialogues word for word.

The game also features a local mode, in which you can compete against a friend or against the games artificial intelligence, and an online version, for social play or for a ranked match using TrueSkill.

On a suggestion from the Xbox Live Arcade team, the game also deploys Xbox Live avatars that represent competing players.

Its your own avatar, Quiñonero Candela says. However youve customized it, thats what you take with you into the game. If youre playing against someone online, you can make certain gestures. If you think the other player made a very good move, you can applaud. It serves to make the game more personal.

Another unique feature for computer Go gamingone familiar to those who play chess and Go by mailis the play-by-message functionality, which enables asynchronous game play, a first for Xbox Live Arcade.

People are not necessarily always online, Quiñonero Candela notes. If they are notif Im playing a game and I need to catch the bus to workI can save the game and pick it up later. I can make a move even if the person I was playing is not online.

The game developers did have to conquer particular challenges en route to the projects completion.

The biggest development challenge was the Xbox Live integration, Jost says. Xbox is a really complex platform to develop for, compared to a phone, for instance, because you have removable storage devices, user profiles that can change while a game is played, trial mode, Xbox Live integration such as achievements and leader boards, and our unique message-play mode. Combining all this and making the implementation stable enough to pass all the testing and the technical certification requirements took a lot of time. XNA was a big help, though, and made it possible for just one person to deal with all that.

Xbox Live Collaboration

The effort was not the work of just a few people. Quiñonero Candela credits a number of individuals from the Xbox Live team, such as Scott Brodie, the initial producer, who lobbied for the use of avatars. He was succeeded by Nick Ferguson, who made some brilliant contributions to the game design. Chad Long, test manager, suggested the addition of message play and was aided by software-test engineer Jeremiah Armstrong.

Im very indebted to these people Quiñonero Candela says, for their amazing contributions to the game.

Such teamwork has helped create a game that has a more natural feeland thereby is more broadly accessible. The vast majority of newcomers will find The Path of Go a distinctly alluring challenge.

I am very proud of the overall look and feel of the game, Quiñonero Candela smiles. Im also proud for us to contribute a very nice, evergreen game to the Xbox platform.

Go has an incredible beauty, and I am very proud that, through the Xbox vehicle, we are going to be spreading to the worldespecially the western world this amazing game.

Stern concurs.

It is fantastic, he says, to see our research being put into such a beautiful product that will be released to the public. I hope it helps to spread the word about the fascinating game of Go.

And then theres Jost, whose Go experience has taken him from the houses of finance to the galaxy of gaming.

I like the fact that it looks very polished and that the functionality is so rich, Jost says. Theres not a single feature that we didnt implement.

Why does that make me happy? Because it offers more than many other games that were developed by big teams, and I did all the development work by myself. That makes me proud.