Minimax Algorithm and Alpha-Beta Pruning Explained

[00:00] say we want to write a program that can play some turn-based game like chess one ahead at possible future positions before deciding what move it wants to

[00:12] make in the current position this white dot represents some position in our game with the white side move to keep things simple let's say that in every position there are only two possible moves to choose between we can visualize these

[00:25] moves as two separate branches at the end of which or two new positions where it's now of course blacks turn to move we can continue expanding the tree of moves until either we reach the end of the game or we decide to stop because

[00:38] going deeper would take too much time either way at the end of the tree we no need to perform a static evaluation on these final positions a static without making any more moves for example a crude approach in chess

[00:55] would be to add up the values of the remaining white pieces and subtract from that the values of all the remaining black pieces so large values would favor white while small values would favor black for this reason white is always

[01:08] trying to maximize the evaluation while black is trying to minimize it so let's not with these two positions on the bottom left so we evaluate them and they come out as minus 1 and plus 3 well in the previous position

[01:23] it was White's turn to move and since white will of course choose the move that leads to the highest evaluation we can assign this position a value of 3 as well next let's evaluate these two positions and so we get plus 5 and plus

[01:36] 1 once again from the previous position white would pick the move leading to the highest evaluation and so we can assign it a value of 5 we've now evaluated both the positions stemming from this position where it's

[01:50] blacks turn to move black will choose the move that leads to the lowest evaluation and so we can assign this position a value of 3 I'll very quickly step through the other half of the tree so we evaluate these as minus 6 and

[02:03] minus 4 which will pick the minus 4 the next two positions are evaluated as 0 and 9 so white will pick the 9 and between minus 4 and 9 pick - for at last we've arrived at the top of the tree or where we can see that

[02:16] why should choose the move on the left since that way even if black plays the best move white will still get a +3 position so now that the basic idea is hopefully clear let's look at how this is implemented in code we have a

[02:29] function called minimax which takes in the current position a depth for how many moves ahead we want to search and a bool called maximizing player we begin position in which case we return the static evaluation of that position

[02:48] otherwise if it's currently the turn of the maximizing player which in our example means it's white to move then we want to find the highest evaluation that can be obtained from this position so we create a variable called Max evaluation

[03:01] and initialize that to negative infinity we then loop through all the children of reached in a single move to find the evaluation of each child we make a

[03:14] recursive call to the minimax function passing in the child depth minus one and false since it will now be the other players turn to move we can then set max eval equal to whichever is greater between the current max evaluation and

[03:29] the evaluation of the child position once we've evaluated all the children we can return the maximum evaluation that we found now we do essentially the same thing for the minimizing player creating mini eval set initially to positive

[03:42] infinity and for each child position we call minimax passing in the child depth minus 1 and this time true the mini value and get set whichever is smaller between the current minimum evaluation and the child evaluation and finally

[03:56] we'll return them in evaluation let's step through this example again this time with the code in front of us first though we'll need an initial call to the minimax algorithm to start things off ok we're at the first position and we want

[04:11] to find the max of the two children so we call minimax on the first child it first child which in turn wants to find the max of its two children so it calls

[04:23] minimax and first at this point though depth is equal to 0 so minimax returns the static evaluation of that position this value on its second child receives the static evaluation from that and returns the max

[04:41] between the two children that value gets passed up to its parent which now calls minimax on its second child minimax is called on its two children getting their static evaluations and the max is passed up to the parent which passes the min of

[04:56] its two children up to its parent which knucles minimax on its second child I'll stop with the blow-by-blow narration now but hopefully it's quite clear how the algorithm uses recursion to search through the tree

[05:12] now that we've seen minimax works let's run through this example yet again to look at how it can be sped up using pruning these first few steps are the same as before but consider the situation we have after

[05:25] evaluating this +5 position without yet evaluating the other position we know being greater than or equal to 5 we can now see that black won't go down this

[05:38] branch because he already has a better option available this observation means that we don't have to waste any computation on evaluating this final pruned it from the tree things now continue as normal again for a few steps

[05:54] until we get here and black to play in this position will be choosing whichever of the two moves leads to the lowest evaluation so we know the evaluation here is going to be less than or equal to minus 4 we can now be sure that white

[06:07] him and so we can prune these positions as you can see the results of the search is exactly the same as before we've just saved some time by not considering

[06:19] positions when they can't affect the outcome ok I want to quickly go through a slightly deeper tree I'll just fly through these first few steps because there's no pruning happening so it's quite straightforward in fact it is

[06:31] been able to prune a single position yet so pruning isn't guaranteed to occur it very much depends on what order the moves are in ideally the moves would be

[06:44] for example if these two moves had been the other way around we would have been able to prune the second one for this reason it's usually a good idea to order the moves based on how likely they are to be good for example in chess

[06:59] capturing a piece with a pawn is very likely to be a good move and so it would be wise to explore at first anyway let's continue with this tree so this next position has been evaluated as plus one and now I have a question do we need to

[07:14] evaluate the other position here or can we prune it if you're in the mood so without evaluating the other position we can say for sure that the previous

[07:26] position is less than or equal to one since black is of course just gotta choose whichever is lowest this means that white will never go down this particular branch because if the best he can hope for is a plus one he'd

[07:39] rather just go the other way at the start where he's guaranteed a plus 3 so we can indeed put in that position all right let's finish off this tree here we got a 5 and a 2 so black would of course choose the 2 that means this position is

[07:54] branch since you can get a 3 by going the other way this means that we can prune the rest of these positions the tree is not complete and we can see that with best play from both sides the game will follow this

[08:08] path let's look at how this pruning stuff works in code we'll start with our original minimax algorithm and add two parameters called alpha and beta which assuming best play from the opponent will measure update our recursive calls

[08:25] to minimax to pass in these two new values now for the maximizing player we'll set alpha to whichever is greater between alpha and the latest evaluation then if beta is less than or equal to alpha we'll break out of the loop

[08:40] similarly for the minimizing player will set beta equal to whichever is smaller between beta and the latest evaluation and then once again if beater is less than or equal to alpha we'll break out of the loop to better understand what's

[08:53] going on let's step through the example one last time in our initial call to the worst possible score for white as our value for alpha and positive

[09:05] infinity the worst possible score for black as the value for beta these values get passed down until we reach our first end position here negative 1 is greater than alpha so the alpha value of the parent gets set to negative 1 3 is then

[09:20] greater than negative 1 so the alpha value gets updated once again however beatriz not less than alpha here so no pruning occurs next in the parent position B to get set to 3 and this is passed down to its second child after

[09:35] evaluating this +5 position alpha get set to +5 and now beta is less than move BtoB unless an alpha means that black had a better option available

[09:48] earlier on in the tree and so we prune going back up the tree alpha get set to three in the first position so we know white is guaranteed at least a three but that so coming down here near the negative

[10:05] so alpha doesn't change in the parent position be sure now get set to negative four which is less than alpha since this position is black to move

[10:18] earlier on in the tree and so once again we can prune we've now completed the tree so hopefully this video has made sense of the minimax algorithm and how

[10:31] it can be sped up using this idea of pruning any branches that can't affect the outcome due to the fact that one side will prevent that branch from ever I'll leave you with the last few moves of this game which was the first time a

[10:46] computer was able to defeat a reigning world champion in classical time controls

[10:58] you