Q: What’s The Path of Go?
A: The Path of Go is an Xbox Live Arcade game based on ‘Go’, the ancient Chinese board game. The game was developed using pioneering artificial intelligence software at Microsoft Research Cambridge. Go is a captivating game that takes minutes to learn but a lifetime to master.
Q: What is Go all about?
A: Go is a strategy game that is at least 2,500 years old and originated from Ancient China. Although it’s not known exactly when the game was invented, by the 3rd century BC it was already a popular pastime. The game is played by two players who take turns placing black and white stones on the vacant intersections of a grid. The objective of the game is to control a larger portion of the board than the opponent.
There are different board sizes available, starting at 9x9; games on this board size can last as little as 10 minutes. However, games on a 13x13 grid can take a bit longer. Experts games’ on a 19x19 board have been known to last for several days, but of course games never take that long in The Path of Go unless you play in correspondence mode via message play.
The objective of the game is to control a larger portion of the board than the opponent by surrounding more of their opponent’s stones with their own. Once placed on the board, stones cannot be moved, unless they are surrounded and ‘captured’ by the opponent's stones.
Q: What prompted computer science researchers to develop this game?
A: Markus Jost, the main developer, entered and won a competition run by Microsoft which encouraged would-be game developers to create their own game. As a result, Markus took up an internship at Microsoft Research where he began developing The Path of Go. This was very challenging to program for a broad audience so represented an interesting research challenge. It required an extremely intricate artificial intelligence (AI) in order to make it a challenging gaming experience.
Q: Why was programming the AI for The Path of Go such a complex challenge?
A: The game is extremely complex. For example, in Chess you might have an average of 20-30 moves per turn. In the starting position of Go, you can make 361 different moves on a 19x19 board.
- The number of possible of different chess games is around 1060
- The number of different atoms is around 1080
- Meanwhile, the number of possible Go scenarios is more like 10700
Due to this complexity, programmers have previously found it very hard to program an AI efficiently.
Q: How has Microsoft revamped the game for a video game experience?
A: The game is built around a first-person scenario. The game starts with the player receiving a letter from a Go master explaining that your twin is missing. When you visit the master, he tasks you with the Path of Go quest, through which you must find your twin. Through the experience, you learn and play the game. In the course of your journey you interact with a number of characters and challenge them in games of Go.
In terms of structure, there are a number of different tracks in the game. Story mode includes full adventure script, powered by AI; Local mode lets you have a multiplayer game either against AI or a friend; Online let’s you play either socially or in a ranked match. In order to guarantee really tight and challenging matches the ranked mode uses the TrueSkill matchmaking system.
The game includes Xbox Avatar integration, letting you play the game as your Xbox Live online Avatar.
Q: Why would Microsoft Research make an Xbox Live Arcade game?
A: Microsoft Research is not in the habit of making games; the rationale for projects always involve a specific research angle in line with a long term goal. Microsoft Research’s interest focuses on the advancement of the artificial intelligence (AI). The Path of Go provided the perfect test bed for a number of key AI principles and lets us tackle these issues in an abstract test bed that is easy to study. Microsoft Research is happy to be able to share the results of its research with the XBLA community, as reflected by its very low cost of 400 points.
Q: Does Microsoft Research plan to conduct more of this type of development?
A: The algorithms used in The Path of Go could certainly be applied to other forms of game AI, as well as other applications such as large scale applications of machine learning including modelling consumer behaviour in online services and automated planning.
The programming of the game
Q: What are the main technologies within The Path of Go?
A: There are three main technologies in the game, two of which were developed by Microsoft Research:
- F# - a functional programming language used to develop the AI (developed jointly between the Microsoft Research and the Microsoft Developer Division)
- TrueSkill - a technology used across the Xbox platform to effectively match players of equal skill levels with each other (developed by Microsoft Research)
- XNA - a set of tools with a managed runtime environment provided by Microsoft that facilitates computer game development and management
Q: What was the role of F# in the game design?
A: We used F# to program the AI. Because it abstracts functionality from coding, F# lets you focus more on the problem domain and less on programming itself.
Q: Why did you decide to write the game in XNA?
A: The main reason for designing the game using XNA was a question of resources. Many games are written in C++, but this requires a lot of ‘libraries’ to store information, along with a lot of man power to create them. XNA comes with a number of pre-made libraries, making it a lot easier to program with. We would never have been able to develop the game so quickly with so few resources without XNA.
Q: How does the AI in the game work?
A: The AI in Path of Go has been in development since 2004 and 250,000 previous games played by Go masters were used to spot patterns and help the AI recognise clever ‘shapes’. The AI is made up of a few key components which enable to it perform efficiently.
The first is the machine learning technique known as “Monte Carlo”, which calculates the most likely outcomes of the game given the position on the board by playing simulated games into the future. In addition, pattern recognition enables the game to analyse the relative merits of different moves in the game, based on which ‘shapes’ were created by experts in 250,000 historical games.
Q: Given enough time, would it be possible for the Monte Carlo system to become perfect and for the AI to become infallible?
A: Theoretically, yes, however, even finding a single move might take many millions of years on current hardware. To provide a reference point, a computer program just recently completed its search for the solution of the far less complex chequers after 18 years.
Q: How strong is the AI?
A: The AI is strong enough that the game could challenge the vast majority of newcomers to the game. It doesn’t compare like-for-like with other high performance computing solutions that have been developed for Go – which only Go experts would be able to compete with – but it does give it a more natural feel and makes the game accessible for a broader audience.