Mini Max Algorithm
A recursive or backtracking technique used in game theory and decision-making is the mini-max algorithm. If the other team is likewise playing optimally, it offers the player the best move.
The majority of AI game play uses the min-max algorithm. like Go, tic tac toe, checkers, chess, and other two-player games. The minimax choice for the current state is calculated by this algorithm.
Two players—one known as MAX and the other as MIN—play the game in this algorithm. Both players engage in combat, with their side reaping the greatest rewards and the other taking the least. In this game, the two players compete against one another by choosing the maximized value (MAX) and the minimized value (MIN). The minimax algorithm explores the whole game tree using a depth-first search strategy. The minimax algorithm runs.
How the Min-Max Algorithm Operates
- It is simple to explain the minimax algorithm's operation with an example.
- An example of a game tree, which represents a two-player game, is shown below.
- One participant in this case is named Maximizer, and the other is named Minimizer. Whereas Minimizer aims to obtain the lowest possible score, Maximizer seeks to obtain the highest possible score.
- Since this algorithm uses DFS, in order to get to the terminal nodes in this game-tree, we must navigate through every leaf. The terminal values are provided at the terminal node, therefore we will compare those values and retrace the tree until the original state is reached.
Example of Mini Max Algorithm
Complexity Of Mini Max Algorithm in AI
Time complexity:
O(b^d), where d is the number of layers or depth in a graph or tree, and b is the branching factor.
Space Complexity:
O(bd), where d is the maximum depth of a tree that resembles DFS and b is the branching factor.
Beta-Alpha Pruning of Mini Max Algorithm
A modified variant of the minimax method is called alpha-beta pruning. It is a method of optimizing the minimax algorithm. The number of game states that the minimax search method must look at is exponential in the tree's depth, as we have seen. Although we can't completely remove the exponent, we can reduce it by half.
Pruning is a method that allows us to determine the proper minimax option without having to examine every node in the game tree. Alpha-beta pruning is the term for this process, which involves two threshold parameters, Alpha and Beta, for future expansion. Another name for it is the Alpha-Beta Algorithm.
The same move is returned by the alpha-beta pruning to a regular minimax algorithm, but it gets rid of all the nodes that slow down the algorithm but don't actually effect the outcome. Because of this, the algorithm becomes quick by pruning these nodes.
The definition of the two-parameter is:
1. Alpha: At every stage of the Maximizer path, this is the best highest-value option we have discovered thus far. Alpha has a starting value of -∞.
2. Beta: The best lowest-value option we have discovered thus far at any stage of the Minimizer process. Beta has a starting value of +∞.
Important points about Beta-Alpha pruning:
- Only the value of alpha will be updated by the Max player.
- Only the beta value will be updated by the Min player.
- The node values- rather than the alpha and beta values—will be transmitted to the top nodes when the tree is being retraced.
- The child nodes will only receive the alpha and beta values from us.
