Network Science of the Game of Go

You can make networks from pretty much anything. Connect music based on taste or phone calls, companies based on their ownership, spread routes of abstract movements, and lots more. It is high time to start using networks to understand games. But what of the structure of games themselves? In a paper that was recently published in EurophysicsLetters, two French scientists decided to apply network science to the game of Go.

They constructed their networks in a simple way: If one board position can lead to another, they are connected. Using a dataset of about 1,000 professional games and 4,000 amateur games, they began to construct these networks.

In a Game of Go players put black and white stones on a grid board.

Of course, the Go board is very large and so you can’t compare entire board layouts. Instead, they decided to make it much more tractable and look at the board composition surrounding a newly placed piece (a move in Go consists of putting a stone on an intersection of the grid lines of the board). In this case, they looked at the pieces immediately surrounding a newly placed piece (for a 3×3 grid). They calculated that this creates 1107 possible moves, which can be connected if the moves occur one after another, and are in the same region of the board. They also examined the frequency of moves, which obeys a heavy-tailed distribution (whether or not it is a power-law as they claim seems a bit weaker).

The network analyses in the paper are a bit odd, though they find many classic graph structures, such as a heavy-tailed link distribution and high amounts of clustering. Gratifyingly, the networks constructed from amateur and professional games are distinct, though in somewhat subtle ways. 

Read the article here, or the short version on Wired!