Connect Four

  • For other reading until then, Sterling Publishing and Hasbro are supposed to release a book soon by James Allen entitled, The Complete Book of Connect Four. In addition, refer to the Additional Resources section.

TheoryEdit

       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.

  • If the only critical space is even (on an even row), the number of empty spaces remaining when a player is forced to move underneath the empty space is even. For example, if the critical space is on the 2nd row, there will be 6 empty spaces remaining (one full column) when the move underneath the critical space is forced. An even number of empty spaces means it is Red's turn, therefore Red must move under the critical space and Black will occupy the critical space.
  • If there are multiple critical spaces and all of them are even, the number of empty spaces remaining when Zugzwang occurs is: (even #) + (even #) = (even #) and therefore it will be Red's turn when Zugzwang occurs and Black will occupy the critical spaces.
  • If the only critical space is odd (on an odd row), there will an odd # of empty spaces when Zugzwang occurs. Therefore it will be Black's turn, and therefore Red will get the critical space.
  • If there are 2 critical spaces and both are odd, the sum of empty spaces when Zugzwang occurs will be: (odd #) + (odd #) = (even #) and therefore it will be Red's turn to move, allowing Black to occupy whichever critical space Red move under. If Black's occupation of that critical space does not end the game, the game will continue until another zugzwang occurs. In that situation, there will be one critical space on an odd row, which is the same situation as previously described. Red will therefore occupy the 2nd critical space. The following generalization can be made: For any even # of odd-row critical spaces, Black will get the 1st, 3rd, etc., and Red will get the 2nd, 4th, etc.
  • If there are 3 critical spaces and all 3 are odd, the sum of empty spaces when Zugzwang occurs is: (odd #) + (odd #) + (odd #) = (odd #) resulting in Black's turn and therefore Red's occupation of whichever critical space Black chooses to give Red. If Red's occupation of that critical space does not end the game, the game will continue until the previous situation occurs. So another generalization can be made: For any odd # of odd-row critical spaces, Red will get the 1st, 3rd, etc., and Black will get the 2nd, 4th, etc. (Note that each generalization is implied by each other)
  • If there are 2 critical spaces, one being odd and the other being even, the following will result from Zugzwang: (odd #) + (even #) = (odd #) and therefore Red will get the first (decided by Black) critical space. Thus only odd-row critical spaces influence the result; even-row critical spaces have no affect because even #'s do not change the evenness/oddness of the sum of the empty spaces remaining.

Theory-based strategy for 7x6 boardEdit

       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.

TacticsEdit

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

Additional ResourcesEdit

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 3DEdit

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:

  • For 3D "boards", assume a box shape.
  • The bullet-rules below assume attacks that are not immediately playable.
  • A 2D board's area, or a 3D board's volume, will be referred to as its "domain".

Even HeightEdit

       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:

  • 1 more unshared odd-row attack than Black, or
  • the same # of unshared odd-row attacks as Black, plus an odd # of shared ones, or
  • an odd # of odd-row attacks (whether shared or unshared), if Black has no unshared ones

For Black to win:

  • an even-row attack, if Red has no odd-row attacks, or
  • two more unshared odd-row attacks than red, or
  • the same # of unshared odd-row attacks as Red, plus an even # of shared ones, or
  • one more unshared odd-row attack than Red, plus any # of shared ones, or
  • one unshared odd-row attack plus any number of shared ones, if Red has no unshared ones, or
  • an even # of odd-row attacks (whether shared or unshared), if Red has no unshared ones

Even domain, odd heightEdit

  • Red: 1 more unshared even-row attack than Black to win, or odd # of shared even-row attacks.
  • Black: odd-row attack or even # of even-row attacks (2 more unshared than Red, or the same # of shared) to win.
  • If Red and Black have the same # of unshared even-row attacks, the game is drawn.
  • If Red has 1 even-row attack and Black has 1 odd-row attack, Red wins.

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 domainEdit

  • Red: odd-row attack or even # of even-row attacks (2 more unshared than Black, or the same # of shared) to win.
  • Black: 1 more unshared even-row attack than Red to win, or odd # of shared even-row attacks.
  • If Red and Black have the same # of unshared even-row attacks, the game is drawn.
  • If Black has 1 even-row attack and Red has 1 odd-row attack, Black wins.

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 variantsEdit

       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")Edit

Section forthcoming: expected to be complete within two weeks.


Edge (4-way/6-way) gravityEdit

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 domainEdit

  • Red needs 1 more unshared odd-ZV attack than Black to win, or an odd # of shared odd-ZV attacks.
    • Any attack will accomplish this.
  • Black needs an even-ZV attack to win or an even # of odd-ZV attacks (2 more unshared than Red, or the same # of shared).
    • A 2 critical space orthogonal, a 2-critical-space diagonal, or 2 of any other type of attack will achieve this.
  • If Red and Black each have 1 unshared odd-ZV attack, and Black has no even-ZV attacks, the game is drawn.
  • If Red has an odd-ZV attack and Black has an even-ZV attack, Red wins.

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

Boards with odd domainEdit

  • Red needs an even-ZV attack to win or an even # of odd-ZV attacks (2 more unshared than Black, or the same # of shared).
    • A 2 critical space orthogonal, a 2-critical-space diagonal, or 2 of any other type of attack will achieve this.
  • Black needs 1 more unshared odd-ZV attack than Red to win, or an odd # of shared odd-ZV attacks.
    • Any attack will accomplish this.
  • If Red and Black each have 1 unshared odd-ZV attack, and Red has no even-ZV attacks, the game is drawn.
  • If Red has an even-ZV attack and Black has an odd-ZV attack, Black wins.

(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-stickingEdit

Section forthcoming: expected to be complete within two weeks.

No barriersEdit

Subsection to be included in forthcoming section.

With barriersEdit

Subsection to be included in forthcoming section.


Two-move turnsEdit

Stacking (downward gravity)Edit

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:

  • Red moves when there are: 1, 4,5, 8,9, 12,13, 16,17, 20,21... spaces left.

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:

  • Red moves when there are: 1,2, 5,6, 9,10, 13,14, 17,18, 21,22... spaces left.

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 domainEdit
  • # of turns = (area/2)+1
    • Alternate: if the area is a multiple of 4 (meaning, if area/4 = an integer), Red moves last. If not a multiple of 4, Black moves last.
  • Last turn consists of 1 move.
  • Last mover moves when # of empty spaces = (any multiple of 4 + 0 or 1) = {1, 4,5, 8,9, 12,13, 16,17, 20,21, 24,25...}
  • 2nd-to-last mover moves when # of empty spaces = the combination of the sets {2,3} and {any multiple of 4 + (2 or 3)} = {2,3, 6,7, 10,11, 14,15, 18,19, 22,23...}
Even heightEdit

Last mover can win with:

  • any even row being the top row or a multiple of 4 rows (2 even rows) down from the top row (note: 4 rows down from the top = 5 rows down, 8 rows down from the top = 9 rows down, and so on).
  • 1 more unshared good odd row than 2nd-to-last mover---good being a multiple of 2 odd rows down from the top row (meaning, the 4th row down or any multiple of 4 rows down from the 4th row down)---or an odd # of shared ones. (If equal # of unshared ones, a draw results.)
  • the combinations of bad attacks listed 2 paragraphs below which result in "+"

2nd-to-last mover can win with:

  • any odd row being the 2nd-to-top row or a multiple of 4 rows (2 odd rows) down from the 2nd-to-top row
  • 1 more unshared good even row than last-mover---good being the 3rd-to-top row or a multiple of 2 even rows down from the 3rd-to-top row---or an odd # of shared ones. (If equal # of unshared ones, a draw results.)
  • an odd # (>1) of bad even rows (3 more unshared than last-mover, or the same # of shared).
  • the combinations of bad attacks listed in the paragraph below which result in "-"

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.

  • Good even-row attack for last-mover (which will be referred to as "+even") + bad even-row attack for last-mover ("-even", aka "good even-row attack for 2nd-to-last mover) = good for 2nd-to-last mover. Summarized: (+even) + (-even) = -
  • (-even) + (-even) = + equivalent to (+odd)
  • (+odd) + (+odd) = - equivalent to (-odd)
  • (+even) + (+odd) = -
  • (+even) + (-odd) = +
  • (+odd) + (-odd) = +
  • (+odd) + (-even) = +

(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 heightEdit

Last mover can win with:

  • any odd row being the top row or a multiple of 4 rows (2 odd rows) down from the top row.
  • 1 more unshared good even row than 2nd-to-last mover---good being the 2nd-to-top row or a multiple of 2 even rows down from the 2nd-to-top row---or an odd # of shared ones. (If equal # of unshared ones, a draw results.)
  • the combinations of bad attacks listed 2 paragraphs below which result in "+"

2nd-to-last mover can win with:

  • any even row being the 2nd-to-top row or a multiple of 4 rows (2 even rows) down from the 2nd-to-top row.
  • 1 more unshared good odd row than last-mover---good being the 3rd-to-top row or a multiple of 2 odd rows down from the 3rd-to-top row---or an odd # of shared ones.
  • an odd # (>1) of bad odd rows (3 more unshared than last-mover, or the same # of shared).
  • the combinations of bad attacks listed in the paragraph below which result in "-"

Other notable situations:

  • (-odd) + (-odd) = + equivalent to (+even)
  • (+even) + (+even) = - equivalent to (-even)
  • (+even) + (+odd) = -
  • (+even) + (-even) = +
  • (+even) + (-odd) = +
  • (+odd) + (-odd) = -
  • (+odd) + (-even) = +
Odd domainEdit
  • # of turns = [(area-1)/2]+1 = (area+1)/2
  • Last turn consists of 2 moves.
  • Last mover moves when # of empty spaces = 1,2, (any multiple of 4 + 1 or 2)
  • 2nd-to-last mover moves when # of empty spaces = 3,4, (any multiple of 4 - 0 or 1)

Last mover can win with:

  • any even row being the 2nd-to-top row or any even row a multiple of 4 rows (2 even rows) down from the 2nd-to-top row
  • 1 more unshared good odd row than 2nd-to-last mover---good being the top row or a multiple of 4 rows (2 odd rows) down from the top row---or an odd # of shared ones.
  • an odd # (>1) of bad odd rows (3 more unshared than 2nd-to-last mover, or the same # of shared).
  • the combinations of bad attacks listed 2 paragraphs below which result in "+"

2nd-to-last mover can win with:

  • any odd row being the 3rd-to-top row or any odd row a multiple of 4 rows (2 odd rows) down from the 3rd-to-top row.
  • 1 more unshared good even row than last mover---good being the 4th-to-top row or a multiple of 4 rows (2 even rows) down from the 4th-to-top row---or an odd # of shared ones.
  • the combinations of bad attacks listed in the paragraph below which result in "-"

Other notable situations:

  • (-even) + (-even) = + equivalent to (+even)
  • (+odd) + (+odd) = - equivalent to (-even)
  • (-even) + (-odd) = +
  • (+even) + (-even) = +
  • (+even) + -(odd) = +
  • (+odd) + (-odd) = +

Four-way/6-way gravityEdit

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:

  • Even domain: # of turns = (#spaces/2)+1
  • Odd domain: # of turns = (#spaces+1)/2

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.

  • ZV's of 9 are created by any attack that creates just one critical space. ZV's of 18 are created by open-ended connected diagonals, and 2-critical-space discontinuous diagonals whose 2 critical spaces are separated by 2 diagonal spaces.
  • ZV's of 14 are created by 2-critical-space orthogonals.
  • ZV's of 16 are created by 2-critical-space diagonals whose 2 critical spaces are separated by only 1 diagonal space.

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 domainEdit

Last mover can win with:

  • 2, 3, or [(2 or 3) + (multiple of 4)] of 9-ZV attacks
  • An odd # of 14-ZV attacks
  • A good attack plus a bad attack.

2nd-to-last mover can win with:

  • 1 or [(0 or 1) + (multiple of 4)] of 9-ZV attacks
  • An even # of 14-ZV attacks
  • A 16-ZV attack
  • Two bad attacks.
Odd domainEdit

Last mover can win with:

  • 3, 4, or [(3 or 4) + (multiple of 4) of 9-ZV attacks
  • An even # of 14-ZV attacks
  • A 16-ZV attack
  • Two bad attacks.

2nd-to-last mover can win with:

  • 1, 2, or [(1 or 2) + (multiple of 4) of 9-ZV attacks
  • An odd # of 14-ZV attacks
  • A good attack plus a bad attack.

Collapsing linesEdit

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

  • Note: I've removed my colleague's submission temporarily, but will incorporate it into this section. "Teachme2play" is an expert and specializes in variants including this one.

InversedEdit

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


Wrap-aroundEdit

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


Diagonal stackingEdit

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 domainEdit

  • Red needs 1 more unshared critical space than Black, or an odd # of shared ones.
  • Black needs an even # of critical spaces (shared, or 2 more unshared than Red).

Odd domainEdit

  • Red needs an even # of critical spaces (shared, or 2 more unshared than Black).
  • Black needs 1 more unshared critical space than Red, or an odd # of shared ones.

Chess-knight motion, no gravityEdit

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 domainEdit

  • Red needs 1 more unshared critical space than Black, or an odd # of shared ones.
  • Black needs an even # of critical spaces (shared, or 2 more unshared than Red).

Odd domainEdit

  • Red needs an even # of critical spaces (shared, or 2 more unshared than Black).
  • Black needs 1 more unshared critical space than Red, or an odd # of shared ones.

Scoring variantEdit

Section forthcoming: expected to be complete within two weeks.

Last modified on 12 December 2011, at 00:31