Bases de la teoría de juegos combinatorios.


El ser humano por naturaleza es un ser competitivo, por lo que siempre ha buscado la forma de ganar en todo lo que se propone, y una herramienta que nos permite obtener la victoria si es posible y sin cometer errores, aunque nuestro adversario juegue de forma óptima, es la Teoría de Juegos.

En el artículo anterior tratamos algunos modelos clásicos de la teoría de juegos, y vimos el concepto de juegos combinatorios, sobre estos últimos vamos a estar hablando, además, veremos algunos conceptos fundamentales y cómo estos se aplican para hallar las soluciones de los juegos propuestos.

Los juegos que veremos con relación al tema, van a tener las siguientes características:

  • Juegos de dos personas: Definamos al jugador que comienza, como A y el segundo en hacer su movimiento B. Los jugadores se alternan.
  • Perfecta Información: Los jugadores disponen de toda la información para poder hacer su jugada.
  • No interviene el azar.
  • Finitos: En algún momento del juego el jugador A o B va a alcanzar una posición terminal.

En esta ocasión me quiero referir al juego de Nim, que cumple con las condiciones anteriores y nos ayudará a sentar las bases para resolver problemas de juegos aparentemente complejos, reduciéndolos a una variante clásica como lo es este juego.

Juego de Nim

Tenemos una pila con n piedras, y los jugadores pueden tomar de dicha pila, desde 1 hasta n piedras. El jugador que en su turno, no pueda retirar más piedras del bulto, se considera perdedor.

Juego de Nim

Fig1: Juego de Nim

Está claro que siempre gana el jugador A, retirando todas las piedras, es decir, el jugador B alcanza un estado terminal que es un bulto con 0 piedras, por lo que podemos definir que la posición p = 0 es perdedora y que cualquier posición p > 0 es ganadora, porque podemos retirar todas las piedras y ganar.

Pero hagamos el juego más interesante, supongamos que cada jugador puede remover una o dos piedras solamente. La posición p = 0 sigue siendo una posición perdedora porque no podemos retirar ninguna piedra, fácilmente podemos ver que las posiciones p = 1 y p = 2 son ganadoras, simplemente retiramos todas las piedras. ¿Pero, qué sucedería si el bulto tiene 3 piedras?

De la posición p= 3 nos podemos mover a p = 2 retirando una piedra, y a p = 1 retirando dos piedras, ambas posiciones ganadoras para el próximo jugador a jugar, por lo tanto, p = 3 es perdedora.

Y si el bulto tuviera 4 piedras, ¿Cuántas piedras se podrían quitar?, ¿una o dos?. Si quitamos dos alcanzamos la posición p= 2 que es ganadora para el próximo jugador, y si quitamos una alcanzamos la posición p= 3 que es perdedora para el próximo jugador, así que la jugada óptima es quitar una sola piedra.

Entonces ya podemos definir dos conceptos importantes:

Posición ganadora (G): Una posición es ganadora, si de esta podemos movernos al menos a una posición perdedora.

Posición perdedora (P): Una posición es perdedora si de esta solo podemos movernos a posiciones ganadoras. Todos los estados terminales son posiciones perdedoras.

A partir de la segunda situación del juego de Nim visto anteriormente, podemos observar que:

n 0 1 2 3 4 5 6 7 8 9
Posición P G G P G G P G G P

 En esta tabla se puede ver el patrón PGG, y llegar a la siguiente conclusión:

Definiendo P(n) como la posición del juego en el estado n.

P(n) = P (perdedora) si n es divisible por 3.

P(n) = G (ganadora) si n no es divisible por 3.

Conclusiones

Hasta aquí hemos visto algunos conceptos fundamentales de la Teoría de Juegos, y cómo a veces podemos encontrar un patrón que se repita a lo largo del juego, lo que es conocido como invariante. Pero, ¿Qué sucedería si nos enfrentamos a un juego de Nim con varias pilas de piedra?, ¿Qué son los números Grundy y cómo nos pueden ayudar a ganar el juego de Nim?

Estos y otros temas serán abordados en el próximo artículo, por ahora es todo, no olvides dejar tu dudas y sugerencias en los comentarios.