5
$\begingroup$

The surreal numbers in Combinatorial Game Theory only work for certain classes of games (e.g. they must satisfy normal play convention). This rules out even reasonable games with fairly well-understood scoring (such as Go). In that case, we approximate Go with a normal-play convention game where the last player to move wins and take the score of that (Mathematical Go: Chilling Gets the Last Point). Dots and Boxes have been analyzed using Nimbers.

Can we analyze games of Connect-4? Is it possible to quantify the degrees of advantage for one side or another using surreal numbers? Here, whoever moves first loses so this game is a "number", if I recall, as the first move is not desirable for either side.

What could be the value of this position? The reasoning could go:

  • $\color{#5256ED}{\textbf{blue}}$ has two potential connect 4's along the diagonal if $\color{#F76353}{\textbf{red}}$ moves first in the left or right column
  • $\color{#F76353}{\textbf{red}}$ must also avoid moving first in the 3rd column
  • if $\color{#5256ED}{\textbf{blue}}$ moves first in the 3rd column, $\color{#F76353}{\textbf{red}}$ must follow with the same, for the win
  • theoretially if $\color{#5256ED}{\textbf{blue}}$ moves twice in the right column, $\color{#F76353}{\textbf{red}}$ can place a chip to win
  • Columns 1 and 5 (from the left seem to have effect on the game leaving columns 1, 3 and 7
  • ...

Very simplistically there is a $\color{#5256ED}{\textbf{3}}-\color{#F76353}{\textbf{1}}$ advantage, but the game tree should cover all this information and provide a "numerical" answer of sorts.

enter image description here

$\endgroup$
  • 1
    $\begingroup$ One model that people sometimes use for games that don't have normal play convention is to define a left winning position as on:={on|} and a right winning position as off:={|off}; these are not finite games but often positions involving them resolve in order to not resolve them (e.g., such positions may pass through $0$). One could try to do that sort of analysis for connect four. $\endgroup$ – Gabriel C. Drummond-Cole Jun 29 '15 at 16:24
  • $\begingroup$ Can you explain what you think is the obstacle to defining a numerical value for Connect 4 games? Why does it not work to simply start from completed games and define values backwards from there in the usual combinatorial game theoretic way? $\endgroup$ – Greg Martin Jun 29 '15 at 18:17
  • $\begingroup$ @GregMartin for one thing disjunctive sums don't make much since since that would involve moving twice in one position. perhaps in the limit of a very large board $6 \times 100$ or taller or wider. $\endgroup$ – john mangual Jun 29 '15 at 18:26
  • 1
    $\begingroup$ I feel like disjunctive sums would just mean multiple boards; and standard combinatorial game theory valuations are valid regardless of how many times the next player is allowed to move (each move changes the valuation in a way independent of who gets to move thereafter). $\endgroup$ – Greg Martin Jun 30 '15 at 19:38
  • 1
    $\begingroup$ Just for the record, Connect 4 has already been solved around 1988 tromp.github.io/c4/c4.html $\endgroup$ – François Brunault Jul 2 '15 at 9:58
4
$\begingroup$

There is a natural definition of a "connect-four monoid". I don’t know if it's mentioned in the literature, and I don’t know what it looks like, apart from some observations (below) that show that it is not a group. If there is a reasonably simple description of this monoid, it could lead to a “solution” of connect-four which is applicable to arbitrary board sizes. But it might be too complicated to be of any help.

To begin with, one should think about how the game naturally splits into components, and what it means for a game position to be the “sum” of its components.

As the game proceeds, the set of unoccupied sites can separate into components that do not interact with each other. In such a situation, a move consists in making a move in one of the components (this is like the classical theory), and winning in one component means winning the entire game (this differs from the so-called normal playing convention where the game ends when a player is unable to move).

In classical combinatorial game theory, games are classified into four outcome classes: Positive (Left wins no matter who starts), Negative (Right wins), Fuzzy (Player to move wins) and Zero (Player not to move wins). In a game like connect-four that can end in a draw, there are nine outcome classes, namely the functions from {Red to move, Blue to move} to {Red wins, Draw, Blue wins}.

Just as in the classical theory, the set of positions is an abelian monoid under addition (position means what the board looks like, without information about who is to move), and one may define two positions $X$ and $Y$ to be equivalent if for every $Z$, the games $X+Z$ and $Y+Z$ belong to the same outcome class.

For instance, all positions with an even number of unoccupied sites, and where none of the players can win, are equivalent. These might be called “zero-positions”, since they include the empty position (neutral element of the monoid).

The additive structure carries over to addition of equivalence classes, but unlike the classical case, it doesn’t become a group. The zero class is a neutral element, but not all positions have inverses. For instance, if $X$ is a position is such that the player to move (whether Red or Blue) can win in one move, then there can be no other position $X’$ so that $X+X’$ becomes zero, because no matter what we add to $X$, the resulting game will still be a win for the player to move.

On the other hand some positions clearly do have inverses. There is a class that contains all positions with an odd number of free sites, and where nobody can win. We might call this class $\star$, since it is similar to the class "star" in the classical theory. These positions are clearly not equivalent to the zero positions, since adding them will turn a “zugzwang” into a first player win. But we do have the equation $\star + \star = 0$.

There are several games, in particular misère games and card games, where the analysis of a corresponding monoid leads to a solution, see for instance my paper The strange algebra of combinatorial games and its references.

A couple of questions: Is the connect-four monoid infinite? What do the connect-two and connect-three monoids look like?

Finally, it seems worth taking a look at the Masters thesis of Victor Allis from 1988: A Knowledge-based Approach of Connect-Four.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.