David Gale y el juego de Chomp: pudo ganar un Nobel, pero se murió antes

Todos los años por esta época alguien me pregunta por qué no existe el Nobel de Matemáticas. La mayoría ya sabe la respuesta, pero lo hace para recordarnos a los matemáticos que don Alfred se olvidó de nosotros. Sí, hay gente así. No voy a volver a contar esta historia porque ya lo contamos en esta casa. Hoy venimos a jugar conDavid Gale.

Gale nunca obtuvo el premio Nobel por una única razón: tuvo el mal gusto de morirse antes. Bien es verdad que dicho motivo se puede aplicar a todos los que no lo han conseguido, pero en su caso estuvo realmente cerca.

En 1962 escribió un artículo sobre el problema del matrimonio estable junto a Lloyd Shapley (sobre ello ya hablé en otra ocasión) que, dicho sea de paso, no sirve para asegurarle una buena elección de pareja para vivir felices comiendo perdices -o tofu si son veganos-, pero sí que tiene un montón de aplicaciones en áreas más mundanas como la economía.

Tanto es esto último verdad que a su colega Shapley le concedieron el Nobel de Economía 2012, cuatro años después de la muerte de Gale. Pobre. Pensándolo bien, no es que el bueno de David se muriera justo después de publicar su resultado: tardó 46 años en ello. El problema es que la Real Academia de las Ciencias Sueca no se dio mucha prisa: también tardaron 50 años en reconocer sus aportaciones.

Pero hoy tampoco quiero hablar de matrimonios, sino de otro de los campos que fascinaba a Gale: la teoría de juegos. Como Conway o a Nash, de los que ya hemos hablado aquí, a Gale le apasionaba la teoría de juegos. Suyo es, por ejemplo, un resultado sobre puntos de equilibrio que profundiza en problemas considerados por Nash. Pero tampoco vamos a hablar sobre resultados teóricos (bueno, puede que un poco sí) sino que os vamos a proponer un juego muy sencillo y sumamente interesante ideado por David Gale: el juego de Chomp.

¿Cómo se juega al Chomp?

Se trata de un juego para dos jugadores utilizando una tableta de chocolate rectangular. Cada jugador, por turno, señala una de las porciones, se la come y todas las situadas bajo ella y a su derecha. Ojo, la porción situada en la esquina superior izquierda está envenenada y el que se vea obligado a comerla pierde.

Un ejemplo sencillo de los comienzos de una partida se muestra en las siguientes figuras:

Inicio de la partida

Primera elección del jugador 

Primera elección del jugador 2

Segunda elección del jugador 1

Como se ve, el juego es finito (a lo más tiene tantos turnos como porciones tenga la tableta, no podemos jugar indefinidamente) y no puede acabar en empate (alguno se verá obligado a elegir la porción chunga). Con estas dos condiciones (finito y sin empate), y gracias a nuestro John Nash, sabemos que para este juego uno de los jugadores tiene siempre una estrategia ganadora: uno de los dos tiene movimientos que le garantizan ganar.

Vale. El problema está determinar quién tiene una estrategia ganadora y cuál es dicha estrategia. Lo apasionante de este juego, y que lo hace distinto a otros, es que sí se sabemos quién tiene dicha estrategia ganadora, pero no sabemos cuáles son los movimientos que tiene que realizar para ganar. Puede parecer absurdo, pero si siguen leyendo trataré de explicarles por qué ocurren ambos hechos que parecen contradictorios.

En primer lugar hay que aclarar que, en principio, cuál de los dos jugadores tenga la estrategia ganadora podría depender del tamaño de la tableta, ¿no?

Bueno, supongamos que tenemos una tableta de ciertas dimensiones NxM. Vamos a probar que es el primer jugador el que siempre tiene una estrategia ganadora. Supongamos que fuera el segundo jugador. En ese caso para cualquier movimiento del primero, el segundo siempre tendría un movimiento que le haría ganar.

Si, por ejemplo, el primer jugador toma solo la porción que está en la esquina inferior derecha (la opuesta a la porción envenenada), el segundo siempre le puede responder con algo que le va a conducir a la victoria: tomando una determinada porción KxL y a partir de allí, por cada jugada del primero, siempre podrá responder el segundo de tal forma que está garantizada su victoria.

La situación sería la siguiente antes de empezar

Inicio de la partida: el primer jugador se come la porción de abajo a la derecha:

El segundo aplica su estrategia ganadora ante ese movimiento, supongamos que sea comerse la porción que ocupa el lugar (3,6) empezando por abajo (esto es una simulación):

Y a partir de aquí, haga lo que haga el primero, el segundo siempre tiene un movimiento ganador.

Pero, un momento, ¡un momento! A esta posición se podría haber llegado con un movimiento del primer jugador, así que si el primero se comiera la porción (3,6), este sería un movimiento ganador para él y es lo que tendría que hacer en primer lugar. Por lo tanto, si el segundo jugador tuviera una estrategia ganadora, el primero también la tendría y eso es imposible.

Por lo tanto el único con estrategia ganadora es el primero. Vamos, que el que empieza, si sabe cómo hacerlo, siempre gana.

Ahora viene la mala noticia: como ya hemos comentado, nadie sabe cuál es esa estrategia. Naturalmente se han realizado simulaciones con ordenadores y se han llegado a encontrar pero para tabletas con relativamente pocas porciones...

Para terminar, existen naturalmente varias implementaciones de Chomp, puedes intentar esta online o esta otra para Android. Pero, ojo, cuidado que enganchan, me lo ha dicho una amiga.