Teorema de Sprague-Grundy

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

Cada 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 nim de un montón, 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 adición combina varios montones para formar un único montón equivalente en nim.

El valor Grundy o valor nim de cualquier juego independiente es el número único al que equivale el juego. En el caso de un juego cuyas posiciones están indexadas por los 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 de nim del juego.

El teorema de Sprague-Grundy y su prueba resumen los principales resultados de una teoría descubierta de forma independiente por R. P. Sprague (1936) y P. M. Grundy (1939).

Definiciones

Para los propósitos 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 infinitas líneas de juego) y la condición normal de juego (el jugador que no puede moverse pierde).

En cualquier momento dado en el juego, un jugador posición es el conjunto de movimientos Se les permite hacer. Como ejemplo, podemos definir el cero juego ser el juego de dos jugadores donde ningún jugador tiene movimientos legales. Refiriéndose a los dos jugadores como $A$ (para Alice) y $B$ (para Bob), denotaríamos sus posiciones como ${displaystyle (A,B)=({},{})}$ , ya que el conjunto de movimientos que cada jugador puede hacer está vacío.

Un juego imparcial es aquel en el que, en cualquier punto del juego, a cada jugador se le permite exactamente el mismo conjunto de movimientos. El nim de juego normal 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 retira 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. giro. Por el contrario, un juego como el de las damas no es imparcial porque, suponiendo que Alicia jugara con el rojo y Bob con el negro, para cualquier disposición dada de las 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 cualquier configuración de un juego imparcial se puede escribir como una sola posición, porque los movimientos serán los mismos sin importar su turno. Por ejemplo, la posición de la cero juego puede simplemente ser escrito ${}$ , 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 se puede asociar con la posición que deja al siguiente jugador en.

Hacerlo permite que las posiciones se definan recursivamente. Por ejemplo, considere el siguiente juego de Nim jugado por Alice y Bob.

Ejemplo de juego Nim

Tallas de montones mueve
A B C

1 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 1 Alice toma 1 de C
0 0 Bob no tiene movimientos, así que Alice gana

Al paso 6 del juego (cuando todos los montones están vacíos) la posición es ${}$ Porque Bob no tiene movimientos válidos para hacer. Nombramos esta posición $*0$ .
Al paso 5, Alice tenía exactamente una opción: eliminar un objeto del montón C, dejando a Bob sin movimientos. Desde ella Muévanse. deja a Bob en posición $*0$ , ella posición escrito ${displaystyle {*0}}$ . Nombramos esta posición $*1$ .
En el paso 4, Bob tenía dos opciones: eliminar uno de B o eliminar uno de C. Nota, sin embargo, que en realidad no importa qué montón Bob eliminó el objeto de: De cualquier manera, Alice quedaría con un objeto exactamente en una pila. Así que, usando nuestra definición recursiva, Bob sólo tiene un movimiento: $*1$ . Así, la posición de Bob es ${displaystyle {*1}}$ .
Al paso 3, Alice tenía 3 opciones: eliminar dos de C, eliminar uno de C, o quitar uno de B. Removing dos de hojas de C Bob en posición $*1$ . Eliminación de una de las hojas de C Bob con dos pilas, cada uno de tamaño uno, es decir, posición ${displaystyle {*1}}$ , como se describe en el paso 4. Sin embargo, la eliminación 1 de B dejaría a Bob con dos objetos en una sola pila. Su los movimientos serían entonces $*0$ y $*1$ Así que ella movida resultaría en la posición ${displaystyle {*0,*1}}$ . Llamamos a esta posición ${displaystyle *2}$ . La posición de Alice es entonces el conjunto de todos sus movimientos: ${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 $*0$ , $*1$ , y ${displaystyle *2}$ referenciado en nuestro juego de ejemplo se llaman nimbers. En general, el nimber $*n$ corresponde a la posición en un juego de nim donde hay exactamente $n$ objetos en un montón. Formally, los nimbers se definen inductivamente de la siguiente manera: $*0$ es ${}$ , $*1={*0}$ , $*2={*0,*1}$ y para todos $ngeq 0$ , $*(n+1)=*ncup {*n}$ .

Si bien la palabra nimber proviene del juego nim, los nimbers se pueden usar para describir las posiciones de cualquier juego finito e imparcial y, de hecho, el Sprague– El teorema de Grundy establece que cada instancia de un juego imparcial finito puede asociarse con un número único.

Juegos de combinación

Dos juegos se pueden combinar con añadir sus posiciones juntos. Por ejemplo, considere otro juego de nim con montones $A'$ , $B'$ , y $C'$ .

Juego de ejemplo 2

Tallas de montones mueve

A' B' C'
1 1 1 Alice toma 1 de A'
1 1 Bob toma uno de B'
0 1 Alice toma una de C'
0 0 Bob no tiene movimientos, así que Alice gana.

Podemos combinarlo con nuestro primer ejemplo para conseguir un juego combinado con seis montones: $A$ , $B$ , $C$ , $A'$ , $B'$ , y $C'$ :

Juego Combinado

Tallas de montones mueve
A B' B' C'

1 2 1 1 1 Alice toma 1 de A
0 2 1 1 1 Bob toma 1 de A
0 2 0 1 1 Alice toma 1 de B'
0 2 0 0 1 Bob toma 1 de C'
0 2 0 0 Alice toma 2 de B
0 0 0 0 0 Bob toma 2 de C
0 0 0 0 Alice no tiene movimientos, así que Bob gana.

Para diferenciar entre los dos juegos, para el primer juego de ejemplo, etiquetaremos su posición de inicio ${displaystyle color {blue}S}$ , y color azul:

{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 de inicio ${displaystyle color {red}S'}$ y color rojo:

{displaystyle color {red}S'={Big {}{*1}{Big }}.}

Para calcular la posición inicial del juego combinado, recuerda que un jugador puede hacer un movimiento en el primer juego, dejando intacto el segundo juego, o hacer un movimiento en el segundo juego, dejando intacto el primer juego. Entonces, la posición inicial del juego combinado es:

{displaystyle color {blue}Scolor {black}+color {red}S'color {black}={Big {}color {blue}Scolor {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 añadir posiciones es: ${displaystyle S+S'={S+s'mid s'in S'}cup {s+S'mid sin S}}$ , lo que significa que la adición es tanto comunitaria como asociativa.

Equivalencia

Las posiciones en juegos imparciales caen en dos Clases de resultados: o el siguiente jugador (el que gira es) gana (un ${displaystyle {boldsymbol {mathcal {N}}}}$ - posición), o el jugador anterior gana (a ${displaystyle {boldsymbol {mathcal {P}}}}$ - posición). Así que, por ejemplo, $*0$ es un ${mathcal {P}}$ -posición, mientras $*1$ es un ${mathcal {N}}$ -posición.

Dos puestos $G$ y $G'$ son equivalente si, no importa qué posición $H$ se les añade, siempre están en la misma clase de resultados. Formalmente, ${displaystyle Gapprox G'}$ si ${displaystyle forall H}$ , $G + H$ está en la misma clase de resultados ${displaystyle G'+H}$ .

Para utilizar nuestros ejemplos de ejecución, note que en los juegos primero y segundo arriba, podemos mostrar que en cada vuelta, Alice tiene un movimiento que obliga a Bob a un ${mathcal {P}}$ -posición. Así, ambos ${displaystyle color {blue}S}$ y ${displaystyle color {red}S'}$ son ${mathcal {N}}$ -posiciones. (Nota que en el juego combinado, Bob es el jugador con el ${mathcal {N}}$ -posiciones. De hecho, ${displaystyle color {blue}Scolor {black}+color {red}S'}$ es un ${mathcal {P}}$ - la posición, que como veremos en Lemma 2, significa ${displaystyle color {blue}Scolor {black}approx color {red}S'}$ .)

Primer Lema

Como paso intermedio para probar el teorema principal, mostramos que por cada posición $G$ y todos ${mathcal {P}}$ -posición $A$ , la equivalencia $Gapprox A+G$ sostiene. Por la definición de equivalencia anterior, esto equivale a demostrar que $G+H$ y $A+G+H$ compartir una clase de resultados para todos $H$ .

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

Por otro lado, si $G+H$ es un ${mathcal {N}}$ - la posición, entonces $A+G+H$ es también un ${mathcal {N}}$ -posición, porque el próximo jugador tiene una estrategia ganadora: elegir un ${mathcal {P}}$ - la posición de entre $G+H$ opciones, y concluimos del párrafo anterior que agrega $A$ a esa posición sigue siendo ${mathcal {P}}$ -posición. Así pues, en este caso, $A+G+H$ debe ser ${mathcal {N}}$ - la posición, como $G+H$ .

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

Segundo Lema

Como paso más, mostramos que $Gapprox G'$ si $G+G'$ es un ${mathcal {P}}$ -posición.

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

En la dirección inversa, desde $A=G+G'$ es un ${mathcal {P}}$ -posición por hipótesis, sigue de la primera lema, ${displaystyle Gapprox G+A}$ , eso $Gapprox G+(G+G')$ . Del mismo modo, desde ${displaystyle B=G+G}$ es también un ${mathcal {P}}$ -posición, sigue de la primera lema en la forma ${displaystyle G'approx G'+B}$ que $G'approx G'+(G+G)$ . Por asociación y comunicatividad, los lados de derecha de estos resultados son iguales. Además, $approx$ es una relación de equivalencia porque la igualdad es una relación de equivalencia en las clases de resultados. Via the transitivity of $approx$ , podemos concluir que $Gapprox G'$ .

Prueba

Probamos 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í mismo es equivalente a un nimber.

Considerar una posición $G={G_{1},G_{2},ldotsG_{k}}$ . Por la hipótesis de inducción, todas las opciones son equivalentes a los nímeros, digamos $G_{i}approx *n_{i}$ . Así que... $G'={*n_{1},*n_{2},ldots*n_{k}}$ . Vamos a mostrar que $Gapprox *m$ , donde $m$ es el mex (exclusión mínima) de los números $n_{1},n_{2},ldotsn_{k}$ , es decir, el menor entero no negativo no igual a algunos $n_{i}$ .

Lo primero que tenemos que notar es que $Gapprox G'$ Por medio de la segunda lema. Si $k$ es cero, la reclamación es trivialmente verdadera. De lo contrario, considere $G+G'$ . Si el próximo jugador hace un movimiento a $G_i$ dentro $G$ , entonces el jugador anterior puede moverse a $*n_{i}$ dentro $G'$ , y a la inversa si el próximo jugador hace un movimiento $G'$ . Después de esto, la posición es una ${mathcal {P}}$ - la posición de la implicación del lema. Por lo tanto, $G+G'$ es un ${mathcal {P}}$ -posición, y citando la implicación inversa del lema, $Gapprox G'$ .

Ahora vamos a mostrar que $G'+*m$ es un ${mathcal {P}}$ -posición, que, utilizando la segunda lema una vez más, significa que $G'approx *m$ . Lo hacemos dando una estrategia explícita para el jugador anterior.

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

O considere el caso de que el próximo jugador se mueva en el componente $*m$ a la opción $*m'$ Donde $<math alttext="{displaystyle m'm..m{displaystyle m'traducidom} <img alt="m'$ . Porque... $m$ era mínimo número excluido, el jugador anterior puede moverse en $G'$ a $*m'$ . Y, como se muestra antes, cualquier posición más en sí es una ${mathcal {P}}$ -posición.

Por último, suponga que el siguiente jugador se mueve en el componente $G'$ a la opción $*n_{i}$ . Si $<math alttext="{displaystyle n_{i}ni.m{displaystyle No.<img alt="n_{i}$ entonces el jugador anterior se mueve en $*m$ a $*n_{i}$ ; si no, $m}" xmlns="http://www.w3.org/1998/Math/MathML">ni■m{displaystyle No.m" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/24371da867045d9d431118f514019d9afb4e9806" style="vertical-align: -0.671ex; width:7.333ex; height:2.176ex;"/>$ , el jugador anterior se mueve en $*n_{i}$ a $*m$ ; en cualquier caso el resultado es una posición más a sí mismo. (No es posible que $n_{i}=m$ porque $m$ se definió para ser diferente de todo $n_{i}$ .)

En resumen, tenemos $Gapprox G'$ y $G'approx *m$ . Por transitividad, concluimos que $Gapprox *m$ , como se desee.

Desarrollo

Si $G$ es una posición de un juego imparcial, el entero único $m$ tales que $Gapprox *m$ se llama su valor Grundy, o número Grundy, y la función que asigna este valor a cada una de tales posiciones se llama la función Sprague-Grundy. R. L. Sprague y P. M. Grundy independientemente dieron una definición explícita de esta función, no basada en ningún concepto de equivalencia a posiciones de nim, y mostraron que tenía las siguientes propiedades:

El valor Grundy de una sola pila de nim de tamaño $m$ (es decir, de la posición $*m$ ) es $m$ ;
Una posición es una pérdida para que el próximo jugador se mueva (es decir, a ${mathcal {P}}$ -posición) si y sólo si El valor Grundy es cero; y
El valor Grundy de la suma de un conjunto finito de posiciones es sólo el nim-sum de los valores Grundy de sus summands.

Sigue directamente de estos resultados que si una posición $G$ tiene un valor Grundy $m$ , entonces $G + H$ tiene el mismo valor Grundy que $*m + H$ , y por lo tanto pertenece a la misma clase de resultados, para cualquier posición $H$ . Así, aunque Sprague y Grundy nunca declararon explícitamente el teorema descrito en este artículo, sigue directamente de sus resultados y se les acredita. Estos resultados se han desarrollado posteriormente en el campo de la teoría combinatorial del juego, especialmente por Richard Guy, Elwyn Berlekamp, John Horton Conway y otros, donde ahora están encapsulados en el teorema Sprague-Grundy y su prueba en la forma que se describe aquí. El campo se presenta en los libros Formas ganadoras para tus juegos matemáticos y Números y juegos.

Contenido relacionado

Más resultados...