Connect Four, Part 1

This blog contains explanation of the paper by Victor Allis called ‘A Knowledge-based Approach of Connect-Four’

Introduction

Connect-Four is a game for two players. Both have 21 identical coins. In the standard form of the game, one set of coins is yellow, and the other is red. You play the game on a vertical, rectangular board consisting of 7 vertical columns of 6 rows each. Each time a player puts a coin down, it falls to the lowest unoccupied block in that column. Players make a move in turns.

If a player connects four coins either horizontally, vertically or diagonally, they win. Occupying each of the 7x6 blocks such that no other move is possible, and ensuring that there is no winning player, entails the draw condition.

Now, some definitions to make referencing the board easier. The 7 columns are labelled ‘a’ through ‘g’, while the rows are numbered 1 through 6. In this way, the lowest square in the middle column is called d1. For convenience’s sake, we are taking the first player as White (W) and second as Black (B) (similar to Chess).

Approaching the Game

Before you show off your excellent techniques, we need to first prove that the dumb approach does not work. It is easy to see that the number of possible positions is at most $3^{42} (\geq 10^{20}).$ This upper bound is a very crude one and can be brought into better proportions. For this purpose, a program was written in the C programming language, which is mentioned later. For the standard, 7 x 6 board, the program saw an upper bound of $7.1* 10^{13}$.

So, too many possibilities, significantly less accuracy, brute force is not an efficient approach. A player cannot win just by instantiating each possible board and trying to follow it. You are a human after all, not a computer 😛

Some Possible Boards

Let’s start small. Consider a board of n columns, but only 2 rows. My claim is that Black will never lose a game on this board. Even if n were to be practical infinity.

This is how B should play:

1. Pair up all the n rows in groups of 2. If n is odd let the nth row be alone.
2. If W plays in row 1, play in row 2 (pair). If W plays in row 2, play in row 1.
3. If W plays in row N, play in row N.

This will always result in a draw, since only way W could win is if it were to get its coin in 4 consecutive rows side by side. This is prevented by B.

Another solved board is with 2n rows (even) and columns ≤ 6. This strategy could also be used for ensuring B always draws.

1. If W plays in columns 1, 2, 5 or 6, B plays in the same column.
2. If W plays for the first time in column 3 or 4, B plays in the other column.
3. Otherwise, if W plays in column 3 or 4, and B can still play in it, B plays in the same column
4. If W plays in column 3 or 4, and B can not play in it, B plays in the other column.

Since B never allows a vertical 4 for W, that is out of the question. For horizontal 4 at row 1, B ends up occupying at least 1 of the two bottom columns, hence denying that for W as well. For any other horizontal 4, it is only possible in odd rows for W. But in column 3 and 4, B ends up having at least 1 in either of the two in all odd rows. Diagonal is not possible at all since W will have all coins at odd rows in column 1, 2, 5 and 6.

Threats

Useless Threats

The threats by W in row 3,4,5 are considered to be useless, due to the threat by B in row 2. Since W cannot move in column 2 and 6, it has to fill column 7. Even number of rows mean that W will still have the turn when column 7 is filled, meaning B will end up winning.

Whether a threat is useless or useful is dependant on control of Zugzwang (explained later).

Odd Even Threat

A threat is only useful if a player is forced to play in a row just below that of the threat. Usually that happens when other columns are filled. In such cases, generally, W has only odd rows, and B has even rows.

Black has odd threats, and White has even. If they are in the same column, the lower threat will win (as seen above)

Generally speaking, W threat is stronger than that of B. Here is how everything rolls out:

• W has odd, B has even threat: W will win.
• W has even, B has even threat: B will win.
• W has even, B has odd threat: Draw.
• W has odd, B has odd threat: Draw. A simple example consisting of multiple threats is:

Here, B has odd threat at c3 and W has odd threat at f3. Going by the table, it should be a draw. Lets play it out. W has to give up its own threat to play the game, which would ideally result in a draw, since B will have to give up its threat in c. But what happens is that B gets to create a new threat at c2 due to coin at f5. This gives B consecutive threats, and thus it wins.

This tells us that though parity of threats tells us a good amount about the winner, we need to be careful about new threats.

Zugzwang

This is a very basic but powerful concept in Connect 4. Zugzwang basically means to force a player to make a move they would rather not make. This is due to the simple rule that they have to make a move, and the constraints of the board.

Initial Position

W always moves first. Therefore B always is in a position to play follow up, hence to control the Zugzwang. Suppose B plays follow up from the beginning, you would end up with a board like this:

Though this is an illegal position, it is interesting to note who won first. Since W controls whole first row, naturally W won the game first. This shows that follow up is not a good strategy at the start of the game for B.

Other Positions

The following board represents a position where W is in control of the Zugzwang:

Here, W has an odd threat in column a. Knowing this, B won’t play there. Since on the rest of the board, odd number of squares are remaining, whoever plays first here, the opposite will have to play in column a. Since W is playing the first, it can control the zugzwang to force B to play at a2. The only option B has to go against the zugzwang and connect its 4 men, but still, it is W’s game to lose.

In this case, B has control of Zugzwang due to even threats

B and W ideally do not want to be the first to play in b or f. Other than these 2, the total number of boxes remaining is even. This means whoever plays first here, will be the player *forced to play first in either column b or f. That means at the end, W will have to play in b1 or f1, thus losing. B is in complete control of Zugzwang here and can play follow up

References

• Resources by Victor Allis
• Alpha Beta Pruning based heuristics
• Principles and Tehniques BY Stanford
• C4 Numbers by oeis org
• Math oriented resources behind Connect-4