After his work for Bell Laboratories since 1928, mostly on vacuum tubes, including improvements of Radar during World War II, the distinguished electrical engineer Arthur Lee Samuel (1901-1990), became a professor of electrical engineering at the University of Illinois at Urbana–Champaign, where he initiated the ILLIAC project. ILLIAC (Illinois Automatic Computer) was a series of supercomputers, built at a variety of locations. In 1949, Samuel left the University before its first computer was complete, and joined IBM's Poughkeepsie Laboratory in New York, where he would conceive and carry out his most successful work. Samuel is credited with one of the first software hash tables, and influencing early research in using transistors for computers at IBM. There he also continued his seminal research on machine learning.
Still in Illinois, working on ILLIAC, Samuel and his team stumbled upon a problem—by the end of 1948 the project was running out of money. Someone suggested that in order to attract attention they should build a cut down machine and do something "dramatic" with it. Samuel had heard about Claude Shannon's work on programming a computer to play chess and he decided that the thing to do was to program his machine to play checkers (draughts), because it is relatively simple, but has a depth of strategy. He reasoned that if Shannon had already done it for chess: it ought to be dead easy to program a computer to play checkers. Samuel's idea was partly motivated by the fact that the world championships was to be held in a neighboring town. The idea was presumably that they would produce a computer that would win.
So Samuel started to write a program safe in the knowledge that it had all be done before, but actually it hadn't. Claude Shannon had just talked about it all in the most general terms and hadn't got anywhere near a computer. In the beginning of 1949 Samuel made a trip to Chicago to talk to Shannon where he discovered the terrible truth. Undaunted, he decided that checkers had been a good choice after all and set about the programming: I started writing a program for a machine that did not exist, using a set of computer instructions that I dreamed up as they were needed.
Samuel soon realized that the small demonstration machine was going to be as complex as the real thing and running out of money was inevitable. Moreover, not being able to pursue computers drove him to seek a new job at a better salary. Thus by the spring of 1949 he moved to IBM at Ploughkeepsie.
In Poughkeepsie, while working on IBM's first stored program computer, the 701, Samuel found himself talking with one of the chief designers of the computer, about the word size that should be used—32 or 36 bits. Then he started to ask himself which would be better for his checkers playing program and, to find out, he started to write it again but using the instruction set of the unfinished 701. Later Samuel realized that teaching computers to play games is very fruitful for developing tactics appropriate to general problems—I became so intrigued with this general problem of writing a program that would appear to exhibit intelligence that it was to occupy my thoughts during almost every free moment for the entire duration of my employment by IBM and indeed for some years beyond. The main driver of the machine was a search tree of the board positions reachable from the current state.
Samuel was the first person to do any serious programming on the 701 and as such had no system utilities to call on. In particular he had no assembler and had to write everything using the op codes and addresses. As he had only a very limited amount of available computer memory, he implemented what is now called alpha-beta pruning. Instead of searching each path until it came to the game's conclusion, Samuel developed a scoring function based on the position of the board at any given time, which tried to measure the chance of winning for each side at the given position. The function took into account such things as the number of pieces on each side, the number of kings, and the proximity of pieces to being kinged.
The program chose its move based on a minimax strategy, meaning it made the move that optimized the value of this function, assuming that the opponent was trying to optimize the value of the same function from its point of view.
Arthur Samuel plays checkers with an IBM 704 computer in Poughkeepsie, New York
Possessing great creativity and essentially working alone, doing his own programming, Arthur Samuel also designed various mechanisms by which his program could improve its skills. In what he called rote learning (or generalization learning), the program remembered every position it had already seen, along with the terminal value of the reward function. This technique effectively extended the search depth at each of these positions. He also used underlying techniques as mutable evaluation functions, hill climbing, and signature tables.
Eventually the 701 was built and it incorporated some changes to the instruction set suggested by Samuel as the result of his work on checkers. Being the first really large non-numerical program it influenced the instruction set of all subsequent IBM machines. As Samuel was frightened that the machine might never be completed or that it might be radically changed, he wrote the checkers program as a set of small self-contained modules loaded by a central module—a sort of primitive operating system. He got it all to run on the first experimental model of the 701.
Later programs reevaluated the reward function based on input from professional gamers. Samuel also had it play thousands of games against itself as another way of learning. With all of this work, his program reached a respectable amateur status, and was the first to play any board game at this high a level. After his retirement from IBM in 1966, Samuel continued to work on checkers until the mid-1970s, at which point his program achieved sufficient skill to challenge a respectable amateur.
Arthur Samuel plays checkers with an IBM computer
Samuel completed his first checker program on the IBM 701, and when it was about to be demonstrated, Thomas J. Watson, Sr., the founder and president of IBM, remarked that the demonstration would raise the price of IBM stock by 15 points. It really did. Samuel was eventually put in charge of a pure research effort after persuading the Watsons that IBM needed to do pure research and not just product development.