Creating the Optimal Connect 3 Agent
Source code kept private to respect Drexel’s academic integrity policies.
A Quick Demo:
This demo shows the minimax agent vs random. The minimax should be able defeat the random agent a majority of the time.
Explanation of the game:
Connect Four Rules
Player 1 drops a disc into any of the slots at the top of the grid.
Player 2 drops a disc into any of the slots at the top of the grid.
Players will alternate turns in this manner until someone gets four-in-a-row vertically, horizontally, or diagonally.
For simiplicity’s sake, this implementation only requires three-in-a-row to win.
There are three agents:
Human
This agent allows players to use the commandline to choose which of the four slots they wish to drop their disc in.
Random
This agent randomly chooses the column the disc is dropped into.
Minimax
This agent chooses the optimal column using the minimax algorithm.
How the Minimax Algorithm Works:
-
A tree is used to represent the game, where each edge represents a legal move, and each node represents the resulting state from the legal move.
-
There are two players, the maximizer and the minimizer. The maximizing player, the current player/agent, chooses the move that will result in the best possible outcome. The minimizing player, or the opponent, chooses the move that will result in the worst possible outcome for the maximizing player.
-
Each state is assigned a score. A winning state usually results in a high score, and a losing state results in a low score. To evaluate none winning/losing states, there are other metrics. For Connect 3, this could be the number of actions, where more actions result in a lower score.
-
Using recursion, the row of nodes are evaluated, and the greatest value is chosen as the next move.