Minimax Algorithm in Connect Four: CS470/570 AI Project, Spring 2018

This document presents a Connect Four game implemented with an AI using the Min-Max algorithm (specifically, the NegaMax approach). The game features both single-player (computer vs. human) and double-player modes. The single-player AI evaluates moves to maximize its chances of winning while blocking the opponent. The report includes screenshots demonstrating the game's functionality, including handling invalid inputs and showcasing victory states. The project details the algorithm's implementation, highlighting its strengths in quick decision-making but also noting potential weaknesses in providing an overly challenging experience for the human player. Improvements for future development are suggested, such as adjusting the algorithm's depth to balance difficulty and enhancing the user interface. The project was part of the CS470/570 Artificial Intelligence course in Spring 2018.

Running head: THE CONNECT FOUR GAME
The Connect Four Game
Name of the student:
Name of the University:
Author note:

1
THE CONNECT FOUR GAME
Table of Contents
Abstract............................................................................................................................................2
Algorithm.........................................................................................................................................2
Min-Max Algorithm....................................................................................................................2
Screenshots..................................................................................................................................3
Conclusion.......................................................................................................................................6

2
THE CONNECT FOUR GAME
Single Player
Abstract
The Connect Four Game has both single player and double player version. In the single
player version, the computer uses the Min-Max algorithm to judge a column to play its turn. The
user is given the choice to select who goes first.
Algorithm
Min-Max Algorithm
In the single player version of the game, the computer uses Min-Max algorithm coded
with the NegaMax approach to make a move. The Negamax search is a type of MinMax search
algorithm, which depends on the zero-sum property of a double player game. The algorithm
identifies the max(x,y) function as –min(-x,-y), thus to simplify the searching approach. This
simplifies the minmax coding by requiring that X selects the move with maximum successor
value and Y selects the minimum value successor.
The evaluation feature is achieved by constantly updating the variable to count the value
of the chances present. With every possible move for the computer, the ‘eval’ variable is
incremented and vice versa with encountering users move. Finally, this variable is used in a
mathematical function to determine the move of the computer.
Finally, the winCheck function of the program evaluates every possible nodes in the
board that can possibly lead to a victory. If there is none such moves, the wincheck function
returns 0 to denote that the winning state or the tie state has not yet been reached. The function
finally makes sure, whether 42 moves, that is the total number of cells in the board has already
been filled. In this case, 3 is returned to denote a Tie state and the program ends. Furthermore, if

3
THE CONNECT FOUR GAME
the function returns 1 to the AI modules, then the minMax algorithm takes over to block the
winning spot of the player with a computer move.
Screenshots
Below are the screenshots of the single-player Connect Four game, that displays every
possible aspect of the programming.

4
THE CONNECT FOUR GAME

5
THE CONNECT FOUR GAME
The screenshots below highlights the program’s ability to handle invalid inputs. The first
screenshot handles inputs below or above the column limit of the board. The second however,
tackles situations where the column entered has no empty cells left.

6
THE CONNECT FOUR GAME
Conclusion
The strength of the program is that the computer never takes more than 2 seconds to
search the complete game tree and make a move. This makes the program faster. It can also be
noticed that the program thinks ahead of the human player, thus making moves that can create
chances for winning if the player makes a set of particular moves. In addition, the algorithm
blocks any possible winning move of the player. One noticeable weakness can be noticed from
the view of the player. The program performs perfectly however, it not only blocks every
winning move of the player, but also tends to be almost unbeatable. This level of difficulty is a
negative aspect for the marketing of the game.
A certain fields can be improved for a better performance. Firstly, the difficulty must be
lowered using a more subtle depth for the algorithm search. Further, the user interface can be
enhanced using larger fonts to denote the moves and the board.

7
THE CONNECT FOUR GAME
Double Player
First few moves

8
THE CONNECT FOUR GAME
Invalid input checking:
Column entry below 1 or above 7.
Filled Column (5th column).

9
THE CONNECT FOUR GAME
Vitory state