Gomoku AI
Game summary
This project is an implementation of the Gomoku board game. Though instead of being made for two human players, it is a single-player game where the player is pitted against an AI opponent powered by the minimax algorithm with alpha-beta pruning. Gomoku is played on a board of varying sizes (usually 15x15 tiles, in this case, 20x20). Each player tries to be the first to get five in a row while simultaneously blocking their opponent from accomplishing the same thing.
Demonstration of a short match against the AI opponent
Development
This was one of two larger projects I made for a university class on data structures and algorithms (find the other one here). The task consisted of implementing the minimax algorithm with alpha-beta pruning for a turn-based game of the student's choice. I chose Gomoku/five-in-a-row over something like chess for its simplicity game rule-wise so as to be able to focus the most on implementing minimax and related optimizations as well as possible.
​
My contribution
This was a solo project, in which I created everything from scratch excluding the utilization of the classic Windows XP background. I concentrated on three primary aspects:
​
-
Incorporating the minimax algorithm
-
Enhancing its efficiency through alpha-beta pruning and Zobrist hashing
-
Constructing an effective heuristic function.
The minimax algorithm was integrated seamlessly. However, the real challenge arose in formulating a competent heuristic function. Initially, I evaluated the players based on their longest in-a-row streak, but this approach proved to be insufficient due to its failure to account for potential blocks at either end of the streak.
To rectify this, I introduced a system to monitor the indexes of the tiles at both ends of each player’s streak. This innovation facilitated the assessment of whether a streak was blocked at one or both ends, allowing for more nuanced evaluations and enhanced AI decision-making.
Despite these advancements, time constraints prevented further refinements of the heuristic function and the introduction of additional features and bug fixes. Future iterations of this project could potentially explore improvements in these areas, advancing both the aesthetic and functional elements of the application.
Extract from minimax class showcasing minimax function code
Heuristic function code snippet