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 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 el valor nim de cualquier juego imparcial es el nimber ú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 nim del juego.
El teorema de Sprague-Grundy y su demostración resumen los principales resultados de una teoría descubierta de forma independiente por RP Sprague (1936) [1] y PM Grundy (1939). [2]
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 infinitas líneas de juego) y la condición normal de juego (un jugador el que 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), denotaremos sus posiciones como , 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. Por el contrario, un juego como las damas no es imparcial porque, suponiendo que Alicia jugara con las rojas y Bob con las negras, 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, sólo se le permitiría mover las piezas negras.