Solving Connect Four with Game Theory
Connect four is a non-cooperative game between two players, red and black, played on a vertical six row, seven column grid. In each game, red makes the first move, dropping a disk or “stone” into one of the seven columns (labeled A-G from left to right), where it then falls to the lowest unoccupied cell in that column. The two players then alternate turns dropping disks into one of the columns until one player is able to “connect four” disks either horizontally, vertically, or diagonally. For example, in the figure below, red wins because he or she creates a diagonal row of four adjacent disks.
Red Player Wins
Unfortunately, players might have little incentive to be the second player, as connect four is a “perfectly solved” game. In fact, it is mathematically impossible for the red player to lose at any game of connect four. All the red player has to do is to begin the game by dropping a disk in the center column (D), and then play perfectly from there. If he or she does so, it is guaranteed that red will win in 41 or fewer moves. Alternatively, if red drops the first disk in the two outward columns (A, B, F, or G), black can play perfectly to guarantee that red loses. Finally, if red drops the first disk in the two columns adjacent to the center (C or E), then the game will always end in a draw.
So if connect four is guaranteed victory for the red player, why do people still play the game? The answer lies in numbers. While in theory, it is an assured victory for red; the only problem is that red must play perfectly. In practice, perfect play is difficult considering that according to Numberphile, there are 4,531,985,219,092 ways to fill a Connect Four grid. In fact, connect four was only solved in 1988 when Victor Allis published this result in his master’s thesis, employing the use of computer programs to generate his proof.
In fact, game theory lies at the center of connect four, and as a result, is directly consequential to the “perfect solution” of guaranteeing red player’s win. This is because connect four is an example of an adversarial, finite zero-sum game of perfect information. This means that there is two players, red and black, play against each other in a game where only one player can win. The strategies given to each player is the column where they can drop their disk, and because there are only a finite amount of positions players can place disks, the game is has a “finite” amount of states. Finally, the payoffs are the positions of disks that each player gains. Moreover, wherever one player gets an advantageous disk position, the other player loses the exact same position such that the sum of payoffs of both players equals zero, resulting in a “finite zero-sum” game. Since the players alternate turns, each player knows what strategy the other player chooses, so connect four is also a game of perfect information.
As proved in the Penn State article, in such finite zero-sum games of perfect information, two results are true: 1) There exists a pure strategy Nash Equilibrium, and 2) The Nash Equilibrium strategies are dominant strategies. In the case of connect four, Red has a dominant strategy which will always result in a win within 41 moves. In fact, much of the “perfect solution” to connect four is built upon this dominant strategy in a theorem known as minimax. In this theorem, player one attempts to maximize his payoff during his turn, while player two tries to minimize player one’s payoff. However, there is always a dominant strategy that player one can play to maximize his payoff, regardless of player two’s strategy. If we apply this theorem to a zero-sum game, we essentially find the Nash Equilibrium. As a result, in connect four, Red always has a dominant strategy which guarantees a win. Moreover, this principle can be applied to other games such as chess such that either player has a dominant strategy to victory or to force a draw. Fortunately, the computational power required to “solve” chess is too high for current computers. However, if one day we manage to find the Nash Equilibrium for all of these games, will they ever be worth playing? I believe so, as humans cannot possibly compute these “perfect solutions” without the aid of computers.
References:
https://www.youtube.com/watch?t=7&v=yDWPi1pZ0Po
http://grizzly.la.psu.edu/~aza12/402_chapter17.pdf
https://johannes89.wordpress.com/2014/02/09/teaching-a-computer-to-play-connect-four-using-the-minimax-algorithm/
http://www.informatik.uni-trier.de/~fernau/DSL0607/Masterthesis-Viergewinnt.pdf
I don’t always go first but when I do……