Chinook es un programa de computadora que juega a las damas (también conocido como borradores). Fue desarrollado entre los años 1989 a 2007 en la Universidad de Alberta , por un equipo liderado por Jonathan Schaeffer y formado por Rob Lake , Paul Lu , Martin Bryant y Norman Treloar . Los algoritmos del programa incluyen un libro de apertura que es una biblioteca de movimientos de apertura de juegos jugados por grandes maestros de damas; un algoritmo de búsqueda profunda; una buena función de evaluación de movimientos; y una base de datos de final de juego para todas las posiciones con ocho piezas o menos. Todo el conocimiento de Chinook fue programado por sus creadores, en lugar de aprendido usando unsistema de inteligencia artificial .
Campeón mundial de hombre contra máquina
Chinook es el primer programa de computadora en ganar el título de campeón mundial en una competencia contra humanos. En 1990 ganó el derecho a jugar en el Campeonato Mundial de humanos al quedar segundo detrás de Marion Tinsley en las Nacionales de Estados Unidos. Al principio, la American Checkers Federation y la English Drafts Association estaban en contra de la participación de una computadora en un campeonato humano. Cuando Tinsley renunció a su título en protesta, la ACF y la EDA crearon el nuevo título de Campeonato Mundial Hombre vs. Máquina , y la competencia continuó. Tinsley ganó con cuatro victorias frente a las dos de Chinook, con 33 empates.
En una revancha, Chinook fue declarado Campeón Mundial Hombre-Máquina en damas en 1994 en un partido contra Marion Tinsley después de seis juegos empatados y la retirada de Tinsley debido a un cáncer de páncreas. Aunque Chinook se convirtió en el campeón mundial, nunca derrotó al mejor jugador de damas de todos los tiempos, Tinsley, quien era significativamente superior incluso a su compañero más cercano. [1]
En 1995, Chinook defendió su título de hombre-máquina contra Don Lafferty en un partido de 32 juegos. La puntuación final fue 1-0 con 31 empates para Chinook sobre Lafferty. [2] Después del combate, Jonathan Schaeffer decidió no dejar que Chinook compitiera más, sino intentar resolver las damas. En ese momento tenía una calificación de 2814 Elo . La solución se logró y el resultado se publicó en 2007. [3] [4]
Algoritmo
El algoritmo del programa de Chinook incluye un libro de apertura, una biblioteca de movimientos de apertura de juegos jugados por grandes maestros; un algoritmo de búsqueda profunda; una buena función de evaluación de movimientos; y una base de datos de final de juego para todas las posiciones con ocho piezas o menos. La función de evaluación lineal hecha a mano considera varias características del tablero de juego, incluido el recuento de piezas, el recuento de reyes, los reyes atrapados, el turno, las damas fugitivas (camino sin obstáculos para ser kinged) y otros factores menores. Todo el conocimiento de Chinook fue programado por sus creadores, en lugar de aprendido con inteligencia artificial.
Cronología
- 1997 - Jonathan Schaeffer escribe un libro sobre Chinook llamado One Jump Ahead: Challenging Human Supremacy in Checkers . [5] En noviembre de 2008 se publicó una versión actualizada del libro.
- 24 de mayo de 2003 - Chinook completa su base de datos de 10 piezas con 5 piezas en cada lado. [6]
- 2 de agosto de 2004 - El equipo Chinook anuncia que la apertura del torneo en damas llamado White Doctor (10-14 22-18 12-16) ha demostrado ser un empate. [7]
- 18 de enero de 2006 - El equipo Chinook anuncia que la apertura 09-13 21-17 05-09 ha demostrado ser un empate.
- 18 de abril de 2006 - El equipo Chinook anuncia que la apertura 09-13 22-17 13-22 ha demostrado ser un empate.
- 10 de marzo de 2007 - Jonathan Schaeffer anuncia (en la conferencia ACM SIGCSE 2007) que se espera una solución final para las damas dentro de 3-5 meses.
- 19 de julio de 2007 - La revista Science publica el artículo del equipo de Schaeffer "Checkers Is Solved", presentando su prueba de que lo mejor que puede lograr un jugador jugando contra un jugador con información perfecta es un empate. [8]
Referencias
- ^ Partido de damas Chinook-Tinsley 1994
- ↑ Detalles del Campeonato Mundial Hombre vs.Máquina de 1995
- ^ Schaeffer, J .; Burch, N .; Y. Björnsson; Kishimoto, A .; Müller, M .; Lake, R .; Lu, P .; Sutphen, S. (2007). "Damas se resuelve" (PDF) . Ciencia . 317 (5844): 1518–22. doi : 10.1126 / science.1144079 . PMID 17641166 .
- ^ Schaeffer, J .; Björnsson, Y .; Burch, N .; Kishimoto, A .; Müller, M .; Lake, R .; Lu, P .; Sutphen, S. "Solving Checkers" (PDF) . Actas de las Conferencias Conjuntas Internacionales de 2005 sobre la Organización de Inteligencia Artificial .
- ^ Schaeffer, Jonathan (1997). Un salto adelante :: Desafiando la supremacía humana en damas . Saltador. ISBN 978-0-387-94930-7.
- ^ Página de inicio de Chinook, 24 de junio de 2003
- ^ Página de inicio de Chinook, 30 de septiembre de 2004
- ^ Schaeffer, J .; Burch, N .; Y. Björnsson; Kishimoto, A .; Müller, M .; Lake, R .; Lu, P .; Sutphen, S. (2007). "Damas se resuelve" (PDF) . Ciencia . 317 (5844): 1518–22. doi : 10.1126 / science.1144079 . PMID 17641166 .