Teorema de Sprague-Grundy

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 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 R.P. Sprague (1935)^[1] y P.M. Grundy (1939).^[2]

Definiciones editar

A los efectos del teorema Sprague-Grundy, un juego es un juego secuencial de dos jugadores 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 punto del juego, la posición de un jugador es el conjunto de movimientos que se le permite 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 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 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 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.

Ejemplo de juego de Nim editar

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 $*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 $*0$ , su posición está escrita $\{*0\}$ . Nombramos esta posición $*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. Entonces, usando nuestra definición recursiva, Bob realmente solo tiene un movimiento: $*1$ . Por tanto, la posición de Bob es $\{*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 $*1$ . Quitar uno de C deja a Bob con dos montones, cada uno de tamaño uno, es decir, posición $\{*1\}$ , 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 $*0$ y $*1$ , por lo que su movimiento resultaría en la posición $\{*0,*1\}$ . La posición de Alice es entonces el conjunto de todos sus movimientos: ${\big \{}*1,\{*1\},*2{\big \}}$ .
Siguiendo la misma lógica recursiva, en el paso 2, la posición de Bob es ${\big \{}\{*1,\{*1\},*2\},*2{\big \}}$ .
Finalmente, en el paso 1, la posición de Alice es

${\Big \{}{\big \{}*1,\{*1\},*2{\big \}},{\big \{}*2,\{*1,\{*1\},*2\}{\big \}},{\big \{}\{*1\},\{\{*1\}\},\{*1,\{*1\},*2\}{\big \}}{\Big \}}$ .

Nimbers editar

Los nombres especiales $*0$ , $*1$ , y $*2$ referenciados en el 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 exactamente un montón. Formalmente, los nimbers se definen inductivamente de la siguiente manera: $*0$ is $\{\}$ , $*1=\{*0\}$ , $*2=\{*0,*1\}$ y para todo $n\geq 0$ , $*(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.

Combinando juegos editar

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

Juego de ejemplo 2 editar

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: $A$ , $B$ , $C$ , $A'$ , $B'$ , and $C'$ :

Juego combinado editar

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 $\color {blue}S$ , coloreado de azul:

$\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 $\color {red}S'$ coloreado de rojo:

$\color {red}S'={\Big \{}\{*1\}{\Big \}}$ .

Para calcular la posición inicial del juego combinado, recuerdése que un jugador puede hacer un movimiento en el primer juego, dejando el segundo 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:

$\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 agregar posiciones es: $S+S'=\{S+s'\mid s'\in S'\}\cup \{s+S'\mid s\in S\}$ , lo que significa que la suma es tanto conmutativa como asociativa