11.5: Four-In-A-Row, a “Connect Four” Clone

Last updated
Save as PDF

Page ID: 13629

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

The game "Connect Four" has a 7 x 6 board where the players take turns dropping tokens from the top of the board. The tokens will fall from the top of each column and come to rest on the bottom of the board or on top of the topmost token in that column. A player wins when four of their tokens line up in a row either horizontally, vertically, or diagonally.

The AI for this game is pretty good. It simulates every possible move it can make, then simulates every possible move the human player can make in response to each of those moves, and then simulates every possible move it can make in response to that, and then simulates every possible move the human player could make in response to each of those moves! After all that thinking, the computer determines which move is most likely to lead to it winning.

So the computer is kind of tough to beat. I usually lose to it.

Since there are seven possible moves you can make on your turn (unless some columns are full), and seven possible moves the opponent could make, and seven moves in response to that, and seven moves in response to that, that means that on each turn the computer is considering 7 x 7 x 7 x 7 = 2,401 possible moves. You can make the computer consider the game even further by setting the DIFFICULTY constant to a higher number, but when I set to a value larger than 2, the computer takes a long time to calculate its turn.

You can also make the computer easier by setting DIFFICULTY to 1. Then the computer only considers each of its moves and the player’s possible responses to those moves. If you set the DIFFICULTY to 0, then the computer loses all intelligence and simply makes random moves.