Teorema de Sprague-Grundy

Cada posición de juego imparcial equivale a una posición en el juego de nim.

En teoría de juegos combinatorios , el teorema de Sprague-Grundy establece que todo juego imparcial según 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 cuyo La operación de suma combina varios montones para formar un único montón equivalente en nim.

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

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 quien no puede moverse pierde).

En cualquier momento del juego, la posición de un jugador es el conjunto de movimientos que puede realizar. Como ejemplo, podemos definir el juego cero como el juego de dos jugadores en el que ninguno de los jugadores tiene movimientos legales. Al referirnos 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 hacer está vacío. ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle (A,B)=(\{\},\{\})}$

Un juego imparcial es aquel en el que, en cualquier momento del juego, a cada jugador se le permite exactamente el mismo conjunto de movimientos. Nim de juego normal es un ejemplo de 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 1 o más objetos de él. El ganador es el jugador que retira el último objeto del montón final. El juego es imparcial porque para cualquier configuración dada de tamaños de pila, los movimientos que Alice puede hacer en su turno son exactamente los mismos movimientos que Bob podría hacer si fuera su turno. Por el contrario, un juego como el de las damas no es imparcial porque, suponiendo que Alice estuviera jugando con el rojo y Bob con el negro, para cualquier disposición dada de las 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, sólo se le permitiría mover las piezas negras.

Tenga en cuenta que, por lo tanto, cualquier configuración de un juego imparcial puede 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 se puede escribir simplemente , porque si es el turno de Alice, ella 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 \{\}}$

Hacerlo permite definir posiciones de forma recursiva. Por ejemplo, considere el siguiente juego de Nim jugado por Alice y Bob.

Ejemplo de juego de Nim

Tamaños de montones de movimientos A B C   1 2 2 Alice 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 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. A esta posición le ponemos nombre . ${\displaystyle \{\}}$ ${\displaystyle *0}$
• En el paso 5, Alice tenía exactamente una opción: eliminar un objeto del montón C, dejando a Bob sin movimientos. Dado que su movimiento deja a Bob en posición , su posición está escrita . A esta posición le ponemos nombre . ${\displaystyle *0}$ ${\displaystyle \{*0\}}$ ${\displaystyle *1}$
• En el paso 4, Bob tenía dos opciones: eliminar uno de B o eliminar uno de C. Sin embargo, tenga en cuenta que en realidad no importaba de qué montón Bob eliminó el objeto: de cualquier manera, Alice se quedaría con exactamente un objeto en exactamente una pila. Entonces, usando nuestra definición recursiva, Bob en realidad solo tiene un movimiento: . Por 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, 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 entonces serían y , por lo que su movimiento resultaría en la posición . A esta posición la llamamos . 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 \}}.}$$

números

Los nombres especiales , y a los que se hace referencia en nuestro juego de ejemplo se llaman 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 números se definen inductivamente de la siguiente manera: es , y para todos ,. ${\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 pueden usarse 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 puede asociarse con un número único .

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 de 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 de movimientos ABCA'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 que Bob gana.

Para diferenciar entre los dos juegos, para el primer juego de ejemplo, etiquetaremos su posición inicial y lo 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 del juego combinado, recuerde que un jugador puede hacer un movimiento en el primer juego, dejando el segundo juego intacto, o hacer un movimiento en el segundo juego, dejando el primer juego intacto. Entonces la posición inicial del juego combinado 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 suma 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 el siguiente jugador (aquel a quien le toca) gana (una posición ), o el jugador anterior gana (una posición ). Entonces, 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 sólo 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 usar nuestros ejemplos en ejecución, observe que tanto en el primer como en el segundo juego anteriores, podemos mostrar que en cada turno, Alice tiene un movimiento que obliga a Bob a adoptar una posición. Por tanto, ambas y son posiciones -. (Observe que en el juego combinado, Bob es el jugador con las posiciones. De hecho, es una posición, 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 , la equivalencia se cumple. Según la definición anterior de equivalencia, esto equivale a demostrar que todos compartimos una clase de resultado . ${\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 de acuerdo con su estrategia ganadora para (que existe en virtud de ser una posición), y responder a los movimientos de acuerdo con su estrategia ganadora para (que existe por la razón análoga ). Así 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 otro lado, si es una posición, entonces también es una posición, porque el siguiente jugador tiene una estrategia ganadora: elige una posición entre las opciones, y del párrafo anterior concluimos que sumar a esa posición aún es 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 dos únicos casos, el lema se cumple.

Segundo lema

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

En la dirección de avance, supongamos que . Aplicando la definición de equivalencia con , encontramos que (que es igual a por conmutatividad de la suma) 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 deduce del primer lema, que . De manera similar, dado que también es una posición -, se deduce 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 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

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

Considere una posición . Según la hipótesis de inducción , todas las opciones son equivalentes a números, digamos . Entonces deja . Demostraremos que , ¿dónde está el mex (mínima exclusión) de los números , es decir, el entero no negativo más pequeño no igual a alguno ? ${\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 cierta. De lo contrario, considere . Si el siguiente jugador hace un movimiento hacia adentro , entonces el jugador anterior puede moverse hacia adentro , y viceversa si el siguiente jugador hace un movimiento hacia adentro . Después de esto, la posición es una posición -por la implicación directa 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, usando 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 es el conjunto nulo, claramente una posición. ${\displaystyle G'}$ ${\displaystyle *m}$ ${\displaystyle G'+*m}$ ${\displaystyle {\mathcal {P}}}$

O considere el caso de que el siguiente jugador se mueva en el componente a la opción donde . Debido a que era el número mínimo excluido, el jugador anterior puede pasar 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}}}$

Finalmente, supongamos que el siguiente jugador mueve el componente a la opción . Si entonces el jugador anterior pasa a ; de lo contrario, si , el jugador anterior pasa a ; en cualquier caso el resultado es una posición más ella misma. (No es posible que porque se haya definido 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 desea. ${\displaystyle G\approx G'}$ ${\displaystyle G'\approx *m}$ ${\displaystyle G\approx *m}$

Desarrollo

Si es una posición de un juego imparcial, el entero único tal que se llama 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 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 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 mueva (es decir, una posición) si y sólo si su valor 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 Grundy de , entonces tiene el mismo valor Grundy que , y por lo tanto pertenece a la misma clase de resultado, para cualquier posición . Por lo tanto, aunque Sprague y Grundy nunca establecieron explícitamente el teorema descrito en este artículo, 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 están resumidos en el teorema de Sprague-Grundy y su demostración en el formulario aquí descrito. El campo se presenta en los libros Maneras de ganar para tus juegos matemáticos y Sobre números y juegos . ${\displaystyle G}$ ${\displaystyle m}$ ${\displaystyle G+H}$ ${\displaystyle *m+H}$ ${\displaystyle H}$

Ver 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 de Matemáticas 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
• Cuenta introductoria de fácil lectura del Departamento de Matemáticas de 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