El turno del ajedrez y Ernesto Zermelo

Desde hace tiempo, creo que el ajedrez es uno de los inventos más magníficos de la historia de la humanidad. Tal vez no sea algo tan útil como la rueda, la máquina de vapor o las computadoras, pero se trata de un juego fascinante, tanto desde lo técnico como desde lo estético. Además, el ajedrez tiene otro aspecto muy particular: el hecho de que, desde hace mucho, sabemos que tiene al menos una "estrategia ideal" pero no sabemos cuál es ni cuál es su resultado. Aquí hago el intento de contar la historia de esta última afirmación.

Había una vez, más precisamente en los albores del siglo XX, un matemático alemán llamado Ernst Zermelo, quien había hecho importantísimos aportes a la teoría de conjuntos. Algunos años después de sus principales trabajos, Zermelo buscó aplicar la teoría de conjuntos para formalizar la estructura de ciertos juegos, en particular aquellos donde dos jugadores se enfrentan por turnos y en ausencia de azar. El ajedrez es uno de los ejemplos más conocidos de este tipo de juego y se convirtió en el que tomó Zermelo.

La pregunta que Ernesto intentó contestar no fue "¿cuál es la mejor estrategia para jugar al ajedrez?" sino "dada una posición posible, ¿puede asignársele un valor determinado matemáticamente?". Para entender esta pregunta, piensen en esto: cualquiera que aprendió a jugar al ajedrez, resolvió alguna vez un problema del tipo "juegan las blancas y dan mate en dos movidas". Esa posición tiene un valor: con certeza ganan las blancas. Pues bien ¿puede asignarse ese valor a cualquier posición legal posible? En otras palabras, tomando una posición posible, ¿puede decirse que, o bien ganan las blancas, o bien ganan las negras, o bien es tablas (empate)? El trabajo de Zermelo, y de otros matemáticos posteriores, mostró que sí.

Zermelo. Con esos anteojos, no podía dedicarse a otra cosa.

La demostración creo que escapa a lo que la mayoría de los lectores de este blog pueden estar interesados en leer pero se puede encontrar en este breve paper (pdf) y también se resume aquí. El punto es que queda demostrado que, dada una posición cualquiera, está determinado si uno de los dos bandos puede forzar una victoria o bien ambos pueden forzar un empate (i.e. ambos pueden forzar no perder). Un caso particular de una posición cualquiera es la posición inicial del juego, claro está. Sin embargo, el ajedrez produce los resultados y posiciones más diversos. Esto implica la existencia de errores por parte de los jugadores. Y es así, el ajedrez es un juego de errores. Y como decía un profesor de ajderez que conocí, gana el que comete el anteúltimo error.

Ahora bien, ¿cómo es posible que hasta hoy, con el progreso de la informática, no hayamos podido responder la pregunta de cuál es la estrategia ideal y cuál es su resultado? Hoy por hoy, gracias a la teoría de juegos, sabemos incluso cuál es el procedimiento necesario para responder esta pregunta: algo que conocemos como inducción hacia atrás. El procedimiento consiste en partir de la posición final e ir retrocediendo mientras pensamos, a cada paso, cuál es la jugada óptima de cada jugador, hasta llegar a la posición inicial.

Pensemos en el siguiente ejemplo: hay 21 monedas iguales sobre una mesa. Hay dos jugadores y cada uno puede tomar una, dos o tres monedas por turno. Pierde el que se ve obligado a tomar la última moneda. Obviamente, la posición final del juego es con una moneda sobre la mesa y pierde el jugador al que le toca, ya que esta claro que si hay dos o tres, nadie va a agarrarlas todas y perder sino que agarrará una o dos, respectivamente, y ganará. Si hay cuatro, al que le toque tomará tres monedas y gana. De esta manera, es evidente que aquél que quede con cinco monedas sobre la mesa está perdido: no le queda otra que tomar al menos una y servirle la victoria al rival. Ahora bien, empezamos diciendo que si hay una moneda en la mesa y te toca, perdiste y llegamos a que si hay cinco y te toca, perdiste también. Repitiendo todo el razonamiento, llegamos a la conclusión de que si hay nueve monedas en la mesa y te toca, estás perdido: tu rival siempre tendrá la posibilidad de dejarte con cinco en su siguiente jugada. Repitiendo el razonamiento una vez más, podemos afirmar que está perdido el que juega con 13 monedas en la mesa, lo mismo con 17 y lo mismo con ¡21! Así, el jugador que debe comenzar está perdido y el que juega segundo siempre gana (si quieren, vean cómo, si cambiamos la regla a que gana el que agarra la última moneda, el resultado es el opuesto). Esto lo demostramos por inducción hacia atrás.

Quiero uno de estos.

Una condición clave para aplicar este razonamiento es que exista una posición final, esto es, que el juego sea finito (si no ¿desde dónde empezamos la inducción hacia atrás?). En el ajedrez, más allá del jaque mate, esto está garantizado por una regla que dice que la partida es tablas si se producen 50 movidas de cada jugador sin captura de piezas ni avance de peones.

Entonces ¿por qué no podemos hacer lo mismo con el ajedrez y encontrar la estrategia ideal? Bueno, como decía el protagonista de Don Segundo Sombra, una cosa es cantar solo y otra cosa es con guitarra. Volvamos al juego del párrafo anterior y pensemos una variante bastante conocida: se juega dibujando 21 palitos en un triángulo, formando filas de 1, 2, 3, 4, 5 y 6 palitos, respectivamente. Cada jugador puede eliminar cualquier cantidad de palitos, siempre que estén en la misma fila y sean contiguos. En este caso, hay 21 posiciones finales posibles ya que, por el curso del juego, no es trivial en cuál de los 21 palitos finaliza. Las monedas, en cambio, eran indistinguibles. Esto singifica que hay que hacer inducción hacia atrás desde las 21 posiciones finales posibles. Más aún, la cantidad de movidas posibles en cada jugada aumentó: antes eran siempre tres, ahora varía según la posición pero en la posición inicial, por ejemplo, hay 56 jugadas posibles. El problema se volvió mucho más complejo. Bueno, con el ajedrez pasa eso: ni siquiera tenemos idea de cuáles son todas las posiciones legales posibles. Como ejemplo absurdo, hasta la posición inicial es una posición final posible: se da si los jugadores mueven caballos desde y hacia la posición inicial 50 veces. Así, no podemos ni empezar a hacer inducción hacia atrás.

Claro que podríamos partir de la posición inicial y desde allí ir descubriendo todas las posiciones posibles, pero la complejidad del ajedrez es tal que aun hoy no tenemos la capacidad para hacerlo. Se estima que la cantidad posible de partidas es alrededor de 10^500 (un uno y quinientos ceros) y la cantidad de posiciones posibles es no más que este número, que es cercano a 2^155:

45193640626062205213735739171550309047984050718

Ah, además hay otro detalle, el teorema de Zermelo (que él nunca enuncio en los términos que conocemos hoy en día, pero que ha conservado su nombre) nos dice que hay al menos una estrategia ideal. Puede haber muchas, aunque claro que todas con el mismo resultado. Zermelo terminó su paper diciendo que, de responderse esta pregunta, el ajedrez perdería su carácter de juego. Hoy, casi 100 años después, sigue muy vivo.

Changos.