Game of go: A complex network

Game of go : A complex network
From their network, the researchers obtained these patterns (each one with 9 intersections) which show the most frequent moves or combine strategic moves (these are patterns on which eigenvectors associated with three large eigenvalues from the weighted adjacency matrix of the graph are localized). The top line corresponds to the ten most frequent moves in go. The middle line isolates patterns most of which correspond to a well known situation in go, ko ('eternity'). In the bottom line, most of the patterns correspond to situations where chains of stones become connected. Black is playing at the cross. Credit: O. Giraud et B. Georgeot

Could computers ever beat the best go players? Although unthinkable at this stage, this could soon become possible, thanks to CNRS theorists. For the first time, two scientists from the Theoretical Physics Laboratory and the Laboratory of Theoretical Physics and Statistical Models, have applied network theory to a game of strategy. Their findings, published in the journal Europhysics Letters, should help to improve future simulation programs.

The study of has attracted increasing interest over the past few years, fuelled in particular by the development of communication and . This new research field is proving very useful for the description of complex systems such as social networks and the Internet. For instance, when is applied to the Internet, every page is a node and hypertext links are links between the nodes. However, this type of approach had never been contemplated for the study of games of strategy such as go or chess. These games, which have a very long history and millions of players around the world, are extremely difficult to model. Computer programs have only been able to beat chess champions since the last fifteen years, and are still unable to compete with top go players. 

Using a database containing around 5 000 games played by professional and amateur go players in international tournaments, Bertrand Georgeot from the Theoretical Physics Laboratory and Olivier Giraud from the Laboratory of Theoretical Physics and Statistical Models applied network theory to this game of strategy. They constructed a network whose nodes are local patterns on the board, while the vertices (which represent the links) reflect the sequence of moves. This enabled them to recapture part of the local game strategy. In this game, where players place their stones at the intersections of a grid consisting of 19 vertical and 19 horizontal lines (making 361 intersections), the researchers studied local patterns of 9 intersections. They showed that the statistical frequency distribution of these patterns follows Zipf's law, similar to the frequency distribution of words in a language. 

Although the go network's features resemble those of other real networks (social networks or the Internet), it has its own specific properties. While the most recent simulation programs already include statistical data from real games, albeit at a still basic level, these new findings should allow better modeling of this kind of board game.

Explore further

'Civilization' lets Facebook players rule world

More information: "The game of go as a complex network," Europhysics Letters, EPL 97, 68002 (2012).
Journal information: Europhysics Letters (EPL)

Provided by CNRS
Citation: Game of go: A complex network (2012, April 16) retrieved 26 January 2020 from
This document is subject to copyright. Apart from any fair dealing for the purpose of private study or research, no part may be reproduced without the written permission. The content is provided for information purposes only.

Feedback to editors

User comments