What is Minimax Algorithm, and why do we use it?
Let’s say we want to write a program that plays a turn-based game like Tic-tac-toe, Checkers, Chess, and more; in such cases, the minimax algorithm would help us find an optimal move for the player with very high accuracy.
The Minimax algorithm is a backtracking algorithm widely used in Game theory, which gets the optimal move for the current player at any point considering the opponent is also playing optimally.
An essential aspect of the minimax algorithm is the search algorithm which allows the program to look ahead at possible future positions before deciding what move it wants to make in the current situation.
Let us consider two players, representing each as white and black dots. As both the game players are opponents of each other, the white dot will select the maximized value, and the black dot will determine the minimized value. For simplicity, we also refer to the white dot as the maximizing player and the black dot as the minimizing player.
The algorithm will work in a depth-first search manner. It processes the value at the child nodes and then proceeds towards the parent node. The parent node value is calculated based on whether the parent is a maximizing or a minimizing player and the importance of the child node:
Illustration of the minimax algorithm in the game tree below:
The scores at each node signify the maximum score the player can get at the point, considering they play optimally.
Can we do better? Yes, Let’s dive into alpha-beta pruning.
Alpha-beta pruning is a search algorithm that seeks to decrease the number of nodes evaluated by the minimax algorithm in its search tree.
The alpha-beta pruning algorithm uses alpha and beta values, representing the minimum score that the maximizing player is assured of and the maximum score that the minimizing player is assured of, respectively. Initially, alpha is negative infinity, and beta is positive infinity.
Whenever the beta value of the minimizing player becomes less than the alpha value of the maximizing player, the evaluation of the other branches becomes redundant as we know that the beta value is only going to reduce or remain the same.
Similarly, when the alpha value of the maximizing player becomes greater than the beta value of the minimizing player, the evaluation of the other branches becomes redundant as the alpha value is only going to increase or remain the same.
Alpha-beta pruning is illustrated in the game tree below:
The black dot represents the minimizing player in the figure, and the white dot represents the maximizing player.
As shown in the above example, the crossed branches are pruned branches, i.e., further evaluation wouldn’t be needed as it is redundant.
The second child of node ‘E’ (maximizing player), i.e., node ‘K,’ is pruned as the parent minimizing player node ‘B,’ has the value 3. After analyzing the ‘J’ child node of node ‘E,’ we know node ‘E’ value will be greater or equal to 5, which is already greater than the beta value of node ‘B.’ Hence, the branch is pruned.
We pass additional parameters that are alpha and beta to our minimax function to enable alpha-beta pruning.
Pseudo-code for Minimax algorithm using alpha-beta pruning:
Alpha-beta thus avoids unnecessary computation, and sometimes it prunes the tree leaves and the entire sub-tree. Hence we save time by not calculating the positions, which does not change the outcome. However, pruning isn’t guaranteed to occur, and it very much depends on the order of the moves. For this reason, it’s usually a good idea to order the actions based on how likely they are to be good. For example, in chess, capturing a piece with a pawn is likely a good move, and it would be wise to explore it first.
– By Deepta Devkota, Third Year Department of Computer Science Engineering