619's blog

Grundy Numbers for Misère Nim?
By 619, history, 2 weeks ago, In English

Misère Nim: Just like normal Nim game but last player to make a move loses

What are the equivalent grundy values for this game?

My Thought Process

UPD: Found a relevant thesis on it.

TLDR


  • Vote: I like it
  • +5
  • Vote: I do not like it

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

But what about multiple piles, for example

1, 1, 1

or

1, 1

both have different outcomes but nim sum is same

→ Reply
»
2 weeks ago, # |
  Vote: I like it +21 Vote: I do not like it

In this case you simply don't allow moves that lead to an invalid state. So if you're at a game with 1 pile you don't allow to remove all stones from it and in all other states you allow the usual moves.

So a game with 1 pile that has x stones (x being at least 1) has nimber (x — 1). The point here is that this isn't a game composed of perfectly parallel games, so you can't simply find the nimber of all piles and xor them all together by using the sprague-grundy theorem. You should instead find the nimber of the entire game without splitting it into parallel games.

→ Reply
  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The point here is that this isn't a game composed of perfectly parallel games

    I didn't quite understand why this is the case can you could elaborate on it with some examples maybe. Also is Sprague-Grundy theorem not being applicable exclusive to Misere Games? I assume it works for all normal impartial games right?

    Also if we consider n piles as a single state and try to compute recursively then of course it will exceed constraint limits. What is your general strategy when thinking about Misere games, you can use the standard misere nim as an example maybe.

    → Reply
    • »
      »
      »
      2 weeks ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      Yes you're right about sprague-grundy working for all impartial games and this is an impartial game, the detail is that I'm actually not sure if everyone thinks of the theorem as the same thing. It can be either "every impartial game has an equivalent nimber" or that + "the nimber of parallel games is the xor of the nimbers of the games". The thing is that in practice it's used by separating a game into parallel games, computing the nimber for those games and then taking the xor of the nimbers which we can't do here because we can't split it into perfectly parallel games. It's the section "combining games" here.

      My usual strategy for such cases where we can't split into parallel games in order to compute the nimber in the solution is basically doing the exponential dp for all tuples of small size and trying to figure out the pattern. To confirm if the pattern is ok, add an assert with your hypothesis and test it in those tuples. I've done exactly that in the past for misere nim and this is what I realized:

      For most states the nimber is exactly the same as the usual nim game (xor of sizes of piles). What's different is when every pile other than one is of size 1. So I then work out the cases:

      if there are N piles of size 1 then the nimber is (N % 2) ^ 1.

      if there are N > 0 piles of size 1 and a pile of size 2, the nimber is at least 2 because we can take the pile of size 2 out completely or only 1 from it. For N = 1 then it's 2, for N = 2 it's 3 and so on (odd N means 2, even N means 3).

      From here iirc I actually figured out that we can reduce the game into some cases: the case of one pile, the case of piles of 1 and at most one pile of 2, the rest. For the first case, the nimber is the size of the pile minus 1. For the second case, the nimber is the usual nimber xor 1. For the last case the nimber is the same as the usual nim game. I'm going mostly by memory here so it'd be good if you tried figuring out the details by yourself.

      → Reply
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Ed loves Grundy !!

download

→ Reply