Minimax Algorithm in Game Playing | Artificial Intelligence

Hello Friends! Welcome to Gate Smasher In today's video we're going to discuss about Minimax Algorithm and we're going to discuss all the important points about Minimax Algorithm Which are important for your competitive exams or theory level exams It will be beneficial for both of them and you can note down all these points So the very first point we have is It is a back tracking algorithm Back tracking means First, we go from the root level to the leaf level At terminals we calculate the values

and again we propagate the calculated values to the Root level and then we decide that which move we have to choose So this is very important point It is a back tracking algorithm and a very important question is asked in game playing Why we don't use Breadth-First Search algorithm? means why we don't use BFS technique in game playing because game playing simply means that If I am playing here I have two choices either I go to B or to C Obviously, we have only one move If I used that one move a

fter that opponent have to move but breadth-search means that It runs of level order means first it will follow all the moves in a level First it will say that I want to move here it can undo this move and play it somewhere else This thing we can't allow in the game playing Whichever move you have used, next is opponent's turn so we can't use Breadth-First Search in this because It follow level by level But we have to use here concept of Back tracking algorithm Then, Best move strategy used Best

move simply means that Let's say that there are two players Me and you are playing What will be my priority here My priority here will be that I should make the best move and I should win and your priority will also be that you also make the best move and don't let me win so this is actually the concept of game playing When the concept of game playing introduced so one side was human being and on other a machine Learning was given to machine in such a way that It can beat human So here if I am

playing as a human so I will try to make my move the best so that I win And the computer will make best move according to my move so that I lose the game So this point We will use only Best move strategy Then Max and Min As the name of algorithm is Minimax here minimax means There are two players Max and Min So I will tell here Let's say I am playing as a Max player means human being is max and machine is Min means your opponent is Min So let's say first turn is of Max We always start with the

Max means first is my turn when I choose my turn means when I will choose my move then I will maximum my move So here is the same thing that Max will try to maximise its utility The max word here is Students gets confused sometimes that what does max means? Max means that we have maximised our utility Utility means the points that I will get after winning As I have discussed it in the Introduction to Game playing all these keywords so you must check that video, so that you get an idea about basi

c points we had discussed there Utility simply means How much point is for winning and lose this concept I will make my move the best, so that my utility is maximum and opponent will minimum Min will try to minimize utility It will try to minimize my utility by choosing the worst move worst move means It is not worse for him, It is worst for me According to him it will be the best move but obviously it will the worst move for me These two are very important points that is Max will try to maximis

e and Min will try to minimise So first if we talk about Max here So here I have a game tree Let's say we start from A in the game tree So, we're on A position, on the root level so on the root level, Max has two choices One is B and other is C He can wither choose B or C If he chooses B Now it will be the turn of Min and Min will make his move we have to play like this As we play normal games We chose one move then opponent chose next move Then I We have to move like this But here an important

point is that As we have chosen move here At the last, at leaf level We have mentioned utility here at terminal So here we're seeing +8 Means if I will chose this move My utility My profit My winning reward will be maximum So we think that we should choose B After B we should choose D Like that If I will move like this then my winning probability will be very high and I will get the maximum reward but this is the important point in the game In the game you can decide your own strategy But you ca

n't decide what move will opponent make So he is trying hard to make you lose So here you have to make your move What will be the next to next move it depends on your opponent's move So here you have to choose max which ever is maximum between B and C and then the turn will be for Min Min will chose the minimum value We will move forward like this Again we have Max again Max have to choose the maximum value As we have talked here about back tracking Only after going back tracking, then we will k

now that which move we have to choose so that our winning is compulsory or loss we will get First we get to the terminal On terminal, first this side We have D, means here we have max because Max will make the very first move then Min and afterwards Max What will Max choose here? -1 or 8 I have two values If I made this move then I will get -1 as utility If I choose this move then 8 Then obviously he will choose Max will try to maximize As I have told you earlier also Max will try to maximize So

which is the maximum between two of them It is 8 So which value he has to choose in this 8 means He will go on this side so that He get the maximum utility or profit then if we talk about this particular node On E, if he go on this side he will get -3 and -1 on the other side Which is maximum value between -3 and -1? He will think that -1, even though I am losing some value but it is lesser than the other one Obviously he will try to choose this move here So, here maximum value is -1 And you go

t the direction of this side Then I we talk about Max will choose the maximum value between 2 and 1 So the maximum value here is 2 and obviously, the direction is of this side Then we have G So G also have 2 choices -3 and 4 Max have to maximize his utility So which is the maximum, this one So maximum value is 4 and direction is of this side so Max has decided according to him If I make this move or this one or this one So in this way I will get the maximum utility As I have told you, that here

it depend on opponent Opponent means Min Min will try to minimize the utility means it will try to minimize my utility so that It get more benefits So, we're discussing this point here So now it's Min turn If he goes towards D See it carefully If it goes towards D then he will get to know that here Max will get profit of 8 means Min will have lose of 8 If it goes towards E means Min will get profit of 1 Max it will be loss for Max So obviously it will choose minimum value between these two and m

inimum value is -1 It is a simple point If it chooses 8 then Max will choose value of 8 and will win with the maximum utility of 8 So, it wants to reduce the utility of Max So, it chooses the minimum value of -1 means this one If we talk about C here By C point of view, it has 2 and 4 which is minimum between 2 and 4 Minimum is 2 So obviously it will try to reduce utility of Max by choosing minimum value that is 2 Now if we talk about max here So, max will try to choose the maximum value in star

ting means whether he will towards -1 or 2 If he goes towards -1 obviously here he knows that his utility is going towards -1 means utility is going towards negative then obviously he will choose the 2 that is a positive sign So he has a guarantee here If he chooses this strategy then In this strategy he has a guarantee that he will definitely win he will get the 2 utility for sure Which direction? If he goes towards C and from C goes toward F and from F he goes to this terminal In this wat he w

ill get winning 2 utility for sure So Minimax Algorithm works like this So time complexity of Minimax Algorithm is Order of B raised to power of D where B is the branching factor and D is the Depth Depth or we can say it Ply Ply means as much depth we go in that is D and B is the branching factor Branching factor means choices How many children are apossible? So if talk about Minimax here Here you can see that we are travelling each and every node atleast one time So complexity B raised to power

D means If we no. of children is 3 and depth is 2 then my time complexity is 9 which is feasible means we can bear this much time complexity But some games like Chess So in Chess on an average we have 35 choices available that means 35 moves are possible means that is a average value it depends on different time but if talk about 35 choices are possible for us and how much is the no. of moves? means how much is the depth? Depth can be 50 on an average for one player and obviously according to 2

players, total will be 100 100 moves are possible So 100 moves are possible 35 on an average are choices So the game tree will be You can see here no. of nodes possible in game tree 35 raised to power 100 means the game tree will be this much huge that will become difficult to traverse So that's why, we can't use Minimax Algorithm in every game Only in few games like Tic-Tac-Toe we can use it Nimb, we can use it in Nimb game also But we can't use it in each and every game because its tree will

become very vast So to reduce this and bring efficiency to it We use Alpha-Beta pruning method Thank You!