Checkers Program
A checkers program is software that plays checkers (draughts in British usage), and the line of such programs from the early 1950s to the present forms one of the longest continuous research threads in artificial intelligence, running from a learning experiment on an IBM mainframe to a complete mathematical solution of the game, published in 2007.
The first landmark was Arthur Samuel's series of programs at IBM, begun around 1952 and developed through the 1960s, which were among the earliest programs to improve their play through experience. Samuel started on early IBM computers, including the IBM 701, and had to be thrifty with memory and speed. The programs searched the game tree a few moves ahead using a minimax procedure with pruning, and scored positions with a polynomial of board features such as piece advantage, mobility and control of the center. Their distinctive trait was that the weights and stored positions were adjusted by the program itself: it memorized the values of positions it had already analyzed (rote learning) and tuned its evaluation by playing against altered copies of itself. Samuel reported the method in the 1959 paper Some Studies in Machine Learning Using the Game of Checkers, in the IBM Journal of Research and Development, with a follow-up in 1967 that used signature tables.
The most publicized event was the 1962 exhibition in which Samuel's program, running on an IBM 7094, beat Robert Nealey, a player billed as a master, a result that was widely reported as proof that machines could outthink people. The reality was more modest. Nealey was a strong amateur rather than a national or world champion, and the program lost to elite players in later matches. Still, it was a genuine first: a program with learned parameters beat a skilled human at a real game. The episode also began a pattern in which each artificial intelligence milestone is first overstated and then, as experts test the system harder, recalibrated.
The next great chapter came from the University of Alberta, where Jonathan Schaeffer and his team began the Chinook project in 1989, trading learning for scale: Chinook relied on deep alpha-beta search, a hand-built evaluation, an opening book assembled from expert play, and databases of endgame positions computed exhaustively. Its opponent in two famous matches was Marion Tinsley, widely regarded as the greatest checkers player in history, who lost very few games in some four decades of competition. Tinsley won the 1992 match against Chinook, and in the 1994 rematch he withdrew after a series of drawn games for health reasons and died in 1995. Chinook then held the man-machine title, and its team continued to extend the endgame databases.
Schaeffer's group published Checkers Is Solved in Science in 2007, announcing that the game had been weakly solved: with best play by both sides, the result is a draw. The search space is about five times ten to the twentieth power of legal positions, so the proof combined massive retrograde computation of endgames with a proof tree built from the standard opening positions, running over many years on many machines. Weakly solved means that a program can guarantee at least a draw from the starting position, and show how to answer any deviation; it does not mean that every position has been catalogued, which would be strongly solving. Misunderstanding this distinction, and assuming a solved game is a dead one, are the usual mistakes. Draughts variants, such as international draughts on a ten-by-ten board, remain unsolved and active.
Read checkers program as a two-act case study in AI methodology: Samuel showed that a program could learn its own evaluation from play, and Chinook showed that engineering and exhaustive search could go all the way to perfect play.