Proof sprague-grundy value is 0 if and only if it is losing position

Question

So, i take this game theory module this summer, and i encountered this exercise problem, i tried to do this by induction by have terminal position (grundy-value = 0) as base case, but can't figure out the inductive step, can someone help me.

Thanks.

Answer 1

Hint: Call a position "weird" if Sprague-Grundy gives the wrong answer, i.e., either the Sprague-Grundy number is zero and it's not a losing position (for the player to move next), or else the Sprague-Grundy number is positive and it's not a winning position. Prove that in any weird position there is a move which leads to another weird position. It follows that, if a weird position exists, then an infinite play from that position is possible. The basic assumptions of the game (an acyclic digraph which is finite or at least "progressively finite") imply that an infinite play is impossible.