I'm trying to understand some concepts of game theory. So far I've understood how the game of nim works, at least the most basic form: as long as the current game has value > 0 the current player can change at least one of the piles such that the next turn will be played with value = 0. If the current game has value = 0 there are only 2 possibilities: Either the game is over and the player lost or he may pick a pile but by doing so in every case will yield value > 0 for the next player. I understood it by reading this Topcoder article. It clearly explains how to choose a pile when value > 0 and change it to value = 0 and that keeping value = 0 for two turns is impossible.
I am now trying to understand how the minimum excluded cardinal is equivalent to a nim value. How will always choosing the minimum value not appearing in the set always yield the correct result? How can the bigger values be discarded and not accounted for if those values can still be reached? Is there any intuitive way to know why this works?
You have a position $X$ from which certain moves are possible, whose nim-values are $a_1,\dots$. You want to know why the value of $X$ equals the smallest number not appearing in $a_1,\dots$. Let $b$ be that number.
To show that the value of $X$ is $b$, let's imagine playing a game of $X$ + (a nim-heap of size $b$). It suffices if I can show that this is a second player win.
Suppose first player makes a move in $b$. There is a move in $X$ to the same value, and this is winning for the second player. Similarly, if the first player makes a move to a position whose value is smaller than $b$, the second player moves in $b$ to the same value. But now (and this is really what you were asking about) what if the first player moves to a larger valued position in $X$? There is a move from that position to a position whose value is $b$! And that is the winning move for the second player.