Teorema de Sprague-Grundy. Nim

Introducción

Este teorema describe los llamados juegos de dos jugadores imparciales (impartial), es decir, aquellos en los que los movimientos disponibles y el ganar/perder dependen solo del estado del juego. En otras palabras, la única diferencia entre los dos jugadores es que uno de ellos mueve primero.

Además, asumimos que el juego tiene información perfecta, es decir, no hay información oculta a los jugadores (conocen las reglas y los movimientos posibles).

Se asume que el juego es finito, es decir, después de un cierto número de movimientos, uno de los jugadores terminará en una posición perdedora, desde la cual no puede moverse a otra posición. Por el otro lado, el jugador que dejó esta posición al oponente gana. Como es comprensible, no hay empates en este juego.

Tales juegos se pueden describir por completo mediante un grafo dirigido acíclico: los vértices son estados del juego y las aristas son transiciones (movimientos). Un vértice sin aristas salientes es un vértice perdedor (un jugador que debe hacer un movimiento desde este vértice pierde).

Como no hay empates, podemos clasificar todos los estados del juego como ganadores o perdedores. Los estados ganadores son aquellos desde los que hay un movimiento que causa la derrota inevitable del otro jugador, incluso con su mejor respuesta. Los estados perdedores son aquellos desde los que todos los movimientos llevan a estados ganadores para el otro jugador. Resumiendo, un estado es ganador si hay al menos una transición a un estado perdedor y es perdedor si no hay al menos una transición a un estado perdedor.

Nuestra tarea es clasificar los estados de un juego dado.

La teoría de tales juegos fue desarrollada de forma independiente por Roland Sprague en 1935 y Patrick Michael Grundy en 1939.

Nim

Este juego obedece las restricciones descritas arriba. Más aún, cualquier juego imparcial de dos jugadores con información perfecta se puede reducir al juego de Nim. Estudiar este juego nos permitirá resolver todos los demás juegos similares, pero más sobre eso después.

Históricamente este juego fue popular en la antigüedad. Su origen es probablemente en China, o al menos el juego Jianshizi es muy similar a él. En Europa las referencias más tempranas son del siglo XVI. El nombre lo dio Charles Bouton, que en 1901 publicó un análisis completo de este juego.

Descripción del juego

Hay varios montones, cada uno con varias piedras. En un movimiento un jugador puede tomar cualquier número positivo de piedras de un solo montón y tirarlas. Un jugador pierde si no puede hacer un movimiento, lo que ocurre cuando todos los montones están vacíos.

El estado del juego se describe de forma unívoca por un multiconjunto de enteros positivos. Un movimiento consiste en disminuir estrictamente un entero elegido (si se vuelve cero, se elimina del conjunto).

La solución

La solución de Charles L. Bouton se ve así:

Teorema. El jugador actual tiene una estrategia ganadora si y solo si la xor-suma de los tamaños de los montones es distinta de cero. La xor-suma de una secuencia $a$ es $a_1 \oplus a_2 \oplus \ldots \oplus a_n$ , donde $\oplus$ es el OR exclusivo bit a bit.

Demostración. La clave de la demostración es la presencia de una estrategia simétrica para el oponente. Mostramos que una vez en una posición con la xor-suma igual a cero, el jugador no podrá hacerla distinta de cero a largo plazo: si transita a una posición con xor-suma distinta de cero, el oponente siempre tendrá un movimiento que devuelve la xor-suma a cero.

Demostraremos el teorema por inducción matemática.

Para un Nim vacío (donde todos los montones están vacíos, es decir, el multiconjunto está vacío) la xor-suma es cero y el teorema es verdadero.

Ahora supongamos que estamos en un estado no vacío. Usando la hipótesis de inducción (y la aciclicidad del juego) asumimos que el teorema está demostrado para todos los estados alcanzables desde el actual.

Entonces la demostración se divide en dos partes: si para la posición actual la xor-suma $s = 0$ , tenemos que probar que este estado es perdedor, es decir, que todos los estados alcanzables tienen xor-suma $t \neq 0$ . Si $s \neq 0$ , tenemos que probar que hay un movimiento que lleva a un estado con $t = 0$ .

Sea $s = 0$ y consideremos cualquier movimiento. Este movimiento reduce el tamaño de un montón $x$ a un tamaño $y$ . Usando propiedades elementales de $\oplus$ , tenemos

$t = s \oplus x \oplus y = 0 \oplus x \oplus y = x \oplus y$

Como $y < x$ , $y \oplus x$ no puede ser cero, así que $t \neq 0$ . Eso significa que cualquier estado alcanzable es ganador (por la hipótesis de inducción), así que estamos en una posición perdedora.
Sea $s \neq 0$ . Consideremos la representación binaria del número $s$ . Sea $d$ el índice de su bit no nulo líder (de mayor valor). Nuestro movimiento será sobre un montón cuyo bit número $d$ del tamaño está activado (debe existir, en caso contrario el bit no estaría activado en $s$ ). Reduciremos su tamaño $x$ a $y = x \oplus s$ . Todos los bits en posiciones mayores que $d$ en $x$ e $y$ coinciden y el bit $d$ está activado en $x$ pero no en $y$ . Por lo tanto, $y < x$ , que es todo lo que necesitamos para que un movimiento sea legal. Ahora tenemos:

$t = s \oplus x \oplus y = s \oplus x \oplus (s \oplus x) = 0$

Esto significa que hallamos un estado perdedor alcanzable (por la hipótesis de inducción) y el estado actual es ganador.

Corolario. Cualquier estado de Nim se puede reemplazar por un estado equivalente siempre que la xor-suma no cambie. Más aún, al analizar un Nim con varios montones, podemos reemplazarlo por un solo montón de tamaño $s$ .

Juego misère

En un juego misère, el objetivo del juego es el opuesto, así que el jugador que quita el último palito pierde el juego. Resulta que el Nim misère se puede jugar de forma óptima casi como un Nim estándar. La idea es primero jugar el juego misère como el juego estándar, pero cambiar la estrategia al final del juego. La nueva estrategia se introduce en una situación en la que cada montón contendría a lo sumo un palito después del siguiente movimiento. En el juego estándar, deberíamos elegir un movimiento después del cual hay un número par de montones con un palito. Sin embargo, en el juego misère, elegimos un movimiento de modo que haya un número impar de montones con un palito. Esta estrategia funciona porque un estado donde cambia la estrategia siempre aparece en el juego, y este estado es un estado ganador, porque contiene exactamente un montón que tiene más de un palito, así que la nim-suma no es 0.

La equivalencia de los juegos imparciales y Nim (teorema de Sprague-Grundy)

Ahora aprenderemos a hallar, para cualquier estado de cualquier juego imparcial, un estado correspondiente de Nim.

Lema sobre Nim con aumentos

Consideramos la siguiente modificación de Nim: también permitimos añadir piedras a un montón elegido. Las reglas exactas sobre cómo y cuándo se permite aumentar no nos interesan, sin embargo las reglas deben mantener nuestro juego acíclico. En secciones posteriores se consideran juegos de ejemplo.

Lema. Añadir aumentos a Nim no cambia cómo se determinan los estados ganadores y perdedores. En otras palabras, los aumentos son inútiles, y no tenemos que usarlos en una estrategia ganadora.

Demostración. Supongamos que un jugador añadió piedras a un montón. Entonces su oponente puede simplemente deshacer su movimiento: disminuir el número de vuelta al valor anterior. Como el juego es acíclico, tarde o temprano el jugador actual no podrá usar un movimiento de aumento y tendrá que hacer el movimiento habitual de Nim.

Teorema de Sprague-Grundy

Consideremos un estado $v$ de un juego imparcial de dos jugadores y sea $v_i$ los estados alcanzables desde él (donde $i \in { 1, 2, \dots, k } , k \ge 0$ ). A este estado le podemos asignar un juego de Nim completamente equivalente con un montón de tamaño $x$ . El número $x$ se llama valor de Grundy (Grundy value) o nim-valor del estado $v$ .

Más aún, este número se puede hallar de la siguiente forma recursiva:

$x = \text{mex}\ { x_1, \ldots, x_k },$

donde $x_i$ es el valor de Grundy del estado $v_i$ y la función $\text{mex}$ (minimum excludant) es el menor entero no negativo que no se encuentra en el conjunto dado.

Viendo el juego como un grafo, podemos calcular gradualmente los valores de Grundy empezando por los vértices sin aristas salientes. Que el valor de Grundy sea igual a cero significa que un estado es perdedor.

Demostración. Usaremos una demostración por inducción.

Para vértices sin un movimiento, el valor $x$ es el $\text{mex}$ de un conjunto vacío, que es cero. Eso es correcto, porque un Nim vacío es perdedor.

Ahora consideremos cualquier otro vértice $v$ . Por inducción, asumimos que los valores $x_i$ correspondientes a sus vértices alcanzables ya están calculados.

Sea $p = \text{mex}\ { x_1, \ldots, x_k }$ . Entonces sabemos que para cualquier entero $i \in [0, p)$ existe un vértice alcanzable con valor de Grundy $i$ . Esto significa que $v$ es equivalente a un estado del juego de Nim con aumentos con un montón de tamaño $p$ . En tal juego tenemos transiciones a montones de todo tamaño menor que $p$ y posiblemente transiciones a montones con tamaños mayores que $p$ . Por lo tanto, $p$ es efectivamente el valor de Grundy deseado para el estado considerado actualmente.

Aplicación del teorema

Por último, describimos un algoritmo para determinar el resultado de victoria/derrota de un juego, aplicable a cualquier juego imparcial de dos jugadores.

Para calcular el valor de Grundy de un estado dado hay que:

Obtener todas las transiciones posibles desde este estado
Cada transición puede llevar a una suma de juegos independientes (un juego en el caso degenerado). Calcular el valor de Grundy de cada juego independiente y hacerles xor-suma. Por supuesto el xor no hace nada si hay un solo juego.
Después de calcular los valores de Grundy de cada transición hallamos el valor del estado como el $\text{mex}$ de estos números.
Si el valor es cero, entonces el estado actual es perdedor; en caso contrario es ganador.

En comparación con la sección anterior, tenemos en cuenta el hecho de que puede haber transiciones a juegos combinados. Los consideramos un Nim con tamaños de montón iguales a los valores de Grundy de los juegos independientes. Podemos hacerles xor-suma igual que en el Nim habitual según el teorema de Bouton.

Patrones en los valores de Grundy

Muy a menudo, al resolver tareas concretas usando valores de Grundy, puede ser beneficioso estudiar la tabla de los valores en busca de patrones.

En muchos juegos, que pueden parecer bastante difíciles para el análisis teórico, los valores de Grundy resultan ser periódicos o de una forma fácilmente comprensible. En la inmensa mayoría de los casos el patrón observado resulta ser verdadero y se puede demostrar por inducción si se desea.

Sin embargo, los valores de Grundy están lejos de contener siempre tales regularidades e incluso para algunos juegos muy simples, el problema de preguntar si esas regularidades existen sigue abierto (p. ej. el “juego de Grundy”).

Juegos de ejemplo

Crosses-crosses

Las reglas. Consideremos una tira cuadriculada de tamaño $1 \times n$ . En un movimiento, el jugador debe poner una cruz, pero está prohibido poner dos cruces una al lado de la otra (en celdas adyacentes). Como de costumbre, el jugador sin un movimiento válido pierde.

La solución. Cuando un jugador pone una cruz en cualquier celda, podemos pensar que la tira se parte en dos partes independientes: a la izquierda de la cruz y a la derecha de ella. En este caso, la celda con una cruz, así como sus vecinas izquierda y derecha, se destruyen: no se puede poner nada más en ellas. Por lo tanto, si numeramos las celdas de $1$ a $n$ , poner la cruz en la posición $1 < i < n$ parte la tira en dos tiras de longitud $i-2$ y $n-i-1$ , es decir, pasamos a la suma de los juegos $i-2$ y $n-i-1$ . Para el caso borde de que la cruz se marque en la posición $1$ o $n$ , pasamos al juego $n-2$ .

Así, el valor de Grundy $g(n)$ tiene la forma:

$g(n) = \text{mex} \Bigl( { g(n-2) } \cup {g(i-2) \oplus g(n-i-1) \mid 2 \leq i \leq n-1} \Bigr) .$

Así que tenemos una solución $O(n^2)$ .

De hecho, $g(n)$ tiene un período de longitud 34 a partir de $n=52$ .