Teorema de Sprague-Grundy

En la teoría de juegos combinatorios , el teorema de Sprague - Grundy establece que todo juego imparcial bajo la convención de juego normal es equivalente a un juego de un montón de nim , o a una generalización infinita de nim. Por lo tanto, puede representarse como un número natural , el tamaño del montón en su juego equivalente de nim, como un número ordinal en la generalización infinita, o alternativamente como un nimber , el valor de ese juego de un montón en un sistema algebraico cuya operación de suma combina múltiples montones para formar un único montón equivalente en nim.

El valor Grundy o valor nim de cualquier juego imparcial es el único nimber al que equivale dicho juego. En el caso de un juego cuyas posiciones están indexadas por números naturales (como el propio nim, que está indexado por el tamaño de sus montones), la secuencia de nimbers para posiciones sucesivas del juego se denomina secuencia nim del juego.

El teorema de Sprague-Grundy y su demostración resumen los principales resultados de una teoría descubierta independientemente por RP Sprague (1936) ^{[ 1 ]} y PM Grundy (1939). ^{[ 2 ]}

A efectos del teorema de Sprague - Grundy, un juego es un juego secuencial de dos jugadores con información perfecta que satisface la condición de finalización (todos los juegos llegan a su fin: no existen infinitas líneas de juego) y la condición de juego normal (un jugador que no puede mover pierde).

En cualquier momento dado del juego, la posición de un jugador es el conjunto de movimientos que se le permite realizar. Como ejemplo, podemos definir el juego cero como el juego de dos jugadores donde ninguno de los jugadores tiene movimientos legales. Haciendo referencia a los dos jugadores como${\displaystyle A}$(para Alicia) y${\displaystyle B}$(para Bob), denotaríamos sus posiciones como${\displaystyle (A,B)=(\{\},\{\})}$, puesto que el conjunto de movimientos que cada jugador puede realizar está vacío.

Un juego imparcial es aquel en el que, en cualquier momento dado, cada jugador tiene exactamente el mismo conjunto de movimientos. El juego normal de nim es un ejemplo de juego imparcial. En nim, hay uno o más montones de objetos, y dos jugadores (llamémoslos Alice y Bob) se turnan para elegir un montón y retirar uno o más objetos del mismo. Gana el jugador que retira el último objeto del último montón. El juego es imparcial porque, para cualquier configuración dada de tamaños de los montones, los movimientos que Alice puede hacer en su turno son exactamente los mismos que Bob podría hacer si fuera su turno. En cambio, un juego como las damas no es imparcial porque, suponiendo que Alice jugara con rojo y Bob con negro, para cualquier disposición dada de las piezas en el tablero, si fuera el turno de Alice, solo podría mover las piezas rojas, y si fuera el turno de Bob, solo podría mover las piezas negras.

Nótese que cualquier configuración de un juego imparcial puede escribirse como una sola posición, porque los movimientos serán los mismos independientemente de a quién le toque. Por ejemplo, la posición del juego cero puede escribirse simplemente${\displaystyle \{\}}$Porque si es el turno de Alice, no tiene movimientos que realizar, y si es el turno de Bob, tampoco tiene movimientos que realizar. Un movimiento puede asociarse con la posición en la que deja al siguiente jugador.

De este modo, las posiciones pueden definirse de forma recursiva. Por ejemplo, consideremos la siguiente partida de Nim jugada por Alice y Bob.

Tamaños de montones Movimientos abecedario   1 2 2 Alicia toma 1 de A 0 2 2 Bob toma 1 de B 0 1 2 Alice toma 1 de C 0 1 1 Bob toma 1 de B 0 0 1 Alice toma 1 de C 0 0 0 Bob no tiene movimientos, por lo tanto, Alice gana 

Tamaños de montones Movimientos   A' B' C' 1 1 1 Alice toma 1 de A' 0 1 1 Bob toma uno de B' 0 0 1 Alice toma uno de C' 0 0 0 Bob no tiene movimientos, por lo tanto, Alice gana. 

Tamaños de montones Movimientos ABC A' B' C'   1 2 2 1 1 1 Alice toma 1 de A 0 2 2 1 1 1 Bob toma 1 de A' 0 2 2 0 1 1 Alice toma 1 de B' 0 2 2 0 0 1 Bob toma 1 de C' 0 2 2 0 0 0 Alice toma 2 de B 0 0 2 0 0 0 Bob toma 2 de C 0 0 0 0 0 0 Alice no tiene movimientos, por lo tanto Bob gana. 

Como paso intermedio para demostrar el teorema principal, mostramos que para cada posición${\displaystyle G}$y cada${\displaystyle {\mathcal {P}}}$-posición${\displaystyle A}$, la equivalencia${\displaystyle G\approx A+G}$se cumple. Según la definición de equivalencia anterior, esto equivale a demostrar que${\displaystyle G+H}$y${\displaystyle A+G+H}$compartir una clase de resultados para todos${\displaystyle H}$.

Supongamos que${\displaystyle G+H}$es un${\displaystyle {\mathcal {P}}}$-posición. Entonces el jugador anterior tiene una estrategia ganadora para${\displaystyle A+G+H}$: responder a los movimientos en${\displaystyle A}$según su estrategia ganadora para${\displaystyle A}$(que existe en virtud de${\displaystyle A}$ser un${\displaystyle {\mathcal {P}}}$-posición), y responder a los movimientos en${\displaystyle G+H}$según su estrategia ganadora para${\displaystyle G+H}$(que existe por la razón análoga). Así pues${\displaystyle A+G+H}$También debe ser un${\displaystyle {\mathcal {P}}}$-posición.

Por otro lado, si${\displaystyle G+H}$es un${\displaystyle {\mathcal {N}}}$-posición, entonces${\displaystyle A+G+H}$también es un${\displaystyle {\mathcal {N}}}$-posición, porque el siguiente jugador tiene una estrategia ganadora: elige una${\displaystyle {\mathcal {P}}}$-posición de entre los${\displaystyle G+H}$opciones, y concluimos del párrafo anterior que agregar${\displaystyle A}$a esa posición todavía es una${\displaystyle {\mathcal {P}}}$-posición. Por lo tanto, en este caso,${\displaystyle A+G+H}$debe ser un${\displaystyle {\mathcal {N}}}$-posición, igual que${\displaystyle G+H}$.

Como estos son los únicos dos casos, el lema se cumple.

Como paso adicional, mostramos que${\displaystyle G\approx G'}$si y solo si${\displaystyle G+G'}$es un${\displaystyle {\mathcal {P}}}$-posición.

En la dirección hacia adelante, supongamos que${\displaystyle G\approx G'}$. Aplicando la definición de equivalencia con${\displaystyle H=G}$, encontramos que${\displaystyle G'+G}$(que es igual a${\displaystyle G+G'}$por conmutatividad de la suma) está en la misma clase de resultados que${\displaystyle G+G}$. Pero${\displaystyle G+G}$debe ser un${\displaystyle {\mathcal {P}}}$-posición: por cada movimiento realizado en una copia de${\displaystyle G}$, el jugador anterior puede responder con el mismo movimiento en la otra copia, y así siempre realiza el último movimiento.

En sentido inverso, ya que${\displaystyle A=G+G'}$es un${\displaystyle {\mathcal {P}}}$-posición por hipótesis, se deduce del primer lema,${\displaystyle G\approx G+A}$, eso${\displaystyle G\approx G+(G+G')}$. De manera similar, dado que${\displaystyle B=G+G}$también es un${\displaystyle {\mathcal {P}}}$-posición, se deduce del primer lema en la forma ${\displaystyle G'\approx G'+B}$eso${\displaystyle G'\approx G'+(G+G)}$. Por asociatividad y conmutatividad, los lados derechos de estos resultados son iguales. Además,${\displaystyle \approx }$es una relación de equivalencia porque la igualdad es una relación de equivalencia en clases de resultados. A través de la transitividad de${\displaystyle \approx }$, podemos concluir que${\displaystyle G\approx G'}$.

Demostramos que todas las posiciones son equivalentes a un nimber mediante inducción estructural . El resultado más específico, que establece que la posición inicial del juego dado debe ser equivalente a un nimber, demuestra que el juego en sí mismo es equivalente a un nimber.

Considere una posición${\displaystyle G=\{G_{1},G_{2},\ldots ,G_{k}\}}$Según la hipótesis de inducción , todas las opciones son equivalentes a números, por ejemplo${\displaystyle G_{i}\approx *n_{i}}$. Así que dejemos${\displaystyle G'=\{*n_{1},*n_{2},\ldots ,*n_{k}\}}$Demostraremos que${\displaystyle G\approx *m}$, dónde${\displaystyle m}$es el mex (exclusión mínima) de los números${\displaystyle n_{1},n_{2},\ldots ,n_{k}}$, es decir, el entero no negativo más pequeño que no sea igual a algún${\displaystyle n_{i}}$.

Lo primero que debemos tener en cuenta es que${\displaystyle G\approx G'}$, por medio del segundo lema. Si${\displaystyle k}$es cero, la afirmación es trivialmente cierta. De lo contrario, considere${\displaystyle G+G'}$. Si el siguiente jugador hace un movimiento a${\displaystyle G_{i}}$en${\displaystyle G}$, entonces el jugador anterior puede moverse a${\displaystyle *n_{i}}$en${\displaystyle G'}$y, a la inversa, si el siguiente jugador hace un movimiento en${\displaystyle G'}$. Después de esto, el puesto es un${\displaystyle {\mathcal {P}}}$-posición por la implicación directa del lema. Por lo tanto,${\displaystyle G+G'}$es un${\displaystyle {\mathcal {P}}}$-posición, y, citando la implicación inversa del lema,${\displaystyle G\approx G'}$.

Ahora vamos a demostrar que${\displaystyle G'+*m}$es un${\displaystyle {\mathcal {P}}}$-posición, lo que, utilizando nuevamente el segundo lema, significa que${\displaystyle G'\approx *m}$Lo hacemos proporcionando una estrategia explícita para el jugador anterior.

Supongamos que${\displaystyle G'}$y${\displaystyle *m}$están vacíos. Entonces${\displaystyle G'+*m}$es el conjunto nulo, claramente un${\displaystyle {\mathcal {P}}}$-posición.

O consideremos el caso en que el siguiente jugador se mueve en el componente${\displaystyle *m}$a la opción${\displaystyle *m'}$dónde${\displaystyle m'<m}$. Porque${\displaystyle m}$era el número mínimo excluido, el jugador anterior puede moverse en${\displaystyle G'}$a${\displaystyle *m'}$. Y, como se mostró anteriormente, cualquier posición más ella misma es una${\displaystyle {\mathcal {P}}}$-posición.

Finalmente, supongamos que el siguiente jugador se mueve en el componente${\displaystyle G'}$a la opción${\displaystyle *n_{i}}$. Si${\displaystyle n_{i}<m}$entonces el jugador anterior se mueve${\displaystyle *m}$a${\displaystyle *n_{i}}$; de lo contrario, si${\displaystyle n_{i}>m}$, el jugador anterior se mueve en${\displaystyle *n_{i}}$a${\displaystyle *m}$; en cualquier caso el resultado es una posición más ella misma. (No es posible que${\displaystyle n_{i}=m}$porque${\displaystyle m}$se definió como diferente de todos los${\displaystyle n_{i}}$.)

En resumen, tenemos${\displaystyle G\approx G'}$y${\displaystyle G'\approx *m}$Por transitividad, concluimos que${\displaystyle G\approx *m}$, según se desee.

Si${\displaystyle G}$es una posición de un juego imparcial, el entero único${\displaystyle m}$de tal manera que${\displaystyle G\approx *m}$Se denomina valor de Grundy o número de Grundy, y la función que asigna este valor a cada una de dichas posiciones se denomina función de Sprague-Grundy. R.L. Sprague y P.M. Grundy, de forma independiente, dieron una definición explícita de esta función, sin basarse en ningún concepto de equivalencia con las posiciones de nim, y demostraron que tenía las siguientes propiedades:

• El valor Grundy de una sola pila de nim de tamaño${\displaystyle m}$(es decir, de la posición${\displaystyle *m}$) es${\displaystyle m}$;
• Una posición es una pérdida para el siguiente jugador que se mueva (es decir,${\displaystyle {\mathcal {P}}}$-posición) si y solo si su valor de Grundy es cero; y
• El valor Grundy de la suma de un conjunto finito de posiciones es simplemente la suma nim de los valores Grundy de sus sumandos.

De estos resultados se deduce directamente que si una posición${\displaystyle G}$tiene un valor Grundy de${\displaystyle m}$, entonces${\displaystyle G+H}$tiene el mismo valor Grundy que ${\displaystyle *m+H}$y, por lo tanto, pertenece a la misma clase de resultados, para cualquier posición.${\displaystyle H}$Así, aunque Sprague y Grundy nunca enunciaron explícitamente el teorema descrito en este artículo, este se deriva directamente de sus resultados y se les atribuye. ^{[ 3 ] [ 4 ]} Estos resultados se han desarrollado posteriormente en el campo de la teoría de juegos combinatorios , en particular por Richard Guy , Elwyn Berlekamp , ​​John Horton Conway y otros, donde ahora se resumen en el teorema de Sprague-Grundy y su demostración en la forma descrita aquí. El campo se presenta en los libros Winning Ways for your Mathematical Plays y On Numbers and Games .

• Teoría de género
• Coeficiente de indistinguibilidad

• El juego de Grundy en el arte de cortar el nudo
• Relato introductorio de fácil lectura del Departamento de Matemáticas de la UCLA
• El juego de Nim en sputsoft.com
• Milvang-Jensen, Brit CA (2000), Juegos combinatorios, teoría y aplicaciones (PDF) , CiteSeerX 10.1.1.89.805