The Sprague-Grundy Theorem states that in any impartial game, a position is losing if and only if the XOR (binary zor) of the Grundy numbers of all possible next positions equals zero; conversely, if the XOR is non-zero, the current player has a winning strategy. To find the optimal move, identify a next position whose Grundy number XORed with the current position's Grundy number equals zero, thereby forcing the opponent into a losing position.
Sprague-Grundy Theorem and Winning Strategies in Impartial Games
Added:hi guys this is gkcs we are going to be talking about the second part of comori Game Theory now and if you haven't seen the first part you can check that out uh quick recap of that is to find out the Grandy number of a given position a game position you need the maximum excluded of the set of all possible positions from that position all right and the reason why we wanted this was going to be very clear now we have this Theory called sprock granty right so I hope hope I get the spelling right but yeah these guys are two mathematicians who uh actually formulated this Theory they say that using Grundy numbers you can tell if a person is winning or losing a position for impartial games of course but uh you can do this using their theorem so what that states is that you have the set of possible positions that you can go to positions and you need to perform an operation on this which gives you results so the operation is zor this is binary zor so if you just you know zor is basically one and one gives you zero even number of ones give you zero and odd number of ones give you one right a simple binary zor you can look it up but if the zor of all the Grandy numbers that you can get from the set of all possible positions is equal to zero that means you're losing all right and if it is not zero that means you're wining so From Any Given position if you take the zor of the set of possible positions from now and if you get a zero then you know that the player playing right now the player who has the turn right now is losing and otherwise it is winning so let's pick an example from last time to understand what's going on uh we have six coins yeah six coins and from this pile of coins you can take out between one to three coins okay so how do we play well last time we learned that the Grandy numbers can be calculated using a recursive function so this time we have learned about spr gry which says that the result of having six coins in your pile and with your turn uh it's the zor of Grandy 6 - one you can take one coin so that would be five the next scenario is when you take two coins giving you grand4 and the only remaining scenario is when you take away all three coins as many as you can basically and you have gr three so last time we discussed that uh these three numbers they evaluate to zor of gr of five remember was one grity of four was zero and grity of three was three all right what does this say if you take the zor binary zor of this you have 01 0 0 and one one numbers in binary zor operation takes even number of ones to give you zero or odd number ones to give you one so even number of ones you have two ones which gives you zero single one which gives you one this in uh in decimal is equal to two so you have the number two as a result and you know what if this is non- negative then we just said that you're winning so if you have six coins in your pile and it's your turn you're winning that's a guarantee that strong gry gives you let's just draw a table to understand when we are winning and when we are losing right so if we have uh number of coins goes like this if you have six then you're winning let's try five if you have five coins then you have grantee of 4 3 and two as the possible states that you can go to all right and we have 432 which gives you numbers of gr of two was 2 grity of three was three grity of four was zero so zor of these three numbers is equal to 0 3 and two so we can change this number so that's two 0 and three that's a all uh this gives us 1 over here and even number of ones so that's zero so this comes out to be one it's still not equal to zero so what we can say is we winning in this position also with five coins you're still winning nice to know now let's try four coins and last time we discussed about why this makes sense but having four coins and losing why that makes sense because if you have four coins you take away all three you're left with one and your opponent takes away that one to leave you with zero coins if you take away two then your opponent has two coins and they take away both to give you zero and finally if you take away just one coin your opponent has three coins they take away all three to leave you with zero coins and you're losing so this should give us zero but let's understand if the theory is doing the same result of four the big moment the time to understand whether the mathematicians do stuff which makes sense or lot uh so zor of Grandy of three two and one are the possible states that we have Grandy of three is three Grandy of two is two and Grand one is one so zor of 3 2 and 1 is our answer zor of three zor of two and zor of one we change this to one one and one even zero one and one even again even number of ones that gives you zero doesn't matter whether it's binary or decimal Zer always give you zero okay uh so you have result Z which means that result of four is losing that's what the theorem just said and we just understood that this theorem makes logical sense so this is this is what it states if you have a position you take the Zord of all possible positions from that position and if it evales to zero you know that you're losing otherwise you're winning so this is a pretty uh common Concept in compar programming where you are given two players who are playing optimally and what you need to find out is who is going to win the game at the end of the entire game play so they don't ask you for the moves or for uh how they're going to play they just ask you who's going to win however you could understand what move to play also using these this Theory and let's see how we can do that the way you can play these games is by doing the game state that you have right now and looking at all possible states that you can go to all right and you take the result of those States to make your decision what decision should you make well if any one of these equals to zero then you know that this position is losing that's good because you made your move your opponent got a position in which the result equates to zero which means they are losing in that position and that in turn means that you are winning right so if any one of these results s of n let's say equates to zero you could choose this you could choose this move and what I mean by move is from this state let's say with six coins if going to four coins is winning for you then you choose that move so you take out two coins is what what the optimal move would be right result of s is the zor of all possible positions that you can go from s all right optimal moves are played this way in case you need to show some sort of winning strategy or any sort of backtracking uh yeah this is how you do it all right so now we can play our really good game of uh Nim in which we have four six eight and two coins on each pile all right and the way we going to play this game is go to a particular pile and perform a certain kind of operation so the operation that I'm talking about is division uh so you can take the floor of division with these three numbers of two three and six so for example uh you can choose this pile and divide by six which is going to give you one so the number of coins in this pile will shrink to just one that's one move that you can play all right and using these moves you need to find out uh at the end who is winning so for that reason we need a table and this is what we're going to do so result of the initial position can be defined this way zor as PR grandi says of grandi of four Grandy of six Grandy of eight and Grandy of two so you take this all of these four numbers if it's equal to zero you're losing too bad otherwise you're winning so yeah of course we need the table yeah I forgot about it so this is what we going to have we going to be having uh yeah the Grandy numbers will be this way and the results will be over here so gry of let's take the simplest gry of two Grandy of two is equal to according to the formula G of Any X is equal to uh Max minimum excluded of all possible states that you can go from there so from two if you divide by two you get one so max of one comma if you divide by three you're taking the floor here so you get zero 0/ 6 is also going to give you 0 so max of 1 0 0 that is equal to two so gr of two is two you see that I uh skipped a few steps the the fact would be that grand of two would be Max of Grandy of 0er grand Grand of 0 and Grandy of one so I took just 0 0 1 Instead This is the procedure but Grandy of 0 is obviously zero because you have no moves to make so you're in a losing position this is also zero granty of one you can move to only one position from one if you divide by two you get zero if you divide by three you get zero if you divide by six you get zero so Grandy of one means that from one you can go to 0 Max of that is equal to one you have the single number the next number is one so yeah we discussed this in the previous video in case you're not sure you could check that out Mex of 0 01 is two as we said what about gry of four yeah next easiest gry of four is yeah the possible States from four are G of 2 comma G of 1 comma G of 0 so we divided them and then we take the Mex G of 2 we side is we just found out is two G of 1 is 1 and G of 0 is 0 so Mex of that Mex of 2 1 0 is equal to take your time don't be in a hurry make the guess three all right uh what about G of 6 G of 6 is meof divide by 6 you get 1 divide by 3 you get two divide by two you get three so this is of course G of 1 G of 2 and G of 3 G of 2 is 2 G of 1 is 1 G of 3 is interesting we need to find that out first G of 3 Max off divide by 6 and you get zero divide by 3 and you get one and divide by two and you get one so G of 0 is Zer G of 1 is 1 and uh so Mex of that is equal to 2 nice to know because we are going to be using it here G of 1 is 1 G of 2 is 2 G of 3 is also two unfortunately we do not have a zero here so Mex of these three numbers is equal to zero okay six has um gr of 6 is equal to Z interesting uh what's the next number that we need we need eight so let's go there that in turn is equal to Max of G of divide by 6 you get 1 G of divide by 3 you get two and G of divide by two you get four so max of these three numbers G of one 1 G of 2 2 G of 4 is three so that's next of what is it again 1 2 and 3 again the smallest number which does not exist in the set is actually equal to zero so tragically we have G of 8 equal to 0 what does that mean let's take our result zor of these numbers so that equates to over here above zor of G of 4 is three G of 6 is zero boom G of 8 is also zero these guys are not going to affect the result G of two is two so zor of these numbers is equal to 1 which is non zero and so you're winning this game all right if both players play optimally the person who's starting this game will win the game game that's what we just learned using SP grandi uh we take the result all right now what does that say also about this entire game Z is equal to one Z of these results is one what do you need to do to put your opponent in a losing position you need to make the zor of all possible positions from the from the new position that you'll take equal to zero so what would be the optimal move to play H well we need to convert this to zero we have two zeros here if only this number became two then zor of this would be zero so this number three what's that g of four is three yeah so G of 4 is three we need to make this file equal to two to get a optimal move so this file needs to be made into two to get our optimal move we have a value of two over here so if we can convert four to two then we are putting our opponent in a losing position all right that's that's the best move to make four can be converted to two by dividing by two so our optimal move in this position is to take this pile divide it by two and get a new pile of size two so this is how you play impartial games usually you have some dynamic programming approach to find out what is the best move you know this was a very manual weight that you need to divide by two to get the winning position and uh quf has this problem in the ma challenge which uses PR gry so I'm working on that and in case you're you could subscribe for that if you have any comments or suggestions please leave them below I'll be happy to help and I'll be sharing all relevant links and description uh below so stay tuned see you next time
Up Next

Grundy Numbers and MEX in Combinatorial Game Theory
@gkcs
48.8K views•2017-03-19

JEE Maths | Circles: Pole & Polar Explained with Equations
@TargetPublications
14.4K views•2019-02-23

Fourier Series Introduction: The Big Idea Explained
@DrTrefor
387K views•2021-05-03

The Mathematical Impossibility of Accurate World Maps
@Vox
23.3M views•2016-12-02
Related Study Plans & Knowledge Roadmaps
Structured learning paths in Mathematics


















