Introducing the Zugzwang

Connect Four is a much deeper game than may be readily apparent. Unlike some children’s games where winning or losing comes primarily by luck, the outcome of a Connect Four game is determined by who plays the best. It is possible to codify the strategic guidelines of the game and construct computer players which range from difficult to impossible to defeat.

Victor Allis and James D. Allen both independently proved that Connect Four is a first player win. If the first player never makes an incorrect move, he, she, or it, as the case may be, will win. Facing an ideal player who starts first, no matter how well you play as the second player, you will always lose. But the game is complex enough that there is no simple list of dos and don’ts that the first-player can follow to play perfectly. In fact, the ideal strategy, while it exists, is complex enough that even the very best human players cannot achieve ideal play in every game.

Allis, in his Master’s thesis, developed a computer system, dubbed VICTOR, that plays Connect Four ideally. If the computer is given first move, it will always win. With the second move, against a human or computer opponent that does not make exactly the right move on every turn, VICTOR will either win or draw.

VICTOR achieves perfect play using a set of strategic rules to always retain control of the Zugzwang. Zugzwang comes from the German “compulsion to move”. Most often used in reference to chess, it refers to the sitatuion where one player must make a move when he would prefer to not move at all. Allis applies the term to describe maintaining control of the board, such that when the end game is reached, the player who has control of the Zugzwang is in position to benefit.

You may have encountered Zugzwang in your own games of Connect Four. As in the example above, one player is forced to move, and that gives his opponent the opportunity to claim victory. It is common to feel that who wins in a situation like this comes down to chance. However, Allis showed that this is not true. His VICTOR engine exploits this fact to guarantee victory.

His thesis is very readable, though I recommend having a copy of the game (physical or virtual) handy to work through the various scenarios and strategic situations he discusses.

Threatening Threats (and Threats That Aren’t)

I will adopt the terminology of Allis’s thesis. The first player, Player A, has white pieces. The second player, Player B, has black pieces. On the board there are 7 columns and 6 rows. The columns are assigned the letters A through G, from left to right, and the rows are numbered 1 through 6, from top to bottom.

A threat is defined as a space, which, if taken by a player, results in a win. In other words, a threat is the last space a player needs to connect four.

Threats are further classified as odd or even. An odd threat is a threat on an odd-numbered row and an even threat is on an even-numbered row. It is possible to make generalizations about which player will get to exploit odd or even threats, given certain conditions on the rest of the board.

The example above is typical of the endgame of Connect Four. Both players have played carefully, and neither is able to connect four in the early game. We see Player A and Player B both have even threats in Column C, Row 4. Whenever some columns are filled and the rest empty, an even number of pieces have been played (there are an even number of spaces in each filled column). As we saw in the example, the next move belongs to Player A. In fact, Player A will play in rows 1, 3, and 5. Player B will get rows 2, 4, and 6. Since Player B has an even threat in row 4, he wins the game.

In this type of end-game scenario, Player A desires odd threats and Player B desires even threats. If Player A had an odd threat in row 3, Player A would have won. However, as Allis demonstrates in great detail in his thesis, there are numerous factors that can disrupt this basic pattern.

In this example, Player A has an odd threat in Column F and Player B has an odd threat in Column C:

It is easy to draw the erroneous conclusion that Player A is going to win, since in the earlier scenario Player B couldn’t use odd threats. But the odd threat in Row C forces Player A to play in Row F, giving up his own threat as Player B follows up by also playing in Row F.

Player A continues to fill Row F, with Player B playing follow up until the row is filled.

With one piece already in Column C, an odd number of pieces have been played. It is Player B’s turn. He is forced to give up his own odd threat.

The game results in a draw. Even though Player A had an odd threat, it was neutralized by Player B’s odd threat.

This is one instance among many where the odd/even threats guideline is not enough to predict the outcome of the game. For a further discussion, see Allis’s thesis or one of the other resources listed below.

Who’s (Probably) Going to Win?

Our simpler approach to creating a computer player was to implement the Minimax alogorithm with Alpha-Beta pruning. We coupled this with a heuristic function that used several strategic rules to estimate the relative strengths of board positions. The computer player looks several moves ahead and chooses the move that the heuristic indicates will lead to the best outcome.

Our heuristic function began by examining all 69 potential winning lines. A winning line is an opportunity for a player to connect four. If both players had at least one piece on a potential winning line, it was ignored as useless to either player. The evaluation function gave a very small amount of importance to the number of winning lines an individual piece contributed to. In the absence of other information, the heuristic valued positions near the center of the board more highly than positions on the periphery.

But if one player occupied three of the four spaces, with the last space empty, it was recorded as a threat for that player. Threats formed the most important part of the heuristic function’s estimate.

The heuristic attached extreme importance to the following three scenarios:

• If Player A had an odd threat with no even threats from Player B below it in the same column, and Player B had no odd threats in other columns, this was scored as a probable win for Player A.
• If instead Player A had a greater number of odd threats (with no even threats from Player B below them) than Player B had odd threats anywhere on the board, and Player B had no even threats, this was also scored as a probable win for Player A.
• And if neither of the above held and Player B had any even threats, it was scored as a probable win for Player B.

Based on the strategic rules of Connect Four, the above heuristic attempts to guide the computer player to victory by controlling the Zugzwang.

It was evident when our program played against Velena (which plays perfectly) that there were many situations where our own program would quickly seize an apparently advantageous situation, such as initially denying Velena even threats while obtaining a good odd threat, that led our heuristic to suggest that our player was going to win. Unfortunately for our computer player, Velena, using Allis’s additional body of strategic rules, was able to subtly control the game such that, towards the end, a threat for Velena would materialize that neutralized our player’s threat and secured a win for Velena.

However, losing to a perfect-play engine is no surprise. Using our heuristic outlined above, and limited to half a second to decide each move, our computer player was able to beat me and my teammates easily in head-to-head games. Moreover, our computer player was able  to beat the majority of computerized opponents using a simpler heuristic, even when those opponents were given additional computation time.

Who “We” Are

The heuristic function described above was implemented by Eric Gribkoff, Pei Guo, and Saerorm Park.

Further Reading

• Connect Four Wikibook – Contains an overview of strategy, as well as variations on the basic game.
• Expert Play In Connect Four – James D. Allen’s writings on Connect Four strategy. Allen literally wrote the book on Connect Four (Amazon).
• John Tromp’s Connect Four page – Includes dataset used to implement real-time perfect play via table lookup.
• Velena – An open-source perfect play engine.
• Victor Allis’s thesis – Very detailed exploration of Connect Four strategy and the implementation of a perfect play engine.