A Connect Four game in progress, using yellow and red discs, which slide to the bottommost open locations under the influence of gravity.

1988

CONNECT FOUR

For a Christmas present, Toby Walsh (b. 1964), a professor of artificial intelligence at the University of New South Wales, once gave his father a program that perfectly plays the game of Connect Four^®. His dad, who had previously loved playing the game, remarked that the program took the fun out of the game, and Walsh had to agree. When smartphones become superior to humans in virtually all games and creative endeavors, from music composition to novel writing, what effect will that have on the collective psyche of humanity?

Connect Four is played by two people using discs (yellow vs. red) on a vertical board with seven columns and six rows. As the discs slide down a column to the bottommost open grid position, the objective is to be the first player to form a line of four adjacent discs of one’s own color (horizontally, vertically, or diagonally). The game is reminiscent of a tic-tac-toe game, but with gravity influencing the pieces. Of course, Connect Four is much more complicated than tic-tac-toe: if one considers all possible game boards filled with 0 to 42 discs, there are a walloping 4,531,985,219,092 positions. In fact, the number of possible positions after n discs have been played on a standard 7 × 6 board grows as thus (where n = 0, 1, 2, 3, . . . ): 1, 7, 56, 252, 1260, 4620, 18480, 59815, 206780, 605934, 1869840, 5038572, 14164920, 35459424, 91871208, 214864650, 516936420, 1134183050, 2546423880, 5252058812, 11031780760, 21406686756, 42121344720, 76871042612 . . .

On October 1, 1988, computer scientist James D. Allen finally “solved” Connect Four—that is, he devised an algorithm that could predict the outcome of moves (win, lose, or draw) from every possible position, assuming players play perfectly from that point on. Two weeks later, the game was solved independently by computer scientist Victor Allis, who employed an AI approach with nine strategies. As a result, we now know that Connect Four can always be won by the first player with perfect play.

There is much room for further research on variations of Connect Four. For example, imagine playing on boards that are wrapped into a cylinder, or playing on boards with different grid sizes, additional colors, and more than two dimensions. The number of possible positions and outcomes would be mind-boggling.