Cómo optimizando, optimizando, se “resolvió” el juego de las damas

Tradicionales juegos de estrategia como el ajedrez, el go o las damas han sido siempre considerados “complicados” de dominar por los ordenadores. La razón es sencilla: con el transcurso de los movimientos del juego aumenta el número de combinaciones posibles de una forma tan exponencial y gigantesca. Pasado cierto punto es imposible examinarlas todas para decidir cuál es el mejor movimiento.

Sin embargo, las damas¹ son el juego más simple de todos ellos, matemáticamente hablando: el tablero es pequeño, hay un número de piezas razonable por jugador (12, aunque a veces coronen y se conviertan en damas) y las opciones de movimientos son bastante limitadas en cada jugada.

Del poder de esta optimización surgida al precalcular los resultados para una consulta rápida se dio cuenta Jonathan Schaeffer, de la Universidad de Alberta en Canadá. Teniendo todo lo anterior en cuenta se preguntó si no sería posible crear un software para jugar a las damas empezando las partidas por el final.

La técnica de Schaeffer funcionaba creciendo paso a paso: primero examinando qué sucedía cuando quedaban dos piezas una contra otra –en todas las posiciones posibles– luego dos piezas una contra otra, luego dos contra dos, etcétera.

Con esta optimización estaba creando una gigantesca base de datos de finales: posiciones en las que se podía consultar al instante si quien ganaba eran las blancas, las negras o si la partida acababa en tablas. Todo esto era posible porque esas jugadas ya se habían calculado antes y no había que hacerlo en tiempo real. Esta misma técnica se usa a veces en cuestiones de seguridad informática, por ejemplo para descifrar contraseñas “por fuerza bruta”, probando con todas las posibilidades -que en realidad ya se han “descifrado” antes y están en una gigantesca base de datos.

Una de las primeras bases de datos poderosas que completó era la de cinco-contra-cinco, un punto final de la partida en el que muchos humanos todavía tienen problemas para calcular qué puede suceder exactamente. Eso significaba que si en el tablero había seis piezas contra cinco y se podía llegar a alguna de las posiciones de la tabla, su destino estaba ya calculado y definido.

“Optimizando, optimizando” Schaeffer se pasó 18 años. Tiempo antes, con tablas incompletas y usando técnicas convencionales para juegos de este tipo similares a las del ajedrez, su programa Chinook había ganado a Marion Tinsley, mítico e invencible Campeón del Mundo hasta los 90.

Tras casi dos décadas y miles de horas de cómputo el juego de las damas estaba completamente analizado. El resumen cabe en una frase: “las blancas juegan y empatan“. Eso quiere decir que se puede jugar a no perder nunca -incluso hay una demo online– o puede interpretarse como que a menos que las blancas se equivoquen las negras nunca pueden ganar, como máximo hacer tablas. Eso es lo que aprendimos de ese examen completo de todas las combinaciones posibles del desarrollo del juego.

(1) Las damas existen en muchas variantes internacionales, pero el trabajo de este artículo se refiere a las conocidas “damas inglesas” en un tablero de 8×8, con 12 piezas por bando.

Add a Comment