Connect Four

Wikipedia-logo.png

Wikipedia has related information at Connect four

Theory

       The board has 42 spaces: 7 columns (vertical lines) and 6 rows (horizontal lines). When all 42 spaces are empty, it is the first player's (Red) turn to move. It is Red's turn again when there are 40 empty spaces, and again when there are 38 empty spaces. There is a pattern: when the number of empty spaces is even, it is Red's turn to move. Conversely, when there are an odd number of empty spaces, it's Black's turn.

       Often there are certain spaces that both players want to occupy and don't want the opponent to occupy. These shall be referred to as "critical" spaces. A wise player will never move under a critical space, but instead wait for the opponent to do so. If both players play this way, no critical space will be playable until one player is forced to move under it due to having no other options (this situation is known as "zugzwang"). Who gets to occupy critical spaces depends, of course, on whose turn it will be when the only playable spaces are those directly below the critical spaces. This depends on the number of empty spaces remaining on the board when the only playable spaces are those directly below the critical spaces. Whether or not that number is even or odd can be predicted based on how many spaces are above the above the critical spaces (whether the critical spaces are on even rows or odd rows*), and how many critical spaces there are. *Note: "odd rows" refers to the 3rd and 5th row up, and excludes the bottom row because its spaces are always playable.

       A critical space on an even row has an even number of empty spaces above it. For instance, the 2nd row has four rows above it, therefore any space on the 2nd row has 4 spaces above it. A critical space on an odd row has an odd number of empty spaces above it.

Theory-based strategy for 7x6 board

       Expert players attempt to create a long-term attack that one's opponent will be forced to move under late in the game when the board is nearly filled. There is a rule of thumb that can be used to tell which kinds of attacks are good long-term attacks (leading to victory), and which attacks the opponent will get to block. Red needs one more unshared attack on an odd row than Black in order to win, or and odd number of shared odd-row attacks. Black needs either an even-row attack or a combination of odd-row attacks. If Black is to win via odd-row attacks, Black needs 2 odd-row attacks, each on a different column, and Red must have no odd-row attack on any column separate from Black's 2 columns, and no even threat below either of Black's odd-row attacks. A draw results if Red has an odd-row attack in a separate column from Black's odd-row threats (separate attacks like these will hereby be referred to as “unshared” as earlier). When Black wins, it is usually by an attack on an even row because those attacks are easier to obtain.

       If both players play flawlessly, Red wins. Therefore, in short, Red's strategy is to play offense and seek an odd-row attack while preventing Black's odd threats (and even threats below his own odd threats). Black's strategy is primarily to defend Red's odd-row attacks and then to obtain (usually) an even-row attack. The major reason Black is on defense is that if Red has an odd-row attack and Black has an even-row attack, Red wins. Black should be content to earn a draw against Red, because it often means Black outplayed Red since Red has the advantage.

Tactics

        (((7/9/2009: Section expected to be completed in 2-3 months)))

Additional Resources

Both provide pictures and examples. Allis' tutorial takes a unique approach and presents nine fundamental rules which are the basis of Allis' Connect Four engine Victor. Allen's has brief discussion of early-game moves. The authors are the first to solve the game, having solved it independently in 1987 only weeks apart from each other.1

1http://web.archive.org/web/20061011163947/http://freepages.genealogy.rootsweb.com/~jamesdow/Tech/c4tutor.htm

Strategy for any board size, 2D or 3D

Note: Any board size’ strategy can be derived using the method of the "Theory" section. The same generalizations cannot always be made, but using the same method, one will arrive at the correct new generalizations and understand why the bullet-rules below are true.

*While expert players on LittleGolem believe 8x8 to be a second player win, no proof is known.

Note:

Even Height

       With these boards, everything is the same is in 7x6 since 7x6 falls in this category. The only difference between 7x6 and other board sizes of this category is the win/loss results, depending on the board size. The strategy section above is summarized below:

For Red to win:

For Black to win:

Even domain, odd height

Remark: The even rows in these types of boards are like 7x6's odd rows.

Note: the situation described in the "Tactics" section applies to (even)by(odd) boards if one reads the section replacing "odd" with "even" and vice versa. ("Red" and "Black" stay the same)

Odd domain

Remark: The even rows in odd-area boards are like 7x6's odd rows, and Red in odd-area boards is like Black in 7x6 (but the win/loss results vary with size).

Note: the situation described in the "Tactics" section applies to (odd)by(odd) boards if one reads the section replacing "Red" with "Black" and vice versa, and replacing "odd" with "even" and vice versa.

Theory and strategy for selected variants

       The theory of the following variants is, as you will see, derived using the same principles as used for regular Connect Four and its board size variations.

2-way gravity (aka "Connect Four Flip")

Section forthcoming: expected to be complete within two weeks.

Edge (4-way/6-way) gravity

Click for explanation of the game rules (on a 2D board). (referred to as "Stack 4x4")

       Red moves when the number of empty spaces = even. There are two types of long-term 3-piece attacks: "even zugzwang value" and "odd zugzwang value", whose meanings will be explained. Furthermore, there are 2 ways to make attacks: orthogonally (horizontally or vertically) or diagonally.

       An orthogonal attack can create up to 2 critical spaces. If it only forms one, the zugzwang situation will be such that one player will be forced to move to one of 4 spaces--2 spaces in the column where the critical space lies and 2 spaces in the row where it lies. Spaces like these---which, when filled, allow the critical space to be occupied on the next turn---will hereby be referred to as "zugzwang spaces". So orthogonals with one end and discontinuous (unconnected/gapped) form 4 zugzwang spaces and 1 critical space, which means when Zugzwang occurs, 5 empty spaces remain. This sum will be referred to as a "zugzwang value" for convenience. Single critical space orthogonals, as shown, have a zugzwang value of 5--or more importantly, an odd zugzwang value.

An orthogonal can form 2 critical spaces by one of two ways: an open-ended connected line (being at least 3 spaces from either perpendicular edge of the board or 2 spaces from any legal move in the extension of the line), or a discontinuous line with two gaps. In both cases, there are 6 zugzwang spaces. Its zugzwang value (ZV from now on) is 8, hence is even. Note, however, that once the 1st critical space is occupied by one player, the 2nd one is immediately playable by the other. Therefore in some situations, an open-ended orthogonal attack can be thought of as forming 1 critical space with 4 zugzwang spaces, and thus having an odd ZV (the "one" critical space could be on either side of the line, depending on which one the opponent chooses).

       Diagonals, whether continuous or not, form 4 zugzwang spaces for each critical space they create. A discontinuous diagonal forms 1 critical space and therefore has an odd ZV (five). A continuous, open-ended diagonal has a ZV of: (2 critical spaces) + 4 + 4 = 10, which is of course even. Notice that this is a combination of 2 odd-ZV attacks. A closed-ended diagonal, for example, has only 1 critical space and 4 zugzwang spaces, and therefore has a ZV of 5 which is odd.

        For 3D, box-shaped boards with 6-way gravity, the only thing that changes is that 2 more zugzwang spaces are created by each kind of attack. Adding an even # to another # does not change the evenness/oddness of it. Therefore, the evenness/oddness of the ZV's will be the same, and each player will need the same attacks as in 4-way-gravity.

From these facts, the following conclusions can be drawn.

Boards with even domain

Note: shared attacks are probably rare situations in the edge-gravity variant, but they are possible.

Boards with odd domain

(In other words, what a color needs for boards with odd domain is the opposite of what that color needs for boards of even domain.)

Zero gravity, surface-sticking

Section forthcoming: expected to be complete within two weeks.

No barriers

Subsection to be included in forthcoming section.

With barriers

Subsection to be included in forthcoming section.

Two-move turns

Stacking (downward gravity)

Rules: Red's 1st turn is one move. Then every turn after that (including Black's first turn) is 2 moves. Other than that, same rules as standard Connect Four.

       In this variant, which rows each player needs depends not on whether they are even or odd, but on which player moves last (and on the board dimensions).

Who moves first depends only on how many turns it takes to fill the entire board. If the # of turns is even, then each player has the same # of turns and therefore Black moves last. If the # of turns is odd, Red gets 1 more turn than Black and therefore Red moves last.

For boards with even domain, the last move is the first and only move of the last turn. On boards with odd domain, the last move is the 2nd move of the last turn. This is important because it determines which zugzwang-values each player needs.

Consider, for example, the 8x8 board. Red moves last and takes the top row; he moves when there is 1 space left. Before that, Black moves and takes the 6th and 7th row; she moves when there are 2 and 3 spaces left. The alternation continues and the following list can be generated:

If the board were instead 9x9, Red moves last and takes rows 8 and 9, thus moving when there are 1 and 2 spaces left. This will change the list to:

To see why this is important, consider some attacks. It has been demonstrated that on an 8x8 board, a 6th-row attack is good for Black. It has a ZV of 5 (4th, 5th, 6th, 7th, and 8th row are empty when Zugzwang occurs) and notice from the list that Red moves when there are 5 empty spaces left. One 6th-row attack would therefore be useless for Red. But what if Red had two 6th-row attacks? The combined ZV would be 10, and notice from the list that Black moves when there are 10 empty spaces left. On Red's turn there would be 9 empty spaces left, and Red would move twice in one column and make Connect Four with one of the 6th-row attacks, so two -6th row attacks are good for Red in 8x8. The complete strategy for the 2-move-turn variant can be solved using this method.

The strategy will now be categorized by board dimensions. But note that the bottom 2 rows are never included in the list of strategic attacks since they are always immediately playable. Strategic rules of thumb only apply to critical spaces that will not be filled until immediately after Zugzwang.

Even domain
Even height

Last mover can win with:

2nd-to-last mover can win with:

The following situations are solved by adding the ZV's of each attack together and knowing which player benefits from the new ZV that results.

(For the situations above where the 1st attack is + and the 2nd is -, the same results apply whether the last-mover has both of the mentioned attacks (1 good and one bad) or whether the last-mover has the first attack and the 2nd-to-last mover has the second attack (meaning, each player has 1 good attack). For the situations with 2 good attacks or 2 bad attacks, the result assumes that the corresponding player has both of the attacks.)

       ~~~Result for 7x6 board: Black wins.

Odd height

Last mover can win with:

2nd-to-last mover can win with:

Other notable situations:

Odd domain

Last mover can win with:

2nd-to-last mover can win with:

Other notable situations:

Four-way/6-way gravity

This (non-existent, but possible) variation is a combination of the 4-way/6-way gravity variant and the 2-move turn variant.

Who moves last is relevant. The same 2 (4 condensed to 2) formulas apply for figuring out the # of turns as with the regular 2-move-turn variant:

Critical spaces in this variant have higher ZV's than those in 1-move-turn edge gravity. There are three different base ZV's that can be created: 9, 14, and 16.

The kinds of attacks needed for each player are equivalent to those needed in the regular 2-move-turn variant in the corresponding board sizes.

By "equivalent attacks" the following is meant. Consider two situations: a connected single-ended orthogonal attack on an 8x8 board with 4-way gravity, and a 4th-row attack on an 8x8 board with downward gravity. Both situations have a zugzwang-value of 7, and therefore are equivalent. So on an 8x8 board, the last mover (who would benefit from a 4th-row attack in the regular 2-move variant) would benefit from a connected single-ended orthogonal attack in 4-way gravity 2-move-turn.

In similar fashion (using the principle of equivalence) one derives the following rules:

Even domain

Last mover can win with:

2nd-to-last mover can win with:

Odd domain

Last mover can win with:

2nd-to-last mover can win with:

Collapsing lines

Section forthcoming: expected to be complete within a few months.

Inversed

Section forthcoming: expected to be complete within a few months.

Wrap-around

Section forthcoming: expected to be complete within a few months.

Diagonal stacking

Rules: a piece can be placed diagonally above another piece. The bottom row is always playable.

       There is only one type of long-term diagonal attack that can be made: a connected one pointed downward (meaning the critical space is below it). This has a ZV of 3 (resulting from the critical space and the 2 zugzwang-spaces below it).

Single orthogonals, whether connected or gapped, have a ZV of 3. Doubles have a ZV of 6.

In short, all critical spaces have 2 zugzwang-spaces.

Since the turns consist of only one move each, the strategy can be understood in more than one way. One could think in terms of last-mover and 2nd-to-last mover (as with 2-move-turn variants), or simply in terms of Red and Black and the evenness/oddness of the # of empty spaces left (as with regular Connect Four). The latter approach will be taken and the strategic rules are:

Even domain

Odd domain

Chess-knight motion, no gravity

Rules: Red's first move can be anywhere, then pieces can be placed a knight-move away from another piece.

       No matter how a critical space is made, it will have a ZV of 9. All single-critical-space attacks will have ZV's of 9 and all double-critical-space attacks will have ZV's of 18.

Strategic rules:

Even domain

Odd domain

Scoring variant

Section forthcoming: expected to be complete within two weeks.

25% developed