Christopher Strachey's Checkers Program

The checkers program by Christopher Strachey is a computer program for the game of checkers, created by British computer scientist Christopher Strachey in 1951. It first ran at a reasonable speed during the summer of 1952 on the Ferranti Mark I computer at the University of Manchester.

Christopher Strachey's Checkers Program
Developer(s)	Christopher Strachey
Director(s)	Christopher Strachey
Platform(s)	Pilot ACE (development beginning), Ferranti Mark I
Release	July 1952
Genre(s)	Checkers
Mode(s)	Single-player

Strachey was quickly drawn to intelligent machines and, at the beginning of 1951, joined the National Physical Laboratory, which had just succeeded in building a prototype computer called the Pilot ACE, based on Alan Turing’s Automatic Computing Engine. To familiarize himself with programming on this machine, Strachey wrote a checkers program inspired by the article A Theory of Chess and Noughts and Crosses published in 1950. He was also influenced in his choice by Charles Babbage, his analytical engine, and his proposals for chess and checkers games.^[1] However, programming errors, the computer’s lack of power, and frequent component changes on the platform prevented the program from working correctly. In the spring of 1952, Strachey learned that the University of Manchester had a more powerful computer than the Pilot ACE—the Ferranti Mark I. He then went to the Computing Machine Laboratory in Manchester, where he met Alan Turing. Encouraged by Turing, he made numerous improvements to his program, which he managed to run at a reasonable speed in July 1952.^[1]

It is the first game on a general-purpose Turing-complete computer, as opposed to games like Bertie the Brain, which run on dedicated machines. The significance of this program extends beyond the realm of computer games. One of the first to operate an artificial intelligence and a heuristic search method, preceded only by the chess program Turochamp, theorized by Alan Turing in 1948.^[2] Furthermore, it is "probably" the first to use a graphical display. At the time when Christopher Strachey ported the checkers game to the Ferranti Mark I and succeeded in making it work in 1952, the tic-tac-toe video game OXO was designed by Alexander S. Douglas on the EDSAC.^[3] OXO and Strachey's program are the oldest games to offer a visual display on an electronic screen. Most works on the subject consider OXO to be the first video game in history, although some observers believe it is difficult to determine which of the two was the first to become functional.^[4]

The program inspired Arthur Samuel, who discovered it the same year in Toronto, Canada, during a conference where Strachey described his computer game. Samuel then developed his own checkers program in 1952 on the IBM 701.

Development

The National Physical Laboratory and the Pilot ACE

Christopher Strachey was a British computer scientist known for being one of the founders who advocated for a mathematical approach to the study of programs, denotational semantics, and one of the pioneers of programming languages.^[5][6] Born in 1916, he was the son of British cryptographer Oliver Strachey and Ray Strachey, a British writer and feminist politician. He studied at Gresham’s School, King’s College, Cambridge, and the University of Cambridge.^[7] Despite his family background, he did not stand out at King’s and later worked on radars during World War II, then taught at Harrow. However, the concept of intelligent machines quickly caught his attention.^[8] In January 1951, a friend introduced him to Mike Woodger of the National Physical Laboratory (NPL), and he subsequently joined the laboratory.^[9] The NPL housed the prototype of the Automatic Computing Engine (ACE), designed and built by Alan Turing starting in 1945. However, the project was delayed for many months due to technical, political, and economic reasons. Discouraged and lacking diplomacy, Turing abandoned the highly ambitious project in 1947. Thanks to Donald Davies, who worked at the NPL, the laboratory continued the work and eventually succeeded in building a more modest, reduced-size version based on Turing’s ACE concept, named Pilot ACE, which began operating in May 1950.^[10]

The Pilot ACE at the Science Museum in London.

In his spare time, Strachey developed a checkers game program to familiarize himself with programming on this machine, which he completed in February 1951. He was inspired by an article titled A Theory of Chess and Noughts and Crosses published in 1950 in Penguin Science News, written by NPL scientist Donald Davies.^[9] He was also influenced in his choice by Charles Babbage, his analytical engine, and his proposals for chess and checkers games.^[11] Strachey compiled a preliminary version of the program in May 1951 at the NPL, and he tested it for the first time on July 30, 1951, on the Pilot ACE computer. However, programming errors prevented the program from functioning correctly.^[12] Additionally, the prototype’s memory was insufficient to run the game properly.^[13] Strachey also faced frequent component changes in the computer, which regularly rendered parts of his code obsolete.^[14][15]

The University of Manchester and the Ferranti Mark I

Meanwhile, in the spring of 1951, Woodger informed Strachey that the Ferranti Mark I computer had just been installed at the University of Manchester, replacing the Manchester Mark I, from which it was derived. This computer had more memory than the Pilot ACE, which better suited the work Strachey wanted to undertake.^[9] In July, he traveled for the first time to the University of Manchester to explore the Ferranti computer and met Alan Turing, who was then the assistant director at the university’s Computing Machine Laboratory. Strachey explained his ideas about creating a checkers game program. He knew Turing somewhat, as they had both attended King’s College, which allowed him to obtain the Ferranti Mark I user manual, which Turing had recently written, to port the game onto this computer. Turing was quite impressed by his checkers program project but suggested to Strachey that an interesting task would be to simulate the machine itself, in the same way as the selective analysis program developed for the EDSAC computer at the University of Cambridge. Convinced by this idea, Strachey temporarily set aside his checkers program. The final version of the program contained nearly 1,000 instructions, making it the longest program ever written for a machine at the time, although Strachey was unaware of this record.^[9]

Nevertheless, Turing’s encouragement was crucial for Strachey, who eventually managed to get the checkers program running on the Ferranti Mark I.^[12][16] Moreover, Turing appreciated Strachey, who had brought fresh ideas from King’s College into the technical atmosphere of the Manchester laboratory, especially since they behaved similarly and shared the same sense of humor. Meanwhile, in 1952, the two of them amused themselves by creating a program on the Mark I that wrote love letters with randomly generated content, using random numbers and pre-recorded text fragments.^[17] Additionally, Turing persuaded Strachey to create two audio programs—the first of their kind—that enabled the computer to play music, notably In the Mood by Glenn Miller and Baa, Baa, Black Sheep.^[18][19]

Initially, the other laboratory members were amused to see Strachey immediately eager to run his program on punched tape, believing that a newcomer could succeed on the first try. However, after correcting a few errors, the program worked, to everyone’s astonishment, and played God Save the King through a speaker. From that point on, Strachey gained a reputation as a "remarkable" developer. The program was over 20 pages long and contained more than 1,000 instructions.^[20][21] Strachey made numerous improvements and eventually completed the port of the checkers program, which, by July 1952, finally could play a complete game of checkers at a reasonable speed.^[20]

Operation

Modern reproduction of Christopher Strachey's ladies program,^{[clarification needed]} fully operational in 1952 on a Ferranti Mark I.

The program simulates a classic game of checkers. It uses a simple heuristic and calculates the next three to four moves. On each turn, it computes all possible positions to choose the strongest one. It also considers other parameters, such as the value of kings, which are assigned a value three times higher than that of a regular piece. The game’s progress is displayed on a cathode-ray tube. Strachey repurposed two of the computer’s screens, originally intended for monitoring the system’s operations, to display graphics.^[14][22] The screens show a bitboard and the positions of pieces or kings. The white squares are numbered from 1 to 31, and the program uses three 32-bit variables to list the positions of pieces or kings for each color. The matches are recorded by a teleprinter.^[20]

The player presses a button to start the game, and the program offers to toss a coin to decide, like a coin flip, who will start. The player then provides this information to the computer using a switch and a button. The computer and the player alternate moves, with the computer recording its move on the teleprinter and the player making their move using a button, followed by another to confirm. One of the screens allows the computer to show the move the player has chosen before they confirm it, or to cancel it to select another move. The other screen displays the progress of the game.^[20]

When the game begins, the computer emits beeps as soon as it is ready to accept the player's move. The program provides pre-recorded responses based on the player's actions. For example, if the player takes too long to play, the computer displays on the screen, "You must play at once or resign."; if the player makes a mistake in handling, it displays "Kindly read the instructions and start the move again."; abnormal player behavior prompts "If you don't follow the instructions I can't play with you." or a sharp "I refuse to waste any more time. Go and play with a human being." The machine, also subject to hardware or software issues, can produce erroneous messages such as "Please dread zthe sintruction fcard. Shall wwe ztoss ffor zthe ffirst xmove."^[22]

When the game is finished, the program plays God Save the King.^[19]

Legacy

Strachey's program has been preserved and is kept at the Bodleian Library at the University of Oxford. Five versions of the program exist, handwritten and about twenty pages long each.^[20] Transcriptions of games played by Strachey during tests, recorded via a teleprinter, are also preserved. These printouts indicate that the program was primarily developed in June and July 1952, but an undated version was likely written before May 1951.^[20] In 2012, David Link emulated Strachey's checkers program.^[20]

It is the first game on a general-purpose Turing-complete computer, as opposed to games like Bertie the Brain, which run on dedicated machines.^[23][24] This program inspired Arthur Samuel, who discovered the game at a conference organized the same year in Toronto, Canada, where Strachey described his computer game. Samuel then created his checkers program in 1952 on the IBM 701. He continued to improve its artificial intelligence, in a rudimentary way, in successive versions, and in 1956, a version was showcased on television.^[23][25][26]

The importance of Strachey's checkers program goes beyond the realm of computer games. It is one of the first programs to implement artificial intelligence^[23] and a heuristic search method,^[27] preceded only by the Turochamp chess program theorized by Alan Turing in 1948.^[25] Furthermore, it was "probably" the first program to use a graphical display.^[20] At the time when Strachey ported the checkers game to the Ferranti Mark I and got it to work in 1952, the tic-tac-toe video game OXO was designed by Alexander S. Douglas on the EDSAC.^[28][20][29] OXO and Strachey's program are the earliest games to feature a visual display on an electronic screen. Most works on the subject consider OXO to be the first video game in history,^{[30][31][32][33]} although some observers believe it is difficult to determine which of the two was the first to be functional.^[23]

When Christopher Strachey wrote his checkers program, he envisioned a machine learning system. He designed a routine learning program he hoped to implement in a Nim game machine one day. He also discussed this with Turing through a letter he sent him. However, Strachey missed the opportunity to be the first to present a functional program incorporating the machine learning concept. He was outpaced by Anthony Oettinger and his programs running on the EDSAC at the University of Cambridge.^[12]