Difference between revisions of "Combinatorial game theory"

Revision as of 03:53, 2 May 2024

This page is about the combinatorial game theory of Hex. For combinatorial game theory in general, see Wikipedia.

Combinatorial game theory is a formalism that can be used to analyze sequential two-player perfect information games. It was introduced by John H. Conway in the 1970s, and has since been applied to a variety of games, including Hex. One of the central ideas of combinatorial game theory is that games can be split into multiple components (for example, separate regions of the Hex board), and each component analyzed separately. Combinatorial game theory can be used to reason about such concepts as domination, reversibility, inferior moves, and equivalence of positions.

Concepts

In this section, we introduce some of the main concepts of combinatorial game theory, as it relates to Hex. We do this mostly by example. A more mathematical treatment follows later.

How the game ends

Normally, a game of Hex ends either when a player has connected their edges, or when a player resigns. However, for the game theoretic analysis, it is easier if we imagine that the game continues until the board is completely filled with stones. Notice that after one player has a winning path, filling the rest of board with stones can no longer change who the winner is. So we are free to assume that the game continues until there are no more empty cells on the board. We will make this assumption throughout this article.

Regions

By a region of the Hex board, we just mean a set of one or more cells on the board. The region may include special features such as board edges, and it can optionally be pre-populated with some stones.

Examples.

• The whole board is a region.

• A single empty cell is a region.

• The 3-cell corner is a region.

• The following region is completely surrounded by red and blue stones, with three groups or red stones (and therefore three groups of blue stones) in the boundary. This kind of region is called a 3-terminal region.

Outcomes

By an outcome for a region, we mean one of the possible ways of completely filling it with stones. Since we assume that the game continues until the board is completely filled, the outcome describes what the region may look like at the end of the game. We say that two outcomes for the same region are equivalent if for every way of filling the rest of the board (i.e., the part outside of the region) with stones, the first outcome produces the same winner as the second one. Since equivalent outcomes produce the same winner in all situations, we often consider them to be equal, i.e., when we say "the same outcome", we mean "equivalent outcomes".

Examples.

• When the region is the whole Hex board, there are only two possible outcomes, namely, "Red wins" and "Blue wins".

• When the region is a single empty cell, there are two possible outcomes, namely, "Red gets the cell" and "Blue gets the cell".

• For the 3-cell corner, there are 8 possible ways of filling it with red and blue stones. However, most of these are equivalent, and we end up with only 3 non-equivalent outcomes:

• Outcome 1: Red gets everything. This outcome can be achieved in 3 possible ways; notice that they are equivalent because the blue stone is dead in all cases.

  Outcome 2: Blue gets everything. This outcome can also be achieved in 3 possible ways.

  Outcome 3: Red and Blue each get half of the corner. This outcome can be achieved in 2 possible ways, because the corner cell is dead.

• For a 3-terminal region, there are 5 possible outcomes. Although there are many ways of filling the region with red and blue stones, at the end of the game, all that matters is which terminals are connected to each other. Suppose Red's terminals have been numbered 1, 2, and 3. Then from Red's point of view, the 5 outcomes are:
  • Red connects all 3 terminals.

  • Red connects only terminals 1 and 2.

  • Red connects only terminals 1 and 3.

  • Red connects only terminals 2 and 3.

  • Red connects none of her terminals.

Positions and options

Consider a region of the Hex board. By a position in the region, we mean the state of the region after zero or more moves have been played, or in other words, a version of the region in which zero or more of its emtpy hexes have been filled with stones (of any color).

Players change positions by making moves. In a given position, we say that Red's options are all positions that Red can reach by making a single move in the region, and Blue's options are all the positions that Blue can reach by making a single move in the region.

Example. Consider the position

In this position, Red has two options:

Also, Blue has two options:

Combinatorial game notation

In combinatorial game theory, the players are called Left and Right. In Hex, Red is Left and Blue is Right. We therefore call Red's options left options and Blue's options right options.

In combinatorial game theory, the word game is used to mean position. Thus, an unfinished game has left and right options that are themselves games.

The notation for a combinatorial game is G = {G₁, …, Gₙ | H₁, ..., Hₘ}, where G₁, …, Gₙ are the left options and H₁, ..., Hₘ are the right options. Note that the game is enclosed in curly braces, and a vertical bar is used to separate the left options from the right options.

Example. Consider the position from the previous example:

As we saw, G has two left options G₁ and G₂ and two right options H₁ and H₂. We can write

G = {G₁, G₂ | H₁, H₂} =

Recursively, each of the positions G₁, G₂, H₁, H₂ is also a combinatorial game with a left and right option. For example,

G₁ = =

By recursively decomposing all options, we arrive at this representation of the game G:

G =

When a position has no empty cells, it is called an atomic position. Atomic positions have no left or right options and can cannot be further decomposed. Instead, we can replace each atomic position by the associated outcome. For example, the position G in this example is a 3-terminal position. Let us write "⊤" (pronounced "top") for the outcome "Red connects all three terminals", "⊥" (pronounced "bottom") for the outcome "Red connects no terminals", and "a" for the outcome "Red connects the right two terminals, but not the left one". With these notations, the combinatorial game G can be more succinctly described as:

G = {​{⊤|⊤}, {⊤|a} | {a|⊥}, {⊤|⊥}}.

Remark. In a combinatorial game, the players do not always alternate. For example, in the game G, Red can move to the left option G₂ = {⊤|a}. Then Red can move again to the left option ⊤. The reason that players are not necessarily alternating is that the combinatorial game is meant to represent play in a region. For example, Red might move in the region, Blue might move somewhere outside the region, and then Red might move in the region again. Thus, although the players were alternating in the game at large, within the region, Red has made two consecutive moves.

Simplification of combinatorial games

The combinatorial game notation we introduced in the previous section is not very compact. In fact, it is basically a representation of the entire game tree, i.e., a description of all moves that both players could make in every possible position of the game. For a position with more than a few empty cells, the game tree is much too large to write down in its entirety.

Fortunately, combinatorial games can be simplified. Much like the rules by which school children learn to simplify (5 + 8) * 2 to 13 * 2 and then to 26, there is a specific set of rules for simplifying combinatorial games and calculating their value. These rules are a bit complicated and we will describe them in more detail in the mathematical section below. However, the main point is that the rules are mechanical and universal: every finite combinatorial game can be simplified to a unique value, and this can be done either by hand or by using a "CGT calculator". Moreover, when a Hex game has been decomposed into several disjoint regions, we can in principle calculate and simplify the value of each region independently, and then combine them to determine the value, and therefore the winner, of the entire game. In practice, this calculation is too hard when there is lots of empty space on the board, but can be feasible for certain end game positions.

Example. Once again, we consider the position from the previous example:

As we saw, the combinatorial notation for this position is

G = {​{⊤|⊤}, {⊤|a} | {a|⊥}, {⊤|⊥}}.

Using the simplification rules we will discuss in more detail later, this can be simplified (or "evaluated") to

G = {⊤ | {a | ⊥}}.

The English explanation of this value is something every Hex player will agree with: If Red moves first in the region, Red moves at x connects all three terminals. After this, the region is settled, i.e., neither Blue nor Red wants to make another move there. If Blue moves first in the region, Blue moves at x and threatens to connect all of Blue's terminals, but Red can reply at y to achieve outcome a. In this latter case, Red connects terminals 2 and 3, but not terminal 1.

Mathematical details

To be written.

References

• J. H. Conway, "On Numbers and Games". 1st edition 1976. 2nd edition, A. K. Peters, 2001.
• P. Selinger, "On the combinatorial value of Hex positions", Integers 22:G3, 2022. Also available from arxiv:2101.06694