Connect Four is a two players game which takes place on a 7x6 rectangular board placed vertically between them. One player has 21 yellow men and the other 21 red men. Each player can drop a man at the top of the board in one of the seven columns; the man falls down and fills the lower unoccupied square. Of course a player cannot drop a man in a certain column if it's already full (i.e. it already contains six men).
Even if there's no rule about who begins first, we assume, as in chess, that the lighter side makes the first move. We also use the chess notation to represent a square on the board. That is, we number rows from 1 to 7 starting from the bottom and the columns from A to G starting from the leftmost.
The object of the game is to connect four men vertically, horizzontally or diagonally. If the board is filled and no one has alligned four men then the game is drawn (i.e. after 42 moves if no one wins).
Look at the following examples...
There are two kinds of strategies in connect four. The first consists in looking ahead a few moves to avoid the opponent to win and in the same time trying to connect four men. The other is looking for a win in the long run.
Virtually all the algorithms I have seen tend to implement the first strategy with some variants of alpha beta search and the most sophisticated ones with tree branch pruning. These strategies assure more or less the unvulnerability in the short run, but they are doomed to fail in the long run because they cannot see beyond the horizzon of a few plies.
Most of the games ends between 35th and 42nd move when you or the opponent is forced to make a particular move since there's only one column available. In this circumstance most of the people believe that the winner is lucky (if there's one). That's not it. An expert player is able to make this happen much time before. Actually this is what Velena does.
The first step consist in noting that after white has moved an odd number of free squares remains on the board. Similary after black has moved an even number of free square remains. When there's only one column available it's clear that the last square will be occupied by black (if no one wins first).
ODD SQUARE: it's a square belonging to an odd row. For example d1,c1,c3, f5 are all odd squares.
EVEN SQUARE: same as above except that the row is even. For example a2, b4,c6,e2 are all even squares.
GROUP: it's a set of four squares connected horizzontally, vertically or diagonally. The first player who fills a group with his men, wins.
THREAT: it's a group filled with three men of the same color which has the fourth square empty, and also the square below the empty square is empty.
ODD THREAT: it's a therat in a group whose empty square is odd.
EVEN THREAT: same as above but the empty square is even.
DOUBLE THREAT: they are two groups which share an empty odd square; each group is filled with only two men (of the same color) and the other two squares (one for each group) are empty and are one above the other. The square below the shared square must be empty too.
Please note that this is a sufficient condition and if black can connect four men somewhere, further knowledge is required.
Similary if black has an even threat and white cannot connect four men the game will be eventually won by black.
It's clear that in both cases we assume that players make the best move available.
Things get more complex when both players have at least one group in which they can connect four men. In this case we need further investigation.
If white has an odd threat and black has an even threat and the columns in which the threats are (i.e. the empty square) are different then white can still win. Of course no player must be able to connect four men except in the group in which he has the odd/even threat stated above.
But if columns are the same then the lower threat (i.e. the lower empty square) wins.
If both players have an odd threat the game will be drawn. Unless one of them can connect four men elsewhere.
Then the strategy for white is to try to obtain an odd threat and for
black an even threat. This is not always sufficient as the restrictions
above shows but it's a good starting point to play connect four,
especially when both players are humans.
Further info can be found in the velena user's manual.
See also: Velena Home Page