Checkers, the ancient game which was quite easy to learn, has been solved. Along with other classical games, such as Connect Four and Qubic, the game has been pronounced dead. It was killed by Jonathan Schaeffer, who made the computer checkers program ‘Chinook’. Besides that, he publicated, “Checkers is solved’, which is a mathematical proof showing that the game always results in a draw when neither player makes a mistake.
Checkers; how to play it
More than 150 documented different variations of Checkers exist. Of those 150, only two versions have a large international playing community, namely ‘checkers/draughts’ and ‘international checkers’. The first one is commonly played in the United States and the British Commonwealth. It is played on an 8×8 board, where checkers can only move one square forward and captures take place by jumping over an opposing piece. Players are allowed to jump multiple pieces in one move. Besides that, checkers can promote to kings when they reach the last rank of the board. These kings can then move one square in any direction. The second variant ‘international checkers’, is the version we know in the Netherlands. Here, a 10×10 board is used. Moreover, checkers are allowed to capture backwards and kings can move more than one square in any direction. Schaeffer restricted its research to the North American variant ‘draughts’. Nevertheless, many of his ideas could also be applied to the version we know in the Netherlands, with the 10×10 board.
The idea
Schaeffer started out as a competitive chess player in his early 20s. Besides having a strength in chess, he had also done a Ph.D. in computer science. The combination of these made him decide to build a chess-playing computer program and named it Phoenix. However, this idea failed massively, since at that time better chess software was already created. On the other side, after this misfortune Schaeffer tried out his colleague’s suggestion to take a shot at checkers, which resulted in the checkers program ‘Chinook’.
Chinook
Chinook was developed at the University of Alberta in 1989. In the 1990s, the program had earned its place in the World Checkers Championship, as the first computer program. At that time, the program was not yet perfected. This became clear when, after reaching the final round, the program had to play against the world champion Marion Tinsley. This world champion is widely regarded as the greatest Checkers player ever, having lost only 9 games in his 45-year playing career. Unfortunately, the checkers program failed to beat Tinsley in the Man-Machine World Championship. Two years later, a rematch took place. Here, after six games that resulted in a draw, Tinsley resigned the match and the title due to health concerns. This meant that Chinook had became the first checkers program in history to win a human world championship. To get rid of the ghost of Tinsley, Schaeffer worked obsessively on building the perfect checkers program for 1994 until 2007. The revamped Chinook, which is now available online, is unbeatable.
How it works
The checkers program was built with machine learning. Schaeffer’s software contained two core components. The first one is a dataset of complete computations of every possible checkers position with a certain (small) number of pieces on the board. He started out with the data for six pieces left, then gained data on seven, then eight pieces left. This made Chinook better and better. However, the number of potential moves is massive, there are about $5 \cdot 10^{20}$ possibilities. The second part of the system is that Chinook needs to search through all possible moves, beginning with the start of the match. Back at the first tries, Chinook could only look ahead fourteen to fifteen moves ahead. Yet, as time moved on, computers and software improved and it could predict more and more moves.
The proof
In 2007, Schaeffer finally completed his work. After 19 years of research and $10^{14}$ calculations, he announced in Science that he had solved the game. Even though he had only found sequence for 19 out of the 300 opening moves, this was all that was needed. It shows that if a game is played without any mistakes, the game always amounts to a draw. If you’re now interested to play against the World Man-Machine Checkers Champion, you can do so here: http://webdocs.cs.ualberta.ca/~chinook/.
Source:
Scheaffer, J., Burch, N., Björnsson, Y., Kishimoto, A., Müller, M., Lake, R., … Sutphen, S. (2007). Checkers is solved. Science, 317(5844), 1518–1522. https://doi.org/10.1126/science.1144079
This article was written by Deirdre Westenbrink
