Arthur Samuel's checkers program

What it was

Arthur Samuel's checkers program was a program that played checkers and, within limits, improved at it through play. It is remembered as a working demonstration that a computer can be programmed so that it learns to play a better game of checkers than the person who wrote the program^[2]. The program ran on the IBM 701, IBM's first commercial computer^[1].

Where it came from

Samuel went to IBM in Poughkeepsie, New York, in 1949, and it was there that he conceived and carried out the work^[1]. His machine-learning research began in 1949, while the checkers program is best known from 1959^[1]. He made the first checkers program on the IBM 701^[1].

How it learned

The published account describes two machine-learning procedures investigated in some detail using the game of checkers^[2].

The first Samuel called rote learning: the program remembered every position it had already seen, along with the terminal value of the reward function, which in effect extended the search depth at those positions^[1]. The second was self-play — the program played thousands of games against itself as another way of learning^[1]. His later programs reevaluated the reward function based on input from professional games^[1].

Scoring a position instead of playing it out

A game of checkers is long enough that following every path to its conclusion is impractical. Instead of searching each path to the game's conclusion, Samuel developed a scoring function based on the position of the board at any given time^[1]. That function measured the chance of winning for each side, taking into account the number of pieces, the number of kings and the proximity of pieces to being kinged^[1]. With it, the program could judge moves by the value of the positions they led to rather than by playing each line to the end.

Results

The program reached a respectable amateur status and was the first to play any board game at that high a level^[1]. Samuel continued working on checkers until the mid-1970s, when his program achieved sufficient skill to challenge a respectable amateur^[1].

The paper

"Some studies in machine learning using the game of checkers" by A. L. Samuel was published in the IBM Journal of Research and Development, Volume 3, Issue 3, pages 210 to 229, on 1 July 1959^[2]. The abstract says two machine-learning procedures had been investigated in some detail using the game of checkers^[2]. It also says enough work had been done to verify that a computer can be programmed so that it will learn to play a better game of checkers than can be played by the person who wrote the program, and that the program can learn to do this in 8 or 10 hours of machine-playing time when given only the rules of the game, a sense of direction and a redundant and incomplete list of parameters^[2].

Why it is remembered

Several of its parts look familiar today: an evaluation function that scores a position rather than searching to the end of the game, learning from games the program plays against itself, and a memory of positions already seen. What made the checkers program notable was that these pieces were fitted together and then measured. The claim in the paper is not that the program played perfectly, but that it played better than its author, and that it got there from the rules and a rough list of parameters rather than from instructions written out for every situation^[2].