Los programas de damas son software informático diseñado para jugar al juego de mesa de damas, también conocido como draughts. Estos programas utilizan técnicas algorítmicas para evaluar posiciones, buscar movimientos óptimos y competir contra jugadores humanos u otras computadoras. El programa de damas más destacado es Chinook, desarrollado en la Universidad de Alberta (aunque el proyecto tenía su sede allí, no en Toronto) por un equipo liderado por Jonathan Schaeffer, que logró hitos históricos tanto en el juego competitivo como en la resolución del juego.
Chinook fue desarrollado entre 1989 y 2007 por un equipo de la Universidad de Alberta, compuesto por Jonathan Schaeffer, Rob Lake, Paul Lu, Martin Bryant y Norman Treloar. A diferencia de los enfoques modernos que dependen del aprendizaje automático, el conocimiento de Chinook fue completamente codificado a mano por sus creadores, utilizando técnicas tradicionales de inteligencia artificial como algoritmos de búsqueda y funciones de evaluación. Esta distinción resalta la evolución de la IA desde sistemas basados en reglas hasta métodos impulsados por datos.
Campeón Mundial Hombre vs. Máquina
En 1990, Chinook ganó el derecho a competir en el Campeonato Mundial humano al terminar segundo detrás de Marion Tinsley en los Nacionales de EE. UU. Inicialmente, la Federación Estadounidense de Damas y la Asociación Inglesa de Draughts se opusieron a la participación de computadoras en campeonatos humanos. Cuando Tinsley renunció a su título en protesta, estas organizaciones crearon el nuevo título de Campeonato Mundial Hombre vs. Máquina, permitiendo que la competencia continuara. Tinsley ganó el primer encuentro con cuatro victorias, dos derrotas y 33 empates.
Una revancha en 1994 resultó en que Chinook fuera declarado Campeón Mundial Hombre-Máquina después de seis juegos empatados, ya que Tinsley se retiró debido a cáncer de páncreas. Esto convirtió a Chinook en el primer programa de computadora en ganar un título de campeonato mundial contra humanos, aunque nunca derrotó a Tinsley, quien era significativamente superior incluso a sus rivales más cercanos. En 1995, Chinook defendió su título contra Don Lafferty en un encuentro de 32 juegos, ganando 1-0 con 31 empates. Después de esto, Schaeffer decidió detener el juego competitivo y centrarse en resolver las damas por completo.
Algoritmo
El algoritmo de Chinook comprendía cuatro componentes principales: un libro de aperturas que contenía movimientos de partidas de grandes maestros, un algoritmo de búsqueda profunda para explorar movimientos posibles, una función de evaluación de movimientos y una base de datos de finales que cubría todas las posiciones con ocho piezas o menos. La función de evaluación era una función lineal hecha a mano que consideraba características como el número de piezas, el número de reyes, reyes atrapados, turno y damas fugitivas (piezas con caminos despejados para convertirse en reyes). Todo el conocimiento fue programado por los creadores en lugar de aprendido, contrastando con sistemas de IA posteriores como los enfoques de DeepMind.
Cronología y Resolución de las Damas
Los hitos clave en el desarrollo de Chinook incluyen: 1997, cuando Schaeffer publicó el libro "One Jump Ahead: Challenging Human Supremacy in Checkers" (actualizado en noviembre de 2008); el 24 de mayo de 2003, cuando se completó la base de datos de 10 piezas (5 piezas por lado); y el 2 de agosto de 2004, cuando la apertura "Doctor Blanco" (10-14 22-18 12-16) se demostró como empate. Otras aperturas se demostraron como empates el 18 de enero de 2006 (09-13 21-17 05-09) y el 18 de abril de 2006 (09-13 22-17 13-22).
El 10 de marzo de 2007, Schaeffer anunció en la conferencia ACM SIGCSE que se esperaba una solución final en 3-5 meses. El 19 de julio de 2007, la revista Science publicó "Checkers Is Solved", demostrando que con juego perfecto, el mejor resultado es un empate. Esto convirtió a las damas en el primer juego de mesa importante en resolverse completamente, siguiendo trabajos anteriores en juegos más simples. En el momento de su pico competitivo, Chinook estaba clasificado con 2814 Elo.
Legado
El éxito de Chinook demostró el poder de las técnicas clásicas de IA, incluida la búsqueda profunda y la evaluación hecha a mano, antes del auge del aprendizaje profundo. Su solución de las damas sigue siendo un logro emblemático en la IA de juegos, comparable a los ajedrecistas por computadora como Deep Blue. Mientras que los programas modernos de damas podrían usar redes neuronales, el enfoque de Chinook influyó en investigaciones posteriores en teoría de juegos y resolución combinatoria de juegos, y sus métodos aún se estudian en cursos de IA en instituciones como Carnegie Mellon University y MIT CSAIL.