Cualquier juego imparcial equivale a un montón de Nim.
El Teorema de Sprague-Grundy es un resultado fundamental en la teoría de juegos combinatorios que generaliza la estrategia del juego de Nim para todos los juegos imparciales bajo la convención de juego normal. Un juego imparcial es uno donde los movimientos disponibles desde cualquier posición dependen solo de la posición misma, no de a quién le toca jugar (a diferencia del Ajedrez), y el último jugador en mover gana (juego normal). El teorema te dice que cada juego imparcial bajo la convención de juego normal es equivalente a una pila de Nim de un tamaño determinado. A este tamaño le decimos el valor de Grundy (o valor-nim) del estado del juego.
Este teorema es increíblemente poderoso porque te permite descomponer juegos complejos en componentes más simples. Muchos juegos los puedes ver como la suma de varios sub-juegos independientes que se juegan al mismo tiempo. En lugar de analizar el espacio de estados gigante del juego combinado, el teorema de Sprague-Grundy te permite calcular el valor de Grundy de cada sub-juego por separado. El valor de Grundy del juego total es simplemente la suma XOR (suma-Nim) de los valores de Grundy de sus componentes.
La idea central se basa en la regla del MEX (Minimum Excluded value o valor mínimo excluido). El valor de Grundy de un estado terminal (una posición perdedora) es 0. Para cualquier otro estado, el valor de Grundy es el entero no negativo más pequeño (MEX) que estrictamente no está entre los valores de Grundy de los estados a los que puedes llegar en un solo movimiento. Esta definición recursiva asegura que un estado con valor de Grundy $k$ se comporte matemáticamente igual a una pila de Nim de tamaño $k$: desde un estado con valor $k$, puedes moverte a un estado con cualquier valor $j < k$, pero no puedes moverte a un estado con valor $k$.
1. La Función MEX Para un conjunto de enteros no negativos $S$, definimos el valor mínimo excluido como: $$ \text{mex}(S) = \min { n \in \mathbb{Z}_{\ge 0} \mid n \notin S } $$
2. La Función de Grundy (función g) Para un estado de juego $G$, toma ${G_1, G_2, \dots, G_k}$ como el conjunto de estados a los que puedes llegar desde $G$ en un solo movimiento. Definimos el valor de Grundy $g(G)$ de forma recursiva: $$ g(G) = \text{mex}({ g(G_1), g(G_2), \dots, g(G_k) }) $$ Caso base: Si $G$ es un estado terminal (no hay movimientos disponibles), $g(G) = \text{mex}(\emptyset) = 0$.
3. El Teorema de Sprague-Grundy (Suma de Juegos) Si un juego $G$ se compone de varios sub-juegos independientes $G_1, G_2, \dots, G_n$ (donde un movimiento consiste en elegir un sub-juego $G_i$ y hacer una jugada legal en él), el valor de Grundy del juego combinado es la suma-Nim (XOR bit a bit, denotado por $\oplus$) de los componentes: $$ g(G_1 + G_2 + \dots + G_n) = g(G_1) \oplus g(G_2) \oplus \dots \oplus g(G_n) $$
4. Condición de Victoria Un estado $G$ es una posición perdedora (posición P, gana el jugador anterior) si y solo si su valor de Grundy es cero. Es una posición ganadora (posición N, gana el siguiente jugador) si el valor es distinto de cero. $$ \text{Resultado}(G) = \begin{cases} \text{Perdedora (posición P)} & \text{si } g(G) = 0 \ \text{Ganadora (posición N)} & \text{si } g(G) > 0 \end{cases} $$
Teorema: Toma $A$ y $B$ como dos juegos imparciales. El valor de Grundy del juego suma $A+B$ es la suma-Nim de sus valores de Grundy individuales: $g(A+B) = g(A) \oplus g(B)$.
Demostración: Toma $a = g(A)$, $b = g(B)$ y $c = a \oplus b$. Para demostrar que $g(A+B) = c$, tienes que mostrar que $c = \text{mex}(S)$, donde $S$ es el conjunto de valores de Grundy de todos los estados a los que puedes llegar desde $A+B$ en un solo movimiento. Por la definición de MEX, esto requiere que demuestres dos propiedades:
Paso 1: Existencia de movimientos a estados con valor $d < c$ Toma $d$ como un entero tal que $0 \le d < c$. Toma $k = d \oplus c$. Como $d < c$, el bit más significativo donde $d$ y $c$ difieren debe ser 0 en $d$ y 1 en $c$. Como $c = a \oplus b$, este bit en particular debe ser 1 ya sea en $a$ o en $b$ (o en ambos, pero específicamente un número impar de veces). Sin perder la generalidad, supón que este bit es 1 en $a$. Considera el valor $a' = a \oplus k$. Como el bit más significativo de $k$ (que es el mismo bit donde $d$ y $c$ difieren) es 1 en $a$, la operación XOR $a \oplus k$ cambiará ese bit de 1 a 0 en $a$, lo que asegura que $a' < a$.
Como $g(A) = a$ y $a' < a$, por la definición de la función de Grundy (la propiedad del MEX), debe existir un movimiento del estado $A$ a un estado $A'$ tal que $g(A')$ sea $a'$. Si haces este movimiento en el juego suma $A+B$, pasas al estado $A' + B$. El valor de Grundy para este nuevo estado es: $$ g(A') \oplus g(B) = a' \oplus b = (a \oplus k) \oplus b = (a \oplus b) \oplus k = c \oplus (d \oplus c) = d $$ Por lo tanto, para cualquier $d < c$, hay un estado alcanzable con valor $d$.
Paso 2: No existencia de un movimiento a un estado con valor $c$ Un movimiento en el juego $A+B$ consiste en moverte en exactamente un componente. Caso 1: Te mueves en $A$ hacia $A'$. El nuevo estado es $A' + B$. El nuevo valor es $g(A') \oplus b$. Como $A \to A'$ es un movimiento válido, $g(A') \neq g(A)$ (por la definición de MEX, $g(A)$ está excluido del conjunto de valores alcanzables). Toma $a' = g(A')$. Si el nuevo valor fuera $c$, tendrías $a' \oplus b = c = a \oplus b$. Por la ley de cancelación de XOR, esto implica que $a' = a$, lo cual es una contradicción. Caso 2: Te mueves en $B$ hacia $B'$. De manera similar, esto lleva a $a \oplus b' = a \oplus b$, lo que implica que $b' = b$, lo cual es imposible.
Conclusión Como puedes alcanzar cualquier valor estrictamente menor que $a \oplus b$, pero no puedes alcanzar $a \oplus b$ mismo, el MEX del conjunto de valores alcanzables es exactamente $a \oplus b$. $$ g(A+B) = g(A) \oplus g(B) $$ Por inducción, esto lo puedes extender a cualquier suma finita de juegos. $\square$