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.

Clear and helpful explanation. Thanks

Solve min max by Python https://youtu.be/mZNKX7sFO-k

Thank you