Teorema de Sprague-Grundy

Toda posición de juego imparcial es equivalente a una posición en el juego de nim

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, se puede representar 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 adición combina múltiples montones para formar un único montón equivalente en nim.

El valor de Grundy o valor nim de cualquier juego imparcial es el nimber único al que el juego es equivalente. En el caso de un juego cuyas posiciones están indexadas por los números naturales (como el propio nim, que está indexado por los tamaños de su montón), la secuencia de nimbers para las 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]

Definiciones

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

En cualquier momento del juego, la posición de un jugador es el conjunto de movimientos que se le permiten realizar. Como ejemplo, podemos definir el juego cero como el juego de dos jugadores en el que ninguno de ellos tiene movimientos legales. Si nos referimos a los dos jugadores como (para Alice) y (para Bob), denotaríamos sus posiciones como , ya que el conjunto de movimientos que cada jugador puede realizar está vacío. ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle (A,B)=(\{\},\{\})}$

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

Nótese que cualquier configuración de un juego imparcial puede, por lo tanto, escribirse como una posición única, porque los movimientos serán los mismos sin importar de quién sea el turno. Por ejemplo, la posición del juego cero puede escribirse simplemente como , porque si es el turno de Alice, no tiene movimientos que hacer, y si es el turno de Bob, él tampoco tiene movimientos que hacer. Un movimiento puede asociarse con la posición en la que deja al siguiente jugador. ${\displaystyle \{\}}$

De esta manera, es posible definir posiciones de forma recursiva. Por ejemplo, considere el siguiente juego de Nim que juegan Alice y Bob.

Ejemplo de juego Nim

Tamaños de montones Movimientos abecedario   1 2 2 Alice toma 1 de A 0 2 2 Bob le quita 1 a B 0 1 2 Alice le quita 1 a C 0 1 1 Bob le quita 1 a B 0 0 1 Alice le quita 1 a C 0 0 0 Bob no tiene movimientos, por lo que Alice gana

• En el paso 6 del juego (cuando todos los montones están vacíos) la posición es , porque Bob no tiene movimientos válidos que hacer. Llamamos a esta posición . ${\displaystyle \{\}}$ ${\displaystyle *0}$
• En el paso 5, Alice tenía exactamente una opción: eliminar un objeto del montón C, lo que dejaba a Bob sin movimientos. Como su movimiento deja a Bob en la posición , su posición se escribe . Llamamos a esta posición . ${\displaystyle *0}$ ${\displaystyle \{*0\}}$ ${\displaystyle *1}$
• En el paso 4, Bob tenía dos opciones: quitar uno de B o quitar uno de C. Sin embargo, tenga en cuenta que en realidad no importaba de qué montón Bob quitara el objeto: de cualquier manera, Alice se quedaría con exactamente un objeto en exactamente un montón. Por lo tanto, utilizando nuestra definición recursiva, Bob realmente solo tiene un movimiento: . Por lo tanto, la posición de Bob es . ${\displaystyle *1}$ ${\displaystyle \{*1\}}$
• En el paso 3, Alice tenía 3 opciones: quitar dos de C, quitar uno de C o quitar uno de B. Quitar dos de C deja a Bob en la posición . Quitar uno de C deja a Bob con dos pilas, cada una de tamaño uno, es decir, la posición , como se describe en el paso 4. Sin embargo, quitar 1 de B dejaría a Bob con dos objetos en una sola pila. Sus movimientos serían entonces y , por lo que su movimiento daría como resultado la posición . Llamamos a esta posición . La posición de Alice es entonces el conjunto de todos sus movimientos: . ${\displaystyle *1}$ ${\displaystyle \{*1\}}$ ${\displaystyle *0}$ ${\displaystyle *1}$ ${\displaystyle \{*0,*1\}}$ ${\displaystyle *2}$ ${\displaystyle {\big \{}*1,\{*1\},*2{\big \}}}$
• Siguiendo la misma lógica recursiva, en el paso 2, la posición de Bob es $${\displaystyle {\big \{}\{*1,\{*1\},*2\},*2{\big \}}.}$$
• Finalmente, en el paso 1, la posición de Alice es $${\displaystyle {\Big \{}{\big \{}*1,\{*1\},*2{\big \}},{\big \{}*2,\{*1,\{*1\},*2\}{\big \}},{\big \{}\{*1\},\{\{*1\}\},\{*1,\{*1\},*2\}{\big \}}{\Big \}}.}$$

Nimberos

Los nombres especiales , , y a los que se hace referencia en nuestro juego de ejemplo se denominan nimbers . En general, el nimber corresponde a la posición en un juego de nim donde hay exactamente objetos en exactamente un montón. Formalmente, los nimbers se definen de manera inductiva de la siguiente manera: es , , y para todos los , . ${\displaystyle *0}$ ${\displaystyle *1}$ ${\displaystyle *2}$ ${\displaystyle *n}$ ${\displaystyle n}$ ${\displaystyle *0}$ ${\displaystyle \{\}}$ ${\displaystyle *1=\{*0\}}$ ${\displaystyle *2=\{*0,*1\}}$ ${\displaystyle n\geq 0}$ ${\displaystyle *(n+1)=*n\cup \{*n\}}$

Si bien la palabra nim ber proviene del juego nim , los nimbers se pueden usar para describir las posiciones de cualquier juego finito e imparcial y, de hecho, el teorema de Sprague-Grundy establece que cada instancia de un juego finito e imparcial se puede asociar con un solo nimber.

Combinando juegos

Se pueden combinar dos juegos sumando sus posiciones. Por ejemplo, considere otro juego de nim con montones , , y . ${\displaystyle A'}$ ${\displaystyle B'}$ ${\displaystyle C'}$

Ejemplo de juego 2

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 que Alice gana.

Podemos combinarlo con nuestro primer ejemplo para obtener un juego combinado con seis montones: , , , , , y : ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle C}$ ${\displaystyle A'}$ ${\displaystyle B'}$ ${\displaystyle C'}$

Juego combinado

Tamaños de montones Movimientos Abecedario A'B'C'    1 2 2 1 1 1 Alice toma 1 de A 0 2 2 1 1 1 Bob le quita 1 a A' 0 2 2 0 1 1 Alice toma 1 de B' 0 2 2 0 0 1 Bob le quita 1 a C' 0 2 2 0 0 0 Alice toma 2 de B 0 0 2 0 0 0 Bob le quita 2 a C 0 0 0 0 0 0 Alice no tiene movimientos, por lo que Bob gana.

Para diferenciar entre los dos juegos, para el primer juego de ejemplo, etiquetaremos su posición inicial y la colorearemos de azul: ${\displaystyle \color {blue}S}$ $${\displaystyle \color {blue}S={\Big \{}{\big \{}*1,\{*1\},*2{\big \}},{\big \{}*2,\{*1,\{*1\},*2\}{\big \}},{\big \{}\{*1\},\{\{*1\}\},\{*1,\{*1\},*2\}{\big \}}{\Big \}}}$$

Para el segundo juego de ejemplo, etiquetaremos la posición inicial y la colorearemos de rojo: ${\displaystyle \color {red}S'}$ $${\displaystyle \color {red}S'={\Big \{}\{*1\}{\Big \}}.}$$

Para calcular la posición inicial de la partida combinada, recuerda que un jugador puede hacer un movimiento en la primera partida, dejando intacta la segunda, o hacer un movimiento en la segunda partida, dejando intacta la primera. Por lo tanto, la posición inicial de la partida combinada es: $${\displaystyle \color {blue}S\color {black}+\color {red}S'\color {black}={\Big \{}\color {blue}S\color {black}+\color {red}\{*1\}\color {black}{\Big \}}\cup {\Big \{}\color {red}S'\color {black}+\color {blue}\{*1,\{*1\},*2\}\color {black},\color {red}S'\color {black}+\color {blue}\{*2,\{*1,\{*1\},*2\}\}\color {black},\color {red}S'\color {black}+\color {blue}\{\{*1\},\{\{*1\}\},\{*1,\{*1\},*2\}\}\color {black}{\Big \}}}$$

La fórmula explícita para sumar posiciones es: , lo que significa que la adición es tanto conmutativa como asociativa. ${\displaystyle S+S'=\{S+s'\mid s'\in S'\}\cup \{s+S'\mid s\in S\}}$

Equivalencia

Las posiciones en juegos imparciales se dividen en dos clases de resultados : o bien gana el siguiente jugador (aquel a quien le toca el turno) (una posición - ), o bien gana el jugador anterior (una posición - ). Así, por ejemplo, es una posición -, mientras que es una posición -. ${\displaystyle {\boldsymbol {\mathcal {N}}}}$ ${\displaystyle {\boldsymbol {\mathcal {P}}}}$ ${\displaystyle *0}$ ${\displaystyle {\mathcal {P}}}$ ${\displaystyle *1}$ ${\displaystyle {\mathcal {N}}}$

Dos posiciones y son equivalentes si, sin importar qué posición se les agregue, siempre están en la misma clase de resultado. Formalmente, si y solo si , está en la misma clase de resultado que . ${\displaystyle G}$ ${\displaystyle G'}$ ${\displaystyle H}$ ${\displaystyle G\approx G'}$ ${\displaystyle \forall H}$ ${\displaystyle G+H}$ ${\displaystyle G'+H}$

Para utilizar nuestros ejemplos de ejecución, observe que tanto en el primer como en el segundo juego anteriores, podemos demostrar que en cada turno, Alice tiene un movimiento que obliga a Bob a adoptar una posición . Por lo tanto, tanto y son posiciones . (Observe que en el juego combinado, Bob es el jugador con las posiciones . De hecho, es una posición , lo que, como veremos en el Lema 2, significa .) ${\displaystyle {\mathcal {P}}}$ ${\displaystyle \color {blue}S}$ ${\displaystyle \color {red}S'}$ ${\displaystyle {\mathcal {N}}}$ ${\displaystyle {\mathcal {N}}}$ ${\displaystyle \color {blue}S\color {black}+\color {red}S'}$ ${\displaystyle {\mathcal {P}}}$ ${\displaystyle \color {blue}S\color {black}\approx \color {red}S'}$

Primer lema

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

Supongamos que es una -posición. Entonces, el jugador anterior tiene una estrategia ganadora para : responder a los movimientos en de acuerdo con su estrategia ganadora para (que existe en virtud de ser una -posición), y responder a los movimientos en de acuerdo con su estrategia ganadora para (que existe por la razón análoga). Por lo tanto, también debe ser una -posición. ${\displaystyle G+H}$ ${\displaystyle {\mathcal {P}}}$ ${\displaystyle A+G+H}$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle {\mathcal {P}}}$ ${\displaystyle G+H}$ ${\displaystyle G+H}$ ${\displaystyle A+G+H}$ ${\displaystyle {\mathcal {P}}}$

Por otra parte, si es una -posición, entonces también es una -posición, porque el siguiente jugador tiene una estrategia ganadora: elegir una -posición entre las opciones, y concluimos del párrafo anterior que añadir a esa posición sigue siendo una -posición. Por lo tanto, en este caso, debe ser una -posición, al igual que . ${\displaystyle G+H}$ ${\displaystyle {\mathcal {N}}}$ ${\displaystyle A+G+H}$ ${\displaystyle {\mathcal {N}}}$ ${\displaystyle {\mathcal {P}}}$ ${\displaystyle G+H}$ ${\displaystyle A}$ ${\displaystyle {\mathcal {P}}}$ ${\displaystyle A+G+H}$ ${\displaystyle {\mathcal {N}}}$ ${\displaystyle G+H}$

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

Segundo lema

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

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

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

Prueba

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

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

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

Ahora demostremos que es una posición , lo que, utilizando el segundo lema una vez más, significa que . Lo hacemos dando una estrategia explícita para el jugador anterior. ${\displaystyle G'+*m}$ ${\displaystyle {\mathcal {P}}}$ ${\displaystyle G'\approx *m}$

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

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

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

En resumen, tenemos y . Por transitividad, concluimos que , como se deseaba. ${\displaystyle G\approx G'}$ ${\displaystyle G'\approx *m}$ ${\displaystyle G\approx *m}$

Desarrollo

Si es una posición de un juego imparcial, el único entero tal que se llama su valor de Grundy, o número de Grundy, y la función que asigna este valor a cada una de esas posiciones se llama función de Sprague-Grundy. RL Sprague y PM Grundy dieron de forma independiente una definición explícita de esta función, no basada en ningún concepto de equivalencia con posiciones nim, y demostraron que tenía las siguientes propiedades: ${\displaystyle G}$ ${\displaystyle m}$ ${\displaystyle G\approx *m}$

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

De estos resultados se deduce directamente que si una posición tiene un valor de Grundy de , entonces tiene el mismo valor de Grundy que , y por lo tanto pertenece a la misma clase de resultados, para cualquier posición . Por lo tanto, aunque Sprague y Grundy nunca enunciaron explícitamente el teorema descrito en este artículo, se deduce 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 están encapsulados 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 . ${\displaystyle G}$ ${\displaystyle m}$ ${\displaystyle G+H}$ ${\displaystyle *m+H}$ ${\displaystyle H}$

Véase también

• Teoría del género
• Cociente de indistinguibilidad

Referencias

1. Sprague, RP (1936). "Über Mathematische Kampfspiele". Revista Matemática Tohoku (en alemán). 41 : 438–444. JFM  62.1070.03. Zbl  0013.29004.
2. Grundy, PM (1939). "Matemáticas y juegos". Eureka . 2 : 6–8. Archivado desde el original el 27 de septiembre de 2007.Reimpreso, 1964, 27 : 9–11.
3. Smith, Cedric AB (1960), "Patrick Michael Grundy, 1917–1959", Revista de la Royal Statistical Society, Serie A , 123 (2): 221–22
4. Schleicher, Dierk; Stoll, Michael (2006). "Una introducción a los juegos y números de Conway". Revista Matemática de Moscú . 6 (2): 359–388. arXiv : math.CO/0410026 . doi :10.17323/1609-4514-2006-6-2-359-388. S2CID  7175146.

Enlaces externos

• El juego de Grundy al 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