Arthur Samuel's Legacy
Milestones | Arthur Samuel's Legacy
Arthur Samuel started developing his checkers program in the 1950s. In 1962, the program played a publicized match against Robert Nealey. The single win by Samuel’s program was an historic event, but over time the accomplishment became exaggerated. Samuel’s program was a monumental achievement for his day. Although the program never lived up to the billing that it received, the ideas that Samuel embodied in his program represented a milestone in artificial intelligence research. This work is still frequently cited in the scientific literature, over thirty years after the fact. Few can claim to have made such an enduring contribution.
This work led to the false impression that checkers was a “solved” game. As a result, researchers moved on to chess, and largely ignored checkers for over 25 years.
“Arthur Samuel (standing), IBM investigator of machines that learn,
watches a checker game between a human player and an electronic player
- a
large computer. The computer is about to win this game and type out: `Sorry,
you lose.’” John Pfeiffer, The Thinking Machine, J.B.
Lippincott Company, Philadelphia & NY, 1962.
The following text describes the historic game against Robert Nealey, and the long-term consequences of that game. It is quoted from One Jump Ahead: Challenging Human Supremacy at Checkers, Jonathan Schaeffer, Springer-Verlag, 1997:
It didn’t take long before Samuel had a program that played a respectable game of checkers, capable of easily defeating novice players. It was first publicly demonstrated on television on February 24, 1956. Thomas Watson, President of IBM, arranged for the program to be exhibited to shareholders. He predicted that it would result in a fifteen-point rise in the price of IBM stock. It did.
In 1961, Edward Feigenbaum and Julian Feldman were putting together their classic book Computers and Thought, the first compendium of artificial intelligence research. They asked Samuel to contribute a paper that included an appendix discussing the program’s best game of checkers. With this best-game motivation in mind, Samuel decided to have his program challenge a strong player to a series of games. The historical record is fuzzy, but for some reason he chose to have his program debut against Robert Nealey a blind checkers champion from Stamford, Connecticut. IBM’s Research News claimed that Nealey was “a former Connecticut checkers champion, and one of the nation’s foremost players.”
Although a self-proclaimed master, Nealey’s tournament results never justified such a claim. At the time of the game, he was not a former Connecticut state champion, although he did win the title in 1966, four years after the game with Samuel’s program. In the history of the state championship, no recognized master had won the event. Nealey didn’t play in any of the premier checkers events, such as the U.S. championship, and apparently acquired his reputation by beating local players.
For the record, here is the fateful game, played in 1962, with Samuel’s annotations in italics.
Black: Samuel Checkers program
White: R.W. Nealey
1. f6-e5 e3-f4 2. g7-f6 c3-b4 3. h8-g7 b4-a5 4. e5-d4 g3-h4 5. b6-c5 d2-e3 6. d6-e5 f4xd6 7. c7xe5 h2-g3 8. e5-f4 g3xe5 9. a7-b6 a5xc7 10. b8xd6xf4xd2 e1xc3xe5 11. f6xd4 c1-d2 12. g7-f6 b2-c3 13. d4xb2 a1xc3 14. f6-e5 f2-e3 15. e5-f4 e3xg5 16. h6xf4
The critical position. See Figure 10.
16. ... g1-f2
White makes a losing move.
This is an understatement! If there was any doubt about Nealey’s claim to be “one of the nation’s foremost players,” this single move lays that to rest. One of the most important principles in checkers is to leave men behind to guard the back rank. By removing his last rear guard, Nealey gives Black a king for free. In contrast, Black has a strong back rank, making it difficult for White to get a king. Chinook says the game was a draw until this blunder. With g1-f2, an eleven-ply search is sufficient for Chinook (circa 1995) to see all the way to the end of the game and announce a forced sequence of moves leading to a Black win. In contrast, h4-g5 is the only move that draws.
Figure 10. Nealey (White) plays g1-f2, a move that will live in infamy.
17. f4-g3
The obvious reply, guaranteeing Black a king.
17. ... f2-e3 18. g3-f2 c3-d4 19. f2-e1=k d4xb6 20. e1xc3 b6-a7 21. c3-d2
A delaying move to force White to advance.
21. ... e3-f4 22. d2-c3 f4-g5 23. c3-d4 a3-b4 24. d4-e3 b4-a5 25. d8-c7
Le coup de maître. A Black win is now certain.
Is it? It hasn’t been pointed out previously in the literature, but d8-c7 is a terrible blunder by Samuel’s program. By weakening the back row, Nealey can get a king and draw.
25. ... g5-f6
Tit for tat. Nealey doesn’t understand the position. Chinook says that with the strange-looking g5-h6 followed by a7-b8=k, White can draw (a7-b8=k first is a loss).
26. e7xg5 h4xf6 27. e3-f4
Le coup mortel. White concedes.
White can’t prevent the Black king from attacking and winning the immobile checker on f6. For example, if a7-b8=k, then f4-g5 b8xd6 g5xe7xc5.
All in all, this was an excellent debut for Samuel’s fledgling program. Nealey wrote of the encounter:
“Our game...did have its points. Up to [move 16], all of our play had been previously published, except where I evaded “the book” several times in a vain effort to throw the computer’s timing off. At the g1-f2 loser and onwards, all the play is original with us, so far as I have been able to find. It is very interesting to me to note that the computer had to make several [very good] moves in order to get the win, and that I had several opportunities to draw otherwise. That is why I kept the game going. The machine, therefore, played a perfect ending without one misstep. In the matter of the endgame, I have not had such competition from any human being since 1954, when I lost my last game.”
Needless to say, I completely disagree with most of what he wrote.
Wait! Hold the presses! A computer defeated a master checkers player! This was a major news story. Computers could solve the game of checkers. Mankind’s intellectual superiority was being challenged by electronic monsters. To the technology-illiterate public of 1962, this was a major event. It was a precursor to machines doing other intelligent things better than man. How long could it possibly be before computers would be smarter than man? After all, computers have only been around for a few years, and already rapid progress was being made in the fledgling computer field of artificial intelligence. Paranoia.
A rematch was organized the following year, and a description made at the time gives some insight into the program that had played the fateful game the previous year:
The match started last fall and lasted more than five months. Playing at his home, Nealey sat at a checkerboard and studied present positions in each of the six games. (Though he isn’t completely blind, he identifies the pieces by feel as much as by sight, largely playing with “my hands and my brains.”) After selecting his moves, Nealey typed them on a postcard—he’s a skilled touch-typist—and mailed them to the IBM Watson Research Center in Yorktown Heights, N.Y., where the computer is housed.
The machine probed to a depth of at least six and at most twenty moves ahead, depending on how thorough an analysis was required. In other words, it often had to compute thousands and tens of thousands of different positions before coming up with the best over-all score indicating its official move. Such feats, of course, are impossible for the human player. The [IBM] 7094 [computer] can do some 15 million additions or six million multiplications in a single minute, which is about as much arithmetic as a man at an ordinary adding machine could do in a year.
The computer often took only 10 or 20 seconds to select its move. (Such lightning-fast responses do not bother an opponent playing by mail, but they could be disconcerting in a face-to-face game.) Tough positions kept its transistorized circuits humming for as much as five minutes, although its average was about a minute. Nealey’s average time per move was about three minutes.
The final result was a win for Nealey, scoring one win and five draws. After the match, Nealey commented on his electronic opponent:
By sticking to its programmed instructions, it may find an extraordinary move that a man who is gifted imaginatively may never find. It knows so much and carries its analysis to such depths that it sometimes, by the beauty of its mathematics, comes up with a truly brilliant move. This is difficult to express, but I think the machine’s complete lack of imagination is its most formidable strength!
In 1966, Samuel took his program to the world championship match between Walter Hellman (defending champion, U.S.A.) and Derek Oldbury (England). IBM was a sponsor of the event, on the condition that the participants play some games with Samuel’s program. Four games were played against each opponent, with Samuel’s program losing all eight rather easily. The promise of the 1962 Nealey game was an illusion.
The legacy of Samuel’s program would haunt anyone who tried to use checkers as an experimental research test bed for decades to come. The perception that checkers is a “solved” game persists up to the present. Many scientific and popular publications continue to perpetuate the myth. A sample of the nonsense includes:
“...it seems safe to predict that within ten years, checkers will be a completely decidable game.” Richard Bellman, Proceedings of the National Academy of Science, 53(1965): p. 246.
“So whereas computers can ‘crunch’ tick-tack-toe, and even checkers, by looking all the way to the end of the game, they cannot do this with chess.” Lynn Steen, “Computer Chess: Mind vs. Machine,” Science News, November 29, 1975.
“Although computers had long since been unbeatable at such basic games as checkers....” Clark Whelton, Horizon, February 1978.
“Computers became unbeatable in checkers several years ago.” Thomas Hoover, “Intelligent Machines,” Omni magazine, 1979, p. 162.
“...an improved model of Samuel’s checkers-playing computer today is virtually unbeatable, even defeating checkers champions foolhardy enough to ‘challenge’ it to a game.” Richard Restak, The Brain: The Last Frontier, 1979, p. 336.
“...the Duke program, Bierman believes, is already ‘knocking at the door’ of the world championship. Jensen and Truscott regard it as now being about the 10th strongest player in the world.” Martin Gardner, Scientific American, January 1980, p. 25.
In 1992 I was at a conference and happened to meet with a member of the Natural Sciences and Engineering Council of Canada (NSERC), the primary funding agency for scientific research in Canada. I asked him why my previous year’s request for funding for artificial intelligence research using checkers as the experimental test bed was turned down. He began, “Didn’t Samuel solve that game thirty years ago?”
