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