Game Theory- Nim Game

Can anyone explain what grundy(i) state represents in any standard nim-game?
Then we calculate grundy(i) = MEX{ grundy(x) , grundy(y), grundy(z) } let this MEX be 0 & non-zero , how a state which can’t be reached from current state can contribute to answer.

It will be helpful even if you could provide some links. @vijju123 @galencolin @ssjgz

Edit: I got some intuition behind these magic functions. If you also struggling then I would suggest checking out these resources:

The Intuition Behind NIM and Grundy Numbers in Combinatorial Game Theory

Sprague-Grundy theorem. Nim

Its just kind of abstraction for the state of game. You should refer to basics of game theory to understand grundy numbers. For starters, see how to calculate them and how they impact simple NIM game, you can skip the mathematical proof to revisit later .


Actually I was looking for intuition behind MEX function. If you could help me. I watched lecture from codechef on game theory. What I learnt from that is , grundy numbers transform the origional game into NIM game. Also please do correct me , if i’m wrong.

You need to do more study on the topic. Squint n read from few more blogs, solve a few easier problems, read their solutions and then revisit your question. Even if you still couldnt answer the question, you’d be able to appreciate the answer. If you are still stuck, we will help.

(By the way, you shouldn’t ping me on this because I know absolutely nothing about game theory)

Actually I was solving questions from hackerrank. Everything was fine until this question throw “grundy nimber” at me.

I think it wouldn’t be hard for you if you try it. Take it as a post request from me. Hope you will help.

Eh, I learn what interests me, not what I (need to), so I’ll put it off till later (it’s not about it being hard, it just doesn’t seem fun)


I agree with you. :slight_smile: