SG(posición) = mex de los sucesores.
El Teorema de Sprague-Grundy es una pieza fundamental de la teoría de juegos combinatorios, específicamente para juegos imparciales jugados bajo la convención de juego normal (donde el último jugador en mover gana). El teorema afirma que todo juego imparcial bajo estas condiciones es equivalente a un montón de Nim de cierto tamaño. A este tamaño lo llamas el valor de Sprague-Grundy (o simplemente el valor de Grundy o nim-valor) del estado del juego. Para analizar un juego complejo, calculas el valor SG para una posición dada, que escribimos como $g(u)$.
Para calcular estos valores, usas el concepto del Mínimo Excluido (mex). Al valor SG de un estado terminal (donde ya no hay movimientos posibles), lo definimos como 0. Para cualquier otro estado $u$, el valor SG lo definimos de forma recursiva como el entero no negativo más pequeño que no está entre los valores SG de los estados a los que puedes llegar en un solo movimiento. Intuitivamente, si puedes moverte a estados equivalentes a montones de Nim de tamaños ${0, 1, 3}$, el estado actual se comporta como un montón de Nim de tamaño 2 (el número más chico que falta).
Esta técnica es muy poderosa porque te permite descomponer un juego complicado en una suma de subjuegos más pequeños e independientes. Por el Teorema de Sprague-Grundy, el valor SG de un juego compuesto (una suma de juegos) es