Minimax Algorithm in Game Playing | Artificial Intelligence

Minimax Algorithm in Game Playing | Artificial Intelligence

Minimax Algorithm in Game Playing | Artificial Intelligence

👉Subscribe to our new channel:   / @varunainashots  

đź”—Link for AI notes: https://rb.gy/9kj1z
👩‍🎓Contributed by: Nisha Gupta

Minimax Algorithm in Game Playing
1) Backtracking Algorithm
2) Best move strategy used
3) Max will try to maximize its utility(Best Move)
4) Min will try to minimize utility(Worst move)

â–ş Artificial Intelligence (Complete Playlist):
   • Artificial Intelligence (Complete Pla…  

Other subject-wise playlist Links:
--------------------------------------------------------------------------------------------------------------------------------------
â–ş Operating System :
   • Operating System (Complete Playlist)  
â–şDatabase Management System:
   • DBMS (Database Management system) Com…  
â–ş Theory of Computation
   • TOC(Theory of Computation)  
â–şData Structure :
   • Data Structure  
â–şComputer Networks (Complete Playlist):
   • Computer Networks (Complete Playlist)  
â–şComputer Architecture (Complete Playlist):
   • Computer Organization and Architectur…  
â–şStructured Query Language (SQL):
   • Structured Query Language (SQL)  
â–şDiscrete Mathematics:
   • Discrete Mathematics  
â–şCompiler Design:
   • Compiler Design (Complete Playlist)  
â–şNumber System:
   • Number system  
â–şCloud Computing \u0026 BIG Data:
   • Cloud Computing \u0026 BIG Data  
â–şSoftware Engineering:
   • Software Engineering  
â–şDesign and Analysis of algorithms (DAA) (Complete Playlist):
   • Design and Analysis of algorithms (DAA)  
â–şGraph Theory:
   • Graph Theory  
â–şProgramming in C:
   • C Programming  
â–şDigital Logic:
   • Digital Logic(Complete Playlist)  

---------------------------------------------------------------------------------------------------------------------------------------
Our social media Links:
► Subscribe to us on YouTube:    / gatesmashers  
►Subscribe to our new channel:    / @varunainashots  
â–ş Like our page on Facebook: https://www.facebook.com/gatesmashers
â–ş Follow us on Instagram: https://www.instagram.com/gate.smashers
â–ş Follow us on Instagram: https://www.instagram.com/varunainashots
â–ş Follow us on Telegram: https://t.me/gatesmashersofficial
â–ş Follow us on Threads: https://www.threads.net/@gate.smashers
--------------------------------------------------------------------------------------------------------------------------------------
â–şFor Any Query, Suggestion or notes contribution:
Email us at: [email protected]


Content

0.399 -> Hello Friends!
1.135 -> Welcome to Gate Smasher
2.336 -> In today's video we're going to discuss about
4.309 -> Minimax Algorithm
6.148 -> and we're going to discuss all the important points
8.804 -> about Minimax Algorithm
10.377 -> Which are important for your competitive exams
13.237 -> or theory level exams
16.696 -> It will be beneficial for both of them
17.814 -> and you can note down all these points
21.331 -> So the very first point we have is
23.132 -> It is a back tracking algorithm
24.784 -> Back tracking means
26.521 -> First, we go from the root level to the leaf level
31.481 -> At terminals we calculate the values
33.807 -> and again we propagate the calculated values to the
36.646 -> Root level and then we decide that
38.701 -> which move we have to choose
41.013 -> So this is very important point
43.739 -> It is a back tracking algorithm
45.538 -> and a very important question is asked in game playing
48.548 -> Why we don't use Breadth-First Search algorithm?
51.287 -> means why we don't use BFS technique in game playing
54.086 -> because game playing simply means that
57.109 -> If I am playing here
59.197 -> I have two choices either I go to B or to C
61.814 -> Obviously, we have only one move
64.644 -> If I used that one move
66.594 -> after that opponent have to move
68.76 -> but breadth-search means that
71.002 -> It runs of level order
72.86 -> means first it will follow all the moves in a level
76.244 -> First it will say that I want to move here
78.935 -> it can undo this move and play it somewhere else
82.158 -> This thing we can't allow in the game playing
85.248 -> Whichever move you have used, next is opponent's turn
88.042 -> so we can't use Breadth-First Search in this because
92.355 -> It follow level by level
95.809 -> But we have to use here concept of Back tracking algorithm
99.852 -> Then, Best move strategy used
102.705 -> Best move simply means that
104.762 -> Let's say that there are two players
106.185 -> Me and you are playing
107.88 -> What will be my priority here
110.359 -> My priority here will be that
113.21 -> I should make the best move and I should win
115.782 -> and your priority will also be
117.774 -> that you also make the best move and
119.544 -> don't let me win
121.275 -> so this is actually the concept of game playing
123.452 -> When the concept of game playing introduced
125.957 -> so one side was human being and on other a machine
128.413 -> Learning was given to machine in such a way that
131.037 -> It can beat human
133.094 -> So here if I am playing as a human
136.219 -> so I will try to make my move the best
141.037 -> so that I win
142.604 -> And the computer will make best move according to my move
148.295 -> so that I lose the game
149.997 -> So this point We will use only Best move strategy
154.551 -> Then Max and Min
156.633 -> As the name of algorithm is Minimax
159.192 -> here minimax means
161.045 -> There are two players Max and Min
163.816 -> So I will tell here
165.878 -> Let's say I am playing as a Max player
169.263 -> means human being is max and
171.239 -> machine is Min
172.881 -> means your opponent is Min
175.018 -> So let's say first turn is of Max
177.485 -> We always start with the Max
180.32 -> means first is my turn
182.469 -> when I choose my turn means
184.59 -> when I will choose my move
186.981 -> then I will maximum my move
190.786 -> So here is the same thing that
192.417 -> Max will try to maximise its utility
195.527 -> The max word here is
198.022 -> Students gets confused sometimes that
199.7 -> what does max means?
201.247 -> Max means that we have maximised our utility
206.006 -> Utility means the points that I will get after winning
210.296 -> As I have discussed it in the Introduction to Game playing
213.062 -> all these keywords
214.486 -> so you must check that video, so that you
216.919 -> get an idea about basic points we had discussed there
219.713 -> Utility simply means
221.702 -> How much point is for winning and lose
225.639 -> this concept
227.074 -> I will make my move the best, so that my utility is maximum
231.769 -> and opponent will minimum
234.414 -> Min will try to minimize utility
237.645 -> It will try to minimize my utility
241.003 -> by choosing the worst move
243.206 -> worst move means
244.614 -> It is not worse for him,
246.199 -> It is worst for me
247.57 -> According to him it will be the best move
249.519 -> but obviously it will the worst move for me
252.281 -> These two are very important points
254.685 -> that is Max will try to maximise
256.995 -> and Min will try to minimise
259.11 -> So first if we talk about Max here
261.383 -> So here I have a game tree
263.152 -> Let's say we start from A in the game tree
265.574 -> So, we're on A position, on the root level
269.527 -> so on the root level, Max has two choices
272.389 -> One is B and other is C
274.539 -> He can wither choose B or C
278.029 -> If he chooses B
279.302 -> Now it will be the turn of Min
281.498 -> and Min will make his move
283.798 -> we have to play like this
285.14 -> As we play normal games
286.152 -> We chose one move
288.047 -> then opponent chose next move
290.539 -> Then I
291.564 -> We have to move like this
293.11 -> But here an important point is that
295.123 -> As we have chosen move here
298.758 -> At the last, at leaf level
302.119 -> We have mentioned utility here at terminal
303.806 -> So here we're seeing +8
307.011 -> Means if I will chose this move
309.823 -> My utility
311.303 -> My profit
312.435 -> My winning reward will be maximum
315.782 -> So we think that we should choose B
318.26 -> After B we should choose D
320.457 -> Like that
321.447 -> If I will move like this then my winning
324.514 -> probability will be very high
325.978 -> and I will get the maximum reward
328.722 -> but this is the important point in the game
331.613 -> In the game you can decide your own strategy
334.888 -> But you can't decide what move will opponent make
338.928 -> So he is trying hard to make you lose
342.968 -> So here you have to make your move
345.398 -> What will be the next to next move
347.25 -> it depends on your opponent's move
349.833 -> So here you have to choose max
352.819 -> which ever is maximum between B and C
354.95 -> and then the turn will be for Min
357.065 -> Min will chose the minimum value
358.855 -> We will move forward like this
360.746 -> Again we have Max
362.876 -> again Max have to choose the maximum value
366.053 -> As we have talked here about back tracking
369.428 -> Only after going back tracking, then we will know
371.497 -> that which move we have to choose so that
374.986 -> our winning is compulsory
376.594 -> or loss we will get
378.732 -> First we get to the terminal
380.861 -> On terminal, first this side
383.65 -> We have D, means here we have max
385.846 -> because Max will make the very first move
387.681 -> then Min and afterwards Max
388.725 -> What will Max choose here?
391.394 -> -1 or 8
393.107 -> I have two values
394.501 -> If I made this move then I will get -1 as utility
399.999 -> If I choose this move then 8
401.562 -> Then obviously he will choose
404.455 -> Max will try to maximize
406.543 -> As I have told you earlier also
407.939 -> Max will try to maximize
409.585 -> So which is the maximum between two of them
411.297 -> It is 8
413.207 -> So which value he has to choose in this
414.675 -> 8 means
415.651 -> He will go on this side so that
419.592 -> He get the maximum utility or profit
422.387 -> then if we talk about this particular node
425.245 -> On E, if he go on this side he will get -3
427.464 -> and -1 on the other side
429.792 -> Which is maximum value between -3 and -1?
434.233 -> He will think that -1, even though I am losing some value
438.559 -> but it is lesser than the other one
440.593 -> Obviously he will try to choose this move here
443.837 -> So, here maximum value is -1
447.031 -> And you got the direction of this side
449.996 -> Then I we talk about
453.649 -> Max will choose the maximum value between 2 and 1
457.594 -> So the maximum value here is 2
459.803 -> and obviously, the direction is of this side
463.178 -> Then we have G
464.895 -> So G also have 2 choices
466.37 -> -3 and 4
467.792 -> Max have to maximize his utility
470.326 -> So which is the maximum, this one
472.157 -> So maximum value is 4 and
474.523 -> direction is of this side
477.098 -> so Max has decided according to him
480.646 -> If I make this move
481.836 -> or this one
482.862 -> or this one
483.839 -> So in this way I will get the maximum utility
487.378 -> As I have told you, that
489.162 -> here it depend on opponent
491.693 -> Opponent means Min
493.533 -> Min will try to minimize the utility
498.731 -> means it will try to minimize my utility so that
501.481 -> It get more benefits
503.74 -> So, we're discussing this point here
506.375 -> So now it's Min turn
508.419 -> If he goes towards D
510.458 -> See it carefully
511.6 -> If it goes towards D then
513.968 -> he will get to know that here Max will get profit of 8
518.93 -> means Min will have lose of 8
523.135 -> If it goes towards E
525.534 -> means Min will get profit of 1
530.399 -> Max it will be loss for Max
532.505 -> So obviously it will choose minimum value between these two
535.425 -> and minimum value is -1
539.084 -> It is a simple point
540.502 -> If it chooses 8
542.197 -> then Max will choose value of 8
544.653 -> and will win with the maximum utility of 8
547.266 -> So, it wants to reduce the utility of Max
551.314 -> So, it chooses the minimum value of -1
554.039 -> means this one
555.823 -> If we talk about C here
557.955 -> By C point of view, it has 2 and 4
561.314 -> which is minimum between 2 and 4
563.596 -> Minimum is 2
565.62 -> So obviously it will try to reduce utility of Max
569.674 -> by choosing minimum value that is 2
575.073 -> Now if we talk about max here
577.299 -> So, max will try to choose the maximum value in starting
580.953 -> means whether he will towards -1 or 2
584.273 -> If he goes towards -1
586.438 -> obviously here he knows that his utility is going towards -1
591.25 -> means utility is going towards negative
593.905 -> then obviously he will choose the 2
596.347 -> that is a positive sign
599.627 -> So he has a guarantee here
601.273 -> If he chooses this strategy then
603.794 -> In this strategy he has a guarantee that he will definitely win
607.298 -> he will get the 2 utility for sure
611.395 -> Which direction?
612.228 -> If he goes towards C and from C goes toward F
615.204 -> and from F he goes to this terminal
618.069 -> In this wat he will get winning 2 utility for sure
621.448 -> So Minimax Algorithm works like this
625.373 -> So time complexity of Minimax Algorithm is
628.814 -> Order of B raised to power of D
632.265 -> where B is the branching factor and D is the Depth
635.641 -> Depth or we can say it Ply
637.456 -> Ply means as much depth we go in
640.842 -> that is D
642.921 -> and B is the branching factor
644.575 -> Branching factor means choices
645.924 -> How many children are apossible?
648.168 -> So if talk about Minimax here
650.531 -> Here you can see that we are travelling
653.796 -> each and every node atleast one time
655.962 -> So complexity B raised to power D means
658.334 -> If we no. of children is 3
662.573 -> and depth is 2
665.355 -> then my time complexity is 9
667.801 -> which is feasible
669.592 -> means we can bear this much time complexity
671.961 -> But some games like Chess
674.482 -> So in Chess on an average
677.466 -> we have 35 choices available
681.431 -> that means 35 moves are possible
684.151 -> means that is a average value
685.792 -> it depends on different time
687.575 -> but if talk about 35 choices are possible for us
692.287 -> and how much is the no. of moves?
694.824 -> means how much is the depth?
696.786 -> Depth can be 50 on an average for one player
699.863 -> and obviously according to 2 players,
702.112 -> total will be 100
703.692 -> 100 moves are possible
705.062 -> So 100 moves are possible
706.398 -> 35 on an average are choices
708.5 -> So the game tree will be
710.419 -> You can see here no. of nodes possible in game tree
713.94 -> 35 raised to power 100
716.797 -> means the game tree will be this much huge that
719.368 -> will become difficult to traverse
721.905 -> So that's why, we can't use Minimax Algorithm in every game
727.34 -> Only in few games like Tic-Tac-Toe
729.559 -> we can use it Nimb,
732.222 -> we can use it in Nimb game also
734.006 -> But we can't use it in each and every game
737.001 -> because its tree will become very vast
740.446 -> So to reduce this and bring efficiency to it
744.132 -> We use Alpha-Beta pruning method
747.167 -> Thank You!

Source: https://www.youtube.com/watch?v=Ntu8nNBL28o