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.

Piedra, papel, tijera, teoría de juegos y cómo la vida imita a los Simpson (XV)

Todos conocemos el viejo juego de piedra, papel o tijera (PPT). Para los que saben teoría de juegos, es bastante fácil e intuitivo mostrar que el juego tiene un único equilibrio de Nash en estrategias mixtas que consiste en jugar cada alternativa con probabilidad 1/3 (este video lo explica brevemente).

Pero todo en la vida se complica. La semana pasada, leía en Futility Closet acerca de un viejo artículo de la revista New Scientist que afirmaba que en realidad hay una estrategia ideal y es comenzar jugando tijera. La explicación a esto es que, supuestamente, la piedra es la elección más popular de manera que la mayoría de la gente espera que su oponente comience con piedra, por lo cual elegirá comenzar jugando papel. Así, uno debería jugar tijera para ganar. Entiendo que esto aplica a la primera jugada en caso de que el juego se repita.

Lamentablemente, el artículo original requiere suscripción, pero la evidencia mencionada en los periódicos que la levantaron es de nada más y nada menos que ¡una observación! En 2005, las subastadoras Christie's y Sotheby's tuvieron que jugar piedra, papel o tijera para ganar el derecho a subastar la colección de un japonés. Cuenta la leyenda que la hija del CEO de Christie's reprodujo a su padre la historia que acabo de contar y este ganó jugando tijera. Creer que esto representa evidencia alguna de que conviene elegir tijera es dejarse engañar por el azar.

El argumento se cae rápido. Vamos de nuevo: dijimos que si el otro espera que yo juegue piedra, va a jugar papel, por lo que me conviene jugar tijera. Pero no hay motivo para que el otro no esté haciendo el mismo razonamiento, de manera que espere que yo juegue tijera, por lo cual le conviene elegir piedra. Sabiendo que mi oponente piensa esto, a mí entonces me conviene jugar papel, por lo que mi oponente debería elegir tijera. Y así podemos seguir hasta el infinito. Este razonamiento es similar al del famoso problema del concurso de belleza que popularizara Keynes y que, en el contexto de la teoría de juegos, descansa sobre el supuesto del conocimiento común de la racionalidad: ambos jugadores son racionales, saben que el rival es racional, saben que el rival sabe que él es racional y así sucesivamente.

Desde la práctica, este paper estudia la dinámica de un juego repetido de PPT. Después de 300 rondas entre seis sujetos, estos jugaron piedra el 32,2% de las veces, papel el 35,6% y tijera el 32,2%. Es decir, estuvieron bastante cerca de un tercio cada una. Curiosamente, la que se juega más que las otras dos es papel, sugiriendo que habría que jugar más tijera pero es una diferencia pequeña (y el paper no calcula su significatividad estadística).

Así y todo, hay un argumento a favor de "la hipótesis de la piedra". En realidad no es a favor suyo específicamente sino más bien de la posibilidad de que exista algo así y es el hecho de que el conocimiento común de la racionalidad no siempre existe. Esto se comprobó en otro conocido juego: el de adivinar dos tercios del promedio. En este, se invita a los participantes a decir un número entre 0 y 100 bajo la regla de que el ganador será quien acierte los 2/3 del promedio de todas las respuestas. Ante un empate, el premio se reparte en partes iguales entre todos los ganadores. Es fácil mostrar que a todos los participantes les conviene decir cero (y que entonces todos ganan y se reparten el premio). Ningún número mayor a 66,67 (dos tercios de 100) puede ser 2/3 del promedio de las respuestas (ya que 66,67 lo es si todos responden 100), por lo tanto, nadie debería entregar un número mayor a ese. Partiendo de esto y repitiendo el mismo razonamiento, ningún número mayor a 44,44 (dos tercios de 66,67) puede ser el promedio de las respuestas así que nadie debería responder algo mayor a eso. El proceso continúa hasta converger a cero. Sin embargo, en la realidad eso no ocurre. Un diario danés realizó este concurso y entre algo menos de 20.000 respuestas, los 2/3 del promedio resultaron ser iguales a 21,6. En una clase en la UBA, con unas 80 personas, un profesor intentó el experimento y el resultado fue algo así como 12, todavía lejos de cero. ¿Qué nos dice esto? La interpretación de estos resultados es que no hay conocimiento común de la racionalidad. Esto es, los participantes no creen que los demás sigan el proceso mencionado hasta responder cero y por lo tanto no responden cero. En PPT, esto equivaldría a que la gente no crea que los demás estén haciendo aquel razonamiento ad infinitum que describíamos más arriba y que esté decidiendo según alguna otra regla. Sin embargo, de eso no se desprende que necesariamente estén pensando en jugar papel.

Lo que queda entonces es algún otro componente psicológico en el juego. En este artículo sobre un torneo escolar de PPT, por ejemplo, un muchacho dice que los jugadores más agresivos juegan piedra más a menudo, aunque es algo meramente anecdotal. Así, limitándome a lo poco que sé hasta el momento, debo decir que la "hipótesis de la piedra" parece tener poco sustento. Por supuesto, siempre se me puede estar escapando algo.

Para terminar, ¿qué tiene que ver todo esto con los Simpson? Resulta que en el viejo capítulo en el que Bart y Lisa escriben episodios de Tomy y Daly, deciden cuál de sus nombres irá primero en el guión con un match de PPT. Curiosamente, Lisa sabe que Bart siempre elige piedra.

Arte arte arte!

Dibujando el INDEK con Guillermo

Les dejo un divertido juego en flash. Personificá al secretario Guillermo y bajá el índice de inflación a las patadas. ¡No dudes en "disuadir" a Doña Rosa! Cualquier semejanza con la realidad no es pura Koincidencia.