# Measuring the Non-Transitivity in Chess
## 3 Theoretical Formulations and Methods
### Non-Transitivity Quantification
#### 3.3.1 Payoff Matrix Construction
Therefore, we used the number of cycles of length three (i.e., rock-paper-scissor or RPS cycles) passing through every pure strategy as a proxy to quantify non-transitivity. To obtain the number of RPS cycles passing through each pure strategy, an adjacency matrix is first formed from the payoff matrix. Letting the payoff matrix from Section 3.3.1 be \(\mathbf{\mathcal{M}}\), the adjacency matrix \(\mathbf{\mathcal{A}}\) can be written as \(\big{\{}\mathbf{\mathcal{A}}_{i,j}\big{\}}_{i,j=1}^{|S_{i}|}\), where \(\mathbf{\mathcal{A}}_{i,j}=1\) if \(\mathbf{\mathcal{M}}_{i,j}>0\), and \(0\) otherwise. Theorem 4: _For an adjacency matrix \(\mathbf{\mathcal{A}}\) where \(\mathbf{\mathcal{A}}_{i,j}=1\) if there exists a directed path from node \(n_{i}\) to node \(n_{j}\), the number of paths of length \(k\) that start from node \(n_{i}\) and end on node \(n_{j}\) is given by \((\mathbf{\mathcal{A}}^{k})_{i,j}\), where the length is defined as the number of edges._

The proof of Theorem 4 can be found in Appendix C. By Theorem 4, the number of RPS cycles passing through a strategy can thus be found by taking the diagonal of \(\mathbf{\mathcal{A}}^{3}\). Note that this does not apply to cycles with length of more than three, as the diagonal element of \(\mathbf{\mathcal{A}}^{n}\) would include cycles with repeated nodes. Finally, the measures of transitive strength used in this method are identical to those applied in Section 3.3.2, but applied to single strategies instead of clusters. This, therefore, completes the quantification of non-transitivity by counting RPS Cycles. ### Relationships between Existing Rating Systems

As mentioned in Section 2, there are various chess player rating systems throughout the world, each of which is only valid for the pool of players over which the system is defined. As we used game data from Lichess and FICS to perform non-transitivity quantification, the results are therefore not directly applicable to different rating systems, such as USCF and FIDE. An investigation into the mappings between these rating systems is, thus, required. We conducted a short experiment to obtain mappings between the rating systems of Lichess, USCF, and FIDE. The data set for this experiment was obtained from Chess-Goals [29], which consisted of player ratings from four sites: Chess.com [30], FIDE, USCF, and Lichess. To investigate the mappings, we created three plots representing the mappings between pairs of rating systems: Lichess to USCF, Lichess to FIDE, and USCF to FIDE. A linear model was then fitted for each plot by MSE minimisation. ### Implications of Non-Transitivity on Learning

Based on the discovered geometry, we also investigated the impact of non-transitivity on multi-agent reinforcement learning (MARL) [31]. Specifically, we designed experiments to verify the influence of non-transitivity on a particular type of MARL algorithm: Population-based learning [32; 33; 34; 35]. This is a technique that underpins much of the existing empirical success in developing game AIs [36; 37]. In fact, for simulated strategies [5], it has been found that, if the spinning top geometry exists in a strategy space, then the larger the non-transitivity of the game, in terms of layer size (for a \(k\)-layered geometry) or Nash cluster size (for Nash Clustering), the larger the population size required for methods such as fixed-memory Fictitious Play to converge. We attempted to verify whether the above conclusion still holds when real-world data are used instead. Furthermore, observing the above convergence trend with respect to the starting population size provides even stronger evidence for the existence of the spinning top geometry in the strategy space of real-world chess. As a proxy for a population-based training method, fixed-memory Fictitious Play starts with a population (or set) of pure strategies \(P^{0}\), of fixed size \(k\). The starting pure strategies in \(P^{0}\) are chosen to be the \(k\) weakest pure strategies, based on the win-rate against other pure strategies, as shown in Equation (4).