Teorema de Sprague-Grundy

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

Este artículo tiene varios problemas. Ayude a mejorarlo o discuta estos problemas en la página de discusión . ( Obtenga información sobre cómo y cuándo eliminar estos mensajes de plantilla ) Este artículo incluye una lista de referencias generales , pero permanece en gran parte sin verificar porque carece de suficientes citas en línea correspondientes . Ayude a mejorar este artículo introduciendo citas más precisas. ( Junio ​​de 2014 ) ( Obtenga información sobre cómo y cuándo eliminar este mensaje de plantilla ) Este artículo puede ser demasiado técnico para que la mayoría de los lectores lo comprendan . Ayude a mejorarlo para que sea comprensible para los no expertos , sin eliminar los detalles técnicos. ( Junio ​​de 2014 ) ( Obtenga información sobre cómo y cuándo eliminar este mensaje de plantilla ) ( Aprenda cómo y cuándo eliminar este mensaje de plantilla )

En la 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 , oa 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 cuyo La operación de adición combina varios montones para formar un único montículo equivalente en nim.

El valor Grundy o valor nim de cualquier juego imparcial es el nimber único al que es equivalente 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 el tamaño de su montón), la secuencia de nimbers para posiciones sucesivas del juego se denomina secuencia nim del juego.

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

Definiciones

A los efectos del teorema Sprague-Grundy, un juego es una de dos jugadores juego secuencial de información perfecta que satisface la condición de finalización (todos los juegos llegan a su fin: no hay líneas infinitas de juego) y el estado de reproducción 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 ningún jugador tiene movimientos legales. Refiriéndonos 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 un momento dado 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 eliminar 1 o más objetos de él. El ganador es el jugador que elimina el objeto final 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 las damas no es imparcial porque, suponiendo que Alice jugara rojo y Bob jugara negro, para cualquier disposición 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.

Tenga en cuenta que, por lo tanto, cualquier configuración de un juego imparcial se puede escribir 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 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. Nombramos esta posición .${\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 . Nombramos esta posición .${\displaystyle *0}$${\displaystyle \{*0\}}$${\displaystyle *1}$
• En el paso 4, Bob tenía dos opciones: eliminar uno de B o eliminar uno de C. Tenga en cuenta, sin embargo, que realmente 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. Por lo tanto, el uso de nuestra definición recursiva, Bob realmente sólo tiene un solo 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 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 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 \}}}$.

Nimbers

Los nombres especiales , y referenciados en nuestro ejemplo de juego 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, nimbers se definen inductivamente como sigue: 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 nimber proviene del juego nim , nimbers puede 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 nimber único .

Combinar 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'}$

Juego de ejemplo 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 combinar con nuestro primer ejemplo para conseguir 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 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 sin tocar, o hacer un movimiento en el segundo juego, dejando el primer juego sin tocar. 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 el turno) 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, independientemente de la posición que 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 usar nuestros ejemplos de 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, ambos 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 un paso intermedio para demostrar el teorema principal, se muestra que para cada posición y cada -Posición , la equivalencia se mantiene. Según la definición anterior de equivalencia, esto equivale a mostrar eso y compartir una clase de resultado para todos .${\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 las jugadas de acuerdo con su estrategia ganadora para (que existe en virtud de ser una posición ), y responder a las jugadas de acuerdo con su estrategia ganadora para (que existe por la razón análoga ). 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 de entre las opciones, y del párrafo anterior concluimos que agregar a esa posición sigue siendo a -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 es válido.

Segundo lema

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

En la dirección de avance, suponga eso . 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, por lo que siempre realiza 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 sentido inverso, 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 ágil 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í mismo es equivalente a un nimber.

Considere una posición . Según la hipótesis de inducción, todas las opciones son equivalentes a nimbers, digamos . Así que vamos . Demostraremos que , donde está el mex (exclusión mínima) de los números , es decir, el número entero no negativo más pequeño no es igual a algunos .${\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, considérelo . Si el siguiente jugador hace un movimiento hacia adentro , entonces el jugador anterior puede moverse hacia adentro y, a la inversa, 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 un -Posición, y, citando 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 , que, usando el segundo lema una vez más, significa eso . 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 mínimo número de excluidos, el jugador anterior puede moverse en a . Y, como se mostró antes, cualquier posición más en sí misma es una -posición.${\displaystyle *m}$${\displaystyle *m'}$${\displaystyle m'<m}$${\displaystyle m}$${\displaystyle G'}$${\displaystyle *m'}$${\displaystyle {\mathcal {P}}}$

Finalmente, suponga en cambio que el siguiente jugador se mueve en el componente a la opción . Si entonces el jugador anterior se mueve hacia ; de lo contrario, si el jugador anterior se mueve hacia ; en cualquier caso, el resultado es una posición más él mismo. (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 desee.${\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 su valor de Grundy, o número de Grundy, y la función que asigna este valor a cada una de estas 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 a posiciones nim, y demostraron que tenía las siguientes propiedades:${\displaystyle G}$${\displaystyle m}$${\displaystyle G\approx *m}$

• El valor de Grundy de una pila nim única 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 solo la suma mínima de los valores de Grundy de sus sumandos.

De estos resultados se deduce claramente que si una posición tiene un valor de Grundy de , entonces tiene el mismo valor de Grundy 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${\displaystyle G}$${\displaystyle m}$${\displaystyle G+H}$${\displaystyle *m+H}$${\displaystyle H}$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 Play y On Numbers and Games .

Ver también

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

Referencias

1. Sprague, RP (1935-1936). "Über mathische Kampfspiele" . Revista matemática de Tohoku . 41 : 438–444.
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 : matemáticas.CO / 0410026 . doi : 10.17323 / 1609-4514-2006-6-2-359-388 .

enlaces externos

• El juego de Grundy en cortar el nudo
• Cuenta introductoria fácilmente legible 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