斯普莱格–格隆第定理
An impartial game is a two-player game in which both players have complete information, no chance is involved, and the legal moves from each position are the same for both players. We will deal with the normal play rule, in which the last player to move is the winner.
An impartial game can be abstractly represented by a directed acyclic graph, in which each vertex corresponds to a position, and each directed edge represents a legal move from one position to another.
We can imagine that a token is initially placed on some vertex, and the two players take turns moving the token from its current vertex to one of its direct followers. The game ends when the token reaches a sink, which is a vertex with no outgoing edges, and then the last player to have moved is the winner.
P- and N-positions
We can classify each position in the game according to whether it is a first- or a second-player win, if both players play optimally starting from that position. A first-player-win position is known as an N-position (because the next player is to win), while a second-player-win position is known as a P-position (because theprevious player is to win).
The P- and N-positions can be characterized inductively as follows:
- A vertex v is a P-position if and only if all its direct followers are N-positions.
- A vertex v is an N-position if and only if it has some P-position follower.
The induction starts at the sinks, which are P-positions because they vacuously satisfy the P-position requirement.
Knowledge of the P- and N-positions of a game provides the winning strategy for it: If it is our turn and the game is in an N-position, we should move into a P-position. Then our opponent will be forced to move into an N-position, and so on. Eventually we will move into a sink and win.
