What is the Minimax Algorithm?

  • by
What is the Minimax Algorithm?

What is the Minimax Algorithm – We are going to be talking about the minimax algorithm now and this is a very useful concept in two-player games when you are trying to code some artificial intelligence. So these two players are people who are fighting against each other and they have, usually have, complete information about the game so one example is chess where white and black are playing against each other. You have a number line: an integer line and any integer which is positive is good for white any integer which is negative is good for black.

So positive infinity would be a win for white and negative infinity would be a loss for white. This is how the game tree comes out so there is a roof node which is the starting position from here you have two possible moves which red can play and these are the two outcomes that you will have from those moves. Similarly blue can play two possible moves here and two possible moves from this position. And so on and so forth.

To keep things simple I will just make two possible moves of course you can have just one move here and it could be a terminal state. So in complicated games it’s going to be a much more complicated game tree but for now let’s assume that this is the tree that we have. So firstly let’s just look at win loss and draw so if this is a win for red it will be colored red if it’s unstable or if it’s a draw then we color it grey and blue is a win for blue so the minimax algorithm says that if a player is winning in any of its choices then it’s going to choose the win.

Otherwise it has no choice and is going to choose the next best thing which is a draw or if it has no choice at all then it’s going to go for the loss so here take a guess what’s going to happen. Yeah, red chooses this move and then wins in this position red has another choice here which is either red or blue so we cannot evaluate this node till we have gone down all of its sub trees so that will be red again because the red chooses this move.

It does not want to lose. And now you can say that blue wants to choose a move which is blue because it wants to win but it has absolutely no choice and it has to choose red. Now we come here and we see that we still haven’t evaluated this node. So we go down this subtree, we come down to the left node. We go over here, that’s a blue node, we return here. Red can either choose blue or go down to the right subtree and both choices are blue it has absolutely no choice and it chooses blue. Now we come up here and again go down to the right to the left we get a red to the right we get a blue.

Amongst red and blue, red is always going to choose red similarly blue has two choices and it’s going to choose the winning move here which is blue. But that didn’t really matter because red can now choose this node instead of this one and end up with the tree over here. So what we are seeing is that two players are playing against each other. They have just three possibilities in each position: it’s either red blue or a draw and they are of course going for the maximum that they can. Mathematically red is trying to maximize their score you can think of red as positive infinity and blue is trying to minimize the score which is negative infinity.

Now in most cases you are not going to see a clear positive infinity or negative you know terminal node which says that yes I won or yes I lost. So in these cases you need heuristics like these. These are very useful things. When in doubt, you know, you should follow the spiders. Well in case you have some heuristics which is (we can get into detail with heuristics later on) but essentially they are just: It is just it’s a function which tells you whether the first player is winning or the second player is winning that’s all.

And if the second player is winning it returns a negative number of the first players winning it returns a positive numbe. At the very core that’s what our heuristic is. How it does that is depending on the game we try to create a heuristic function which returns positive if white is winning and negative if black is winning. We’ll get into more details later on. So again the same algorithm can be used for this kind of evaluation. Let’s say these are the leaf nodes and they have scores as shown below. So first we start from the starting node we go to the left we go to the left we go to the left we get a -3 and then we come up and see a 7. So red is maximizing its score, so it goes for 7.

It goes up comes to the right to the left to the right -1. Take a guess, what is red going to do here? Yes. it’s going to take the maximum score 2. Now we can evaluate the parent node and what we see is that blue is trying to minimize its score. It is trying to minimize the board score, so it’s not going to choose this 7 is actually going to choose 2.

This is very important to notice because they’re playing against each other they’re playing against each other’s intentions against each other’s aspiration, will, everything. So it’s going to choose a minimum 2. Now we come here we can’t evaluate it because this node is empty and so is this so -7 and -3 are possible choices for red it’s going to try to maximize its score and it chooses minus 3.

Similarly, it comes over here and chooses 8. Now we have this node which needs to be evaluated. Well it’s going to choose the minimum that it can which is -3 because it’s blue turn. Blue came to these two positions and it’s going to choose that which is going to help it the most so -3 is here. But red can choose 2 instead of -3, so that’s what it does. It chooses 2. And so this entire position with all these nodes, these 8 nodes, evaluate to a value of 2 in our minimax algorithm.W hat this tells us is that red is winning this position and the way this helps us is in most games you won’t be able to calculate all the way to the end you won’t be able to see all positions except in maybe tic-tac-toe.

If you have a game like chess, it’s impossible to go down to the terminal depth of every position and figure out you know who is winning this position. In a very clear-cut manner. What you need is heuristic functions which can tell you what’s happening to some extent. To a reasonable extent and then you need to evaluate the overall position through this minimax algorithm. There are enhancements to this algorithm which we have discussed in this series but the most important enhancement is actually alpha beta so we will discuss that in a separate article and we will also discuss how heuristics are calculated in a separate article.

 

Useful links:

reference – What is the Minimax Algorithm? – Artificial Intelligence

Share this post ...

Leave a Reply

Your email address will not be published. Required fields are marked *