Sites Inria

Version française

MoGo Software - The Game of Go

26/02/2009

The Game of Go, technology territory for many fields

As part of the Inter-Regional Program of the European Union and invited to the 2009 Taiwan Open, the MoGo project coordinated by Olivier Teytaud of the TAO project team broke a new record by producing the best worldwide performance to date in Go 19x19. This parallelized algorithm can be used, beyond the game of Go, to solve a wide range of problems.

In 1997, for the first time, a computer defeated Garry Kasparov, the world chess champion. The game of Go, however, had until recently been a field limited to humans. More complex than chess, with more than 10 to the 600th power possible plays, meaning more than the number of particles in the universe, the game of Go is a remarkable school for strategy. In this game, where humans had enjoyed a clear superiority, the computer managed to come up to the level of a professional Go player.
However, since current programs are still too weak to defeat high-level players, they are given an advantage: they play a certain number of moves in a row at the beginning of the game, which corresponds to handicap stones for the professional player. MoGo’s progress through a series of victories must thus be measured mainly in terms of the reduced number of handicap stones for professional players. At the 2009 Taiwan Open (February 10-13, 2009), MoGo thus won a game for the first time with only 7 handicap stones, played against a top-ranking player, Zhou Junxun, an extremely renowned player of the 9th Pro Dan and winner of the 2007 LG Cup, as well as a game at 6 handicap stones against another professional player, Li-Chen Chien.
At the heart of this international competition, MoGo, a product of French research in computer science, is thus able to show the results of three scientific or technological advances:

  • First of all, the so-called Bandits Manchots (“One-Armed Bandits”) algorithms made it possible (partially) to explore the space of possible moves. They thereby revolutionized the world of planning in an uncertain universe.
  • Secondly, the evaluation of positions is based on Monte-Carlo algorithms, simulating the behavior of a low-level stochastic player but without any bias.
  • Lastly, the parallelism on a large scale (with, in particular, GRID’5000) served to provide the computational power required for a Monte-Carlo evaluation to give sufficiently precise results.

These evolutions thereby enabled new applications of this algorithm. In addition to the game of Go, the software used is based on innovative technologies that can be used in many fields, especially in the conservation of resources, which is crucial for environmental problems.
In reality, the game of Go poses scientific problems that are very difficult to solve. Even if the game is determinist in theory, meaning that it can be programmed without any special difficulties, it would take an astronomical amount of computation time to obtain the solution. However, in this case the parallel algorithms allow one to use the computational grids and solve problems concerning the sequencing of possibilities and of planning. The sequencing of possibilities amounts, for example, to thousands of millions and the objective is to find the most efficient order in this mass of possibilities. The game of Go is thus a good model for developing and testing new techniques for solving this type of sequencing problem.

Keywords: Software MoGo Olivier Teytaud Team TAO Centre de recherche Inria Saclay - Île-de-France Game of Go

Top