2
$\begingroup$

I'm looking at some work with Combinatorial Game Theory and I have currently got: (P-Position is previous player win, N-Position is next player win)

Every Terminal Position is a P-Position,

For every P-Position, any move will result in a N-Position,

For every N-Position, there exists a move to result in a P-Position.

These I am okay with, the problem comes when working with the Sprague-Grundy function; g(x)=mex{g(y):y \in F(x)}, where F(x) are the possible moves from x and mex is the minimum excluded natural number.

I can see every Terminal Position has SG Value 0, these have x=0, and F(0) is the empty set.

The problem comes in trying to find a way to prove the remaining two conditions for positions, can anyone give me a hand with these?

$\endgroup$
1
$\begingroup$

If I understand correctly, you're trying to prove that the Sprague-Grundy function outputs zero exactly on the $\mathcal P$ positions. Since you have a characterization of $\mathcal P$ positions and $\mathcal N$ positions in terms of the options (positions you can get to in one move), then the best way for you to do this would be induction, the exact form of which depends on your background.

If you have a theorem about how induction can work for games, use that. If you don't, but are comfortable with structural induction (say, on graphs), then induct on the game tree. If you're not comfortable with that, but are okay with the idea of the game tree and standard induction, induct on the depth $n$ of the game tree. The proof is essentially the same in all cases.

$\endgroup$
1
$\begingroup$

If you can win a given game, you must use the following strategy: always move to a 0-position, so your opponent is forced to move to a non-zero position, then reply to a 0-position again. Eventually you reach a terminal position, because games end in a finite number of turns by definition. Since a terminal position has always value 0, this means you made the last move, so you won.

If a game is not zero, the next player wins using that strategy (he begins moving to a 0 position, and so on). On the other hand, if the game is 0, the next player can only move to a non-zero position, and therefore the previous player can win with the previously stated strategy.

You will can also find this, along with other results that might be useful for you, in the first chapter of my Master's Thesis (https://upcommons.upc.edu/bitstream/handle/2117/78323/memoria.pdf)

$\endgroup$

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.