Solved in 1988: Why the First Player Always Wins at Connect Four

Connect Four looks like the game tic-tac-toe should have been. The board is bigger, the diagonals are harder to see, and gravity means you cannot simply play wherever you like — a disc lands on top of whatever is already in the column, so half of your good ideas are unavailable until somebody else builds the stack that supports them. It feels open-ended in a way that noughts and crosses stops feeling at about age eight.

It is not open-ended. Connect Four is solved, in exactly the same sense that tic-tac-toe is solved, and the answer is more lopsided than most players would guess: with perfect play from both sides, the player who goes first wins. Not draws. Wins.

The scale is what makes that surprising. We counted tic-tac-toe at 765 essentially different positions, which fits in a notebook. A 7×6 Connect Four board has 4,531,985,219,092 legal positions — four and a half trillion, a number computed by John Tromp, who has spent an unreasonable and rather admirable amount of time on this particular board. There was never any question of solving it by hand.

So it waited for computers, and then two people got there within a fortnight of each other in October 1988. James Dow Allen and Victor Allis solved it independently, Allis as a master’s thesis at the Vrije Universiteit in Amsterdam. His program was called VICTOR, and it did something more interesting than brute force: rather than search every branch, it worked with a small library of provable threat patterns, which is why it could reach a verdict on a game this large on 1988 hardware.

The verdict comes in three parts, and the third is the part worth memorising. Open in the centre column and the first player wins with perfect play, on or before the 41st move of a 42-move board. Open in either column next to the centre and the game is a draw. Open in any of the four outer columns and the first player loses — the advantage of moving first is not merely given away, it is handed to the opponent.

That is a brutal opening rule for a children’s game. One move, made before anything has happened, decides the theoretical result of the whole thing.

The reason is the same counting argument that makes the centre square strongest in tic-tac-toe, just louder. There are 69 possible four-in-a-row lines on the board: 24 horizontal, 21 vertical, and 24 diagonal. Of those 69, fifty-one pass through the centre column. Only fifteen pass through an outer column. Put it cell by cell and the gap is starker still — the two middle cells of the centre column each sit on 13 different winning lines, while a cell in the top or bottom corner sits on 3. Every disc you place in the centre is doing four times the work of a disc placed on the edge, and it is doing that work for both attack and defence at once.

This is why the standard advice to beginners — take the middle, keep taking the middle — is not a stylistic preference. It is the solution, compressed into four words.

Beyond the opening, there is one idea that separates people who win regularly from people who play well and lose anyway, and it is almost never explained. Connect Four is decided by threat parity: not just where your threats are, but which row they sit on.

Here is the logic. A threat is a gap that would complete four for you, sitting above the current stack — it does not win now, it wins whenever the column fills up to it. Because the players alternate and the board holds an even number of discs, the first player ends up filling the odd-numbered rows counting from the bottom, and the second player the even-numbered ones, whenever a column is played out to the end. So a threat on an odd row is a threat that the first player will eventually be handed, and a threat on an even row belongs to the second player. In a tight endgame, where every remaining move is forced, whoever owns a threat on the right parity wins by simply waiting. The other player runs out of safe moves and has to build the stack that hands the game over.

That is why strong players talk about odd threats and even threats rather than about tricks. If you go first, you want your threats on rows 1, 3 and 5; if you go second, you want them on 2, 4 and 6, and you want to neutralise the opponent’s odd ones. It sounds abstract, and then you notice a game where you were forced to drop a disc you did not want to drop and lost immediately, and it stops sounding abstract.

There is a matching defensive rule that costs nothing to learn: never place a disc directly beneath a square that completes four for your opponent. It sounds obvious written down, and people do it constantly — usually while concentrating hard on a threat of their own on the far side of the board. The move is worse than a wasted turn, because it does not merely fail to help, it builds the platform your opponent needs.

Which brings us to the computer opponent here, and it is worth being straight about what it does. It runs a minimax search five plies deep with alpha-beta pruning, scoring positions with a heuristic that likes the centre column, rewards its own twos and threes, and penalises leaving you with three in a window. That combination makes it genuinely sharp at close range: it will not miss a win that is available now and it will not miss a block that is needed now, so careless play loses quickly and predictably.

But five plies is about two and a half moves each, and everything above is invisible to it. It has no notion of threat parity, so it will cheerfully build towards an even-row threat as the first player, and it cannot see a trap that needs six or seven plies to spring. And there is one more thing in your favour: you are always Red, and Red always moves first. Every game you play against it starts from the position that is theoretically won — which means every loss is your own, and that is exactly what makes it a decent thing to practise against.

The history is lighter than the mathematics. Milton Bradley put Connect Four in shops in 1974, but the game is older than the box — a version was sold as The Captain’s Mistress, a name attached by legend to Captain James Cook, who was said to disappear into his cabin with it for hours. The story is retold more often than it is sourced, which is generally the sign of a good story rather than a true one.

Play a few rounds at cerdikcerdik.com/games/connect-four. Open in the centre, keep an eye on which row your threats are sitting on, and check the square underneath before you drop. When there is someone else around, switch to pass-and-play — a human is the only opponent who will build a diagonal you did not see coming. If you want the smaller board where the same forks and blocks are easier to spot, we wrote about it at cerdikcerdik.com/blog/tic-tac-toe-solved-game, and when you want a game with far more pieces and the same habit of thinking one exchange ahead, cerdikcerdik.com/games/checkers is waiting.