I noticed that there doesn’t seem to be an open source MiniMax Algorithm yet, so I decided to make one myself. Link is at the bottom, this post is more to describe the library and give some notes about how it works.
It’s designed to be as generic as possible, meaning it should work in any implementation. However, it does have the requirement that it must be used for turn-based games involving two players, where each player goes in sequence (so Player 1 will always go after Player 2, and Player 2 will always go after Player 1).
It should be helpful for AI-based games.
Overview
Minimax is mostly used for turn-based games (things like Chess, Checkers, Connect 4, etc.). The algorithm allows you to find the optimal move that you might make at each turn, which helps to build smarter AI.
1. How It Works
The algorithm starts with a function that can convert a game state into a numerical value. In Chess, for example, this might be as simple as asking how many pieces you have remaining on the board.
The algorithm assumes that we’ll try to optimize this value, while our opponent will try to minimize it. In the case of the number of pieces on the board, our goal will be to protect our pieces as much as we can, while our opponent’s goal will be to destroy all the pieces that they can.
1.1. Depth
The algorithm takes in a “depth” argument which tells us how many layers deep we should go. For example, if our depth is 3, then we’ll go 3 turns deep: we’ll make a move, our opponent will make a move, and we’ll make a move. We then provide a value to this end state - in the case of the number of pieces on the board, we would check our pieces after all three moves have been made.
1.2. Backtracking - MiniMax
The main logic of the algorithm takes place after we’ve reached our target depth on the board. From here, at each level, we can calculate the “best” move to make: when its our turn, we want to maximize the numerical state values; on an opponent’s turn, we minimize these values. Our optimal move is whichever one returns our best value.
1.3 Alpha-Beta Pruning
Alpha-Beta Pruning is an additional step which can be added on top of the algorithm to help reduce the number of steps that have to be taken. Because we know at each level that we’re either minimizing or maximizing our target values, we can pass in our current best through each branch being checked, and exit early if we determine that we can’t bypass our best so far. This can drastically reduce the amount of work that has to be done.
1.4 More Information
This was just a super quick overview of the algorithm. For more details, I’d suggest the Geeksforgeeks page on MiniMax - they give a much deeper analysis, including their own implementation that works against Tic Tac Toe. It’s really helpful for getting a deeper understanding of the algorithm.
2. Using the Library
I designed the function with the goal of having it be as generic as possible. In that manner, all board states and transitions are provided by generic type arguments, and several functions are used to progress between the states (i.e. each move).
More analysis is provided in the script itself, which refers to each parameter that has to be passed in. The code of the algorithm is also deeply commented so that it should be easy to read through and understand what the code is doing if you’re interested.
3. Sample
The algorithm is currently being used in my Checkers game for the AI player Pierce. You can take a look at it here: Checkers - Roblox
Let me know if you’re interested in code samples using the algorithm and I can put something together for that.