1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.