adzo261's blog

Doubt Classical Nim Game
By adzo261, history, 6 years ago, In English

In normal Nim game, the player taking the last object wins.
And terminal position here is always a P -position.
Now, I have a question where you are given the terminal P and N positions unlike the only terminal condition in normal Nim.
Is this a variation of Nim? If yes, how to analyze it, how should I go about assigning grundy numbers?

Formally:
I have n heaps with represented by a set S={a1,a2,a3, .... an}.
And, I have a set T which gives terminal positions and tell whether it is a P-position or N-position.
One element of the set can be {{k1,k2,k3, .... kn},P}
where,
k1<=a1
k2<=a2
k3<=a3
.
.
kn<=an

It means the set {k1,k2,k3, .... kn} is a terminal position.
And, the second parameter denotes either 'P' or 'N' as P-position or N-position.

Can this be made equivalent to Nim?
How to analyze this?

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

»
6 years ago, # |
  Vote: I like it +6 Vote: I do not like it

This works in exactly the same way. The rules for P and N-positions are:

  • If you can reach a P-position in one move, then this position is a N-position.
  • If all positions that you can reach are N-positions, then this position is a P-position.

You can start analyzing the game in the opposite direction. Take any known P-position, and mark all position that can reach this position with N. Do this with all P-positions. Also check the positions that can reach the N-positions. Once you find a position that can only reach N-positions, mark it with P. Do this procedure as long as possible.

If there are still some positions left, that don't are P or N positions, then this position is neither winning or loosing. I.e. the game will end in a draw. E.g. this is possible if there is a loop in the game, which means you can visit the same position multiple times.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Thank you so much! Can you share some resources or implementation of this problem?

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Here are two problems, that can be solved with the exact same approach: http://codeforces.me/contest/917/problem/B, http://codeforces.me/contest/919/problem/F

      However it should be pretty easy to implement. You just start a BFS with all P- and N-positions. Once you find a new N-postion, put it in the queue. For each unknown positions keep a counter with how many N-positions it can reach. And once that counter is equal to the number of possible moves, mark it a P and also put it in the queue.

      → Reply