# Measuring the Non-Transitivity in Chess
## 3 Theoretical Formulations and Methods
### Game Theory Preliminaries
#### 3.1.2 Extensive Form (EF) Games  
EF games [23] model situations where participants take actions sequentially and interactions happen over more than one step. We consider the case of perfect information, where every player has knowledge of all the other player's actions, and a finite horizon, where interactions between participants end in a finite number of steps (denoted as \(K\)). In EF games, an action refers to a single choice of move from some player at some stage of the game. Therefore, the term action space is used to define the actions available to a player at a certain stage of the game.  
**Definition 3**.: _A history at stage \(k\), \(h_{k}\), is defined as \(h_{k}=\{a_{1},...,a_{k-1}\}\), where \(a_{j}=\{a_{j}^{1},...,a_{j}^{n}\}\) for \(j\in[k-1]\). \(a_{j}\) is the action profile at stage \(j\), denoting the actions taken by all players at that stage._The action space of player \(i\) at stage \(k\) is, therefore, a function of the history at that stage (i.e., \(A_{i}(h_{k})\) for \(k\in[K]\), \(i\in[n]\)), as the actions available to a player depend on how the game goes.  
Definition 4: Let \(H_{k}\) be the set of all possible histories at stage \(k\). Let \(A_{i}(H_{k})=\bigcup_{h_{k}\in H_{k}}A_{i}(h_{k})\) be the collection of actions available to player \(i\) at stage \(k\) from all possible histories at that stage. Let the mapping \(s_{i}^{k}:H_{k}\to A_{i}(H_{k})\) be a mapping from any history at stage \(k\) (i.e., \(h_{k}\)) to an action available at that stage due to \(h_{k}\); that is, \(s_{i}^{k}(h_{k})\in A_{i}(h_{k})\)\(\forall h_{k}\in H_{k}\). A strategy of player \(i\) is defined as \(s_{i}=\bigcup_{k\in[K]}s_{i}^{k}\), \(s_{i}\in S_{i}\), where \(S_{i}\) is the strategy space of player \(i\).  
In EF games, behavioural strategies are defined as a contingency plan for any possible history at any stage of the game. According to [PERSON]'s theorem [24], for perfect recall EF games, each behavioural strategy has a realisation-equivalent mixed strategy. Finally, the payoff function of an EF game is defined as the mapping of every terminal history (i.e., the history at stage \(K+1\)) to a sequence of \(n\) real numbers, denoting the payoffs of each player (i.e., \(M_{i}:H_{K+1}\to R\) for \(i\in[n]\), where \(H_{K+1}\) is the set of all terminal histories). However, any terminal history is produced by at least one joint strategy adopted by all players. Therefore, the payoff of a player is also a mapping from the joint strategy space to a real number, consistent with Definition 1.  
An EF game can be converted into an NF game. When viewing an EF game as an NF game, the \"actions\" of a player in the corresponding NF game would be the strategies of that player in the original EF game. Therefore, an \(n\)-player EF game would have a corresponding \(\boldsymbol{\mathcal{M}}\) matrix of \(n\) dimensions, where the \(i^{\text{th}}\) dimension is of length \(|S_{i}|\). The entries of this matrix correspond to a sequence of \(n\) real numbers, representing the payoff of each player as a consequence of playing the corresponding joint strategies.