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.

Entradas de Microsiervos en Sin Vuelta de Hoja

La difícil y metódica optimización en el pequeño mundo de los ascensores
5 consejos para sacar mejor partido a tus gadgets sin agobiarte
Cómo limpiar el teléfono móvil y otros gadgets
Otra forma más de optimizar el embarque de pasajeros en los aviones
Otra forma –más segura– de pensar a la hora de escoger claves
Cómo acceder desde el móvil a páginas web abiertas en el ordenador
Cómo ganar tiempo a las horas del día
Cómo manejar el ordenador, las tabletas y el móvil cuidando la vista y el cuerpo al mismo tiempo
Nuestra paradójica y anumérica relación con los seguros
Cómo mantener ordenados los cables del escritorio de forma óptima
¿Cómo averiguar cuáles son realmente las mejores baterías AA? Comprobándolas todas
¿Hay sitio para una tercera opción en el mercado de los smartphones?
Evernote Web Clipper, para guardar “recortes” de páginas web cómodamente
Cómo evitar que los GPS de los móviles se “chupen” toda la batería
El móvil que sabe dónde estarás mañana con 20 metros de precisión
Algunos consejos para que tu equipaje sobreviva a tu próximo viaje
Apps para aplicar la técnica Pomodoro de administración del tiempo de trabajo
Consejos para no perder los gadgets… e incluso encontrarlos si se pierden
Los consumidores y sus peculiares querencias numéricas
Cómo disponer de conexión a Internet también en vacaciones
Mucho ojito con esos ofertones de garantías extendidas
Los mercados financieros, las supersticiones y otros métodos raros de ganar dinero en bolsa
Robar bancos no es un crimen que compense, matemáticamente hablando
Usa tu smartphone para ayudarte a mantenerte en forma
Organiza la pantalla del móvil de forma óptima y cómoda
Las redes del metro son óptimas y parecidas en todas partes del mundo
Consejos para ser más productivo con el teléfono móvil
No vayas de compras sin tu móvil
Una tienda de ropa muestra en las perchas el número de “Me gusta” que reciben sus prendas en Facebook
Cómo evitar estresarse delante del ordenador
Cómo elegir la mejor fecha para comprar billetes de avión, cine o las mejores rebajas, matemáticamente hablando
Las matemáticas del aparcamiento: una cuestión de estadística y lógica
Evernote, para no olvidarte nunca de nada
Formas de identificar gadgets y otros objetos, por si los pierdes
Cómo calcular distancias de rutas a pie o en bici sin necesidad de un GPS
Cómo elegir la cola más eficiente en las tiendas, una cuestión matemática
Algunos consejos para pasar por el aeropuerto y no morir en el intento
Cuatro trucos de Internet interesantes para quienes las palabras son lo más importante
Cómo guardar fácilmente múltiples páginas en el navegador web
Cómo rellenar formularios web sin tocar el ratón
Cómo encontrar sin problemas el coche perdido en un parking
Cómo organizar una colección de fotos (y vídeos) digitales
Cómo hacer mejores fotos con la cámara del móvil
Siete consejos de sentido común relacionados con las contraseñas del ordenador
Cómo conseguir gasolina al mejor precio gracias a Internet
Cómo ahorrar en cualquier compra evitando el truco psicológico del precio escandalosamente alto
Cinco servicios de disco duro virtual gratis

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos necesarios están marcados *

Puedes usar las siguientes etiquetas y atributos HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

*