Zipf’s Law in the Popularity Distribution of Chess Openings
Decision making refers to situations where individuals have to select a course of action among multiple alternatives . Such processes are ubiquitous, ranging from one’s personal life to business, management, and politics, and have a large part in shaping our life and society. Decision making is an immensely complex process and, given the number of factors that influence each choice, a quantitative understanding in terms of statistical laws remains a difficult and often elusive goal. Investigations are complicated by the shortage of reliable data sets, since information about human behavior is often difficult to be quantified and not easily available in large numbers, whereas decision processes typically involve a huge space of possible courses of action. Board games, such as chess, provide a well-documented case where the players in turn select their next move among a set of possible game continuations that are determined by the rules of the game.
Human fascination with the game of chess is long-standing and pervasive , not least due to the sheer infinite richness of the game. The total number of different games that can be played, i.e., the game-tree complexity of chess, has roughly been estimated as the average number of legal moves in a chess position to the power of the length of a typical game, yielding the Shannon number . Obviously only a small fraction of all possible games can be realized in actual play. But even during the first moves of a game, when the game complexity is still manageable, not all possibilities are explored equally often. While the history of successful initial moves has been classified in opening theory , not much is known about the mechanisms underlying the formation of fashionable openings . With the recent appearance of extensive databases, playing habits have become accessible to quantitative analysis, making chess an ideal platform for analyzing human decision processes.
The set of all possible games can be represented by a directed graph whose nodes are game situations and whose edges correspond to legal moves from each position (Fig. 1). Every opening is represented by its move sequence as a directed path starting from the initial node. We will differentiate between two game situations if they are reached by different move sequences. This way the graph becomes a game tree, and each node is uniquely associated with an opening sequence.
Using a chess database  we can measure the popularity or weight of every opening sequence as the number of occurrences in the database. We find that the weighted game tree of chess is self-similar and the frequencies of weights follow a Zipf law 
with universal exponent . Note, the precise scaling in the histogram of weight frequencies and in the cumulative distribution over the entire observable range [Fig. 2(a)]. Similar power law distributions with universal exponent have been identified in a large number of natural, economic, and social systems [7–15]—a fact which has come to known as the Zipf or Pareto law [7,8]. If we count only the frequencies of opening weights after the first moves we still find broad distributions consistent with power law behavior [Fig. 2(b)]. The exponents are not universal, however, but increase linearly with [Fig. 2(b), inset). The results are robust: similar power laws could be observed in different databases and other board games, regardless of the considered game depth, constraints on player levels or the decade when the games were played. Stretching over 6 orders of magnitude, the here-reported distributions are among the most precise examples for power laws known today in social data sets.
As seen in (Fig. 1) for each node the weights of its subtrees define a partition of the integers ( ). The assumption of self-similarity implies a statistical equivalence of the branching in the nodes of the tree. We can thus define the branching ratio distribution over the real interval by the probability that a random pick from the numbers is in a subset of size smaller or equal to . Taking to infinity may have a continuous limit for which we find the probability density function (PDF) . If the limit distribution of branching ratios exists it carries the fingerprint of the generating process. For instance, the continuum limit of the branching ratio distribution for a Yule-Simon preferential growth process  in each node of the tree would be , where is a model specific parameter. On the other hand, in a -ary tree where each game continuation has a uniformly distributed random a priori probability the continuum limit corresponds to a random stick breaking process in each node, yielding . For the weighted game tree of chess can directly be measured from the database [Fig. 3(a)]. We find that is remarkably constant over most of the interval but diverges with exponent 0.5 as , and is very well fitted by the parameterless arcsine distribution
The form of the branching ratio distribution suggests that in the case of chess there is no preferential growth process involved, but something entirely different which must be rooted in the decision process during the opening moves of a chess game .
In the following we show that the asymptotic Zipf law in the weight frequencies arises independently from the specific form of the distribution , and hence, the microscopic rules of the underlying branching process. Consider realizations of a general self-similar random segmentation process of integers, with paths ( ) in the corresponding weighted tree. In the context of chess each realization of this process corresponds to a random game from the database of games (e.g., dark shading in Fig. 1). The weights describe a multiplicative random process
where the branching ratios for sufficiently large are distributed according to independent of . For lower values of the continuous branching ratio distribution is no longer a valid approximation and a node of weight one has at most one subtree; i.e., the state is absorbing.
To calculate the PDF of the random variable after steps it is convenient to consider the log-transformed variables and . The corresponding process is a random walk with non-negative increments and its PDF transforms as . An analytic solution can be obtained for the class
of power law distributions, which typically arise in preferential attachment schemes. In this case the jump process is Poissonian and distributed according to a gamma distribution . After retransformation to the original variables and noting that from the probability for a single node at distance to the root to have the weight one obtains the expected number of these nodes in realizations of the random process as , and in particular
The functions are strongly skewed and can exhibit power law like scaling over several decades. A logarithmic expansion for shows that they approximately follow a scaling law with exponent
The exponent is linearly increasing with the game depth and with a logarithmic finite size correction which is in excellent agreement with the chess database [Fig. 2(b), inset]. Power laws in the stationary distribution of random segmentation and multiplicative processes have been reported before  and can be obtained by introducing slight modifications, such as reflecting boundaries, frozen segments, merging, or reset events [16–18]. In contrast, the approximate scaling of in Eq. (5) is fundamentally different, as our process does not admit a stationary distribution. The exponents increase due to the finite size of the database.
As shown in Fig. 3(b) we find excellent agreement between the weight frequencies in the chess database and direct simulations of the multiplicative process, Eq. (3) using the arcsine distribution Eq. (2). If the branching ratios are approximated by a uniform distribution the predicted values of are systematically too small, since a uniform distribution yields a larger flow into the absorbing state than observed in the database. Still, due to the asymptotic behavior of for , this approximation yields the correct slope in the log-log plot so that the exponent can be estimated quite well based on Eq. (6) with .
By observing that in Eq. (5) is the th term in a series expansion of an exponential function, we find the weight distribution in the whole game tree as to be an exact Zipf law. For branching ratio distributions different from Eq. (4) the weight frequencies are difficult to obtain analytically. But using renewal theory  the scaling can be shown to hold asymptotically for and a large class of distributions . For this, note that the random variable is a renewal process in . The expectation is the corresponding renewal function related to the distributions of the as . If the expected value is finite and positive [e.g., for the distribution (4) ], the renewal theorem provides
Thus, we obtain and finally
Thus, the multiplicative random process [Eq. (3)] with any well behaving branching ratio distribution on the interval [0, 1] always leads to an asymptotically universal scaling for [compare also the excellent fit of Eq. (8) to the chess data in Fig. 2(a)]. In  the same Zipf-law scaling was found for the sizes of the directory trees in a computer cluster. The authors propose a growing mechanism based on linear preferential attachment. Here we have shown that the exponent for the weight distribution of subtrees in a self-similar tree is truly universal in the sense that it is the same for a much larger class of generating processes and not restricted to preferential attachment or growing.
There are direct implications of our theory to general composite decision processes, where each action is assembled from a sequence of mutually exclusive choices. What in chess corresponds to an opening sequence, may be a multivariate strategy or a customized ordering in other situations. The question how such strategies are distributed is important for management and marketing . One consequence of our theory is that in a process of composite decisions the distribution of decision sequences, or strategies, which occur times shows a transition from low exponents , where a few strategies are very common, to higher exponents , where individual strategies are dominating. This is due to the divergence of the first moment in power laws with exponents smaller than 2 . From [Eq. (6)] the critical number of decisions at which this transition occurs depends logarithmically on the sample size and on the leading order of near zero as
Applied to the chess database with we obtain [see also Figs. 2(b), inset, and 4]. This separates the database into two very different regimes: in their initial phase ( ) the majority of chess games are distributed among a small number of fashionable openings (for , for example, 80% of all games in the database are concentrated in about 23% of the most popular openings), whereas beyond the critical game depth rarely used move sequences are dominating such that in aggregate they comprise the majority of all games (Fig. 4). Note, that this result arises from the statistics of iterated decisions and does not indicate a crossover of playing behavior with increasing game depth.
Our study suggests the analysis of board games as a promising new perspective for statistical physics. The enormous amount of information contained in game databases, with its evolution resolved in time and in relation to an evolving network of players, provides a rich environment to study the formation of fashions and collective behavior in social systems.
- H. Simon, Administrative Behaviour (Macmillan, New York, 1947); I. L. Janis and L. Mann, Decision Making: A Psychological Analysis of Conflict, Choice, and Commitment (Free Press, New York, 1977).
- H. J. R. Murray, A History of Chess (Oxford University Press, London, 2002), reprint.
- C. E. Shannon, Philos. Mag. 41, 256 (1950).
- The Encyclopedia of Chess Openings A–E, edited by A. Matanovic (Chess Informant, Beograd, Serbia, 2001), 4th ed.
- M. Levena and J. Bar-Ilan, Computer Journal (UK) 50, 567 (2007).
- Here we present results based on ScidBase (http://scid.sourceforge.net) with recorded games. Each game was uniquely coded by a string (up to half moves) and the game strings were sorted alphabetically, so that all games following the same move sequence up to a given game depth were grouped together in clusters. Popularities were obtained by counting the cluster sizes .
- G. K. Zipf, Human Behaviour and the Principle of Least-Effort (Addison-Wesley, Cambridge, 1949).
- V. Pareto, Cours d’Economie Politique (Droz, Geneva, 1896).
- D. Sornette, Critical Phenomena in Natural Sciences (Springer, Heidelberg, 2003), 2nd ed.
- M. Mitzenmacher, Internet Math. 1, 226 (2004).
- M. E. J. Newman, Contemp. Phys. 46, 323 (2005).
- J. Willis and G. Yule, Nature (London) 109, 177 (1922).
- H. A. Simon, Biometrika 42, 425 (1955).
- R. A. K. Cox et al., J. Cult. Econ. 19, 333 (1995); ; S. Redner, Eur. Phys. J. B 4, 131 (1998); ; A. L. Barabasi and R. Albert, Science 286, 509 (1999); ; R. L. Axtell, 293, 1818 (2001); ; X. Gabaix et al., Nature (London) 423, 267 (2003).
- K. Klemm et al., Phys. Rev. Lett. 95, 128701 (2005).
- H. Kesten, Acta Math. 131, 207 (1973); ; D. Sornette Phys. Rev. E 57, 4811 (1998); ; D. Sornette and R. Cont, J. Phys. I 7, 431 (1997); ; S. C. Manrubia and D. H. Zanette, Phys. Rev. E 59, 4945 (1999).
- P. L. Krapivsky et al., Phys. Rev. E 61, R993 (2000).
- J. R. Banavar et al., Phys. Rev. E 69, 036123 (2004).
- W. Feller, An Introduction to Probability Theory and Its Applications (John Wiley & Sons, New York, 1971), Vol. 2.
- C. Anderson, The Long Tail: Why the Future of Business Is Selling Less of More (Hyperion, New York, 2006).
- J. L. Gastwirth, Rev. Econ. Stat. 54, 306 (1972).