Chinook is a computer program that plays the board game checkers (also known as draughts). Developed by a team at the University of Alberta led by computer scientist Jonathan Schaeffer, Chinook was designed to compete at the highest levels of human checkers. It achieved a historic milestone in 1994 by becoming the first computer program to win a world championship in a game of strategy against a human world champion, defeating Marion Tinsley. In 2007, the Chinook team announced that the program had effectively solved checkers, meaning that with perfect play from both sides, the game always results in a draw.
Chinook's development began in 1989 as a research project in artificial intelligence and game theory. The program uses a combination of search algorithms, evaluation functions, and an extensive opening book. Its success was built on the principles of minimax search with alpha-beta pruning, a technique that allows the program to explore millions of positions per second. The program was refined over several years, with significant improvements in its evaluation function and search efficiency.
World Championship Achievements
Chinook's most famous achievement came in 1990 when it earned the right to challenge for the world championship by finishing second in the U.S. National Checkers Championship, becoming the first computer to qualify for a human world title. In 1992, Chinook played a match against Marion Tinsley, the reigning world champion and widely considered the greatest checkers player of all time. The match ended in a draw after 40 games, with Tinsley retaining his title. In 1994, a rematch was held, but Tinsley withdrew after six games due to health reasons, and Chinook was declared the winner, making it the first computer program to hold a world championship in a board game.
Following Tinsley's retirement, Chinook defended its title in 1995 against Don Lafferty, winning the match. The program continued to compete in human tournaments but was eventually retired from competition after the 1996 season.
Solving Checkers
In 2007, the Chinook team published a paper in the journal Science announcing that they had solved checkers. The solution involved a massive computational effort that used a combination of retrograde analysis and search algorithms to prove that the game is a draw with perfect play. The team computed a database of all positions with up to 10 pieces on the board, which required approximately 10^14 calculations and took over 18 years of continuous computing time (using distributed computing). The result showed that from the standard starting position, checkers is a theoretical draw, meaning that neither player can force a win if both play optimally.
The solution of checkers was a landmark achievement in machine learning and game AI, as it was the largest game solved at the time, with a search space of about 5×10^20 possible positions. It demonstrated the power of combining search algorithms with large-scale computation, and it provided insights into the limits of human expertise in games.
Technical Approach
Chinook's architecture was based on a classic game-playing AI design. It used a depth-first search with alpha-beta pruning to evaluate positions, and it employed a sophisticated evaluation function that considered material, mobility, and positional advantages. The program also had a large opening book, containing millions of positions from expert play, and an endgame database that was built using retrograde analysis. The endgame database was crucial for the solving process, as it allowed the program to play perfectly in the late stages of the game.
For the solving effort, the team used a technique called "proof-number search" to guide the search toward positions that were most likely to be wins or losses. They also used a distributed computing network to process the billions of positions in the endgame database. The final solution was a proof that checkers is a draw, but the team also showed that if either player makes a mistake, the other can force a win.
Legacy and Impact
Chinook's success had a significant impact on the field of artificial intelligence and game research. It inspired subsequent efforts to solve other games, such as Connect Four (solved in 1988) and, later, the game of Go, which was tackled by programs like AlphaGo. Chinook also contributed to the development of techniques for solving games with large state spaces, and its approach has been applied to other combinatorial problems.
In addition to its technical contributions, Chinook raised philosophical questions about the nature of human versus machine intelligence. The program's victory over a human world champion was a precursor to later achievements in chess (Deep Blue in 1997) and Go (AlphaGo in 2016). Today, Chinook is remembered as a pioneering effort that demonstrated the potential of computers to master complex strategic games.
The Chinook project also led to the development of the Fhourstones benchmark, a test used to measure the performance of search algorithms. The program's code and databases have been made available for research purposes, and its legacy continues to influence the design of game-playing AI systems.