El único requisito previo para comprender este concepto es conocer el Juego de Nim. Esta respuesta tiene la intención de explicar qué son los números grundy y cómo se relacionan con este juego.
¿Qué son los números grundy?
Considera un problema:
- ¿Qué pasaría si más personas se dieran cuenta de que la Ley podría entenderse como una serie de algoritmos sociales en un programa que se resiste a la compilación?
- ¿Qué temas de geometría y álgebra son importantes para concursos de programación como ICPC?
- Cómo insertar un nuevo nodo en un árbol binario (no buscar árbol binario)
- ¿Cómo son útiles la estructura de datos y los algoritmos en el aprendizaje automático?
- ¿Siempre es bueno tener una solución recursiva que una solución iterativa?
Dos jugadores están jugando un juego G que consiste en N juegos combinatorios imparciales [2] [1]. Un movimiento consiste en elegir un juego y hacer un movimiento en ese juego. Dado el estado inicial de todos los N juegos, averigua si el estado dado del juego G está perdiendo o ganando para el primer jugador.
Primero entendamos el problema:
[1 [ referencia ]] Los juegos combinatorios no son más que un juego que sigue las siguientes reglas:
- hay dos jugadores moviéndose alternativamente;
- no hay dispositivos de azar y ambos jugadores tienen información perfecta;
- las reglas son tales que el juego finalmente debe terminar; y
- no hay sorteos, y el ganador está determinado por quién se mueve por última vez.
[2] Defino juego combinatorio imparcial como {S, F y T}. Dónde,
- S es el conjunto de todos los estados posibles del juego. Por ejemplo: en el Juego de Nim, un estado se define como un vector de número de monedas en cada pila. Entonces este conjunto contiene todos los vectores posibles. Son N1 * N2 … Nk en número si N1 es el número de objetos en la primera pila, N2 es el número de objetos en la segunda pila y así sucesivamente.
- F es el conjunto de todos los estados finales del juego. Por ejemplo: en el Juego de Nim, este conjunto solo contendrá un vector con todos los elementos como 0.
- T es el mapa de transición. La clave en este mapa es un estado y el valor es la lista de estados a los que puede ir, desde el estado actual. La entrada de ejemplo del Juego de Nim en el mapa será:
[1, 1, 0,…, 0] -> [[0, 1, 0,…, 0], [1, 0, 0,…, 0]]
Ahora ya puedes imaginar que un juego imparcial se puede visualizar como un gráfico acíclico dirigido. Donde los nodos son los estados, puede etiquetar los estados finales y hay un borde de estado1 a estado2 si es posible moverse de estado1 a estado2 de acuerdo con el mapa de transición.
¿Por qué debería ser un gráfico acíclico dirigido?
- Es un gráfico dirigido porque poder pasar del estado 1 al estado 2 no implica que pueda pasar del estado 2 al estado 1.
- Es un gráfico acíclico porque la definición del juego combinatorio dice que nunca debería ser posible dibujar el juego y la presencia de un ciclo viola esta condición.
Ahora, si asigna a cada nodo del juego una etiqueta entera (número Grundy) con la siguiente lógica.
- Todos los nodos terminales están marcados con 0.
- Para cada nodo no terminal, la etiqueta es el número mínimo que no está presente en ninguno de los vecinos.
Después de haber asignado números grundy a cada nodo para cada juego en G. Saque números grundy en el estado actual para todos los juegos en G. El teorema Sprague-grundy establece que si el xor de todos estos números es cero, entonces el estado actual es Perder más está ganando.
¿Por qué?
Si observa la lógica de asignar números grundy a un juego, termina dividiendo todos los estados de los juegos en nivel. Cada nivel es un número sucio.
Observación 1:
De cada nodo en el nivel i, hay una ventaja para algún nodo en todos los niveles debajo de i.
Prueba por contradicción: si no hubiera habido una arista desde un nodo N en el nivel i hasta el nivel j st (j <i), el nodo N debería haber estado en el nivel j.
Observación 2:
No habrá un borde de un nodo A al nodo B si están en el mismo nivel.
Nuevamente, prueba similar por contradicción (dejada para el lector como ejercicio).
Ahora, si ves que el juego puede verse como una pila (de niveles) en el Juego de Nim. Puedes disminuir el nivel tanto como quieras en un solo movimiento. Entonces,
Si el xor de todos los números grundy no es cero, entonces el estado actual G ganará con la misma lógica que el Juego de Nim.
Una pequeña captura
Puede haber bordes que van a niveles más altos. Así que aquí es posible “agregar algo a la pila de Nim”. Pero no debería ser una preocupación porque todo lo que le importa al juego de Nim son dos cosas:
- Debería ser posible pasar de un estado de xor distinto de cero a un estado de xor cero. El jugador ganador nunca usará la opción de agregar y en su lugar sacar algo y mantener el xor cero.
- Solo debería ser posible pasar a un estado distinto de cero xor del estado de cero xor. Todavía se mantiene, independientemente de si agrega o elimina objetos.
Por lo tanto, ambos invariantes siguen siendo válidos y estos bordes no deberían cambiar la estrategia general del juego. Además, estos bordes no pueden conducir a un juego infinito porque ya hemos demostrado que es un gráfico acíclico dirigido.
¡Espero que ayude!
