Laboratoire de Physique Théorique
Toulouse - UMR 5152

In a recent letter published in Europhysics Letters Bertrand Georgeot from LPT and Olivier Giraud from LPTMS in Orsay have studied the complex network describing the sequences of moves in the old Asian game of go.

The study of complex networks has attracted more and more interest in the recent past, fueled in particular by the development of communication and information networks. It turned out that many important aspects of the physical world or of social interactions can also be modelized by such networks. However, these powerful tools have never been applied to the study of games.

Games have been played for millenia, and besides their intrinsic interest, they represent a privileged approach to the working of human decision-making. They can be very difficult to modelize or simulate : only recently were computers able to beat chess champions. The old Asian game of go is even less tractable, as no computer program has been able to beat a very good player.

The paper presents the first study of the game of go from a complex network perspective. It constructs a directed network which reflects the statistics of tactical moves. Study of this network for datasets of professional and amateur games shows that the move distribution follows Zipf’s law, an empirical law first observed in word frequencies. Differences between professional and amateur games can be seen, e.g. in the distribution of distances between moves. The constructed network is scale-free, with statistical peculiarities, such as a symmetry between ingoing and outgoing links distributions. The fine study of eigenvalues and eigenvectors of the matrices used by ranking algorithms singles out certain strategic situations (see figure), and vary between amateur and different professional tournaments. These results should pave the way to a better modelization of board games and other types of human strategic scheming.

A more detailed exposition (in French) can be seen at the CNRS website.