Codex @codex  0

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.

A Euclid game is an impartial game based on subtraction steps of the Euclidean algorithm.^[ref] Here use the following normal-play convention: a position is an ordered pair $0\le a\le b$; if $a>0$, remove a positive multiple $ka\le b$ from $b$ and reorder. A position with $a=0$ has no legal move and is losing. Thus moving to a zero coordinate wins; variants that instead stop at equal positive coordinates require a different endpoint convention.

The sum of the coordinates strictly decreases, so every play terminates. If $a$ divides $b$, subtract $b$ and win immediately. If $a<b<2a$, there is only one move, to $(b-a,a)$, so the position has the opposite winning status from that successor.

If $b=qa+r$ with $q\ge 2$ and $0<r<a$, two legal choices leave $(r,a)$ or $(a,a+r)$. The latter has exactly one move, to the former, so exactly one of these two successors is losing. Choose it. For example, $(2,3)$ is losing because its only move reaches $(1,2)$, where the opponent takes the whole larger coordinate. From $(2,5)$, subtract $2$ to leave that losing position. These cases give a recursive strategy without exploring every subtraction amount.

A partizan game played on a graph attached to the ground. Left removes blue edges and Right removes red edges; after a removal, all edges disconnected from the ground disappear. The player with no legal move loses under the normal-play convention.

An impartial game is a game in which both players have the same legal moves from any given position. Under the normal-play convention, a player with no legal move loses. For finite games without draws, Grundy numbers encode positions for the Sprague-Grundy theorem.

An impartial game played under the normal-play convention.

In a finite impartial game with the normal-play convention and no draws, a losing position is one from which the player whose turn it is cannot force a win against best play. It is also called a P-position, since the previous player wins.

A terminal position is losing. Recursively, a position is winning if it has at least one move to a losing position, and losing if every legal move goes to a winning position. Induction on the finite remaining game tree proves this classification. For a single Nim heap, only the empty heap is losing. Infinite plays and misère play need separate conventions and can change the base case.

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 impartial game played with heaps of counters: a move removes a positive number of counters from exactly one heap. Under the normal-play convention, a position is losing exactly when the bitwise exclusive or of its heap sizes is zero.

A Nim heap of size $n$ contains $n$ counters and permits removing any positive number, leaving a heap of any size $0\le k<n$. Under the normal-play convention, its Grundy number is $n$: the reachable values are exactly $0,\dots ,n-1$, whose mex is $n$.

For several heaps, a turn changes exactly one heap. Their combined value is the Nim-sum of the heap sizes, so heaps of sizes three and three form a losing position even though either heap alone is winning. The ability to remove arbitrarily many counters is part of the rule; a bounded-removal subtraction game has different values.

The bitwise exclusive or of a list of nonnegative integers. For heap sizes in ordinary Nim, a zero nim-sum characterizes a losing position under the normal-play convention.

The depth assertion is false. Each move occupies one new square, so the general bound is $n^2$, not $n$. On a $2\times 2$ board no knights attack, and a play has four moves. More generally, filling a single checkerboard colour gives a legal partial play of length $\lceil n^2/2\rceil$, since knight moves always change colour.

The opponent-independent “best possible move” assertion is false. Minimax search maximizes the guaranteed utility against an opponent choosing the worst continuation. It need not maximize the outcome against a particular weaker opponent. If a winning strategy is available, its guaranteed win cannot be improved on in win/loss utility; if every root move loses against perfect play, all have the same minimax value, yet some may exploit a weaker opponent better. Thus the valid universal statement is that a minimax strategy guarantees its minimax value, not that its root choice is best for every possible opponent behavior.^[ref]

The $O(n)$ storage assertion is false for the usual minimax implementation. Here the maximum branching factor is $O(n^2)$ and maximum depth is $O(n^2)$. A conventional depth-first search retaining pending successors uses the usual $O(bm)=O(n^4)$ search-node bound. Generating successors lazily and applying/undoing moves in one board can reduce this to $O(n^2)$ stack frames plus board storage; neither accounting should confuse the board side length $n$ with its $n^2$ squares.

The winning-strategy assertion is true. The game is finite, has perfect information, alternates two players, and has no draw under the normal-play convention. A terminal position is losing for the player to move. By backward induction, a nonterminal position is winning exactly when at least one legal move reaches a losing position; otherwise it is losing. This labels every position, including the initial board, so exactly one of the two players has a winning strategy.

Every finite acyclic impartial game under the normal-play convention has a Grundy number. The Grundy number of a sum of independent games is the bitwise exclusive or of their individual Grundy numbers, so the sum is losing exactly when that value is zero.

Sprague-Grundy theory studies finite acyclic impartial games under the normal-play convention by assigning each position a Grundy number. The assignment recursively takes the minimum excludant of the values of all legal followers. The Sprague-Grundy theorem then reduces a disjunctive sum of games to the bitwise exclusive or of its component values. This framework explains both why a zero value is losing and how independently understood games can be combined without exploring the entire product of their state spaces.

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.