Los números Grundy en la Teoría de Juegos


Hola mundo. Hoy les hablaré acerca de los números Grundy, también conocidos como nimbers. Los números Grundy son tratados en la teoría de juegos como los valores de los bultos del juego de Nim. A lo largo del artículo aclararemos algunas interrogantes como: ¿Dónde podemos aplicar los números Grundy?, ¿Para qué problemas nos sirven?, entre otras preguntas.

Para empezar definiremos un concepto básico que llamaremos Teorema de Sprague-Grundy”. Este teorema dice que todo juego imparcial es equivalente a un bulto de Nim de cierto tamaño.

A partir de esto podemos inferir que muchos de los juegos conocidos, podemos expresarlos como un juego de Nim, y así por medio de los números Grundy darle solución.

Entonces quedan planteadas las siguientes interrogantes: ¿Qué sucede si se presenta un juego de Nim con varios bultos de piedra? ¿Cómo calcular el número Grundy de cierto estado n el cual definiremos por G(n)?

Explicando el teorema

Sea y: Todas las posibles posiciones a las cuales nos podemos mover desde n.

G(n) = min(x>=0, x != G(y)).

Es decir, del conjunto de todos los números Grundy de las posiciones a las que me puedo mover desde n, el número Grundy de n va a ser el menor entero no negativo que no aparezca en dicho conjunto. Todas las posiciones terminales tienen números Grundy 0.

Vamos a ver cómo calcular los números Grundy de las dos variantes de Nim vistas en el artículo anterior.

Variante Nim quitando desde 1 hasta n piedras.

n 0 1 2 3 4 5 6 7 8 9
G(n) 0 1 2 3 4 5 6 7 8 9

Como la posición n = 0 es una posición terminal su valor grundy es G(0) = 0. Desde n = 1 se puede mover hacia n = 0 con G(0) = 0, por tanto aplicando la definición:

G(1) = min(x>=0, x != G(0)). El menor número no negativo es 1, por tanto G(1) = 1.

Para G(2) = min(x>=0, x != G(0), x!=G(1)), que es x=2. Por tanto G(2) = 2, y así para los demás estados.

En este caso, no se tiene que ir iterando por cada posición a las que nos podemos mover desde el momento inicial, ya que fácilmente se puede observar que G(n) = n.

Variante de Nim quitando una o dos piedras solamente.

n 0 1 2 3 4 5 6 7 8 9
G(n) 0 1 2 0 1 2 0 1 2 0

 G(0) = 0 ya que n = 0 es una posición terminal. Desde n = 1 nos podemos mover hacia n=0 con G(0) = 0, por lo que G(1) = 1, y consecutivamente queda que G(2) = 2.

Ahora, desde n=3 nos podemos mover hacia n=1 con G(1) = 1, y a n = 2 con G(2) = 2, entonces el menor número no negativo que sea distinto de G(1) y G(2) es cero, por tanto G(3) = 0.

Viendo el patrón formado podemos llegar a la conclusión de que G(n) = n%3.

Una vez que hemos visto los números Grundy de estos ejemplos, ¿Cómo podemos usarlos? Pues si una posición tiene valor Grundy cero significa que es una posición perdedora, y si una posición tiene un número Grundy mayor que cero, significa que es ganadora.

Ahora retomemos el juego de Nim con más de un bulto de piedra, esto es lo que se conoce como suma de k-ésimos juegos, es decir, si tenemos un juego de Nim con cuatro bultos de piedra, es como si tuviéramos cuatro juegos de Nim con solo un bulto cada uno.

Un ejemplo de este caso es el siguiente problema:

Dado un juego de Nim con 3 bultos de piedra, cada jugador en su turno puede seleccionar un bulto y remover de este desde 1 hasta n piedras, siendo n el total de piedras del bulto seleccionado. De ser posible encuentre una estrategia ganadora.

Veremos qué sucede si tenemos 3 bultos con 1, 2 y 4 piedras respectivamente.

Juego de 3 bultos

Fig1:Juego de 3 bultos

El jugador en turno está en la posición (4, 2, 1). ¿Cómo determinamos que una posición es ganadora? La respuesta está dada por la operación binaria xor:

¿Qué es el xor y cómo se calcula?

Es una operación a nivel de bits tal que:

0 xor 1 = 1.

1 xor 1 = 0.

0 xor 0 = 0.

Otra manera de calcularlo es la siguiente:

Escribimos los números en su representación binaria.

El xor es la suma de las columnas módulo 2. En el lenguaje de programación C++ para calcularlo podemos utilizar el operador xor o el operador ^.

4 -> 100

2-> 010

1-> 001

————

R = 111 —> 7 en base 10. G(4, 2, 1) = 7.

 

Si el xor entre los números Grundys de todas las posiciones es cero estamos en una posición perdedora y si es mayor que cero estamos en una posición ganadora.

Entonces, la posición (4, 2, 1) es ganadora ya que G(4) xor G(2) xor G(1) > 0.

Ahora sabiendo que estamos en una posición ganadora, ¿Cómo ganamos el juego?

Lo que debemos hacer es movernos hacia una posición perdedora, para que el próximo jugador sólo pueda moverse a una posición ganadora y así sucesivamente hasta que el próximo jugador llegue a una posición terminal y pierda el juego.

Entonces, ¿Cómo nos movemos hacia una posición perdedora? Volvamos a la representación binaria de los números:

4 -> 100

2 -> 010

1 -> 001.

Buscamos la columna más a la izquierda donde el número de unos sean impares, cambiamos cualquiera de esos unos a cero, y cambiamos los demás dígitos a la derecha del seleccionado a uno o cero, tal que obtengamos una cantidad par de unos en todas las columnas.

En el juego, vemos que la columna más a la izquierda, donde la cantidad de unos son impares, es la primera columna. Cambiamos el uno del primer bulto, nos quedaría:

=> 000

010

001.

Saltamos para la siguiente columna, y cambiamos el valor de 0 a 1.

=> 010

010

001.

Saltamos a la última columna, y también cambiamos el valor de 0 a 1.

=> 011

010

001.

Llevándolo a base 10 nos quedarían tres bultos, el primero con 3 piedras, el segundo con 2 y el tercero con 1, es decir, nuestro movimiento fue quitarle una piedra al bulto de cuatro.

El siguiente jugador está en la posición (3, 2, 1) que es perdedora, ya que G(3) xor G(2) xor G(1) = 0, juegue lo que juegue, seguimos utilizando la misma estrategia, hasta que nuestro rival alcance un estado terminal y pierda el juego.

 Conclusiones

Hasta aquí hemos visto cómo utilizar los números Grundy para resolver problemas de la Teoría de Juegos. Estos nos ofrecen mucha más información que las posiciones ganadoras y perdedoras, ya que podemos saber cómo jugar óptimamente en un juego o en una suma de juegos.

Vimos el teorema de Sprague-Grundy, y la importancia que tiene el juego de Nim, ya que muchos juegos al final se pueden reducir a una variante de este. En el siguiente artículo veremos cómo darle solución a problemas reales de juego utilizando esta poderosa herramienta.