The game of go as a complex network

Tuesday, April 10, 2012

Graphe go

© O. Giraud et B. Georgeot

Strategic moves of the game of go.

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, fuelled 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 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 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.

References:

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

Contacts:

Olivier Giraud l T. 01 69 15 31 75 l olivier.giraud@u-psud.fr
Bertrand Georgeot l T. 05 61 55 65 63 l bertrand.georgeot@irsamc.ups-tlse.fr

 

Filter

Date

Agenda

04/10/2018 Cold-atom superradiance

John Martin (Université de Liège, Belgium) 10 avril 2018, 14h00   In my talk, I...