Grundy Numbers and MEX in Combinatorial Game Theory

Added:

Partisan Game Theory and Conway's Game Values

While the Sprague-Grundy theorem and the MEX (minimum excludant) operation provide a complete framework for analyzing impartial games under normal play, they are fundamentally limited. They fail when applied to partisan games—where players have different options (such as Chess, Go, or Hackenbush)—and in misère play, where the last player to move loses. To address these limitations, John Horton Conway developed a broader framework of Partisan Game Theory. In this theory, games are represented as structured sets of left and right options rather than single Grundy numbers, leading to the creation of surreal numbers and complex game values (like 'star', 'up', and 'down'). Under partisan or misère rules, the simple additive nature of Nim-values and the MEX rule break down, requiring algebraic structures like misère quotients or combinatorial game arithmetic to determine winning strategies. Exploring this broader framework reveals that Grundy numbers are just a small, highly restricted subset of a much larger mathematical landscape.

Fundamentals of Impartial Games, including the definitions of game states, transition rules, and the normal play convention.
The Game of Nim, including its rules, winning strategies, and the classification of states into P-positions (previous-player-winning) and N-positions (next-player-winning).
Bitwise operations, specifically the bitwise XOR operation (addition without carry) used to calculate Nim-sums.
Graph Theory basics, particularly how to represent sequential game states as Directed Acyclic Graphs (DAGs) where vertices are game positions and edges are valid moves.
The Sprague-Grundy Theorem, learning the formal proof and implications of why every impartial game under normal play is equivalent to a one-pile game of Nim.
Analysis of Misère Play, exploring how winning strategies and Grundy-value evaluations change when the last player to move loses.
Partisan Games and Conway's Game Values, transitioning to games where players have asymmetric move options (like Hackenbush or Chess) and studying surreal numbers.
Dynamic Programming in Game Theory, writing algorithms to compute MEX and Grundy values for complex, custom state-spaces in competitive programming and computer science.
48.8K views660likes11:27@gkcsOriginal Release: 2017-03-19

Grundy Numbers are fundamental values used to analyze impartial games, calculated recursively using the Minimum Excludant (Mex) operation on the set of Grundy Numbers of all possible next moves; a position's Grundy Number equals the smallest non-negative integer not present in the set of Grundy Numbers of its reachable positions, allowing players to determine winning strategies by evaluating game states mathematically.