El mejor contra el resto del mundo

Hoy se cumplen 12 años del comienzo de la partida de ajedrez que ostenta el incomprobable título de "la más analizada de la historia": Kasparov contra el mundo.

Organizada por el servicio de juegos en línea de Microsoft, esta partida enfrentó al número 1 del ranking mundial y uno de los mejores jugadores de la historia, Garry Kasparov (con blancas) al resto del mundo, esto es, a todo aquel que se registrara en un foro donde se podía votar por cada movida de las piezas negras. Los más de 50.000 participantes del resto del mundo recibieron sugerencias de cuatro grandes maestros.

Uno de los aspectos más curiosios de la partida fue que el resto del mundo eligió enfrentar a Kasparov con su defensa predilecta, la siciliana, a lo que el ruso contestó con una movida (3.Ab5+) que no es la más habitual y que sacó a la partida del cauce de muchas grandes batallas de Kasparov. Esto causó una gran desilusión en el público, al punto que, luego de terminada la partida, el campeón pidió disculpas por esa movida. Lo que se presume, es que intentó no mostrar su mejor repertorio, que quería guardar para sus partidas "por los puntos". Luego de esto, la partida se extendió hasta la movida 62, en la cual el resto del mundo abandonó al no poder evitar la coronación de un peón blanco. La partida terminó el 22 de octubre, cuatro meses y un día después de iniciada.

Así, el mejor resultó ser más que la suma de todos los demás. Cierto o no, tal vez por compromiso, Kasparov afirmó que fue la partida que más analizó. Y al día de hoy es la única partida a la que se le ha dedicado un libro entero. Asimismo, una pequeña polémica se desató cuando Kasparov admitió que leía el foro en el que la gente discutía la estrategia de las negras.

Tal vez hoy en día una partida así no tendría tanto sentido, dado que cualquier aficionado tiene acceso a los más potentes programas de análisis, con lo cual se daría poco más que una partida entre computadoras. En ese entonces, de una manera u otra, fue uno de los grandes eventos en la historia del ajedrez y también de internet.

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.

Jaque

Hay muchas cosas en las que el cine no es verosímil. Un ejemplo es que los personajes no se despiden al finalizar una conversación telefónica. Esto tiene una explicación lógica y es ahorrar tiempo. Pero hay una cosa que no tiene un motivo válido y los guionistas y directores necesitan entender: los ajedrecistas nunca, pero nunca, dicen "jaque" cuando dan jaque en una partida. En las películas lo hacen permanentemente y para alguien que juega al ajedrez queda ridículo. Esto me lo trajo a la mente la flojita "Revolver" de Guy Ritchie:

Aunque esta escena en particular no revela la trama, advierto que, desde ya, la ven a su propio riesgo.