Connect-Four

Rules of the Game

Connect-four (also known as Four-in-a-row) is a board game which is played by two players on an 7x6 vertical grid with pieces that are dropped into the top of the grid to slide down to the lowest available position in that column. The objective is to get four of one's own pieces in a line horizontally, vertically or diagonally.

Each player drops a piece into the grid in turn. The game ends when one of the players achieves a line of four (or more) pieces, or when the grid is full. If neither player has managed to achieve a line of four then the game is drawn. The game starts with an empty grid and red plays first.

Conventions

Squares on the grid are referenced by a number from 1 to 7 representing the column and a number from 1 to 6 representing the row, as shown in the board below, which has yellow winning the game with a diagonal line (1,2), (2,3), (3,4) and (4,5).

Game Complexity

Connect-four has a state-space complexity (the number of nodes in the game tree for a fully evaluated game) in the order of 10¹⁴.

Strategy

Some of the common strategies used when playing connect-four are discussed here.

Groups

A group (or line) is a collection of two or more pieces in an unbroken line horizontally, vertically or diagonally. A group of four represents a winning situation. Simply attempting to create a group of four early in a game will be blocked by an opponent, so usually several lines need to be built up simultaneously.

Possible Winning Groups

On an empty board, there are 69 possible ways to create a group of four. As the game progresses, these possibilities decrease as the opponent places pieces within these groups. The greater the number of groups that have not been broken by an opponent piece, the higher the chance of winning. Additionally, the more pieces that a player has in these unbroken groups, the more useful these groups become. The diagram below shows all the winning groups, numbered 1 to 69.

It is evident from the above diagram that some squares on the board participate in more possible winning groups than others. As a result, these squares tend to be slightly more valuable. The diagram below shows the distribution of the number of winning groups that each square participates in.

Threats

A threat exists when three of the pieces required for creating a group four are in place and the fourth square is open.

An immediate threat (or atari) is a threat in which the fourth square does not have an open square below it; which means that unless the opponent can win on the next move, they must play in that column. Creating an immediate threat is a way of forcing the opponent to make a particular move. Creating a double immediate threat results in victory if the opponent cannot create a group of four themselves.

An active threat is a threat in which the fourth square has an open square below it, but not below that; which means that if the opponent plays in this column the player will be able to complete the group. Active threats are therefore useful in limiting where the opponent can play.

Threats are called odd or even, depending on the row on which they occur. For example, in the board below, red has created an odd active threat in column 6.

A threat is called shared if the opponent has an equivalent threat in the same column. So, a shared odd threat requires an odd threat for each player in the same column and a shared even threat requires an even threat for each player in the same column.

As red plays first, after every move by red an odd number of open squares remain on the board and after every move by yellow an even number of open squares remain on the board. Given this, if the board is completely full except for a single line, red will win if there is an odd red threat in the column and no even yellow threats, or only even yellow threats above the red threat. Conversely yellow will win if there is an even yellow threat in the column and no odd red threats, or only odd red threats above the yellow threat. Logically, one would think then that the strategy for red is to create odd threats and for yellow to create even threats. This situation however only holds for a single column and is more complicated when the whole board is considered. Generally, the rules below may be applied.

For red to win, red needs:

• more odd threats (shared or unshared) than yellow

For yellow to win, yellow needs:

• more odd threats than red if one or more threats are shared
• an even number of odd threats which is the same number of odd threats than red, if one or more threats are shared
• the same number of odd threats (which can be zero) as red plus at least one even threat

Opening Moves

It can be shown that with perfect play, red can force a win by starting in the middle column (4). Yellow can force a win by starting in one of the four outer columns (1, 2, 6 or 7), or can obtain a draw starting with one of the columns adjacent to the middle column (3 or 5).