What is the Minimax Algorithm? – Artificial Intelligence

What is the Minimax Algorithm? – Artificial Intelligence


Hi everyone, this is gkcs! 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 video
and we will also discuss how heuristics are calculated in a separate video. If
you want a notification for that you can subscribe. Thank you for watching this! I will see
you later.

3 thoughts to “What is the Minimax Algorithm? – Artificial Intelligence”

Leave a Reply

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