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 , oa 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 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éndose a los dos jugadores como (para Alice) y (para Bob), denotaríamos sus posiciones como , ya que el conjunto de movimientos que puede realizar cada jugador está vacío.
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 Alicia jugara rojo y Bob jugara negro, para cualquier disposición dada de piezas en el tablero, si fuera el turno de Alicia, 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 tanto, cualquier configuración de un juego imparcial se puede escribir como una sola posición, 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.
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.
- 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 puesto esta escrito. Nombramos esta posición.
- 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. Entonces, usando nuestra definición recursiva, Bob realmente solo tiene un movimiento:. Por tanto, la posición de Bob es.
- 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 montones, cada uno 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 serían entonces y , por lo que su movimiento resultaría en la posición. Llamamos a esta posición. La posición de Alice es entonces el conjunto de todos sus movimientos:.
- Siguiendo la misma lógica recursiva, en el paso 2, la posición de Bob es .
- Finalmente, en el paso 1, la posición de Alice es
.
Nimbers
Los nombres especiales , , y a los que se hace referencia en nuestro juego de ejemplo se llaman nimbers . En general, el ágil corresponde a la posición en un juego de nim donde hay exactamente objetos en exactamente un montón. Formalmente, los nimbers se definen inductivamente de la siguiente manera: es , , y para todos , .
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 .
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 combinarlo con nuestro primer ejemplo para obtener un juego combinado con seis montones:, , , , , y :
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 inicialy coloréalo de azul:
Para el segundo juego de ejemplo , etiquetaremos la posición inicial y colorearlo de rojo:
.
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:
La fórmula explícita para agregar posiciones es: , lo que significa que la suma es tanto conmutativa como asociativa.
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 (un- posición ). Así por ejemplo, es un -posición, mientras es un -posición.
Dos posiciones y son equivalentes si, no importa en qué posiciónse les agrega, siempre están en la misma clase de resultado. Formalmente, si y solo si , está en la misma clase de resultado que .
Para usar nuestros ejemplos de ejecución, observe que tanto en el primer como en el segundo juego de arriba, podemos mostrar que en cada turno, Alice tiene un movimiento que obliga a Bob a hacer un-posición. Por lo tanto, tanto y están -posiciones. (Observe que en el juego combinado, Bob es el jugador con el-posiciones. De echo, es un -posición, que como veremos en el Lema 2, significa .)
Primer lema
Como paso intermedio para demostrar el teorema principal, mostramos que para cada posición y cada -posición , la equivalencia sostiene. Según la definición anterior de equivalencia, esto equivale a mostrar que y compartir una clase de resultados para todos .
Suponer que es un -posición. Entonces el jugador anterior tiene una estrategia ganadora para: responder a movimientos en según su estrategia ganadora para (que existe en virtud de ser un -posición), y responder a los movimientos en según su estrategia ganadora para (que existe por la razón análoga). Entonces también debe ser un -posición.
Por otro lado, si es un -posición, entonces es también un -posición, porque el siguiente jugador tiene una estrategia ganadora: elija una -posición de entre los opciones, y del párrafo anterior concluimos que agregar a esa posición sigue siendo un -posición. Así, en este caso, debe ser un -posición, al igual que .
Como estos son los dos únicos casos, el lema es válido.
Segundo lema
Como paso adicional, mostramos que si y solo si es un -posición.
En la dirección de avance, suponga que . Aplicando la definición de equivalencia con, encontramos eso (que es igual a por conmutatividad de adición) está en la misma clase de resultado que. Pero debe ser un -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 hace el último movimiento.
En sentido inverso, ya que es un -posición por hipótesis, se sigue del primer lema, , que . Del mismo modo, dado que también es un -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 .
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. Entonces deja. Te mostraremos que, dónde es 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 .
Lo primero que debemos tener en cuenta es que , a través del segundo lema. Sies cero, la afirmación es trivialmente cierta. De lo contrario, considere. Si el siguiente jugador hace un movimiento 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, el puesto es un-posición por la implicación directa del lema. Por lo tanto, es un -posición y, citando la implicación inversa del lema, .
Ahora demostremos que es un -posición, que, usando el segundo lema una vez más, significa que . Lo hacemos dando una estrategia explícita para el jugador anterior.
Suponer que y están vacíos. Luego es el conjunto nulo, claramente un -posición.
O considere el caso de que el siguiente jugador se mueva en el componente a la opción dónde . Porqueera el número mínimo excluido, el jugador anterior puede moverse en a . Y, como se mostró antes, cualquier posición más en sí misma es una-posición.
Finalmente, suponga en cambio que el siguiente jugador se mueve en el componente a la opción . Si entonces el jugador anterior se mueve en a ; de lo contrario, si, el jugador anterior se mueve en a ; en cualquier caso, el resultado es una posición más él mismo. (No es posible que porque se definió como diferente de todos los .)
En resumen, tenemos y . Por transitividad, concluimos que, como se desee.
Desarrollo
Si es una posición de un juego imparcial, el número 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 denomina 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:
- El valor Grundy de una sola pila nim de tamaño (es decir, de la posición ) es ;
- 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
- 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 desprende claramente que si una posición tiene un valor Grundy de , luego tiene el mismo valor de 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 se encapsulan en el teorema de Sprague-Grundy y su demostración en el formulario descrito aquí. El campo se presenta en los libros Winning Ways for your Mathematical Play y On Numbers and Games .
Ver también
Referencias
- ↑ Sprague, RP (1935-1936). "Über mathische Kampfspiele" . Revista matemática de Tohoku . 41 : 438–444.
- ^ 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.
- ^ Smith, Cedric AB (1960), "Patrick Michael Grundy, 1917-1959", Revista de la Royal Statistical Society, Serie A , 123 (2): 221-22
- ^ 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