Misère Connect Four is Solved

Abstract

Connect Four is a two-player game where each player attempts to be the first to create a sequence of four of their pieces, arranged horizontally, vertically, or diagonally, by dropping pieces into the columns of a grid of width seven and height six, in alternating turns. Misère Connect Four is played by the same rules, but with the opposite objective: do not connect four. This article announces that Misère Connect Four is solved: perfect play by both sides leads to a second-player win. More generally, this article also announces that Misère Connect $k$ played on a $w \times h$ board is also solved, but the outcome depends on the game’s parameters $k$ , $w$ , and $h$ , and may be a first-player win, a second-player win, or a draw. These results are constructive, meaning that we provide explicit strategies, thus enabling readers to impress their friends and foes alike with provably optimal play in the misère form of a table-top game for children.

Keywords

Connect Four misère games weak solution

1. Introduction

To solve a game is to predict its outcome with certainty when both players play perfectly. For instance, Tic-Tac-Toe, Connect Four (Allis, 1988), and Checkers (Schaeffer et al., 2007) are solved, while Chess and Go are not. This means that, although there exist computer programs that can beat any living human in Chess or Go, it is unknown what perfect play consists of, or how a perfect game ends. In contrast, we know with certainty that perfect play leads Tic-Tac-Toe and Checkers to a tie, while Connect Four ends with a first player win.

The solutions to Tic-Tac-Toe, Connect Four, and Checkers are all rather different from each other. Tic-Tac-Toe has such a small game tree that one can write out each player’s optimal move for any opponent move on a single sheet of paper and show that both player 1 (P1) and player 2 (P2) can avoid losing via perfect play. Moreover, this complete solution can still guide one player optimally even against an imperfect opponent. In contrast, the game tree of Connect Four is far too large to write out, so the first published solution to Connect Four (Allis, 1988) instead introduced a set of rules and proved that P1’s application of them guarantees a win.¹ However, the existence of these rules—a so-called knowledge-based approach—does not mean that one can use them from memory to beat an imperfect opponent.² Moreover, for Checkers, perfect play is out of reach of humans entirely, as the solution to Checkers is purely computational, and not rule-based. It required three computer programs to intelligently search from the game’s initial position forward, combined with a painstakingly computed endgame database of 10 trillion solutions for 10 pieces or fewer, which enabled search backward (Schaeffer et al., 2007). A human can implement optimal Tic-Tac-Toe against any opponent, and can understand perfect Connect Four against a perfect opponent, but truly perfect Checkers is played only by machines.

Solutions to games can also be categorized along a different axis, proposed by Allis (1994): an ultra-weak solution proves whether a player will win, lose, or draw from the game’s initial state under perfect play by both sides. A weak solution provides an algorithm for perfect play by one player against any possible play by the opponent, starting from the game’s initial position. And a strong solution provides an algorithm for perfect play for both players from any legal position. In other words, an ultra-weak solution proves the outcome, a weak solution shows how to achieve it, and a strong solution comprises a weak solution for every starting condition. Through this lens, the 1988 results from Allen and Allis were weak solutions to Connect Four, which were followed by a strong solution due to John Tromp around 1995 (Tromp, 1995a, 1995b). While weak solutions are intellectually stimulating, strong solutions can be staggering in scale: the number of possible board positions on a typical $7 \times 6$ Connect Four board was computed in 2008 to be $4, 531, 985, 219, 092$ (Edelkamp & Kissmann, 2008).

One interesting type of game for theorists and players alike is the misère game. A misère game is a game played by typical rules, but with the winning condition reversed. For instance, in Misère Tic-Tac-Toe, the loser is the first to get three in a row. In Misère Chess, after the addition of a rule making capturing compulsory, the winner is the first to have no pieces remaining. Thus, in Misère Connect Four, one’s goal is to avoid connecting four.

Misère games are practically, mathematically, and computationally interesting. Practically, optimal play in misère games often involves moves and strategies that would be considered poor or counterproductive in normal play, which can be novel, fun, and challenging to experienced players—one cannot simply “reverse” one’s tactics and strategy. Mathematically, analysis of misère games has challenged combinatorial game theorists because some of the common techniques and arguments used to analyze normal games do not apply to their misère forms (but see Milley and Renault’s review of recent progress (Milley & Renault, 2018)). Indeed, one result has even shown that there is no relationship between normal and misère outcomes, such that for every pair of (not necessarily distinct) outcomes $O_{1}, O_{2} \in {P 1, P 2}$ , there exists a game with normal outcome $O_{1}$ and misère outcome $O_{2}$ (Mesdal & Ottaway, 2007).³ And computationally, solutions to normal games do not imply solutions to their misère forms, nor vice versa: Checkers is weakly solved (draw, (Schaeffer et al., 2007)), while Misère Checkers is unsolved.⁴ Chess remains unsolved, while Misère Chess is weakly solved (P1 win, Watkins, 2017).

This article announces that Misère Connect Four is weakly solved: perfect play by both sides results in a P2 win. More generally, this article also announces that Misère Connect $k$ played on a board of width $w$ and height $h$ is also weakly solved, but the outcome depends on the games parameters $k$ , $w$ , and $h$ , and may be a P1 win, a P2 win, or a draw. Finally, we solve “infinite” Misère Connect $k$ by addressing boards of infinite height or infinite width, both of which are draws. A summary of these results is given in Table 1.

Table 1.
Outcomes Under

Optimal Play for all Parameters of Misère Connect $k$ . If $w$ or $h$ is Infinite, or $w < k$ , Optimal Play Leads to a Draw.

Misère Connect $2$

Width

Height $w \geq 3$ odd $2$ , $4$ , or $6$ $w \geq 8$ even

$h = 1$ P2 Draw P2

$h \geq 2$ P2 P2 P2

Misère Connect $k \geq 3$

Width

Height $w \geq k$ odd $w \geq k$ even

$h = 1$ Draw Draw

$h \geq 2$ even P2 P2

$h \geq 3$ odd P1 P2

Misère Connect $2$
$h = 1$	P2	Draw	P2
$h \geq 2$	P2	P2	P2
Misère Connect $k \geq 3$
	Width
Height	$w \geq k$ odd	$w \geq k$ even
$h = 1$	Draw	Draw
$h \geq 2$ even	P2	P2
$h \geq 3$ odd	P1	P2

Table 2.

The Four Canonical Plays for Misère Connect $k$ with $k = 2$ and $h = 1$ . The Four Named Plays, being Described in the Text, are Tabulated here With Their Effects on the Tally of Remaining in-Template Moves. One Column Shows the Impact of Such a Play When X Makes That Play, and the Other Column Shows the Impact When O Makes That Play.

Play name	$Δ$ tally (X played)	$Δ$ tally (O played)
In-template	$(- 1, 0)$	$(0, - 1)$
Double contradiction	$(- 2, - 1)$	$(- 1, - 2)$
Offensive	$(- 1, - 1)$	$(- 1, - 1)$
Self-immolation	$(- 2, 0)$	$(0, - 2)$

2. Rules and Notation

Misère Connect $k$ is played on a board of height $h$ and width $w$ which forms a grid. Player 1 (P1) plays as X and Player 2 (P2) plays as O.In alternating turns, each player selects a column in which to place a piece, and gravity pulls that piece to the lowest open position. Consequently, once a column has been played $h$ times, it is full and neither player can play in it. The game ends when one player has $k$ pieces in a contiguous horizontal, vertical, or diagonal line. Because the game is played in the misère condition, the first player with $k$ pieces in a row loses.

Using common vocabulary from the literature, this makes Misère Connect $k$ is a two-player partisan⁵ game with perfect information⁶, played under the misère condition: the player who connects four loses.

3. Solving the Game

Our solution is divided into six parts. First, we introduce a strategy and prove that the second player (P2) can always use it to win Misère Connect Four on a standard $6 \times 7$ board. Second, using the same strategy, we extend the proof to show that P2 wins Misère Connect $k$ on all boards of even height $h$ and $k \leq w$ . Third, we extend the strategy to cover boards of odd height $h \geq 3$ , proving that P2 wins when the width $w \geq 4$ is even, but P1 wins when $w \geq 5$ is odd. Fourth, we analyze games of height $h = 1$ for $k \geq 3$ . Fifth, we analyze games for $k = 2$ . Finally, we treat two special cases: narrow boards $w < k$ and infinite boards.

Perhaps surprisingly, the proofs for $k = 2, 3$ and $h = 1$ turn out to be the most technical and important results in the paper. In fact, the proof for $k = 3$ and $h = 1$ underpins some of the solutions in the sections that precede it. Due to that importance, we state its result informally here: On a single-row board (height $h = 1$ ) of arbitrary width, neither player can be forced to connect $k \geq 3$ , even if we allow their opponent to connect as many as they wish. This key result means that all $h = 1$ and $k \geq 3$ games are a draw.

3.1. Misère Connect Four on a Standard $6 \times 7$ Board

The second player (P2) can always win Misère Connect Four played on a standard board of height $h = 6$ and width $w = 7$ . P2 achieves this victory using a simple strategy: playing only in the even rows. As a consequence P1 is eventually forced to connect in the first row, resulting in a P2 win. We prove that P2’s take-even strategy results in an unavoidable P2 win in Theorem 1, and illustrate it in Figure 1.

Figure 1.

Illustration of the take-even strategy. (Top-left) In the First Move of the Game, P1 (X) Must Play into Row 1. (Top-right) The Take-even Strategy Dictates that P2 (O) Plays in an Even Row. The Existence of this Move is Guaranteed by P1’s Play in an Odd Row. Grey (X)’s Indicate the Available Next Moves For P1, All of Which are in Odd Rows. (Bottom-left) An Example Game State After 25 Turns, in Which P2 is Using the Take-Even Strategy, With P2 To Play. (Bottom-Right) Example Final Game State With a P2 Win on Turn 37. This Solution is Proved in Theorem 1.

Theorem 1

The take-even strategy, played by P2, on a board with height $h = 6$ and width $w = 7$ , eventually forces P1 to connect four resulting in a guaranteed P2 win.

Proof.

When the game begins, the board is empty so P1 has no choice but to play in the first row—an odd-numbered row. By playing in an odd row, P1 has created an opportunity for P2 to play in an even row. In fact, the space on top of P1 is the only even-row move that P2 has available. According to the take-even strategy, P2 plays on top of P1. This fills the even-row space, confronting P1 with only odd-row options.

This opening illustrates three important facts. First, if P1 has only odd-row plays available, then P1 must play in an odd row. Second, if P1 plays in an odd row, this creates an even-row play for P2 on top of P1’s most recent piece. P2’s even-row option is guaranteed, in fact, because the board is even height, so P1’s odd-row play must have at least one empty space above it. Third, when P2 takes the even-row play that P1 has created, P2 removes the even-row option from the board, confronting P1 with only odd-row options. Note that if P2’s move completely fills a column, the number of playable columns decreases but P1 has only odd-row options.

Together, these facts mean that P2 always has the option to play in an even row and that P1 is forced to play in odd rows. In other words, P2 can exercise the take-even strategy, and P1 must play in odd rows. P2 has control of the game.

Now, note that because P2 plays only in even rows and P1 plays only in odd rows, neither player can connect four vertically or diagonally. Instead, P1 will eventually be forced to connect four in the first row, once the other columns are filled (by P2) and thus unavailable. P2 therefore wins on the 37th move, or sooner.

3.2. Misère Connect

k \leq w

on a Board With Even Height

The take-even strategy works on the standard $6 \times 7$ board because of three key ingredients. First, the board’s even height guarantees that any odd-row play by P1 will have an empty even-row space above it, into which P2 will play. Second, the board is finite so eventually the columns fill forcing P1 to play in the first row. Third, the board is wide enough that if P1 fills the first row, P1 loses, i.e. $k \leq w$ . The fact that these key ingredients are not restricted to $6 \times 7$ boards alone leads to the following, more general Corollary to Theorem 1.

Corollary 1
The take-even strategy played by P2, on a board with even height $h$ and finite width $w$ , with $w \geq k$ , eventually forces P1 to connect $k$ resulting in a guaranteed P2 win.
Proof.
The proof of Theorem 1 applies directly without modification. P1 can delay loss as long as possible by playing only in sets of $k - 1$ adjacent columns. Under this delay tactic, with $w$ total columns and at most $⌊ \frac{w}{k} ⌋$ individual columns may be empty. Each column allows $h$ moves. Thus, P1 loses on or before move number $1 + (w - ⌊ (w / k) ⌋) h$ .
3.3. Misère Connect $k \leq w$ on a Board With Odd Height $h \geq 3$

An even board height $h$ is required by the assumptions of Theorem 1 and Corollary 1, but what if the board’s height is odd? At first glance, an odd height appears to undermine a key pillar of the take-even strategy, namely the fact that any odd-row move by P1 creates an even-row option for P2. Now, with an odd number of rows, P1 could play in the top row, filling a column but creating no even-row option for P2’s strategy. Without an even-row option, P2’s take-even strategy, by definition, falls apart.

While at first this appears to spell trouble for P2 (and our proof strategies), we now show that, in fact, the machinery of Theorem 1 can still be used for odd-height boards, but with a twist: the player whose win is guaranteed now depends on the width of the board, with P2 winning even-width games but P1 winning odd-width games.

To build intuition toward our next Theorem, consider a board with odd height where we have numbered the bottom row $0$ , and the rows above as $1, 2, \dots, h - 1$ . Because $h$ is odd by assumption, $h - 1$ is even, and so the board can be divided into two sections: row $0$ , and a section on top with an even number of rows. We call the area on top of row $0$ with an even $h - 1$ number of rows the even board space (Figure 2).

Figure 2.

The Delayed Take-Even Strategy Works by Conceptually Partitioning the Board. The Bottom Row is Counted as “row Zero” and the Rows Above, of which there Must be an Even Number, are Called the “even Board Space.”

With this partition of the board in hand, we introduce the delayed take-even strategy for boards of odd height $h$ —an unbeatable strategy for P2 when width $w$ is even, and for P1 when width $w$ is odd. Here is how it works, in two simple rules: (a) if the opponent plays in row $0$ , follow with a non-losing move in row $0$ ; (b) if the opponent plays in any other row, play on top of them, thus using a take-even strategy in the even board space.

The logic of this strategy is simple: if row $0$ were to be filled, then the game could be played as if there were an even number of rows, thus allowing the take-even strategy to guarantee a win. Indeed, the take-even strategy for even boards tells us that the first player to play will lose. In odd height boards the finding is similar: the first player to play in the even board space loses. When there are an even number of moves available in row $0$ , P2 can force P1 to be the first to enter the even board space (and thus lose); when there are an odd number of moves available in row $0$ , P1 can force P2 to be the first to enter (and thus lose). The following theorem proves this optimal strategy for $k \geq 3$ and $w \geq k$ .

Theorem 2

The delayed take-even strategy, played by P2 on a board with odd height $h \geq 3$ and even width $w \geq k \geq 3$ , eventually forces P1 to connect $k$ resulting in a guaranteed P2 win.

Proof.

P1 has no choice but to begin the game by playing in row $0$ . Because P1 has played in row $0$ , the delayed take-even strategy dictates that P2 should also play in row $0$ . No one has yet lost (or won) because each has played just once and $k \geq 3$ by assumption. Thus, P1 now has a choice between two options: (i) play into an odd-numbered row (that is, row $1$ , in the even board space, on top of one of the existing moves), or (ii) play again into row $0$ .

Note that no matter which option P1 chooses, P2 will return to P1 a board with only option (i), option (ii), or both, meaning that P1 will not have the option to play into an even-numbered row in the even board space. Why must this be so? First, if P1 plays into an odd row, P2 will play on top, either giving P1 another odd-row option on top, or completing a column and removing it from P1’s options entirely. The availability of P2’s move is guaranteed by the fact that there are an even number of rows in the even board space above row $0$ . On the other hand, if P1 plays into row $0$ , P2 will also play a non-losing move into row $0$ , either giving P1 another row- $0$ option or completing row $0$ . The availability of P2’s move is guaranteed by the fact that there are an even number of columns in row $0$ , so that any time P1 plays in row $0$ , there is at least one column into which P2 may play. Critically, the guarantee that such a move by P2 is non-losing is established in Theorem 3 which shows that both players can bring play in row $0$ to a draw with perfect play.

Taken together, when P2 uses the delayed take-even strategy, P1’s options are restricted entirely to playing in row $0$ or playing in an odd row. And, regardless of P1’s choice, P2 will have an available move that returns P1 to these identical choices. Eventually, if P2 has not already won in the even board space by Theorem 1 and Corollary 1, row $0$ will be filled, and the game will be forced into the even board space, leading to a P2 win.

The proof of Theorem 2 shows how the delayed take-even strategy can be utilized by P2 to eventually force P1 into the even board space leading to a P2 win, provided that the height of the board is odd and the width of the board is even. Using similar arguments, we now show that when the height of the board is odd and the width of the board is odd, the delayed take-even strategy reverses the outcome, allowing P1 to force P2 into the even board space leading to a P1 win.

Corollary 2

The delayed take-even strategy, played by P1 on a board with odd height $h \geq 3$ and odd width $w \geq k \geq 3$ eventually forces P2 to connect $k$ resulting in a guaranteed P1 win.

Proof.

P1 has no choice but to begin the game by playing row $0$ . P2 now has a choice between two options: (i) play into an odd row (in the even board space, on top of one of the existing moves), or (ii) play again into row $0$ . Identical arguments to Theorem 2 now apply: P1’s use of the delayed take-even strategy will always return P2 to these two choices. However, in contrast with Theorem 2, this Corollary assumes the width to be odd, allowing P1 to play the final move in row 0. Thus, P1 can force P2 into the even board space, eventually resulting in a P1 win. Once more, this result rests on the fact that P1 can avoid a loss during gameplay in row 0, a result which we establish in Theorem 3.

Theorem 2 and Corollary 2 prove all cases of $k \geq 3$ for both odd and even width, and both odd and even height, provided that there is sufficient width to connect $k$ in a row, that is, $w \geq k$ . However, as noted, both proofs rely on an as-yet unproven Theorem, one which guarantees that P1 always has a non-losing move available in row $0$ for odd-width boards, and that P2 always has a non-losing move available in row $0$ for even width boards. This result follows from proving that perfect play by both players results in a draw for boards with height $h = 1$ when $k \geq 3$ , the precise result of Theorem 3.

3.4. Misère Connect

k

With

k \geq 3

and Height

h = 1

When a board has height $h = 1$ , Misère Connect $k$ simply asks whether it is possible for either player to force the other to occupy $k$ adjacent positions along a strip of some width. The answer, as we will prove, is that it not possible: Misère Connect $k$ with $h = 1$ and $k \geq 3$ is a draw. In fact, a stronger statement can be made: neither player can force the other to connect even under a surprising relaxation of the rules! For $k = 3$ , either player can avoid connecting $3$ , even if we allow the other player to connect as many pieces as desired without losing. In other words—and perhaps to our surprise—P1 can draw the $h = 1$ game even if P2 cannot lose, and P2 can draw the $h = 1$ game even if P1 cannot lose.

In the definitions and strategies below, we let P1 play as X and P2 as O. The core of the proof relies on enumerating all the empty spaces on the board at the start of the game, in pairs, from left to right.⁷ For instance, for a game of $w = 8$ or $w = 11$ , we would label the spaces

board: -------- board: -----------

labels: 11223344 labels: 11223344556

If the game ends in a balanced state such that every pair has one X and one O, the game is a draw for any

k \geq 3

, as there can be at most two-in-a-row. Note that this is true regardless of who has played in the unpaired rightmost space when

w

is odd. We refer to this as a pair-balanced board.

Now consider a simple two-rule strategy, which can be employed by either player, and is designed to force any game to a pair-balanced board, and thus, a draw. The two rules are:

(1)
Take-other: If your opponent has taken one half of a pair, take the other half of the pair.
(2)
Rightmost: If there are no available take-other moves, play the rightmost space available.
In the theorem that follows, we prove that this two-rule strategy leads to a draw because it guarantees that the board ends in a pair-balanced state, either (i) by showing that every pair is balanced, or (ii) by showing that no pair is XX or OO.
Theorem 3
Suppose that $h = 1$ and $k \geq 3$ . Either P1 playing X or P2 playing O can force a draw by playing the two rules of take-other and rightmost.
Proof.
Case 1: Suppose that $w$ is even and O is employing the two-rule strategy. By definition, X plays somewhere on the board, half filling a pair. Because O uses take-other, a balanced pair is created. With only empty pairs to play in, X’s subsequent play must half fill another pair, which O will then complete. Because $w$ is even, the game consists of $w / 2$ repetitions of this process, and the final board is guaranteed to be pair-balanced.

Case 2: Suppose that $w$ is even and X is employing the two-rule strategy. Their first move fills half of the rightmost pair, creating a -X. When O plays, they will either fill that -X or half fill some other pair. If O fills the -X, that pair is balanced and the game is equivalent to a new $w - 2$ game. If O half fills some other pair, then X plays take-other to balance that pair, and once more, O has two options: balance the -X or half-fill another pair. Thus, X always has an in-strategy option and is never forced to play the other half of the -X. Because $w$ is even, O plays last, and the final board is guaranteed to be pair-balanced.

Case 3: Suppose that $w$ is odd and O is employing the two-rule strategy. Because $w$ is odd, the first move from X either takes the rightmost space, which is not part of any pair, or X half fills a pair elsewhere on the board. Suppose that X takes the rightmost space. In this case, it is as if O is playing first on a $w - 1$ board, and so the arguments of Case 2 (with the players reversed) guarantee a pair-balanced final board. If instead, X takes some other space, O will take-other to balance the pair, and we restart Case 3 with $w - 2$ .

Case 4: Suppose that $w$ is odd and X is employing the two-rule strategy. By the rightmost rule, X takes the singleton space, leaving O to play somewhere in the even $w - 1$ board. The arguments of Case 1 (with the players reversed) guarantee a pair-balanced final board.

These four cases cover both even and odd width $w$ for both players, meaning that either player can force $h = 1$ and $k \geq 3$ to a draw.

With the result of Theorem 3, the results of Theorem 2 and Corollary 2 are complete: because Misère Connect $k$ with $h = 1$ and $k \geq 3$ is a draw, neither player can win in the bottom row (row 0) of an odd-height board, which means that the delayed take-even strategy cannot be escaped: for odd heights $h \geq 3$ , P2 wins when width $w$ is even, and P1 wins when width $w$ is odd.
3.5. Misère Connect $k$ With $k = 2$

When $k = 2$ , the game takes on a fundamentally different character. Connecting two requires only that a player place two pieces adjacent or diagonal to each other, leading to the question: can one player force another to play adjacent to one of their previous moves? The answer, as we shall see, is generally yes, and in particular, the advantage belongs to P2.

We begin by analyzing the special case of $k = 2$ with height $h = 1$ , which will be subsequently used to solve $k = 2$ and arbitrary $h$ . Playing Misère Connect $k$ with $k = 2$ with height $h = 1$ amounts to a game in which each player must simply avoid placing two pieces adjacent to each other. This simple goal leads to a few preliminary and useful observations.

First, the game is a draw if and only if it ends with alternating X and O pieces. This means that there are only two types of final boards for any game that ends in a draw: one in which X has placed a piece in the leftmost position, and one in which O has. Consequently, once X has played the first piece, the final game state that would constitute a draw is uniquely specified. We call this the board’s template. A move that complies with the template is an “in-template” move, and a move that does not—and thus asserts a contradicting template of its own—is an “anti-template” move.

If either player chooses to play an anti-template move after the opening move has asserted a template, then the game must have a winner and a loser. Thus, the key question to be addressed is whether playing an anti-template move is strategically useful in allowing one player to force the other to connect 2.

We now introduce a simple bookkeeping scheme, which tracks the number of non-losing in-template moves available to X and O, respectively, as an ordered pair. For instance, the following board has 1 available in-template move for X and 2 for O, as annotated.

board: -XO--

^ ^^

template:O XO

We would therefore write the number of available in-template moves at

(1, 2)

This bookkeeping scheme extends to boards with two contradictory templates. For instance, we can count $(1, 1)$ available template moves in the board X---O if we assert X’s template and annotate from left to right:

board: X---O

^^

template: OX

Note that we count an identical number if we assert O’s template annotate from right to left:

board: X---O

^^

template: OX

In fact, we can assert both templates and annotate from the outside in—we again get an identical number:

board: X---O

^ ^

template: O X

This example illustrates the point that we can choose any template as our reference to tabulate the number of remaining moves for each player, and the result will be the same. It is the contradiction between two templates that reduces the number of available moves; not the order of tabulation. In some sense, our bookkeeping scheme simply imagines that both players play alternating non-losing moves arbitrarily until there are none left.

Our bookkeeping scheme is useful because it tells us what will happen if both players play alternating non-losing moves. For instance, if there exist both in- and anti-template moves on the board (guaranteeing a winner and a loser), and the move tally is $(1, 0)$ with X to play, then X will win: X has an available move and will play it, while O will have no moves available. By extension, if the tally is $(a + 1, a)$ with X to play, then X will win, unless of course O plays outside the existing templates to intentionally shift the tally. We will now explore such tally-shifting plays by both players.

From the perspective of the tally, there are only four canonical plays. Without loss of generality, we’ll define them from the perspective of X, though they equally apply to O.

The first canonical play is the in-template play, in which X plays into an existing template. For instance,

X----O \overset{X}{\to} X-X--O

is an in-template play. The tally keeps track of available in-template plays, so tabulating it before and after X’s play shows

(2, 2) \overset{X}{\to} (1, 2)

, as expected. The in-template play affects only the person who played it, decreasing their tally by one. We therefore give the in-template play a score of

(- 1, 0)

for its effect on the tally.

Note that an in-template does not require that all plays on the board conform to one template. For instance, returning to a previous example, in which two contradictory templates have already been asserted, note that

X---O \overset{X}{\to} X--XO

is also an in-template play, such that

(1, 1) \overset{X}{\to} (0, 1)

. Thus, this play requires only that X play in one of the templates. Any play that does not create a new contradiction with an existing template is an in-template play.

The second canonical play is the double contradiction play, in which X plays in contradiction to an existing template that is bounded on both the left and the right by existing moves, thus creating a first contradiction to the left of the play and a second contradiction to the right. For instance,

X------O \overset{X}{\to} X--X---O

OXOXOX O- -OX

shows a play (top line), its template before the play (bottom left) and one possible templating afterward (bottom right). Note that this play created not one but two contradictions. Consequently, the play itself debits once from the tally, and the two contradictions debit once each. Tabulating the tally before and after X’s play shows

(3, 3) \overset{X}{\to} (1, 2)

. We therefore give the double-contradiction play a score of

(- 2, - 1)

for its effect on the tally. Note that a double contradiction requires a minimum of three empty spaces between the template walls (a consequence of the fact that there must be at least three template moves that can be depleted from the tally).

The third and fourth canonical plays are when X plays in contradiction to an existing template that is bounded on only one side by an existing move, and meets the edge of the board on the other. Both plays are played in the same manner, but their effects differ dramatically, depending on which player is prescribed the wall-adjacent place in the existing template. Consider the following two examples.

In the first example, X is not prescribed the wall in the existing template,

XO------ \overset{X}{\to} XO---X--

XOXOXO -XO OX

so when X plays a contradiction, it amounts to

(3, 3) \overset{X}{\to} (2, 2)

, thus scoring

(- 1, - 1)

. We call this play an offensive play because it decreases X’s tally by one like an in-template play, but also decreases O’s tally. An offensive play is strictly better than an in-template play.

In this first example, one might also note that X left the wall position available after flipping its template. Consequently, O has an opportunity to counter with an offensive play of their own, reversing X’s short-lived advantage. Therefore, we note that an offensive play directly against the wall is advised, as it prevents one’s opponent from countering with a followup offensive play. We call the offensive play against the wall an exclusive offensive play for this reason.

In a second example, X is prescribed the wall in the existing template,

XO----- \overset{X}{\to} XO---X-

XOXOX -XO O

so when X plays a contradiction, it amounts to

(3, 2) \to (1, 2)

, thus scoring

(- 2, 0)

. We call this play a self-immolation because it depletes two from X’s tally, but none from O’s. A self-immolation is strictly worse than an in-template play.

These plays now allow us to analyze gameplay more generically. For one player to beat another, someone must create a contradiction, and only double contradiction, offensive, or self-immolation moves do so. Relative to in-template moves, double contradiction plays affect both players equally, offensive plays improve the standing of the one who plays, and self-immolations are bad for their player.

Lemma 1
In a game of Misère Connect $k$ with $k = 2$ , $h = 1$ , and odd width $w \geq 3$ , Player 2 wins.
Proof.
If $w \geq 3$ is odd, then $w = 2 m + 1$ for a natural number $m \geq 1$ . The first move by P1 (i.e., X) will either template the board to have $(m - 1, m + 1)$ template spaces remaining for each player or $(m, m)$ template spaces remaining for each player. The latter outcome happens when X plays into an odd-numbered space (indexing from $1$ to $w$ , left to right), and the former outcome happens when X plays into an even-numbered space.

First, suppose that X’s opening move is in an even-numbered space, leaving the tally at $(m - 1, m + 1)$ with O to play. If both players play in-template moves for the rest of the game, O wins by tally. Thus, the burden will be on X to rescue themself from the opening play. Without yet considering O’s move, note that X’s only path to victory is if X is able to play two offensive moves to gain the advantage in the tally. Unfortunately, O plays second, and can therefore take one of the in-template wall positions ( $1$ or $w$ ), removing any possibility of an offensive move by X on that side. With at most one offensive move available to X, O can win by tally by playing only in-template moves.

Instead, suppose that X’s opening move is in an odd-numbered space, leaving the tally at $(m, m)$ with O to play. Note that X must have left either one or both walls open and templated as X. Thus, O can play an exclusive offensive move by playing an available wall. The tally is now guaranteed to be $(m - 1, m - 1)$ with X to play, and a contradiction on the board. Because there are no offensive moves available to X, X has no opportunity to reverse their fate, and thus O can win by tally by playing only in-template moves.

In short, if X opens an odd-width game in an even numbered space, O should play an in-template move against a wall. If X opens an odd-width game in an odd numbered space, O should play an offensive move against an open wall. In every possible scenario for odd width $w \geq 3$ , $h = 1$ , and $k = 2$ , O wins.

Even-width games are more interesting. Starting from $w = 4$ , we note that if X opens by playing against a wall, then O should take the opposite wall, guaranteeing a draw. If X opens by playing an interior space, O plays an offensive move and X loses. Thus, X should open against a wall, and $w = 4$ is a draw.

Similarly, when $w = 6$ , X should open against a wall to draw the game. Why? If X were to open in space 2 or 3, then O could play an offensive move and win by tally. This holds true even when X is able to play an offensive move of their own, a possibility when X opens in space 3. Importantly, the path to a draw with $w = 6$ is narrow: after X opens against a wall, O must take the other wall to prevent X from winning. And, after O takes that wall, X must play in-template closest to her first piece, avoiding three empty spaces in a row into which O could play a double contradiction to win. Exhaustively, $w = 6$ is a draw.

Unfortunately for X, when $w = 8$ , X loses the ability to draw the game, which we now prove.
Lemma 2
In a game of Misère Connect $k$ with $k = 2$ , $h = 1$ , and even width $w \geq 8$ , Player 2 wins.
Proof.
First, assume that P1 (i.e., X) opens with a wall play. Then O is free to take the opposite wall, an in-template play. The entire board is now templated with zero contradictions, and the tally is $(m - 1, m - 1)$ with X to play. Because the walls are both taken, there are only in-template and double contradiction moves remaining. If X plays a double contradiction, the tally will drop to $(m - 3, m - 2)$ , and X will lose by tally. Thus, X must play only in-template moves. After X plays an in-template move, the tally will be $(m - 2, m - 1)$ with O to play. If O plays a double contradiction, the tally will drop to $(m - 3, m - 3)$ with X to play, and X will lose by tally. The existence of the double contradiction for O to play on their second turn is guaranteed: O needs three or more empty spaces in which to play this move, and X can break the stretch of six spaces into a length of two and a length of three.⁸ Consequently, if X opens with a wall play, O can win by taking the opposite wall on their first turn and a double-contradiction on their second, with in-template moves thereafter to win by tally.

Next, assume that X opens with something other than a wall play. This means that both walls are open, one of which must be an offensive move for O. Thus, O plays the offensive move, and the tally is $(m - 2, m - 1)$ with a contradiction on the board. From here, it is hopeless for X. Even if X has left enough room to play an offensive move against the opposite wall, this will bring the tally to $(m - 3, m - 2)$ with O to play. With no tools to overcome the tally deficit, template moves by O will lead to a O win.

In short, if X opens an even-width $w \geq 8$ game against a wall, then O should take the opposite wall and then play a double-contradiction. If X opens somewhere other than a wall, then O should play an exclusive offensive move at the appropriate wall. In every possible scenario for even width $w \geq 8$ , $h = 1$ , and $k = 2$ , O wins.

Our analysis of $k = 2$ and $h = 1$ games is complete, and points to a general advantage for O, who can win for any odd width $w \geq 3$ and any even width $w \geq 8$ . The special cases of $w = 4$ and $w = 6$ are a draw. We conclude with a final theorem, generalizing these results to arbitrary $h$ .
Theorem 4
In a game of Misère Connect $k$ with $k = 2$ , optimal play leads to a draw for height $h = 1$ and widths $w = 1$ , $2$ , $4$ , and $6$ , and a P2 win for all other finite widths. When $h > 1$ and $w = 1$ , the game is a draw. When $h > 1$ and $w > 1$ , optimal play leads to a P2 win.
Proof.
For height $h = 1$ , widths $w = 1$ and $2$ are obviously draws because neither player has a chance to play more than once. All other odd widths are wins for P2 by Lemma 1. Even widths $w = 4$ and $6$ are draws by directly exploring all possible game trees (see text), while all other even widths $w \geq 8$ are wins for P2 by Lemma 2. The Lemmata and discussion above provide strategy prescriptions for P2, and thus, this proof is constructive.

For height $h > 1$ and width $w = 1$ , the game follows a deterministic trajectory where the players fill the single column in alternative moves until the board is full with no winner. We include this game only for the sake of completion.

For even heights $h \geq 2$ and finite width $w > 1$ , we simply observe that O can use the take-even strategy, guaranteeing a P2 win, despite the other peculiarities of the $k = 2$ cases.

For odd heights $h \geq 3$ and finite width $w > 1$ , P2 wins. This is because, on each turn, each player must decide whether to play in the bottom row, or to play above in the even board space (Figure 2). P2 can always win by using a delayed take-even strategy—that is, by following P1’s bottom-row moves with bottom-row moves, and otherwise playing on top of P1. This follows from two facts: First, the delayed take-even strategy forces P1 into alternating bottom row play. Second, Lemmata 1 and 2 provide a strategy by which P2 can either win or draw in alternating bottom-row play.

One lingering question might be whether, somehow, the existence of additional rows would somehow disrupt the tally arguments used to prove $h = 1$ cases. However, we alleviate this concern by noting that (i) for even heights $h$ , the take-even strategy drives P2 to victory, not a tally-based strategy, and (ii) for odd heights $h$ , the tally-based strategy is never disrupted by the delayed take-even strategy because P2 would never play in row 1, and thus P2 would never decrease their tally of in-template plays in row 0 via the threat of a diagonal connect 2.
3.6. Two Special Cases: Infinite Games and Narrow Games

Trivially, boards of infinite width must be draws: either player can play arbitrarily far from any previous play. Similarly, boards of infinite height must also be draws: either player can indefinitely play on top of the other’s most recent move. Incidentally, infinite Connect Four is also a draw (Yamaguchi et al., 2012).

Finally, if $k$ exceeds the width of the board $w$ , the game is a draw: either play can play on top of the other’s most recent move, avoiding a vertical connection. Because the board is also too narrow to connect horizontally or diagonally, the game is a draw.

4. Discussion and Conclusion

In this article, we described Misère Connect Four, the misère form of Connect Four in which players must force their opponents to connect four in order to win, and generalized it to Misère Connect $k$ played on a board of width $w \geq 1$ and height $h \geq 1$ . We proved that under optimal play the game may be a draw, Player 1 win, or Player 2 win, summarized in Table 1. In general, the outcome of the game has little to do with $k$ , and more to do with the dimensions of the board, particularly whether height and width are even, odd, one, or infinite.

One observation is that the game gently defies expectations, in that one might expect that the first player to play is at a disadvantage, and thus games ought to end in either a draw or a Player 2 win. However, this is not always the case: when $3 \leq k \leq w$ with $w$ and $h$ both odd, Player 1 wins.

A second observation is that the solution to Misère Connect $k$ is constructive, realizable by a human, and in some sense thick: over all possible plays by an opponent, the proven winner (or drawer) can apply the knowledge-based strategies of this article to pull the game toward the optimal outcome. In contrast, when one’s opponent plays suboptimally in other games, even a (human) player who understands how a perfectly played game unfolds may struggle to respond optimally. In other words, we have not computed a thread between the opening of an optimally played game and its conclusion, but have instead provided a set of blanket strategies that always pull the game toward its inevitable conclusion.

Finally, we leave one open problem for readers’ consideration. Consider Misère Connect $k$ played on an annulus, i.e., on a board of height $h$ and circumference $w$ (or width $w$ with periodic walls). If the height is even, the take-even strategy in this article can be used without modification, but who wins when the height is odd, including when the height is one?

Footnotes

ORCID iDs

Robert Steele

Daniel B Larremore

Funding

The authors received no financial support for the research, authorship and/or publication of this article.

Declaration of Conflicting Interests

The authors declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Notes

References

Allen

J. D.

(2010). The Complete Book of Connect Four: History, Strategy, Puzzles. Sterling. Available online at https://fabpedigree.com/james/connect4.htm.

Allis

L. V.

(1988). A Knowledge-based approach of connect-four. ICGA Journal, 11(4), 165.

Allis

L. V.

(1994). Searching for solutions in games and artificial intelligence. PhD thesis, Maastricht University. doi:https://doi.org/10.26481/dis.19940923la.

Bosboom

Congero

Demaine

E. D.

Demaine

M. L.

Lynch

(2019). Losing at Checkers is hard. The Mathematics of Various Entertaining Subjects (MOVES 2017), 3, 103–118.

Edelkamp

Kissmann

(2008). Symbolic classification of general two-player games. In KI 2008: Advances in Artificial Intelligence: 31st Annual German Conference on AI, KI 2008, Kaiserslautern, Germany, September 23–26, 2008. Proceedings 31 (pp. 185–192). Springer.

Fraenkel

A. S.

Garey

M. R.

Johnson

D. S.

Schaefer

Yesha

(1978). The complexity of checkers on an N

\times

N board. In 19th Annual Symposium on Foundations of Computer Science (SFCS 1978) (pp. 55–64). IEEE.

Mesdal

Ottaway

(2007). Simplification of partizan games in misére play. Integers, 7, G06.

Milley

Renault

(2018). Restricted developments in partizan misére game theory. Games of No Chance, 5, 113–123.

Schaeffer

Burch

Bjornsson

Kishimoto

Muller

Lake

Sutphen

(2007). Checkers is solved. Science (New York, N.Y.), 317(5844), 1518–1522.

10.

Steele

Larremore

D. B.

(2024). Misére Connect Four is Solved. arXiv preprint arXiv:2410.05551.

11.

Tromp

(1995a). John’s Connect Four Playground. Website. Accessed September 1, 2024. https://tromp.github.io/c4/c4.html

12.

Tromp

(1995b). Connect-4. UCI Machine Learning Repository. DOI:https://doi.org/10.24432/C59P43.

13.

Watkins

(2017). Losing Chess: 1. E3 Wins for White. Journal of the International Computer Games Association, 39(2), 123–125.

14.

Yamaguchi

Tanaka

Kaneko

(2012). Infinite connect-four is solved: Draw. In Advances in Computer Games: 13th International Conference, ACG 2011, Tilburg, The Netherlands, November 20–22, 2011, Revised Selected Papers 13 (pp. 208–219). Springer.

Misère Connect $2$
	Width
Height	$w \geq 3$ odd	$2$ , $4$ , or $6$	$w \geq 8$ even
$h = 1$	P2	Draw	P2
$h \geq 2$	P2	P2	P2
Misère Connect $k \geq 3$
	Width
Height	$w \geq k$ odd	$w \geq k$ even
$h = 1$	Draw	Draw
$h \geq 2$ even	P2	P2
$h \geq 3$ odd	P1	P2

Misère Connect Four is Solved

Abstract

Keywords

1. Introduction

3. Solving the Game

3.1. Misère Connect Four on a Standard 6 × 7 Board

4. Discussion and Conclusion

Footnotes

ORCID iDs

Funding

Declaration of Conflicting Interests

Notes

References

3.1. Misère Connect Four on a Standard $6 \times 7$ Board