Applied Mathematics, Computation and Simulation
MoGo on top of its game!
The game of Go, a breeding ground for technologies for a number of fields. MoGo, a project coordinated by Olivier Teytaud from the Tao project-team, was invited to attend the 2009 Taiwan Open. It beat the world record for the best performance in 19x19 Go.
Combining innovative Artificial Intelligence and multi-core, message-passing parallelisation, it has been notching up victories against professional players. In addition to its application in the game of Go, this parallel algorithm can also be used to address a vast range of problems.
In 1997, a computer beat world chess champion Garry Kasparov for the first time. Until recently, however, the game of Go was the exclusive preserve of human beings. More complex than chess, with more than 10 to the power 600 possible games, which is more than the number of particles in the Universe, the game of Go represents a remarkable education in strategy. In a game where human beings had shown themselves to be far superior to machines, computers have now managed to reach the level of a professional Go player.
However, as the current programs are still not strong enough to beat high-level players, they are given an advantage: they are given a number of successive moves at the start of the game, which constitutes a handicap for the professional player. The progression of MoGo through its series of victories is therefore principally measured in terms of the reduction in the size of the handicap imposed on the professional players. At the 2009 Taiwan Open (10-13 February 2009), MoGo won a match for the first time
with a handicap of only 7 stones against an elite player, Zhou Junxun, a highly respected 9th Dan Pro who won the 2007 LG Cup, as well as a match with a 6-stone handicap against a professional player, Li-Chen Chien.
At this international competition, MoGo, a product of French computer science research, demonstrated the results of three scientific or technological advances:
- Firstly, the "One-Armed Bandit" algorithms have made it possible to (partially) explore the space of possible matches. In so doing they have revolutionised the notion of planning in an uncertain world.
- Furthermore, the assessment of positions is founded on Monte-Carlo algorithms, simulating the behaviour of a low-level stochastic player, but without any bias.
- Finally, large-scale parallelism (notably with GRID’5000) has made it possible to have the necessary computing power for a Monte-Carlo evaluation to provide sufficiently precise results.
These developments have thus made it possible to find new applications for this algorithm. Beyond the game of Go, the software used is based on innovative technologies that can be used in numerous fields, particularly resource saving, which is crucial to environmental issues.
Indeed, the game of Go poses scientific problems that are very difficult to solve. Even if, in theory, the game is deterministic - i.e. it can be programmed without any particular difficulties - astronomical computing times would be required to find the solution. Yet here the parallel algorithms make it possible to use computer grids and to solve problems of planning and possibility ordering. Ordering possibilities, for example, may be counted in billions of billions, and the aim is to find the most efficient order among this host of possibilities. The game of Go is therefore a good model for developing and testing new techniques to resolve this kind of scheduling problem.