# Measuring the Non-Transitivity in Chess
## 3 Theoretical Formulations and Methods
### Non-Transitivity Quantification
#### 3.3.1 Payoff Matrix Construction  
The raw data for the experiments were game data stored in Portable Game Notation (PGN) format [26], obtained from two sources. The primary source was the Lichess [9] database, which contains games played from 2013 until 2021. The second data set was sourced from the FICS [10] database, and we used games from 2019, as it contained the highest number of games. Figure 2 shows an example of a chess game recorded in PGN format. Altogether, we collected over one billion match data records from human players. In order to process such a large amount of data, we introduced several novel procedures to turn the match records into payoff matrices. The first processing step was to extract the required attributes from the data of every game. These include the outcome of the game (to create the payoff matrix) and the Elo ratings of both players (as a measure of transitive strength). The second step concerned the number of games taken from the whole Lichess database. As of 2021, the Lichess database contains a total of more than 2 billion games hosted from 2013. Therefore, sampling was required. Games were sampled uniformly across every month and year, where the number of games sampled every month was 120,000 as, for January of 2013, the database contains only a little more than 120,000 games. To avoid the influence of having a different number of points from each month, the number of games sampled per month was, thus, kept constant. In earlier years, sampling uniformly across a month was trivial, as games from an entire month could be loaded into a single data structure. However, for months in later years, the number of games in any given month could reach as many as 10 million. Therefore, a two-stage sampling method was required, as shown in Algorithm 1. ```
Inputs: Set of \(m\) objects, i.e., \(U=\{U_{1},...,U_{m}\}\), number of objects to sample \(d\in\mathbb{N}_{1}\);  Divide \(U\) into \(k\) chunks \(H_{1},...,H_{k}\), each of size \(h\) (i.e., \(h\times k=m,h,k\in\mathbb{N}_{1}\)), where \(H_{i}\cap H_{j}=\emptyset\ \forall i\
eq j\), \(i,j\in[k]\), \(U_{j\in[k]}\ H_{j}=U\);  Initialize \(G=[]\); for\(i\in[k]\)do  Sample \(d\) objects uniformly from \(H_{i}\), forming \(t\);  Append all elements in \(t\) to \(G\);  end for  Sample \(d\) objects uniformly from \(G\), forming \(F\);  Output \(F\) as the set of \(d\) objects sampled uniformly from \(U\). ```  
**Algorithm 1**Two-Stage Uniform Sampling. Algorithm 1 can be proven to sample uniformly from \(U\); that is, the probability of any object in \(U\) being sampled into \(F\) is \(\frac{d}{m}\). The proof is given in Appendix C. Note that, for FICS, the number of games in every month was relatively small, such that the database could be sampled directly. The third processing step concerned discretisation of the whole strategy space to create a skew-symmetric payoff matrix representing the symmetric NF game. For this purpose, a single game outcome should represent the two participants playing two matches, with both participants playing black and white pieces once. We refer to such match-up as a  
Figure 2: Lichess PGN format. two-way match-up. A single strategy, in the naive sense, would thus be a combination of one contingency plan (as defined in Definition 4) if the player plays the white pieces with another one where the same player plays the black pieces. However, such a naive interpretation of strategy would result in a very large strategy space. Therefore, we discretised the strategy space along the transitive dimension. As we used human games, we utilised the Elo rating of the corresponding players to measure the transitive strength. Therefore, given a pair of Elo ratings \(g_{1}\) and \(g_{2}\), the game where the white player is of rating \(g_{1}\) and the black player is of rating \(g_{2}\), and then another game where the black player is of rating \(g_{1}\) and the white player is of rating \(g_{2}\), corresponds to a single two-way match-up.