Teoría de juegos: nim y el valor de Sprague-Grundy

Juegos combinatorios imparciales

Un juego combinatorio es una competencia de dos jugadores con las siguientes características: (1) los dos jugadores alternan turnos, (2) ambos tienen información perfecta del estado del juego (sin cartas ocultas ni dados), (3) el juego termina en un número finito de movimientos, y (4) no hay empates — el último jugador en moverse gana (regla de normalización).

Un juego se llama imparcial si, en cada posición, el conjunto de movimientos disponibles es el mismo para ambos jugadores. En un juego parcial (como el ajedrez), las piezas blancas y negras son distintas y los movimientos dependen de quién juega. En olimpiadas, casi todos los juegos son imparciales.

Los ejemplos más importantes de juegos imparciales son: Nim (quitar fichas de montones), el Juego de Euclides (restar múltiplos del número menor), el Nim modular (quitar a lo sumo $k$ fichas de un montón), y los juegos de divisores.

El objetivo central de la teoría es clasificar cada posición como ganadora o perdedora para el jugador que le toca mover, y encontrar la estrategia óptima. Esta clasificación da automáticamente una estrategia ganadora: si la posición actual es ganadora, el jugador actual puede mover a una posición perdedora para el rival; si es perdedora, cualquier movimiento lleva a una posición ganadora para el rival.

Nim: posiciones P y N

Nim es el juego combinatorio fundamental. Se tiene una colección de montones de fichas con tamaños $a_1, a_2, \ldots, a_k \geq 0$. En cada turno, el jugador elige un montón (no vacío) y retira cualquier cantidad positiva de fichas de ese montón. Quien quita la última ficha gana.

Una posición se llama P-posición (posición perdedora, del inglés "Previous player wins") si el jugador que acaba de mover gana; es decir, el jugador que enfrenta esta posición pierde con juego óptimo del rival. Una posición es N-posición (posición ganadora, "Next player wins") si el jugador que le toca mover puede ganar.

Las reglas de clasificación son: (i) la posición terminal (todos los montones vacíos) es P-posición (el jugador que debe mover no puede y pierde); (ii) una posición es N-posición si existe al menos un movimiento que lleva a una P-posición; (iii) una posición es P-posición si todos sus movimientos llevan a N-posiciones.

Teorema de Bouton (1901): La posición $(a_1, a_2, \ldots, a_k)$ en Nim es P-posición si y solo si $a_1 \oplus a_2 \oplus \cdots \oplus a_k = 0$, donde $\oplus$ denota la suma XOR bit a bit (también llamada "nim-suma").

Ejemplo: El estado $(3, 5, 6)$ tiene nim-suma $3 \oplus 5 \oplus 6 = 011 \oplus 101 \oplus 110 = 000$, así que es P-posición — el jugador que mueve primero pierde con juego óptimo del rival. El estado $(1, 2, 3)$ tiene $1 \oplus 2 \oplus 3 = 01 \oplus 10 \oplus 11 = 00$, también P-posición. El estado $(1, 2, 4)$ tiene $1 \oplus 2 \oplus 4 = 7 \neq 0$, N-posición.

Estrategia ganadora en Nim: Si la nim-suma $s = a_1 \oplus \cdots \oplus a_k \neq 0$, siempre existe un montón $a_i$ tal que $a_i \oplus s < a_i$ (un bit alto de $s$ está en $a_i$). Reducir ese montón a $a_i \oplus s$ hace que la nueva nim-suma sea $0$, convirtiendo la posición en P-posición para el rival.

El teorema de Sprague-Grundy

El teorema de Sprague-Grundy es la generalización más profunda de la teoría de juegos combinatorios. Establece que todo juego imparcial finito y acíclico es equivalente a un montón de Nim de cierto tamaño, llamado el valor de Grundy (o nimber) de la posición.

Formalmente, el valor de Grundy $\mathcal{G}(P)$ de una posición $P$ se define recursivamente mediante la función mex (mínimo excluido no negativo): $\mathcal{G}(P) = \text{mex}\{\mathcal{G}(Q) : Q \text{ es posición alcanzable desde } P\}$. El mex de un conjunto de enteros no negativos es el menor entero no negativo que no pertenece al conjunto.

La posición terminal tiene $\mathcal{G} = \text{mex}(\emptyset) = 0$. Una posición con $\mathcal{G}(P) = 0$ es P-posición (equivalente al montón vacío de Nim), y una posición con $\mathcal{G}(P) > 0$ es N-posición.

Teorema de suma de juegos: Si un juego es la suma de juegos independientes $G_1 + G_2 + \cdots + G_k$ (en cada turno el jugador elige un juego $G_i$ y hace un movimiento en él), el valor de Grundy de la suma es la nim-suma de los valores individuales: $\mathcal{G}(G_1 + \cdots + G_k) = \mathcal{G}(G_1) \oplus \cdots \oplus \mathcal{G}(G_k)$. La posición es P-posición si y solo si esta nim-suma es $0$.

Este teorema es enormemente poderoso: reduce el análisis de combinaciones arbitrarias de juegos imparciales a calcular los nimbers individuales y hacer XOR. La estrategia ganadora en la suma consiste en llevar la nim-suma a $0$ en cada turno.

Cálculo de valores de Grundy: ejemplos

Ejemplo 1 — Nim de un montón: Para un montón de tamaño $n$, los movimientos llevan a montones $0, 1, \ldots, n-1$. Luego $\mathcal{G}(n) = \text{mex}\{0, 1, \ldots, n-1\} = n$. El nimber de un montón de Nim de tamaño $n$ es $n$ (como era de esperarse).

**Ejemplo 2 — Nim con restricción ($\leq k$ fichas):** Si solo se pueden quitar entre 1 y $k$ fichas de un montón de $n$: $\mathcal{G}(0) = 0$; $\mathcal{G}(n) = \text{mex}\{\mathcal{G}(n-1), \mathcal{G}(n-2), \ldots, \mathcal{G}(n-k)\}$ para $n \geq 1$. Calculando: $\mathcal{G}(n) = n \bmod (k+1)$. Las P-posiciones son los múltiplos de $k+1$.

Ejemplo 3 — Juego de Euclides: Dados dos enteros positivos $a \geq b$, el jugador elige un múltiplo positivo de $b$ que no supere $a$ y lo resta de $a$. Si $a \geq 2b$, el jugador puede forzar cualquier residuo (en particular, puede pasar a $b, a-b, a-2b, \ldots$), luego $\mathcal{G}(a,b) > 0$. Si $a < 2b$ (solo se puede restar $b$ una vez), $\mathcal{G}(a,b) = \mathcal{G}(b, a-b)$ y se reduce al par más pequeño. El análisis completo revela que $(a,b)$ es P-posición $\iff$ $a/b < \phi$ (la razón áurea) tras aplicar las reducciones.

Ejemplo 4 — Juego en grafos: Se tiene un token en un vértice de un grafo dirigido acíclico; cada turno el jugador mueve el token por una arista. El jugador que no puede mover pierde. Entonces $\mathcal{G}(v) = \text{mex}\{\mathcal{G}(w) : (v,w) \text{ es arista}\}$. Este es el modelo más general de juego imparcial: todo juego imparcial finito se puede representar así.

Cálculo práctico: Para calcular $\mathcal{G}$ en olimpiadas, conviene calcular los primeros valores a mano y buscar un patrón periódico (la mayoría de los juegos de olimpiada tienen nimbers periódicos). Luego se verifica la periodicidad por inducción.