What is the difference in speed between enumeration of all game states and Sprague-Grundy functions?

Question

Algorithms

In general, while walking around emaxx, I came across the Sprague-Grnady function (translating the states of any game into Nim-number), but I don’t understand why this function is needed at all. Why is it better than just enumeration, we are there, that we are iterating over all possible states, only in enumeration we do not use MEX, therefore enumeration should be even faster. Then the question arises: why do we need this function? I will be very grateful for the answer.

Answer 1

Just like that, Grandi's function applied in the forehead is not at all faster than the usual marks "winning" / "losing" situation. Even slower, because you need not just to see if there is a transition to a winning situation, but you need to look at what values ​​you can make the transition to and find the minimum not covered by them.
But it has a remarkable property - if the state of the game can be decomposed into several independent games and the player can make a move in any of the games on his turn, then the Grundy function can be calculated as an xor of values ​​for all states. It is cleverly called that the game is the sum of the games. In some problems, this makes it possible to colossally reduce the space of states.
One example is playing Nim. There are several heaps of stones. During his turn, a player can take as many stones as he likes from any heap. The one who has no stones left loses. In a simple iteration, you would have to store as a state a vector of the number of stones in each pile. But here the standing is obviously decomposed into sub-games: each pile is its own separate game. Moreover, Grandi's function here is trivial - it's just the number of stones. So the solution to the Nim game turns out - take xor sizes of all heaps. If not 0, then the state is winning. It is necessary to take so many stones from some pile to get xor equal to 0.
Another example is a chocolate bar. Players break it along the cells. During his turn, the player can take any rectangular piece and break it somehow along the cells (if there are more than 1x1 cells, of course). The one who cannot make a single move loses. Again, with a simple enumeration, we would have to store the sizes of all the pieces in a state. There are SO many options here. And with the Grundy function, it is enough to consider the states of the form "one tile of size nx m". After one turn, you will have 2 tiles, but smaller. You already know the grandi function for them, XOR them and you get a function for a possible transition.