The game of go as a complex network (Vol. 43 No. 4)

image Moduli squared of right eigenvectors of the 7 largest eigenvalues of the Google matrix for the first 100 most frequent moves, showing that each eigenvector is localised on specific moves.

The study of complex networks attracts more and more interest, fuelled in particular by the development of communication and information. It turns out that such networks can also modelize many important aspects of the physical world or of social interactions. However, they have never been used in the study of games.

Games have been played for millennia, 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 the symmetry between ingoing and outgoing links distributions. The 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.

The game of go as a complex network
B. Georgeot and O. Giraud, EPL, 97, 68002 (2012)