Jump to content

Connect Four

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by Ianushii (talk | contribs) at 18:59, 20 April 2016 (→Mathematical solution). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

Connect Four
Game play of Connect Four
DesignersHoward Wexler[1]
Ned Strongin[2]
PublishersMilton Bradley / Hasbro
Publication1974
GenresAbstract strategy
Players2
Playing time1 - 5 minutes
Age range6 and up

Connect Four (also known as Captain's Mistress, Four Up, Plot Four, Find Four, Fourplay, Four in a Row, Four in a Line and Gravitrips (in Soviet Union) ) is a two-player connection game in which the players first choose a color and then take turns dropping colored discs from the top into a seven-column, six-row vertically suspended grid. The pieces fall straight down, occupying the next available space within the column. The objective of the game is to connect four of one's own discs of the same color next to each other vertically, horizontally, or diagonally before your opponent. Connect Four is a strongly solved game. The first player can always win by playing the right moves.

The game was first sold under the famous Connect Four trademark by Milton Bradley in February 1974.

Mathematical solution

Connect Four is a two-player game with "perfect information". This term describes games where one player at a time plays, players have all the information about moves that have taken place, and all moves that can take place, for a given game state. Connect Four also belongs to the classification of an adversarial, zero-sum game, since a player's advantage is an opponent's disadvantage.

One measure of complexity of the Connect Four game is the number of possible games board positions. For classic Connect Four played on 6 high, 7 wide grid, there are 4,531,985,219,092 positions[3] for all game boards populated with 0 to 42 pieces.

The game was first solved by James Dow Allen (October 1, 1988), and independently by Victor Allis (October 16, 1988).[4] Allis describes a knowledge based approach,[5] with nine strategies, as a solution for Connect Four. Allen also describes winning strategies[6][7] in his analysis of the game. At the time of the initial solutions for Connect Four, brute force analysis was not deemed feasible given the game's complexity and the computer technology available at the time.

Connect Four has since been solved with brute force methods beginning with John Tromp's work in compiling an 8-ply database[4][8] (Feb 4, 1995). The artificial intelligence algorithms able to strongly solve Connect Four are minimax or negamax, with optimizations that include alpha-beta pruning, dynamic history ordering of game player moves, and transposition tables. The code for solving Connect Four with these methods is also the basis for the Fhourstones integer performance benchmark.

The solved conclusion for Connect Four is first player win. With perfect play, the first player can force a win,[4][5][6] on or before the 41st move[9] by starting in the middle column. The game is a theoretical draw when the first player starts in the columns adjacent to the center. For the edges of the game board, column 1 and 2 on left, and column 7 and 6 on right, the exact move-value score for first player start is loss on the 40th move,[9] and loss on the 42nd move,[9] respectively. In other words, by starting with the four outer columns, the first player allows the second player to force a win.

Rule variations

There are many variations of Connect Four with differing game board sizes, board arrangements, game pieces, and/or gameplay rules. Many variations are popular with game theory and artificial intelligence research, rather than with physical game boards and gameplay by persons.

The most commonly used Connect Four board size is 7 columns × 6 rows. Size variations include 8×7, 9×7, 10×7, 8×8, and Infinite Connect-Four.[10] Alternate board arrangements include Cylinder-Infinite Connect-Four.[11] One board variation available as a physical game is Hasbro's Connect 4x4.

A travel version of the Milton Bradley game.

Several versions of Hasbro's Connect Four physical gameboard make it easy to remove game pieces from the bottom one at a time. Along with traditional gameplay, this feature allows for variations of the game.[12]

Pop Out

Pop Out starts the same as traditional gameplay, with an empty board and players alternating turns placing their own colored discs into the board. During each turn, a player can either add another disc from the top or, if one has any discs of his or her own color on the bottom row, remove (or "pop out") a disc of one's own color from the bottom. Popping a disc out from the bottom drops every disc above it down one space, changing their relationship with the rest of the board and changing the possibilities for a connection. The first player to connect four of their discs horizontally, vertically, or diagonally wins the game.

Pop 10

Before play begins, Pop 10 is set up differently from the traditional game. Taking turns, each player places their opponent's color discs into the slots filling up only the bottom row, then moving on to the next row until it is filled and so forth until all rows have been filled.

Gameplay works by players taking turns removing a disc of one's own color through the bottom of the board. If the disc that was removed was part of a four-disc connection at the time of its removal, the player sets it aside out of play and immediately takes another turn. If it was not part of a "connect four", then it must be placed back on the board through a slot at the top into any open space and the turn ends, switching to the other player. The first player to set aside ten discs of his or her color wins the game.

5-in-a-Row

The 5-in-a-Row variation for Connect Four is a game played on a 6 high, 9 wide, grid. Hasbro adds two additional board columns, already filled with player pieces in an alternating pattern, to the left and right sides of their standard 6 by 7 game board. The game plays similarly to the original Connect Four, except players must now get five pieces in a row to win. Notice this is still a 42-ply game, since the two new columns added to the game represent twelve game pieces already played, before the start of a game.

Power Up

In this variation of Connect Four, players begin a game with one or more specially marked, "Power Checkers" game pieces, which each player may choose to play once per game. When playing a piece marked with an anvil icon, for example, the player may immediately pop out all pieces below it, leaving the anvil piece at the bottom row of the game board. Other marked game pieces include one with a wall icon, allowing a player to play a second consecutive non winning turn with an unmarked piece, a "×2" icon, allowing for an unrestricted second turn with an unmarked piece, and a bomb icon, allowing a player to immediately pop out an opponent's piece.

Other versions

Hasbro also produce various sizes of Giant Connect Four, suitable for outdoor use. The largest is built from weather-resistant wood, and measures 120 cm in both width and height. Connect Four was released for the Microvision video game console in 1979, developed by Robert Hoffberg. It was also released for the Texas Instruments 99/4 computer the same year.

With the proliferation of mobile devices, Connect Four has regained popularity as a game that can be played quickly and against another person over an Internet connection.

In 2015 Winning Moves published Connect 4 Twist & Turn. This game variant features a game tower instead of the flat game grid. The tower has 5 rings that twist independently. Game play is similar to standard Connect 4 where players try to get 4 in a row of their own colored discs. However, with Twist & Turn, players have the choice to twist a ring after they have played a piece. It adds a subtle layer of strategy to game play.

Algorithms

As opposed to calculating perfect play, computer algorithms that play Connect Four must be able to run in real time and find good moves in just a few seconds. The most common real-time algorithm for Connect Four is alpha-beta pruning, usually run at a depth of around 10 plies.[13] While this method can play strongly against humans, ultimately a more efficient way to get a fast and strong solution is using a Monte Carlo tree search.[14] This method has a particular advantage in Connect Four since many games last close to the end when one player is forced to play a move that will allow their opponent to play a winning move. Monte Carlo uses simulations of the whole game when building its tree, and thus statistically provides moves that are not only good in the present, but would also bring about good end game positions.

Due to fact that the Monte Carlo tree search was first popularized in 2006 for a Computer Go program,[15] implementation of the method for Connect Four is rare. The few examples that exist generally outplay their alpha-beta pruning counterparts in the end game, view the external links for examples.

See also

References

  1. ^ "A City College Toy Story". CUNY Matters. City University of New York. Winter 2001.
  2. ^ "Obituary: Ned Strongin". New York Times. April 18, 2011.
  3. ^ Number of legal 7 X 6 Connect-Four positions after n plies, Online Encyclopedia of Integer Sequences
  4. ^ a b c "John's Connect Four Playground". Homepages. May 25, 2010.
  5. ^ a b Allis, Victor, A Knowledge-based Approach of Connect-Four, Vrije Universiteit, October 1988
  6. ^ a b Allen, James D., Expert Play in Connect-Four, 1990
  7. ^ Allen, James D. (2010). The Complete Book of Connect 4: History, Strategy, Puzzles. Sterling Publishing Company. ISBN 1402756216.
  8. ^ Tromp, John, Connect-4 Data Set, February 4, 1995
  9. ^ a b c asun.net, Four in a Row Solver, August 2013
  10. ^ Yamaguchi, Y.; K. Yamaguchi; T. Tanaka; T. Kaneko (2012). "Infinite Connect-Four is solved: Draw". Advances in Computer Games, ACG 2011. LNCS 7168: 208–219.
  11. ^ Yamaguchi, Y.; K. Yamaguchi; T. Tanaka (2013). "Cylinder-Infinite-Connect-Four except for Widths 2, 6, and 11 is Solved: Drawn". The 8th International Conference on Computers and Games (CG2013).
  12. ^ "Connect 4 Instructions" (PDF). Hasbro Inc. 2009.
  13. ^ "Teaching a computer to play Connect Four using the Minimax-Algorithm". Johannes' Blog. Retrieved 2015-12-09.
  14. ^ "The Monte Carlo Method for Game AI". beej.us. Retrieved 2015-12-09.
  15. ^ Coulom, Rémi (January 2009). "The Monte-Carlo Revolution in Go" (PDF). Retrieved 2015-12-09.
  16. ^ Thair, David (22 May 2009). "HIGNFY Guest interview: Stuart Maconie". Comedy Blog. BBC.
Wikibooks has more on the topic of: Connect Four
Retrieved from "https://en.wikipedia.org/w/index.php?title=Connect_Four&oldid=716258016"