Combinatorial Game Theory

A combinatorial game has two players who alternate moves, perfect information (no hidden state), no chance, and a finite set of positions that cannot recur (the game always terminates). The outcome depends only on the current position, not on history.

Under normal play the player who makes the last move wins — equivalently, a player who cannot move loses. Under misère play the player who makes the last move loses, so being unable to move means you win. Most CP theory (Nim-sum, Sprague-Grundy) targets normal play; misère analysis is generally harder.

In an impartial game the set of moves available from a position is the same for both players (e.g. Nim). In a partizan game the two players have different available moves (e.g. chess, Hackenbush with colored edges). Sprague-Grundy theory applies only to impartial games.

A P-position is a win for the Previous player (the one who just moved): the player about to move loses with optimal play. An N-position is a win for the Next player to move. Terminal positions under normal play are P-positions (the player to move cannot move and loses).

A position is a P-position iff every move from it leads to an N-position. A position is an N-position iff at least one move leads to a P-position. From an N-position you win by moving to some P-position; from a P-position all moves hand the opponent a win.

Label positions by backward induction over the state DAG: terminals are P-positions, then a state is N if any successor is P, else P. Memoize win(state) so each state is evaluated once. Total cost is O(states × moves per state); requires the position graph to be acyclic.