2-player games: Ergodic Theory and Ramsey Theory results

This post aims to summarise key results from the literature of two-player games, both finite (with an absorbing state) and infinite (without an absorbing state). Canonical examples include competitive or recreational games like chess, tic-tac-toe (including the ultimate version), and attacker-follower games (known as Stackelberg games in game-theoretic economics).

On Math Stack Exchange, for over than 7 years ago, the user account of M. Azad asked – what is a chess piece mathematically?. The question sought to find out what the maths community thought about a suitable abstract framework that can unify in the nature of every possible move of every piece in a chessboard, with one potential candidate being a graph. The response by J.D. Hamkins highlighted that chess game could be seen as being (isomorphically) played on game trees, with parents nodes and child nodes hosting the current game state and next-step game state respectively. Once a player wins the game, their state in the tree has reached the terminal node (the absorbing state). In another intriguing suggestion, Terry Tao drew a parallel between chess and fluid dynamics, by pointing out that chess pieces could be seen as possible values of Lagrangian coordinates, while chessboard squares are possible values of Eulerian coordinates. Further to his response, J.D.H. reformulated his question by asking when does a game tree become the game tree of a board game, to which he elaborated it to be the case when the game tree of a board game has only finitely many isomorphism types of its lower cones (a specific type of geometric structure in a tree; a convenient reference here). With the above discussion in the background, we do get an intuition that there is some sort of cyclical argument here; a finite (2-player for simplicity) game with an absorbing state, with its rules, constraints, and goals expressed in a tree framework, would have to have its geometric structure also of finitely many types. The next question, certainly is, is there any formal result that underscores this intuition, and if so, how does it extend to infinite-games?

Luckily, we do not need to go more than 112 years ago to answer this question, as the German logician and mathematician Ernest Zermelo, after his ICM 1912 talk, published (in German) some of his key findings for the two-person games, the most famous of which is the fundamental theorem of finite games (which is now known as Zermelo’s theorem). The theorem states that, if one assumes in a 2-person game that: (i) no probabilities or chance events are involved and both players have strictly opposite motivations; (ii) both finite and infinite number of positions in the game are possible, Zermelo answered two questions. The first question (Q1) asked how to mathematically define the winning position of either player and question 2 (Q2) asked the number of moves required to force the win. In response to Q1, Zermelo constructed a nonempty set which contains all possible sequences of moves such that one player wins irrespective of how other player plays. Note that Zermelo’s construction is not a game-specific one but generic, but at least answers the Math Stack Exchange question for the winning move [1]. In the case when the set above is empty, the best a player could achieve is a draw. In response to Q2, Zermelo used proof by contradiction that should there be more number of moves than number of positions, player can always play the repeated move (pigeonhole principle) prior to the first move and thus, ensure that the upper bound of the number of moves is the number of positions in the game. This time, it is a non-constructive proof, and thus, Zermelo’s proofs only supplies further evidence to the conjectural responses by J.D.H. above. In reference to Q1 above, we ask what would have happened if, not just one, but both players would have their best game scenario as draw. This would mean that the game would continue indefinitely, and thus, would not have any finite isomorphism type of some geometric structure specific to the game. An “infinite game” of such kind, thus naturally emerge as one possible scenario from a given 2-player game.

The summary of Zermelo’s results above, thus points to an intriguing question that will be the focus of this blogpost: can we identify a potential formalism that distinguishes finite 2-player games from infinite 2-player games? In other words, this question can be reformulated as: can we identify formalism for the draw scenario in a 2-player game (when no players win)? If so, what is the computational complexity of such an outcome? Knowing the computational complexity of a draw outcome is a useful information, as this can help the players to not invest cognitive resources beforehand for a game, which has a higher likelihood of a draw. This is something players often realise mid-way of the game: for example, in a simple tic-tac-toe game, after one or two moves, it becomes apparent to both players that there would be a draw, so they do not continue drawing the circles and crosses. The best possible case we want to explore in this blogpost is: how feasible it is to identify the chance of a draw before the game starts and after the first move?

Let us compile our questions here:

Q3: Can we identify a theoretical formalism for a draw outcome in a 2-player game? How to find out the computational complexity of such an outcome?
Q4: How feasible is it to identify the chance of a draw, (a) before the game starts and (b) after the first move by both players?

Let us now shift gears to trace some conceptually much abstract results in graph theory, that can tentatively be connected to 2-player games. By exploring the literature of graphs (in particular, the existing of monochromatic cliques and related other subgraphs), we could try to identify conceptual insights from such results, before being able to pose a 2-player tree problem (upon acknowledging the response by J.D.H. that a tree could be a suitable framework) towards the end of this blog in the format of Q3 and Q4. Our hope before beginning this literature-search is that, the existence of subgraphs satisfying certain properties, is potentially similar in concept to the geometric structure in a game-tree that annotate a winning strategy for one player; though it is also true that the methods for obtaining such geometric structures for tree would vastly differ from those for graphs, but we defer those technical difficulties to later, after we pose a much precise question towards the end of this blogpost.

1. Hypergraph Ramsey: Let ${K}$ be a set of colours, ${V}$ a vertex set, and ${k \in \mathbb{Z}_{\geq 1}}$ . Define a hypergraph ${G = (V, E)}$ of order ${k}$ on ${V}$ , where $\displaystyle E : \binom{V}{k} \rightarrow K$ is a function assigning a colour to each ${k}$ -element subset of ${V}$ . Here, $\displaystyle \binom{V}{k} := \left\{ e \subseteq V : |e| = k \right\}$ denotes the set of all ${k}$ -element subsets of ${V}$ .

A hypergraph of:

order ${k = 1}$ is vertex-colouring,
order ${k = 2}$ is an edge-colouring,
order ${k = 3}$ is a triangle-colouring,
order ${k = 4}$ is a quadrilateral-colouring, and so forth.

A hypergraph ${G}$ is said to be monochromatic if ${E}$ is constant. This intuitively means that independent of my $k$ value or how I choose my $k$ vertices, the way I assign colours to $k-$ element vertices would be the same. For example, for an edge $(k=2)$ colouring would be the same for all edges.

For any subset ${W \subseteq V}$ , define the induced subhypergraph:

$\displaystyle G|_W := \left(W, E \binom{W}{k} \right)$

Theorem 1 Let ${K}$ be a finite set, ${k \geq 1}$ , and let ${G = (V, E)}$ be a ${K}$ -coloured hypergraph of order ${k}$ on a countably infinite vertex set ${V}$ . Then ${G}$ contains arbitrarily large finite monochromatic subhypergraphs.

This theorem can be conceptually translated to a 2-player game, if we assume that that meta game exists in a monochromatic hypergraph. Consider this argument: if the hypergraph vertices are considered as nodes for all possible moves in a 2-player game (choosing a game such as chess with $10^{120}$ moves or super tic-tac-toe with $10^{15}$ is more feasible, as the vast set of moves can be approximated as the nodes of a hypergraph with countably infinite vertex set), then the theorem guarantees the existence of an arbitrarily large finite monochormatic subhypergraph. By carefully choosing six colours to represent the winning, neutral, and defeating moves of both players, the theorem guarantees the existence of a ‘finite monochromatic subhypergraph’, say $FMS_{i}$ for which the way I assign my set of winning, neutral, and defeating moves of player $i$ is constant. In other words, upon choosing any k-element subset of game nodes within $FMS_{i}$ , it is deterministic, and in fact, a constant-complexity task, that of querying if a given move in the game-graph is rewarding/neutral/unrewarding for the player $i$ .

There are many simplifications in the framework above, which makes such an existence a distant dream. Firstly, it is not straightforward to define what is a neutral move, in comparison to winning/defeating moves (which are, for instance, much simpler to define in chess). A neutral move could be a winning or defeating move in hindsight, and hence, much harder to define formally. Secondly, we are not sure how well approximately we will be able to meet the requirement of having an infinite vertex set for the hypergraph upon choosing a game of chess or super tic-tac-toe. It can be only clear after defining the problem precisely; it is the relative magnitude of the K-moves of a player (modelled in the $FMS_{i}$ to all possible moves (modelled in infinite hypergraph $G$ ) in the game that would certify the feasibility of our approximation.

It is possible to switch to a different abstract framework, which can get rid of the second simplification above, and possibly, suggest further new insights.

2. Hales-Jewett: Let there be a finite alphabet ${A}$ and ${A^{<\omega}}$ be the free semigroup generated by ${A}$ , which is the set of all finite non-empty words using the alphabet ${A}$ , with concatenation as the semigroup operation. Now, upon adding a new “wildcard” letter ${*}$ to the alphabet ${A}$ , creates a larger semigroup $\displaystyle (A \cup \{ * \})^{<\omega}$ . Given any letter ${x \in A}$ , let us define a semigroup homomorphism $\displaystyle \pi_x : (A \cup \{ * \})^{<\omega} \rightarrow A^{<\omega}$ such that every occurrence of ${*}$ in a word is substituted with ${x}$ , and all other letters are left unchanged. Let us also define a combinatorial line in ${A^{<\omega}}$ to be any set of the form $\displaystyle \{ \pi_x(w) : x \in A \}$ for some ${w \in (A \cup \{ * \})^{<\omega}}$ . For instance, If ${A = \{ a, b, c \}}$ , then the set $\displaystyle \{ abaaac, abbbc, abcccc \}$ is a combinatorial line, generated by the word $\displaystyle w = ab * * * c.$

Theorem 2 (Hales-Jewett) Let ${A}$ be a finite alphabet. If ${A^{<\omega}}$ is finitely coloured, then one of the colour classes contains a combinatorial line.

This theorem guarantees that one of the colour classes (set of words in the semigroup that have been assigned the same colour) consists of the combinatorial line. Let us now translate this theorem, conceptually, to a 2-player game, and churn new insights. The first thing to notice is that the alphabets are finite in capacity, which can be mapped to the positions on the board, for both players (for example, in chess, there would be 64*2=128 alphabets). The words in the free semigroup constitute of the set of moves on the board each player make chronologically. Note that there are two free semigroups for both players, which can be concatenated to one, for simplicity. The addition of a new wildcard letter $*$ is like annotating a fictitious new position in the board (for the symmetry purposes, we might have to introduce multiple such wildcard letters, such as sixteen in tic-tac-toe to make it 5X5, thirty-six in chess to make it 10X10) which despite being a computationally costly step, but eases with the analysis that follows (note that, this is still not that bad compared to apprpoximating an infinite graph to be finite graph as in Theorem 1 above, and could be seen as a formalism for that, eventually getting rid of the “second simplification” alluded to in the discussion above). Let us now categorise the moves by player $i={1,2}$ as winning, neutral, and losing (similar to before for Hypergraph Ramsey) and assign them a fixed colour $c \in K$ , denoted by $W_{i}, N_{i}, L_{1}$ . We can do the same for when $*$ is introduced, say by, $W^*_{i}, N^*_{i}, L^*_{i}$ . The combinatorial line in this context is then a set of maps (much precisely, semigroup homomorphisms) from $W^*_{i}, N^*_{i}, L^*_{i}$ to $W_{i}, N_{i}, L_{i}$ (total 6^6 = 46656 such maps, including injective, surjective, and bijective). The Hales-Jewett theorem states then that the combinatorial line defined above is assigned one colour class. In other words, the set of 46656 maps from the fictitious to the original game board are assigned the colour of the element from the codomain to which they map to. The certainty that for each colour there would always be a combinatorial line, translates in the 2-player game, to a certainty that for one of the six possible types of sequence of moves (for both players), it is possible to build a set of maps from the fictitious larger board to the original game board.

Though this might seem a powerful potential result, as compared to the previous one, it suggests that it is possible to completely get rid of the infinite meta-game framework requirement as in Theorem 1 above, by building a fictitious, larger, but still finite board such that one of the player has a certain sequence of moves which are mapped to from another sequence of moves from the fictitious board, but not necessarily of the same player and not necessarily of the same type. Simply speaking, had the players been originally playing in the fictitious board where, say, the game was dominated by the winning sequence of moves by player 2, then this can be mapped directly to, say, a winning sequence of moves by player 1. This theorem, naively speaking, potentially suggests that we can not say, anything with certainty about the strength of a player when the complexity of the gaming board is reduced, and the winner might become loser and so forth.

Having established much preciser formulations for the 2-player games above, let us acknowledge that the clear formalism for winning/neutral/defeating moves is still not clear. We now explore one way to get around this problem by conditioning on the type of such moves by a certain player, and ask what is the range of the size of meta game-board?

3. Ramsey number:

Let $R(k)$ be the minimum $n \in \mathbb{N}$ such that every red–blue edge-colouring of $K_n$ (complete graph on $n$ vertices) contains a monochromatic clique on $k$ vertices. In other words, to get a monochromatic clique on $k$ vertices, at minimum, how large must the graph be?

The key results in this direction are the known bounds. Ramsey proved in 1930 that $R(k)$ is finite for all $k \in \mathbb{N}$ . A lower bound for the Ramsey number was found by Erdős to be: $\displaystyle R(k) \geq 2^{k/2}$ .

The upper bound established in 2023 is as follows.

Theorem 3: $\displaystyle R(k) \leq (4 - \epsilon)^k$

Some additional comments on recent numerical developments in Ramsey numbers are below [2].

Let us see how this theorem might translate in the context of 2-player game, and in the modification to the Section 1 interpretation above. Existence of a finite Ramsey number suggests that upon fixing a certain monochromatic clique of $k$ vertices, which could denote a specific sequence of moves (or the combination of multiple of those) by either player, the size of the graph which contains that, has a lower and an upper bound. In simpler words, upon fixing a certain sequence or the collection of moves in a monochromatic clique, the permissible graph, with its red-blue colouring of its edges – which are the ways of assigning colours (winning/neutral/losing moves by either player) to it, has a size which maintains a lower and an upper limit (with the most advanced tools we have in hand).

This potentially allows us to compare the size range of the graph for different types of monochromatic cliques. For example, does the winning strategy of player 1 covers a bigger span of graph-size in comparison to the winning strategy of player 2? Knowing an answer to this question would be very helpful in designing computationally efficient game engines which can aid the players in performing the moves as demanded by them.

The natural next question arises: does this count as a formalism for the winning/neutral/defeating moves by either player?

To answer this question, we would get specific, and take an example case of the Ultimate Tic-Tac-Toe (UTTT) game, which is mid-way in complexity between chess and simple Tic-Tac-Toe game.

4. Minimum Working Example (MWE) Case for UTTT:

From 2013 to 2020, research in UTTT has advanced both artificial intelligence techniques for gameplay and the mathematical understanding of UTTT’s game structure. In 2013, Lifshitz and Tsurel conducted a comprehensive study of AI methods for Ultimate Tic-Tac-Toe, comparing the performance of minimax, alpha-beta pruning, and expectimax algorithms. In 2016, George and Janoski focused on the symmetries inherent in Super Tic-Tac-Toe. They established that both the set of game boards and the set of games themselves are acted upon by a dihedral group of rotations and reflections. This formal group action enabled the classification of isomorphic game states and the systematic enumeration of structurally equivalent winning boards. Notably, they identified 228 distinct isomorphism classes of winning boards containing eight elements on a 2×2 UTTT board. Their analysis provided a rigorous framework for understanding redundancy in winning configurations and set the stage for further combinatorial investigations.

In 2020, Bertholon and collaborators provided the first formal proof of an optimal strategy for the first player in Ultimate Tic-Tac-Toe. They demonstrated that the first player can force a win in at most 43 moves by adhering to a precise sequence of actions that divides the game into an opening, middlegame, and endgame phase. The optimal strategy emphasises early control of the central field and forces the second player into constrained and progressively weaker responses. Furthermore, they established that, with perfect defense, the second player can prolong the game to at least 29 moves before succumbing. These findings delivered tight bounds on the length of an optimally played game and highlighted the critical initial moves that any winning first-player strategy must contain.

Certainly, we can see in the literature review of UTTT above (despite very sparse), that there is some evidence of upper (43 moves) and lower (29 moves) limits on the conditioning of the winning potential of one player. This demands a much clear formalism to establish upper and lower limits, for a wider class of winning strategies, and not necessarily of the empirical type discovered by Bertholon and collaborators. While their work provides rigorous theoretical bounds and a winning strategy for the first player, there is no computationally efficient engine that currently operationalises these findings in a live gaming scenario. The proposed engine will encode the optimal move sequences, support adaptive deviation handling against imperfect opponents, and provide a modular architecture which is suitable for AI benchmarking and human-vs-AI play.

Ensuring that the engine can compute moves rapidly under practical constraints, enabling interactive applications, and also featuring visualisation tools to illustrate game-tree traversal and strategy phases, can enhance its value for research and education.

It is evident that the design of a UTTT game engine in the style prescribed above, tentatively answers both questions, Q3 and Q4, which we posed above.

To summarise, in this blogpost, we identified existing wheels such as the Zermelo’s theorem, hypergraph Rasmey theorem, Hales-Jewett theorem, and Ramsey numbers and their translations to 2-player games. We started with asking for a formalism to distinguish finite games from infinite games, but ended up focusing more clearly defining formalism for a winning/neutral/defeating moves by either player in the game. This led us to acknowledge the range of complexity (upper and lower limits) of such moves. To ensure exemplification of these rather abstract ideas, we choose to do a case study of Ultimate Tic-Tac-Toe game, which is a 3X3 version of the simple Tic-Tac-Toe game. Existing papers in the literature from 2013 to 2020 pointed out to us that there is a need for constructing of a gaming engine that can be adpative and comprehensive with the gaming tree traversal (as suggested in the Maths Stack Exchange by J.D.H.) and strategy phases. This by no means is a short-term project, but demands a dedicated attention to tackling the order of 10^12-10^15 moves (we do not know exact possible states yet).

References:

[1] The Zermelo’s proof for the Q1 will be filled in here in due time.

[2] With reference to key literature here, the IP algorithm or optimisation methods have been developed to find lower bounds of Ramsey numbers. The problem of determining the Ramsey number can be modeled as a Stackelberg problem by devising a game where the leader maximises q and two followers attempt to find blue and red cliques of size at most m and n respectively. This convert the problem to a bi-level integer programming problem under certain constraints, which can then be transferred to a single-level integer programming problem. Upon applying an efficient branch-and-bound procedure, Furing, Ljubic, Sejundo 2021 were able to improve 17 best-known lower bounds of R(3,n) for n between 26 and 46. An updated survey of Ramsey numbers is given in Small Ramsey Numbers by Stanisław P. Radziszowski.

[3] A nice discussion in Lean Zulip Chat regarding the “need for an interface where people can play such games, visualise a position on a per-game basis, and then, certainly have an algorithm for engine to play for the player” Buzzard, K. https://leanprover.zulipchat.com/#narrow/channel/113488-general/topic/Combinatorial.20game.20theory.20repository/with/528477994

2-player games: Ergodic Theory and Ramsey Theory results

Published by Saksham

Leave a comment Cancel reply

Share this:

Related

Published by Saksham

Leave a comment Cancel reply