Connect Four Clone is a board game simulation that was written in JavaScript. It uses the p5.js library for the interactive and graphcal elements. An artificial intelligence (AI) was implemented using the minimax algorithm, optimised with alpha-beta pruning.
This project aims to create a functional Connect Four clone and implement a minimax AI for the game.
I learnt the minimax algorithm from a video by Sebastian Lague who will be able to explain the algorithm much better than I can.
For a game with a smaller game space (such as tic-tac-toe), the minimax algorithm usually runs until one player has won. However, for Connect Four, the game space is too big and it would take too much time to go through every permutation. Hence, an evaluation function is needed to allow us to compare between game states without actually knowing the outcome.
A good evaluation function indicates how "good" a game state is for a certain player. The more accurate the evaluation function, the more likely that the minimax algorithm will pick the most ideal next move for that player.
An evaluation heuristic needs to balance between computing time and accuracy.
The heuristic that I have chosen calculates the total number of "four in a row" possible for the red pieces minus the total number of "four in a row" possible for the blue pieces. Paths that have 2 or 3 pieces are given higher weights in order to account for their higher value.
For each piece, the algorithm searches in 7 directions. There is no need to search below the piece as it is not possible to place a new piece underneath an existing piece.
For the sake of demonstration, assume that we are only searching to the right of one particular piece.
- If the search space contains a different coloured piece or the search space is out of bounds, then a score of 0 is given.
- If the search space contains only empty spaces or pieces of the same colour, then a score is given based on how many pieces are inside the search space.
Alpha-beta pruning works by storing the minimum and maximum values while treversing the game states. With the minimum and maximum values, we do not need to search some parts of the search tree, allowing us to increase the depth of our minimax algorithm without severe performance issues. Once again, the video by Sebastian Lague explains alpha-beta pruning much better.
We can determine one move earlier whether the next move will lead to a win by also checking whether there is a token underneath the empty space in the search tree. If there is a token under the empty space and the search space has 3 tokens, then the next move can be a winning move. This method make the search tree shallower and prevents the AI from missing obvious moves.
In order to have more accurate evaluation function, it is important for the function to know who will play the next move.
For instance, the evaluation function would not favour any side if given a board state like this.
However, it is clear that the player with the next move would win the game. Hence, by coding in the next turn, we can make more accurate predictions.
If you have found any bugs or have a feature to suggest, I can be contacted at joelchanzhiyang@gmail.com.
All code was written by me.
This article by Gilles Vandewiele inspired this project.
"A Knowledge-based Approach ofConnect-Four" by Victor Allis was an interesting read that guided this project.