Connect 4

Connect 4 is a game where two players drop their pieces into columns and try to get "four in a row" horizontally, vertically, or diagonally. In this demo, we built a program that finds the best move on a given Connect 4 board. We ran the program on the HPC and on a personal laptop to highlight why processing in parallel is advantageous in finding the best move quickly.

How it works

Our Connect 4 bot finds the best move by creating and exploring a game tree. When deciding on the best move, we expect that the opponent will also be playing the best move. So, when it is our turn to move, we will try to maximize our advantage and when it is our opponents turn, they will try to minimize our advantage. This process of minimizing and then maximizing the game evaluation is known as the Minimax Algorithm.

Our bot will search every move in the position and then it will search every move in the resulting position until it reaches a certain depth. Once the maximum depth is reached, we evaluate the position and then return to searching the other available moves. After the entire game tree has been explored, our bot will choose the move that leads to the best outcome for itself.

Game

We gave the local machine the red pieces and the HPC the yellow pieces. This may not seem significant, but that is a serious advantage for the local machine. Connect 4 is solved, meaning that we know the outcome of every possible game position. From the starting position, if both players play perfectly red will win every time. This means that at some point the local machine made a mistake and the HPC was able to capitalize.

HPCs Advantage

If the HPC bot and the local bot are the same, why does the HPC win? Well, the HPC bot takes advantage of the HPCs large CPU count to reduce processing time and increase the depth that the bot is able to search. Specifically, instead of searching every move one by one, the HPC searches all possible moves at once and then evaluates them all once the moves return a score. Since the HPC is searching multiple positions at once, it has the time to search each position more thoroughly. This means that on average the HPC will find better moves than the local bot.

Code

Our Connect 4 bot is built using six different class objects: Game, Engine, Search, Evaluation, Moves, and Bitboard. Our bot is built using bitwise operations to maximize performance, so the code can be a bit confusing. I have left comments throughout the code explaining what everything does if you are curious. Here is a basic overview of the different class objects.

Class Object	What it does
Game	The highest-level class, it creates a Bitboard object and implements the Engine class to let the user play against the bot. **This class works differently on the HPC version. Instead of writing to the terminal, it reads and writes from a file in the user's home directory.
Engine	When given a Bitboard object, this class will use the Search class to search every move on the board. Then it will save the best move that is found. **This class works differently on the HPC version. Instead of iterating through the list of available moves, it runs all of the moves at once in parallel.
Search	The Search class is created with a maximum depth and will continue searching until that maximum depth is reached. Then it will use the Evaluation Object to return a general evaluation to the position. **This code is identical in both versions.
Evaluation	The Evaluation class handles win-checks and general evaluations. It scores a position based on how good it is for each player. Strongly positive means Red is winning, strongly negative means Yellow is winning, and zero means the game is likely a draw. **This code is identical in both versions.
Moves	This class will return a list of all possible moves in the position. It is used by both the Engine and Search classes. **This code is identical in both versions.
Bitboard	This class stores the game state in a bitboard. It also allows you to apply moves and undo moves as you please. **This code is identical in both versions.

If you followed the tutorial, you should be able to get this program running on the HPC on your own. The local code doesn't need any preparation and can be ran once it is downloaded. HPC Code Job Script Local code