Grundy Numbers are fundamental values used to analyze impartial games, calculated recursively using the Minimum Excludant (Mex) operation on the set of Grundy Numbers of all possible next moves; a position's Grundy Number equals the smallest non-negative integer not present in the set of Grundy Numbers of its reachable positions, allowing players to determine winning strategies by evaluating game states mathematically.
Grundy Numbers and MEX in Combinatorial Game Theory
Added:Hi everyone, this is gkcs!
We are going to be talking about Combinatorial Game Theory today.
So, the games that we are going to be focusing on are impartial games.
You have games like chess or tic tac toe.
And those games are partial, so they are more fun to play with in a way.
Because you have, in chess, you have pieces which are specific to you.
So you can't move your opponents pieces.
Similarly in tic tac toe, you have symbols which are specific to yourself.
You can't use your opponent's symbol over here to make your own streak.
You can't of course, use your opponent's symbol.
This looks ridiculous, but that's what a partial game is.
You can't use anything specific to your opponent because all the game states have everything generic.
The most common example of an impartial game, let's write that down, is the game of Nim.
So Nim has these piles of coins, and you have N piles of stones or coins or anything that you like.
And you have to take out zero, no zero is not allowed in fact.
You have to take out one or equal to one coin from a specific pile.
So you come across these piles.
And lets say these have A1, A2 and A3 coins.
And you choose a pile first, so lets say you choose A2.
And then you can take out one or more than one coins from this pile.
And the objective of the game is that you take away the last coin from all the piles.
No. not exactly.
'You take away all possibilities of your opponent' is the objective of the game.
So you have these three piles and essentially you reach a state where two of the piles need to be zero.
And one the piles needs to be non-zero.
So that if you take out all the coins and give your opponent this state, in which they can make no moves and lose.
So that is the objective of the game of Nim.
And the reason why I am stressing on impartiality is because the theory that we are going to be talking about is very specific to only these impartial games.
Alright, so let's start!
The first operation that we need to know about is called 'Minimum Excludant'.
MEX is the short form for it, and it stands for 'Minimum Excludant'.
This is an operation that you need to perform on a set.
So you have a set of numbers, which are non-negative and if you perform this operation on this set, you get a single number.
You get the smallest number which does not exist in this set.
So 0, 1 exist, those integers exist.
And two does not.
So this is the smallest number which does not exist in the set.
The reason why you might want to use this is because this tells you... S gives you the set of moves that you can play.
MEX tells you the smallest move, the first move that you can never play.
That might be useful information to have.
And so that is the operation we will keep in mind.
Using this very operation we can calculate something called Grundy Numbers.
Grundy Numbers are core to impartial games.
A Grundy Number defines the entire game state.
If you have a board or if you have a pile of coins, N piles of coins with different coins in each one, a single Grundy Number can define the entire game state.
Even impartial game has this Grundy Number.
The way to calculate it is, you take the minimum excludant of your set.
If your set is empty, thats the base condition.
Then MEX(0) is equal to zero.
MEX({ }) is zero.
And MEX of anything else is equal to the way that we have defined above.
You take the numbers, you take the next number which comes up and that's what you give out.
MEX(S) over here is 2.
Alright?
Let's just go through a quick example.
You have this MEX operation that you know about.
And Grundy is MEX of a set of moves that we can play.
Lets say you have a pile of 10 coins, and the only kinds of moves that you can make is: either take one or two or three coins.
So these are the number of coins you can take.
And the termination condition is if you have no more coins to take, if you have no move possible, then you lose the game.
So 0 is losing.
So, you need to play optimally from 10 coins such that your opponent loses.
So Grundy(10) is what we are looking at.
And that is defined by MEX of all possible states that you can have from this state.
So you might think that this is 9,8 and 7.
Because those are the positions that you can go to.
But that won't define the game states, that would define just numbers.
What you really need is game states.
So this is incorrect.
What we have instead is Grundy(9), Grundy(8), Grundy(7).
So what you are seeing is that this function is recursive in nature.
Grundy(9) in turn will call 8, 7 and 6.
And so on and so forth.
You know what?
I am just going to simplify this a little bit.
I am going to keep at Grundy(5)... Yeah, 5 seems to be good.
And here we will have then 5, 4 and 3.
So lets pick the scenario where there is Grundy(3).
Which is MEX of Grundy(2), Grundy(1) and Grundy(0).
Grundy(0) is losing.
So that is zero.
You have no more moves to play when you have just 0 coins remaining.
So this is 0.
Grundy(1)... what could that be?
Well, you could move to state 0.
You have just one coin.
In fact, you have just one choice.
So if you have one coin you have to take it and then you move to this state which is losing for the other player.
So 0 is in your set, the next number which is missing from you set is 1.
So this is 1.
Grundy(2) on the other hand, if you have two coins, you can either go to 1 or you can go to 0.
So you can either go to 1 or 0.
This is your set.
You can of course do grundy over here also.
Grundy(0) is 0 and Grundy(1) is one.
But you don't need to do that, because these are the base conditions.
MEX of this is equal to 2.
So thats what Grundy(2) is.
Its 2.
Alright, and we have Grundy(3) giving us : between zero one and two, we need to take the MEX.
So MEX of this is 3.
Grundy(3) gives us 3.
Lets replace that.
Similarly Grundy(4) is going to give us MEX of Grundy(3), Grundy(2) and Grundy(1).
We know Grundy(1) is 1.
And Grundy(2) is 2.
And Grundy(3) is 3.
So, they become 3, 2 and 1.
Now, interestingly, it might seem like the MEX is now 4.
But we have missed the integer 0.
So the smallest number which does not exist in this set is 0 now.
Great, so Grundy(4) turns out to be surprisingly 0.
And this makes logical sense.
Because if you have 4 coins, there is nothing you can do apart from losing.
If you take out one coin, you reach 3, your opponent takes out 3 coins.
If you take out 2 coins, 2 coins are remaining.
Your opponent takes those.
And if you take out all 3, there is just one coin remaining and your opponent takes that out to put you in the losing state.
So you should be at 0, and that's what we are seeing over here, in the theory.
Alright, Grundy(5) gives us Grundy(4), Grundy(3) and Grundy(2).
We need to take the MEX of these three.
So Grundy(2) we know is equal to 2.
Grundy(3) is equal to 3.
And Grundy(4) surprisingly is 0.
So 0, 3 and 2 are your numbers in the set.
What we get from this is that 1 is missing.
Because we are taking the MEX operation.
So, Grundy(5) turns out to be 1.
Oh!
Well, I think I have found out the Grundy(5).... Ah well, we are in luck!
We are going to be using 6 coins then.
But you see how to calculate this.
Grundy(6) now is equal to the MEX of 0, 1 and 3.
So that is 2.
So Grundy(6) turns out to be 2.
And this is just the basic theory.
Using this, we are actually going to be solving Nim games.
And this is just the basic theory about impartial games.
I am sorry there is no practical implementation yet, but that will be very soon in the very next video.
So hang on!
Its coming soon!
Up Next

The Game of Nim: Binary Strategy & Winning Solutions
@UCLDepartmentofMathematics
1.7K views•2020-07-11

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

Sprague-Grundy Theorem and Winning Strategies in Impartial Games
@gkcs
21.7K views•2017-03-20

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








![[s4 | 2026] Алгоритмы и структуры данных, Орешников Д. М., лекция 8](https://i.ytimg.com/vi/z4JsgJnC1W4/maxresdefault.jpg)









