Can we apply the Sprague-Grundy theorem/algorithm if the final position is a winning position ?

If we have a finite two-person impartial game where the final position is a loosing position, we can apply the Sprague-Grundy method to find which player has a winning strategy by assigning each position a nonnegative integer, called the nimber :

  • The nimber of the final position is $0$
  • The nimber of a position is the mex (minimal excluded number) of all the nimbers of all the next possible positions

We have the very useful property :

  • The nimber of the sum of two games is the XOR of the numbers of the two games

Now, from a position with non-zero nimber, the winning-strategy is to go to a position with zero nimber (it is proven to be always possible). The (nimber=0)- positions correspond to the loosing positions.

How to do the same if the final position is winning ?

  • $\begingroup$ Is "nimber" a nickname for "number" or is it a distinct notion? $\endgroup$ – mlc Aug 24 '17 at 18:07
  • $\begingroup$ It is a nonnegative number associated with a position in a (generalised) game of Nim. This is all linked with the Sprague-Grundy theorem :) $\endgroup$ – Friedrich Aug 24 '17 at 18:11
  • 2
    $\begingroup$ Nim games where the last person to move loses are called misère games. See this previous math exchange question"Nimbers for misère games" and the website miseregames.org for details. $\endgroup$ – Jaap Scherphuis Aug 25 '17 at 4:28

As Jaap Scherphuis commented, if you change "terminal positions are losing positions" to "terminal positions are winning positions", then you are considering a game under the "misère play convention" (as opposed to the "normal play convention").

Now, if you have an impartial game (the sort of game you would apply Sprague-Grundy to) under misère play, and just want to see who has a winning strategy, then the difficulty of that depends a lot on the game you're considering.

If your question is just something like "can a tiny modification to the method of the Sprague-Grundy theorem handle all impartial games under misère play?", then the answer is "no", as in my answer to Nimbers for misère games.

More broadly, many papers have been written on handling sums of games that are coming from a single ruleset (e.g. Nim, or Kayles), both general theory and papers on specific games. Sometimes that's a straightforward analysis, and sometimes it's not. You can see a lot of these papers at miseregames.org.

The Sprague Grundy Theorem also tells you a lot more than just how to play a sum of Nim games and Kayles, it says that the nimber tells you enough information to determine who wins a sum of that game in combination with any other impartial games in normal play. However, there cannot be a similarly tidy result for misère games.

There is theory (see, for instance, section V.3 of Aaron N. Siegel's Combinatorial Game Theory) that lets you discard some of the information of an impartial game when misère-played in a sum of arbitrary impartial games. However, I do not believe this simplifies things significantly in any known nontrivial ruleset. For example, in my paper Equality Classes of Nim Positions under Misère Play, it is shown that: In the case of Nim, the only simplification this buys you is basically the ability to subtract 1 from any pair of odd-sized heaps (or add 1 to any pair of even-sized heaps).


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.