Función de Sprague-Grundy

La función Sprague-Grundy se usa ampliamente en la teoría de juegos para encontrar una estrategia ganadora en juegos combinatorios como el juego de Nîmes . La función Sprague-Grundy se define para juegos de dos jugadores en los que el jugador que no puede hacer otro movimiento pierde.

En el caso de juegos discretos, a veces llamado nimber .

El teorema de Sprague-Grundy es una deducción general de los resultados que R. Sprague (1935) y P. M. Grandy (1939) establecieron y demostraron de forma independiente. Consiste en que para cualquier juego imparcial donde gana el jugador que hizo el último movimiento, para cada posición se determina de manera única el valor de la función Sprague-Grundy, que determina la estrategia ganadora o su ausencia.

Definiciones

Definición 1

Una función de Sprague-Grundy es una función F definida para x y que toma valores no negativos tales que:

F(x)=\min\{n\geq 0:n\neq F(y),y\in G(x)\},

dónde

n es cualquier número entero no negativo,
y es una de las posiciones que se puede mover directamente desde la posición x en un solo movimiento,
F( y ) - Valores de Sprague-Grandy de posiciones que se pueden mover directamente desde la posición x en un solo movimiento,
G( x ) es una lista de posiciones que se pueden mover directamente desde la posición x en un solo movimiento.

Así, F( x ) es el entero no negativo más pequeño que no se encuentra entre los valores de Sprague-Grundy para cierto x .

Definición 2

La función F se define en el conjunto de todas las posiciones de juego de la siguiente manera: $GRAMO$

{\ estilo de visualización F (P) = 0,}

si la posición P es inequívocamente perdedora (no se puede hacer ningún movimiento)

F(P)=\min(\Omega \setminus \{F(Q)|Q\in G(P)\})

de lo contrario,

donde es el conjunto de enteros no negativos y es el conjunto de todos los movimientos permitidos desde la posición P . $\Omega$ $G(P)$

Propiedades básicas

Si x es la posición final, entonces F( x ) = 0. Las posiciones x para las que F( x ) = 0 son posiciones P (que pierde el jugador al que le toca moverse), mientras que todas las demás posiciones son respectivamente H- posiciones (ganadora para el jugador al que le toca hacer un movimiento). Una estrategia ganadora es elegir en cada paso un movimiento en el que el valor de Sprague-Grundy sea cero.
Desde la posición x para la cual F( x ) = 0, solo hay movimientos a la posición y tales que F( y ) ≠ 0.
Desde la posición x para la cual F( x ) ≠ 0, hay al menos un movimiento a la posición y para la cual F( y ) = 0.

Aplicación

Una de las propiedades útiles de la función Sprague-Grundy es que es cero para todas las posiciones perdedoras y positiva para todas las posiciones ganadoras. Esto da un método para encontrar una estrategia ganadora:

Encuentre la función Sprague-Grundy, por ejemplo, construyéndola recursivamente , comenzando desde las posiciones finales.
Si en la posición inicial la función de Grundy es igual a cero, el primer jugador pierde el juego.
De lo contrario, el primer jugador puede ganar moviendo cada movimiento a una posición con valor cero de la función Grundy.

Suma de juegos

Si tenemos juegos , entonces podemos considerar una combinación de estos juegos, para los cuales el campo de juego consiste en un conjunto de campos de juego para juegos y en un movimiento el jugador puede elegir algunos y hacer un movimiento en el campo de juego para jugar . Tal combinación se llama suma de juegos y se denota por . La situación en el campo de juego del juego , cuando el campo de juego del juego está en posición , se indica convenientemente como . $norte$ $G_{1},G_{2},\puntos,G_{n}$ $G_{1},G_{2},...,G_{n}$ $i,1\leq i\leq n$ $Soldado americano}$ $G_{1},G_{2},\puntos,G_{n}$ $G_{1}+G_{2}+\puntos +G_{n}$ $G_{1}+G_{2}+\puntos +G_{n}$ $Soldado americano}$ $Pi}$ $(P_{1},P_{2},\puntos,P_{n})$

La función Sprague-Grundy tiene una propiedad sorprendente que permite jugar de forma óptima la suma de partidas , conociendo la función Sprague-Grundy para todas las posiciones de cada una de las partidas . Está formulado de la siguiente manera: $G_{1}+G_{2}+...+G_{n}$ $Soldado americano}$

F(P_{1},P_{2},\dots ,P_{n})=F(P_{1})\oplus F(P_{2})\oplus \dots \oplus F(P_{ norte}),

donde - exclusivo "o" (también conocido como XOR). $\oplus$

Ejemplo

Una tarea

Hay un área que consta de 10 celdas. Juegan dos jugadores. En un movimiento, se permite dividir el área en dos áreas desiguales distintas de cero para que no se viole la unidad de cada celda individual (es decir, la celda no se puede dividir). El que no puede hacer un movimiento pierde. ¿Quién gana bajo la condición de juego limpio correcto?

Solución

El problema se resuelve desde el final. Considere las opciones para dividir el área para todos los casos de 1 a 10 celdas y encuentre los valores de la función Sprague-Grandy para ellos. Tenga en cuenta que para este juego, como resultado de dividir el área cada vez en dos áreas nuevas, el valor de la función Sprague-Grundy se encuentra usando Nim-sum .

El valor de Sprague-Grundy para n = 10 resulta ser 0. Por lo tanto, el jugador que hace el primer movimiento pierde. En cualquiera de sus movimientos, el segundo jugador se mueve a las posiciones 4 + 4 o n = 1/2/7, para las cuales el valor de Sprague-Grundy también es igual a 0.

Responder

El que se mueve segundo gana.

Véase también

Enlaces

Berge K. Teoría de grafos y sus aplicaciones. M.: IL, 1962. 320c.
Nivasch G. La teoría de Sprague-Grundy de juegos imparciales (enlace descendente desde 13-05-2013 [3456 días] - historia )
Kummer B. N. §2.2. La función de Grundy y las sumas de orden p // Graph games. - mil novecientos ochenta y dos.
BCA Milvang-Jensen. Juegos Combinatorios, Teoría y Aplicaciones (indefinido) . — 2000.
Thomas S. Ferguson TEORÍA DE JUEGOS
La teoría de Sprague-Grundy de los juegos imparciales (enlace descendente desde el 13/05/2013 [3456 días] - historia ) (ing.) , 9 de noviembre de 2005
Sprague-Grundy Valores del Juego de Grundy
PM Grundy. Matemáticas y Juegos (neopr.) // Eureka. - 1964. - T. 27 . Archivado desde el original el 27 de septiembre de 2007.