Combinatorial game theory

Combinatorial game theory studies positions in alternating-move games with fully specified legal moves, usually perfect information and no chance. A position can be defined recursively by the positions available to each player. Under the normal-play convention, a player with no legal move loses.

An impartial game gives both players the same moves; Nim is the standard example. A partizan game allows different moves for Left and Right. The disjunctive sum lets a player move in exactly one component on each turn, making it possible to study how game positions combine algebraically. Infinite play or misère play requires additional conventions; normal-play results do not automatically transfer.

Wythoff's game is an impartial game played with two finite heaps. A move removes any positive number of objects from one heap, or removes the same positive number from both heaps. Under the normal-play convention, the player with no legal move loses.

For example, $(0,0)$ is losing, while $(n,n)$ with $n>0$ is winning because one move empties both heaps. The position $(1,2)$ is losing: its possible moves lead to $(0,2)$, $(1,1)$, $(1,0)$ or $(0,1)$, each of which can be emptied by the next player. This directly checks a first nontrivial losing position.

The equal-removal diagonal move distinguishes the game from two-heap Nim, where only one heap may change in a turn. A winning strategy is determined by moving to a losing position whenever possible; identifying the complete family of losing positions is a further number-theoretic result.

Misère play is the terminal convention in which the player making the last legal move loses. For finite games without draws, this means a player whose turn begins with no legal move wins. The same move rules with the normal-play convention instead make that player lose.

A one-heap removal game makes the difference immediate. If a single object remains and the only move removes it, the player to move loses under misère play and wins under normal play. With two unit heaps in Nim, the first player removes one heap and forces the other player to take the last object, so the position is misère winning even though its normal-play nim-sum is zero.

Changing the terminal condition changes the recursive winning/losing classification. Normal-play formulas, including unrestricted use of Sprague-Grundy theory, therefore cannot be transferred unchanged. Infinite play requires a separate draw or outcome convention.

An alternating grid-removal game in which choosing an occupied cell removes it and every occupied cell above and to its right. The player who removes the designated lower-left poison cell loses. Reachable occupied-cell sets are order ideals for coordinatewise order. A nonempty reachable position always contains the poison cell, and removing that cell empties the board. The monotone boundary representation of a grid order ideal supports compact board updates.