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?
This works in exactly the same way. The rules for P and N-positions are:
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.
Thank you so much! Can you share some resources or implementation of this problem?
Here are two problems, that can be solved with the exact same approach: http://codeforces.com/contest/917/problem/B, http://codeforces.com/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.