Mini-Max
When someone talks about artificial intelligence, people only think of some methods mostly related to machine learning like regression models or classification techniques. But as I mentioned in my previous articles, assuming these approaches as the total cluster of artificial intelligence is not sensible. There are a lot of different approaches, algorithms, models that require training data sets or not, and even basic mathematical formulas like cosine similarity in the discipline of artificial intelligence. One of these algorithms that are generally not mentioned in machine learning classes is the Mini-Max algorithm. This algorithm is not only used in artificial intelligence but other fields like game theory, decision theory, statistics, and even philosophy. In this article, I explain it by giving examples from aspects AI and game theory.
Definition
If you want to learn what the Mini-Max algorithm is, you can define it on a game board where two opponents are playing against and one of them wants to maximize the total score and the other one tries to minimize it basically. For a player P1, capturing her opponent’s Bishop in a chessboard earns her 100 points. And her opponent P2 may lose -100 points if he makes the same move from his side. The important point is P2 satisfies losing points since he wants to minimize the total score while P1 tries to maximize it. In this scenario, positiveness or negativeness of the value does not mean the largeness of the value but it marks the side of the player.
Scoring
Using only one scoring method is not mandatory. You can also add other scoring layers not only capturing chess pieces but also for positions of the pieces on the board, the value of each square on the board to your algorithm. In a chess game, sometimes players sacrifice their pieces for better gains in the future. In such a scenario, losing a Bishop may not be the worst case if you plan to take your opponent’s Queen next turn. So in that case, you can use a value matrix for the positions of the pieces on the board to provide this intelligence to the model. There are some websites that explain the importance value of each square in a chessboard and they share a value matrix based on the importance scores for each chess piece like it as shown in Figure 1.
You can use the exact matrices in Figure 1 or other matrices. You do not even have to use one. You may prefer to use another scoring layer. For example, instead of using position matrices, you can use a value list of chess pieces directly like a Pawn costs 1 point and a Queen costs 10 points. But this time your AI model focuses on capturing the pieces ignoring the positions. In such a scenario, you can see that a King moves to the center of the board just for capturing a Pawn. But locating your King in a safer zone (not center) is the wiser choice most of the time. As you see, AI models may behave differently depending on your choices in the algorithm. You change the model’s intelligence (or characteristics). That is the beauty of artificial intelligence.
You have to specify the needs of the algorithm carefully by considering the main purpose. In the chess example, capturing an opponent’s piece is a purpose. But it is not the main purpose. The main purpose is defeating your opponent with a checkmate. Capturing a piece is the lower focus. So I think adding a value matrix for positions to your scoring layers instead of using a piece value list directly is a better solution for the problem.
Depth
For any game that uses the Mini-Max algorithm, there is a parameter called ‘depth’ which is mostly declared by the persona user of the game. When you played in your turn and it is time for the AI model to play, the model simulates the game for each legal move. For each move, it calculates the output value of this move to the model. It also keeps simulating the game for its opponent’s side after its possible moves. Then after it assumes two moves (one move for AI and one for opponent), it simulates the third move (for AI this time). It keeps repeating this process until the parameter depth is achieved. Then it starts to calculate the score of each state of the board from the deepest. If the model is the maximizing side of the game, it considers that it needs to take the minimum value for the opponent’s moves (if the model is Maximizer, so its opponent is Minimizer) and maximum value for its move. You can think of it as the what-if simulations of the model.
Increasing the depth of the model causes the complexity to increase logarithmically. So increasing the depth to serious numbers is a tough decision. Because since the calculation part increasing giantly, you need to be sure that you have a computer that may handle this process in seconds or you may have to wait for a couple of hours for a move from the model. Also, it is good to know that in a chess game there are 8,902 total positions after 3 moves, and in a go game, this number increases dramatically. In a typical go game with a depth of 150 moves, there are about 250¹⁵⁰, or 10³⁶⁰ possible moves. For detailed information, you can check Link 1 and Link 2.
It is possible to illustrate the Mini-Max algorithm like in Figure 3. Remember that in the Maximizer step, the model chooses the node that gives the maximum number and the minimum one in the Minimizer step. Finally, it makes the move according to the state followed by the selected nodes.
Alpha-Beta Pruning
When a model simulates the scenarios for the Mini-Max algorithm, it may have to make giant calculations especially when the depth is very high. And it is observed that the model calculates a state even if it is guaranteed not to select. You can decide that a calculation is unnecessary by comparing the values of the current node in the same row of Minimizer (or Maximizer) states to the decision of the previous upper node which stated the value by choosing a number between its children nodes.
In Figure 4, there is an illustration of Alpha-Beta Pruning method. First, the calculation that a Mini-Max model performs is calculating the value of the left node under node D. Its value is calculated as 3. The second step is calculating the right node under node D and its value is 5. So the value of node D is 5 since it is a Maximizer node and the maximum value between the numbers 3 and 5 is 5. The next step is calculating the value of the left node under node E and its value is calculated as 6. So the model knows that any value of node E must be larger than or equal to 6 since node E is another Maximizer node and it has already a child node with a value of 6. In the future, node B is going to choose one of the values between node D and node E. Since node B is a Minimizer node, it needs to choose one of the values 5 or 6≥. The choice of node B is 5 and the value of node B is 5 after now. As you see, the model did not calculate the value of the right node under E thanks to Alpha-Beta Pruning. Let’s imagine a scenario where this method is not used and models calculate each step regardless of checking the need of doing it. Also, the depth is so high in this scenario. The combination of these two factors results so badly in processing time.
Summary
You can find fundamental information about Mini-Max algorithm and Alpha-Beta Pruning in this article. You can also have a basic understanding in order to implement a model that uses these methods in any programming language after you read this article completely.
Check my Github repos where you can find the code implementation of Mini-Max and Alpha-Beta Pruning on chess game and TicTacToe game by using the links or cards.
