Jump to content

Draft:Christopher Strachey's Checkers Program

From Wikipedia, the free encyclopedia


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

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.

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

[edit]

The National Physical Laboratory and the Pilot ACE

[edit]

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

[edit]

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

[edit]
Modern reproduction of Christopher Strachey's ladies program, 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

[edit]

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]

References

[edit]
  1. ^ a b Hodges 2015
  2. ^ Copeland, B. J (2004). The Essential Turing: Seminal Writings in Computing, Logic, Philosophy, Artificial Intelligence, and Artificial Life. Clarendon Press. ISBN 978-0198250807.
  3. ^ Raessens, Joost (2016). "Game Studies". The International Encyclopedia of Communication Theory and Philosophy. doi:10.1002/9781118766804.wbiect219.
  4. ^ Wolf, M. J. P (2014). The Video Game Explosion: A History from PONG to PlayStation and Beyond. Greenwood Press. ISBN 978-0313338687.
  5. ^ "Christopher Strachey (1916-1975)". Virtual Museum of Computing. Archived from the original on September 26, 2007.
  6. ^ Gordon, Mike (2000). "Christopher Strachey: Recollections of His Influence". Higher-Order and Symbolic Computation. 13 (1): 65–67. doi:10.1023/A:1010097524009. ISSN 1388-3690.
  7. ^ The National Archives. "Catalogue of the papers and correspondence of Christopher Strachey (1916 - 1975)". The National Archives. Archived from the original on March 4, 2021.
  8. ^ Hodges 2015, p. 463
  9. ^ a b c d "Computer Pioneers - Christopher Strachey". IEEE Computer History. Archived from the original on April 5, 2021.
  10. ^ Garret, Yann (1989). "Le mystère Alan Turing". Science et Vie micro (57): 70.
  11. ^ Schaeffer 2008, p. 88
  12. ^ a b c Copeland & Turing 2004, pp. 563–564
  13. ^ Turing 2015, Chap. 9 - Taking Shape.
  14. ^ a b Moor 2003, Chap. 9 - Taking Shape
  15. ^ Campbell-Kelly, Martin (2008). "Pioneer Profiles - Donald Davies". Computer Resurrection (44). Computer Conservation Society.
  16. ^ Alvarez, Julian; Djaouti, Damien (2010). "Arcade : Les Pionniers du jeu vidéo" [Arcade: The pioneers of video games]. Pix'n Love (in French) (11). Éditions Pix'n Love: 32–43. ISBN 9782918272106.
  17. ^ Hodges 2015, p. 499
  18. ^ Cawthorne 2014, Chapter 7 - Men and Machines
  19. ^ a b Fildes, Jonathan (June 17, 2012). "Oldest computer music unveiled". BBC News. Archived from the original on January 25, 2021.
  20. ^ a b c d e f g h i Link, David (2012). "Programming ENTER: Christopher Strachey's Draughts Program". Computer Resurrection, Computer Conservation Society: 60.
  21. ^ "First digital music made in Manchester". University of Manchester. June 18, 2008. Archived from the original on September 18, 2016.
  22. ^ a b Copeland 2012, pp. 166–170
  23. ^ a b c d Smith, Alexander (January 22, 2014). "The Priesthood at Play: Computer Games in the 1950s". They Create Worlds. Archived from the original on March 4, 2016.
  24. ^ Ahl, David H. The Early Days - chapitre 1 : Mainframe Games and Simulations? (in 31-34).{{cite book}}: CS1 maint: unrecognized language (link)
  25. ^ a b Donovan 2010, pp. 1–9
  26. ^ "IBM100 - The IBM 700 Series". IBM. 2011. Archived from the original on January 3, 2016.
  27. ^ Copeland, Jack; Proudfoot, Diane. "Turing, Father of the Modern Computer". The Rutherford Journal. Archived from the original on January 30, 2016.
  28. ^ Loguidice & Barton 2014, p. 7
  29. ^ Dillon 2016, pp. 3–4
  30. ^ Wood 2014, p. 7
  31. ^ Andersen & Gray 2008, p. 538
  32. ^ Baker 2013, p. 2
  33. ^ Kaplan 2013, p. 8

Bibliography

[edit]
  • Donovan, Tristan (2010). Replay : The History of Video Games. East Sussex, England: Yellow Ant. ISBN 978-0-9565072-0-4.
[edit]
This page will be placed in the following categories if it is moved to the article namespace.
Categories:
Retrieved from "https://en.wikipedia.org/w/index.php?title=Draft:Christopher_Strachey%27s_Checkers_Program&oldid=1284239869"