Friday, 1 March 2013

The game of go as a complex network

Board games are one of the oldest activities of humankind and have been played for millenniums. Besides their inherent interest, they represent a privileged approach to the working of decision-making in the human brain. Some of the board games are very difficult to model or simulate: only recently were computer programs able to beat world chess champions. The old Asian game of go is even less tractable. The game complexity, that is, the total number of legal positions, is about 10171, compared to a mere 1050 for chess [2]. It remains an open challenge for computer scientists: while Deep Blue famously beat the world chess champion Kasparov in 1997, no computer program has beaten a very good player even in recent times.

The game of go is played by two players (Black and White) on a board consisting of 19 horizontal and 19 vertical lines. The players alternately place a stone of their own color at an empty intersection on the board. Stones entirely surrounded by the opponent must be removed, and the aim of the game is to delimit large territories. As the game unfolds, local and global properties of stones are involved. A network approach will obviously not be able to capture all features of the game, as the number of possible moves is far too large. Here we follow an approach where only local features are retained. This approach is reminiscent of the one used in the context of language networks [3].

 A move consists in placing a stone at an empty intersection (h, v) with 1 <= h, v <= 19. We call ”plaquette” a square of 3 × 3 intersections, that is, a subset of the board of the form {(h + r, v + s),−1 <= r, s <= 1} (to account for edges and corners of the board one can imagine that there are two additional dummy lines at each side of the board). To define our network we only take into account intersections closest to (h, v). Vertices correspond to the different kinds of plaquettes in which a player can put a stone, irrespective of where it has been played on the board. Since each of the 8 neighboring intersections can be either empty, black or white, there are approximately 38 different plaquettes. We choose to consider identical plaquettes that transform to each other under any symmetry of the square (rotation or flip). We also identify patterns with color swapped. That is, a move where Black plays in a given plaquette is considered the same as a move where White plays in the same plaquette with colors swapped. An exact computation taking into account borders and symmetries leaves us with 1107 nonequivalent plaquettes with empty centers, which are the vertices of our network. We note that certain computer programs based on knowledge from real professional games also consider similar 3 × 3 stone patterns [4, 5]. Considering larger plaquettes is possible and would convey more relevant information; however, the number of vertices then becomes enormously large (approximately 3.1010 for 5 × 5 plaquettes).

This definition of inequivalent moves enables us to investigate the first properties of the databases in term of frequencies of moves. Zipf’s law is an empirical characteristics which has been observed in many natural distributions, such as e. g. word frequency in the English language [6], city sizes [7], and income distribution of companies [8], and chess openings [9]. If items are ranked according to their frequency, it predicts a power-law decay of the frequency as a function of the rank. Zipf’s law was observed in the frequency distribution of 5×5 go patterns [10]

(Color online) Normalized integrated frequency distribution of moves F(n) for Honinbo (black), Meijin (red), Judan (green), Kisei (blue) and amateur (violet) tournaments. The normalized number of occurrences of the 500 most frequent moves (among the 1107 moves described in the text) is shown vs. the ranks of the moves (rankings slightly depend on the database). Slopes are, respectively, 1.058, 1.056, 1.065, 1.067, 1.081. The thick dashed line is y = x. Inset: the same with moves defined as the position of the stone on the board. Log is decimal.

In above figure[1] we display the integrated frequency distribution for our 1107 moves labeled from the most to the least frequent. The integrated distribution of moves is very similar for all databases and clearly follows a Zipf’s law, with an exponent approximately equivalent to 1.06. In contrast, such a law cannot be seen if one simply takes the 361 possible positions (h, v) as vertices, disregarding local features (inset of Fig. 1). Thus Zipf’s law appears when tactical information is taken into account. For all databases the 10 most frequent moves are the same, but sometimes in a slightly different order.

References :
[1] Georgeot (Universit´e de Toulouse; UPS; Laboratoire de Physique Th´eorique (IRSAMC); F-31062 Toulouse, France and CNRS; LPT (IRSAMC); F-31062 Toulouse, France)  and O. Giraud (Univ. Paris-Sud, CNRS, LPTMS, UMR 8626, Orsay, F-91405, France)

[2] Tromp J. and Farneb¨ack G., Combinatorics of Go, Proc. of the 5th Int. Conf. on Computer and Games, edited by      Van den Herik H. J., Ciancarini P. and Donkers H. H. L. M. Lect. Notes in Comp. Sciences, 4630 (2007) 72 (Springer-Verlag, Heidelberg, Germany)

[3] Ferrer-i-Cancho R. and Sole R. V., Proc. Royal Soc. Lond. B, 268 (2001) 2261; Dorogovtsev S. N. and
Mendes J. F. F., Proc. Royal Soc. Lond. B, 268 (2001) 2603; Masucci A. P. and Rodgers G. J., Phys. Rev. E,
74 (2006) 026102

[4] Coulom R., ICGA Journal, 30 (2007) 199

[5] Huang S.-C., Coulom R. and Lin S.-S., Lect. Notes in Comp. Science, 6515 (2011) 81

[6] Zipf G. K., The Psycho-Biology of Language (Houghton Mifflin, Boston) 1935

[7] Gabaix X., Quart. Jour. of Econ., 114 (1999) 739

[8] Okuyama K., Takayasu M. and Takayasu H., Physica A, 269 (1999) 125

[9] Blasius B. and T¨onjes R., Phys. Rev. Lett., 103 (2009) 218701

[10] Liu Z., Dou Q. and Lu B., Lecture Notes in Computer Science, 5131 (2008) 125

No comments:

Post a Comment