WAITS: Arthur Samuel's Checkers

Samuel playing against the IBM 7090. Source: IBM

Arthur Samuel started out working on vacuum tubes at Bell Labs in the 1930s. In 1946 he became a professor at the University of Illinois. Wanting to get a computer for the university, he came up with a proposal to build one, and for it to run a program that could play checkers. He started planning for it on paper, but both it and the computer were not finished when he left in 1949 to work at IBM.

There his main role was on vacuum tubes and later transistors, but the problem of checkers still intrigued him. He worked on it using the IBM 70x series of machines - according to a letter to a computer magazine journalist in 1979, it was written initially in raw machine code as even an assembler was not available for the IBM machine yet. A first version was ready in 1952, but

It was not until 1954, with the advent of the IBM 704 that my program was able to play an interesting game. My contribution was to add learning to the program, and I believe that I can claim a first for this.

In 1956 the program was demonstrated on TV and caught the imagination of the public. Eventually it was able to play games at a level that could sometimes challenge a master player.

Using techniques such as minimax, alpha-beta pruning and rote learning, his work was influential in the early years of AI; Samuel was present at John McCarthy's 1956 Dartmouth workshop and his work was included in Feigenbaum and Feldman's seminal 1960s overview of AI, Computers and Thought.

He retired from IBM in 1966 and came to SAIL as a senior member of staff. Here he helped with many of the lab's projects, and also ported his IBM 7090 assembly program to PDP-10 assembly language. The version we have running today is from 1972.

Checkers running on WAITS. Source: Rupert Lane. License: CC0.

He picked it up again in 1976 due to interest from other researchers, and played against a team at Duke University who had a new program running on an IBM System/360. Two games were played, but not to completion due to the amount of CPU time needed. According to an account by Samuel:

it was believed that the Duke program had a possible win in both games. Subsequent analysis reveals that one of these games might still lead to a draw.

Also in 1977, he worked with the makers of the VideoBrain Family Console to develop a version of checkers for this early home computer. This was a cut-down version, as the system only had 1KB of RAM, but offered four different levels of difficulty. He also helped on the AI for the VideoBrain version of Reversi/Othello, Vice Versa.

VideoBrain checkers program and manual. Source (l) atariprotos.com (r) archive.org

The program can be run on any terminal type by typing R CHECKE. Type HELP (must be in upper case) to see a list of commands: you can enter initial board settings, adjust playing parameters and even have the computer play itself with the PS command.

By default, you are playing first (as black/red) and the computer second (as white/blue). You enter moves by typing the source and destination squares, using the standard notation where 1 is the bottom right position and 32 the top left.

Here I start the program and move from square 9 to square 13.

.R CHECKE

        26 JUL 74


1*      9 13

The program will then try to find the best move and print it, along with some statistics on the number of positions it searched, the best value of its evaluation function, and the time taken in milliseconds (so about 13s here, would have been much slower on real hardware)

        MOVE   # OF BDS    PIECE   EVAL   TIME

2       23-19    219956.       0     35  13567

so it has moved 23-19. You can type the instruction BD to display the board in ASCII:

3*     BD

* * * * * * * * * *
* + W + W + W + W *
* W + W + W + W + *
* + W +   + W + W *
*   + W +   +   + *
* +   +   +   + B *
* B + B + B +   + *
* + B + B + B + B *
* B + B + B + B + *
* * * * * * * * * *

But to make life easier, you can also use something like gametable in two player mode to record the moves; here's how the board would look like:

Playing checkers against CHECKE. Source: Rupert Lane. License: CC0.

If you type a nonsensical move it will print:

3*    99 66
SORRY CHARLIE!

I won't give a full account of the game, but by move 44 the program announced:

THE PDP-10 EXPECTS TO WIN IN 11 MOVES.
44      26-22     15171.   11 MOVE WIN.   1017

but my downfall occurred just three moves later. Here, FORCED is printed because by the game's rules if it can take an opposing piece it must.

45*    10 15
46      17-1          3.       FORCED        0
47*    15 18


        26 JUL 74


1*

The original IBM 7090 code is not publicly available as far as I am aware.

Samuel's directories on the WAITS system can be found on saildart.org. It's hard to tell what code matching the CHECKE binary from 1972, but CKP2.MAC[2,ALS] is the oldest file, dating back to 1971. Further enhancements - up to 1977 - can be found in [CH2,ALS] and sample game data in [CH3,ALS], [CH4,ALS] and [3,ALS].

The code shows evidence of it being a port of the IBM 7090 version, with translations into subroutines of some instruction where there was not an equivalent on the PDP-10 , eg CAQ.

The VideoBrain development directory is called F8. This includes several versions of the checkers source code along with a cross-assembler in Fortran, presumably written by Fairchild (who made the CPU in the VideoBrain). It's not clear how much was written by Samuel, and how much by his collaborators at VideoBrain. There is also some correspondence between Samuel and the makers of the Videobrain, with Samuel suggesting other games that could be produced and complaints about the unreliability pf the development hardware.

IBM's article The games that helped AI evolve is a first introduction to Samuel's work at the company on checkers and also discusses Tesauro's TD-Gammon program.

Samuel's original July 1959 paper, "Some Studies in Machine Learning Using the Game of Checkers", in IBM Journal of Research and Development, vol. 3, no. 3, pp. 210-229 is available for download at IEEExplore. The IEEE also has a memorial on Samuel's work.

Richard Sutton and Andrew Barto's book Reinforcement Learning: An Introduction is available in full online and has a case study on Samuel's checkers.

MAME has an emulator for the VideoBrain and copies of the game's cartridge ROM can be found online.

Another early checkers program was written by Christopher Strachey for the Ferranti Mark 1 in the early 1950s; there is an emulator that can run this.

I welcome any questions or comments, and also especially any corrections if I have got something wrong. Please email me at rupert@timereshared.com and I will add it here and update the main text.