The minimax algorithm, and Alpha–beta pruning | Tutorial in 30 lines of Python code
In the field of artificial intelligence, game theory plays a significant role in creating intelligent agents capable of making strategic decisions. One of the most popular and efficient algorithms used in game theory is the Minimax algorithm, which can help determine the best possible move for a player in a two-player zero-sum game.
This tutorial will guide you through the process of implementing both the Minimax and Alpha Beta Pruning algorithms in only 30 lines of Python code. Despite its brevity, our implementation will be both general and effective. While the primary focus of this tutorial is the implementation itself, it is worth noting that a comprehensive course on Udemy is available for those interested in deepening their understanding of the Minimax algorithm and Alpha Beta Pruning algorithms.
For the algorithm to function properly, it requires a game / environment, which we’ll refer to as “game_map” in our implementation. The game_map must provide four essential function calls:
- is_terminal: This function returns a Boolean value indicating whether the game has reached a terminal state, i.e., one of the players has won, or it’s a draw.
- get_possible_moves: This function returns all the possible moves that a player can make from the current state of the game.
- get_new_state: This function takes a move as input and returns a new game state.
- get_score: This function returns the score of the game. For instance, if Team A has won, it returns 1, if Team B has won, it returns -1, and if it’s a draw or no team has won, it returns 0. When the game is not in a terminal state, a heuristic function can be used to estimate the score of the game and determine which player has the upper hand. This is particularly useful for games with large branching factors, such as chess.
This indicates that you can easily apply the algorithm to your own game without modifying a single line of the algorithm. To accomplish this, you will need to create an API in your environment that includes the four function calls described earlier — this is what I did for my implementation of a chess game. The Move class is generic, so you can customize it to suit your particular requirements.
This implies that you can seamlessly integrate the Minimax algorithm into your game and take advantage of its benefits.
Minimax Algorithm
The Minimax algorithm can be implemented recursively with ease. It requires two inputs: the depth that needs to be reached and a boolean value indicating whether the score should be maximised or minimised.
If the depth that needs to be evaluated is zero, the recursion can be stopped, and the score of the leaf game state can be returned. This is achieved by simply returning the score of the game state. It is important to note that we return an additional variable as well. Since our primary goal is to determine the best move to play, we need to calculate this move as well. This variable is set to None in leaf nodes since there is no move to be made. However, this will be computed in non-terminal states latter.
The code is divided into two primary sections — one for layers where maximisation is required and the other for layers where minimisation is required.
In the former case, the objective is to find the value that maximises the score. Thus, we set it to -inf by default. We then obtain all possible moves and iterate over them, getting the states that can be reached from those moves. For each state, we recursively call the Minimax algorithm. If we encounter values that are better than the value returned by the best move, we update the best move. Finally, at the end of the function, we can return the score and the best move for this node. The process for minimization is similar.
It’s worth noting that the algorithm can be applied to any game with the appropriate API without modification.
Alpha-beta pruning
As the game tree’s size increases, the computational requirements of the Minimax algorithm grow exponentially, making it impractical for most purposes. To address this issue, we employ Alpha Beta Pruning, which reduces the number of nodes evaluated by the Minimax algorithm while still producing the same outcome.
The alpha beta pruning algorithm derives its name from the two additional parameters it takes as input: alpha and beta. These values are instrumental in pruning the tree, thereby avoiding unnecessary computation of nodes. During the maximisation phase, if we encounter a node with a value greater than beta, we can immediately stop exploring that branch. This is because the score of this node is higher than the best alternative for the minimising player, who will not choose this node anyway. As a result, even if a better move is found, it will never be reached.
A straightforward way to implement this in code is to check if the value of a node exceeds beta during the maximisation phase. If this condition holds, we can stop exploring further because we know that the opposing player already has a better alternative than the current node’s value. Therefore, even if we find a better value, the opposing player will still choose the action with the reward beta. Note that this algorithm assumes that the opposing player plays optimally. Against a random agent, the alpha beta pruning algorithm may not necessarily be the best choice.
I hope this tutorial was helful to you. If it was, consider clapping this story, and do not forget to follow for more tutorials related to Artificial Intelligence, and Machine Learning.
