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>

*