Chinook (computer program)
Chinook is a computer program that plays checkers (also known as draughts). It was developed between the years 1989 to 2007 at the University of Alberta, by a team led by Jonathan Schaeffer and consisting of Rob Lake, Paul Lu, Martin Bryant, and Norman Treloar. The program's algorithms include an opening book which is a library of opening moves from games played by checkers grandmasters; a deep search algorithm; a good move evaluation function; and an end-game database for all positions with eight pieces or fewer. All of Chinook's knowledge was programmed by its creators, rather than learned using an artificial intelligence system.
Man vs. Machine World Champion
[edit]In 1990 Chinook won the right to play in the human World Championship by being second to Marion Tinsley in the US Nationals. At first, the American Checkers Federation and English Draughts Association were against the participation of a computer in a human championship. When Tinsley resigned his title in protest, the ACF and EDA created the new title Man vs. Machine World Championship, and competition proceeded. Tinsley won with four wins to Chinook's two, with 33 draws.
In a 1994 rematch, Chinook was declared the Man-Machine World Champion in a match against Tinsley after six drawn games and Tinsley's withdrawal due to pancreatic cancer. This made Chinook the first computer program to win a world championship title in a competition against humans, but while Chinook became the world champion, it never defeated Tinsley, who was significantly superior to even his closest peers.[1]
In 1995, Chinook defended its man-machine title against Don Lafferty in a 32-game match. The final score was 1–0 with 31 draws for Chinook over Lafferty.[2] After the match, Jonathan Schaeffer decided not to let Chinook compete any more, but instead try to solve checkers. At the time it was rated at 2814 Elo. The solution was achieved, and the result published in 2007.[3][4]
Algorithm
[edit]Chinook's program algorithm includes an opening book, a library of opening moves from games played by grandmasters; a deep search algorithm; a good move evaluation function; and an end-game database for all positions with eight pieces or fewer. The linear handcrafted evaluation function considers several features of the game board, including piece count, kings count, trapped kings, turn, runaway checkers (unimpeded path to be kinged), and other minor factors. All of Chinook's knowledge was programmed by its creators, rather than learned with artificial intelligence.
Timeline
[edit]- 1997 - Jonathan Schaeffer writes a book about Chinook called One Jump Ahead: Challenging Human Supremacy in Checkers.[5] An updated version of the book was published November 2008.
- May 24, 2003 - Chinook completes its 10 piece database with 5 pieces on each side.[6]
- August 2, 2004 - The Chinook team announces that the tournament-opening in checkers called the White Doctor (10–14 22–18 12–16) is proven to be a draw.[7]
- January 18, 2006 - The Chinook team announces that the 09–13 21–17 05–09 opening is proven to be a draw.
- April 18, 2006 - The Chinook team announces that the 09–13 22–17 13–22 opening is proven to be a draw.
- March 10, 2007 - Jonathan Schaeffer announces (at the ACM SIGCSE 2007 conference) that a final solution to checkers is expected within 3–5 months.
- July 19, 2007 - The journal Science publishes Schaeffer's team's article "Checkers Is Solved", presenting their proof that the best a player can achieve playing against a player with perfect information is a draw.[3]
References
[edit]- ^ "1994 Chinook-Tinsley checkers match". Archived from the original on 2006-08-29.
- ^ "Details of the 1995 Man vs. Machine World Championship".
- ^ a b Schaeffer, J.; Burch, N.; Y. Björnsson; Kishimoto, A.; Müller, M.; Lake, R.; Lu, P.; Sutphen, S. (2007). "Checkers is Solved" (PDF). Science. 317 (5844): 1518–22. Bibcode:2007Sci...317.1518S. doi:10.1126/science.1144079. PMID 17641166. S2CID 10274228.
- ^ Schaeffer, J.; Björnsson, Y.; Burch, N.; Kishimoto, A.; Müller, M.; Lake, R.; Lu, P.; Sutphen, S. "Solving Checkers" (PDF). Proceedings of the 2005 International Joint Conferences on Artificial Intelligence Organization.
- ^ Schaeffer, Jonathan (1997). One Jump Ahead:: Challenging Human Supremacy in Checkers. Springer. ISBN 978-0-387-94930-7.
- ^ "Chinook home page". 24 June 2003. Archived from the original on 2003-06-24.
- ^ "Chinook home page". 30 September 2004. Archived from the original on 2004-09-30.