Chinook (draughts player)
Encyclopedia
Chinook is a computer program that plays English draughts
(also known as checkers), developed around 1989 at the University of Alberta
, led by Jonathan Schaeffer
. Other developers are Rob Lake, Paul Lu, Martin Bryant
, and Norman Treloar. In July 2007, Chinook's developers announced that the program has been improved to the point where it cannot lose a game.
to win the world champion title in a competition against humans. In 1990 it 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 rematch, Chinook was declared the Man-Machine World Champion in checkers in 1994 in a match against Marion Tinsley after six drawn games, and Tinsley's withdrawal due to pancreatic cancer. While Chinook became the world champion, it had never defeated the best checkers player of all time, Tinsley, who was significantly superior to even his closest peer.
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. After the match, Jonathan Schaeffer decided not to let Chinook compete any more, but instead try to solve checkers. It was rated at 2814.
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
.
On May 24, 2003, Chinook completed its 10 piece database with 5 pieces on each side.
On August 2, 2004, the Chinook team announced that the tournament opening in English draughts called the White Doctor (10-14 22-18 12-16) has proven to be a draw.
On January 18, 2006, the Chinook team announced that the 09-13 21-17 05-09 opening has been proven to be a draw.
On April 18, 2006, the Chinook team announced that the 09-13 22-17 13-22 opening has been proven to be a draw.
On March 10, 2007, Jonathan Schaeffer announced (at the ACM
SIGCSE
2007 conference) that a final solution to checkers was expected within 3-5 months.
On July 19, 2007, the journal Science
published Schaeffer's team's article "Checkers Is Solved", presenting their proof that the best a player playing against Chinook can achieve is a draw.
English draughts
English draughts or checkers , also called American checkers or straight checkers or in Israel damka, is a form of draughts board game. Unlike international draughts, it is played on an eight by eight squared board with twelve pieces on each side...
(also known as checkers), developed around 1989 at the University of Alberta
University of Alberta
The University of Alberta is a public research university located in Edmonton, Alberta, Canada. Founded in 1908 by Alexander Cameron Rutherford, the first premier of Alberta and Henry Marshall Tory, its first president, it is widely recognized as one of the best universities in Canada...
, led by Jonathan Schaeffer
Jonathan Schaeffer
Jonathan Herbert Schaeffer is a Canadian researcher and professor at the University of Alberta and the Canada Research Chair in Artificial Intelligence....
. Other developers are Rob Lake, Paul Lu, Martin Bryant
Martin Bryant (programmer)
Martin Bryant is a British computer programmer known as the author of Colossus Chess, a 1980s commercial chess-playing program, and Colossus Draughts, gold medal winner at the 2nd Computer Olympiad in 1990.- Computer chess :...
, and Norman Treloar. In July 2007, Chinook's developers announced that the program has been improved to the point where it cannot lose a game.
Man vs. Machine World Champion
Chinook is the first computer programComputer program
A computer program is a sequence of instructions written to perform a specified task with a computer. A computer requires programs to function, typically executing the program's instructions in a central processor. The program has an executable form that the computer can use directly to execute...
to win the world champion title in a competition against humans. In 1990 it won the right to play in the human World Championship by being second to Marion Tinsley
Marion Tinsley
Marion Tinsley is considered the greatest checkers player who ever lived. He was world champion from 1955–1958 and 1975–1991. Tinsley never lost a World Championship match, and lost only seven games in his entire 45 year career...
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 rematch, Chinook was declared the Man-Machine World Champion in checkers in 1994 in a match against Marion Tinsley after six drawn games, and Tinsley's withdrawal due to pancreatic cancer. While Chinook became the world champion, it had never defeated the best checkers player of all time, Tinsley, who was significantly superior to even his closest peer.
In 1995, Chinook defended its man-machine title against Don Lafferty
Don Lafferty
Don Lafferty was a Grandmaster checkers player. In 1982 he defeated Derek Oldbury for the World GAYP championship with a score of 1-0-23. He was challenged for the championship in 1984 by Paul Davis, winning easily 5-0-15...
in a 32 game match. The final score was 1-0 with 31 draws for Chinook over Lafferty. After the match, Jonathan Schaeffer decided not to let Chinook compete any more, but instead try to solve checkers. It was rated at 2814.
Algorithm
Chinook's program algorithmAlgorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
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
Artificial intelligence
Artificial intelligence is the intelligence of machines and the branch of computer science that aims to create it. AI textbooks define the field as "the study and design of intelligent agents" where an intelligent agent is a system that perceives its environment and takes actions that maximize its...
.
Timeline
Jonathan Schaeffer wrote a book about Chinook called One Jump Ahead: Challenging Human Supremacy in Checkers, in 1997. An updated version of the book was published November 2008.On May 24, 2003, Chinook completed its 10 piece database with 5 pieces on each side.
On August 2, 2004, the Chinook team announced that the tournament opening in English draughts called the White Doctor (10-14 22-18 12-16) has proven to be a draw.
On January 18, 2006, the Chinook team announced that the 09-13 21-17 05-09 opening has been proven to be a draw.
On April 18, 2006, the Chinook team announced that the 09-13 22-17 13-22 opening has been proven to be a draw.
On March 10, 2007, Jonathan Schaeffer announced (at the ACM
Association for Computing Machinery
The Association for Computing Machinery is a learned society for computing. It was founded in 1947 as the world's first scientific and educational computing society. Its membership is more than 92,000 as of 2009...
SIGCSE
SIGCSE
SIGCSE is the Association for Computing Machinery's Special Interest Group on Computer Science Education, which provides a forum for educators to discuss issues related to the development, implementation, and/or evaluation of computing programs, curricula, and courses, as well as syllabi,...
2007 conference) that a final solution to checkers was expected within 3-5 months.
On July 19, 2007, the journal Science
Science (journal)
Science is the academic journal of the American Association for the Advancement of Science and is one of the world's top scientific journals....
published Schaeffer's team's article "Checkers Is Solved", presenting their proof that the best a player playing against Chinook can achieve is a draw.