# Does Sprague-Grundy help solve any impartial games that don't comprise independent sub-games?

By "solve" I mean efficiently compute whether a given position is a $$\mathcal{P}$$-position (first-player win). By "efficiently" I mean compared with "brute force", which involves recursively labeling every reachable position a $$\mathcal{P}$$-position if you can directly reach at least one $$\mathcal{N}$$-position from it. Calculating the nimber of a state with the $$mex$$ formula for a general impartial game seems, if anything, slightly less efficient than brute force.

Clearly Sprague-Grundy helps when the game comprises independent sub-games because you can use nimber addition on the sub-games' nimbers, but impartial games in general don't have this property. For example, the Nim variant where you also have the option of choosing one stone from every nonzero pile. Does Sprague-Grundy help at all here? Or with any other impartial games other than the ones that comprise independent sub-games? Or might you just as well use brute force when a game lacks this property?

For an example where the theory helps but the game does not obviously consist of independent subgames, see "Turning Turtles" in Winning Ways (Vol 2 in the original edition, Vol 3 in the new edition). Here, the game consists of a line of $$n$$ coins each of which may be heads or tails. A move (for either player) consists of flipping at least one and at most $$k$$ coins, provided the rightmost flipped coin goes from heads to tails (the other coins may be flipped in either direction). The values $$n$$ and $$k$$ are fixed parameters for the duration of the game. At first, it does not seem like this game decomposes into independent subgames, but in fact, the Sprague-Grundy theory can be applied. See Winning Ways for details.