Before leaving the 1950s behind, we now turn to the most prolific computer game concept of the decade: chess. While complex simulations drove the majority of AI research in the military-industrial complex during the decade, the holy grail for much of academia was a computer that could effectively play this venerable strategy game. As Alex Bernstein and Michael de V. Roberts explain it for Scientific American in June 1958, this is because chess is a perfect game to build an intelligent computer program around because the rules are straightforward and easy to implement, but playing out every possible scenario at a rate of one million complete games per second would take a computer 10108 years. While this poses no real challenge for modern computers, the machines available in the 1950s and 1960s could never hope to complete a game of chess in a reasonable timeframe, meaning they actually needed to learn to react and adapt to a human player to win rather than just drawing on a stock of stored knowledge. Charting the complete course of the quest to create a perfect chess-playing computer is beyond the scope of this blog, but since chess computer games have been popular entertainment programs as well as platforms for AI research, it is worth taking a brief look at the path to the very first programs to successfully play a complete game of chess. The Computer History Museum presents a brief history of computer chess on its website called Mastering the Game, which will provide the framework for most of this examination.
El Ajedrecista (1912)
Leonardo Torres y Quevedo (left) demonstrates his chess-playing automaton
According to scholar Nick Montfort in his monograph on interactive fiction, Twisted Little Passages (2005), credit for the first automated chess-playing machine goes to a Spanish engineer named Leonardo Torres y Quevedo, who constructed an electro-mechanical contraption in 1912 called El Ajedrecista (literally “the chessplayer”) that simulated a KRK chess endgame, in which the machine attempted to mate the player’s lone king with his own king and rook. First demonstrated publicly in 1914 in Paris and subsequently described in Scientific American in 1915, El Ajedrecista not only calculated moves, but actually moved the pieces itself using a mechanical arm. A second version constructed in 1920 eliminated the arm and moved pieces via magnets under the board instead. Montfort believes this machine should qualify as the very first computer game, but a lack of any electronics, a key component of every modern definition of a computer game — though not a requirement for a machine to be classified as an analog computer — makes this contention problematic, though perhaps technically correct. Regardless of how one chooses to classify Quevedo’s contraption, however, it would be nearly four decades before anyone took up the challenge of computer chess again.
Turochamp and Machiavelli (1948)
Alan Turing, father of computer science and computer chess pioneer
As creating a viable chess program became one of the long-standing holy grails of computer science, it is only fitting that the man considered the father of that field, Alan Turing, was also the first person to approach the problem. Both the computer history museum and Replay state that in 1947 Turing became the first person to write a complete chess program, but it proved so complex that no existing computer possessed sufficient memory to run it. While this account contains some truth, however, it does not appear to be fully accurate.
As recounted by Andrew Hodges in the definitive Turing biography Alan Turing: The Enigma (1983), Turing had begun fiddling around with chess as early as 1941, but he did not sketch out a complete program until later in the decade, when he and economist David Champernowne developed a set of routines they called Turochamp. While it is likely that Turing and Champerdowne were actively developing this program in 1947, Turing did not actually complete Turochamp until late 1948 after hearing about a rival chess-playing program called Machiavelli written by his colleagues Donald Michie and Shaun Wylie. This is demonstrated by a letter Hodges reprinted in the book from September 1948 in which Turing directly states that he had never actually written out the complete chess program, but would be doing so shortly. Copeland also gives a 1948 date for the completion of Turochamp in The Essential Turing.
This may technically make Machiavelli the first completed chess program, though Michie relates in Alan M. Turing (1959), a biography written by the subject’s own mother, that Machiavelli was inspired by the already in development Turochamp. It is true that Turochamp — and presumably Machiavelli as well — never actually ran on a computer, but apparently Turing began implementing it on the Ferranti Mark 1 before his untimely death. Donovan goes on to say that Turing tested out the program by playing the role of the computer himself in a single match in 1952 that the program lost, but Hodges records that the program played an earlier simulated game in 1948 against Champerdowne’s wife, a chess novice, who lost to the program.
Programming a Computer for Playing Chess, by Claude Shannon (1950)
Claude Shannon (right) demonstrates a chess-playing automaton of his own design to chess champion Edward Lasker
While a fully working chess game would not arrive for another decade, key theoretical advances were made over 1949 and 1950 by another pioneer of computer science, Claude Shannon. Shannon was keenly interested in the chess problem and actually built an “electric chess automaton” in 1949 — described in Vol. 12 No. 4 of the International Computer Chess Association (ICCA) Journal (1989) — that could handle six pieces and was used to test programming methods.
His critical contribution, however, was an article he wrote for Philosophical Magazine in 1950 entitled “Programming a computer for playing chess.” While Shannon’s paper did not actually outline a specific chess program, it was the first attempt to systematically identify some of the basic problems inherent in constructing such a program and proffered several solutions. As Allen Newell, J.C. Shaw, and H.A. Simon relate in their chapter for the previously mentioned landmark AI anthology Computers and Thought, “Chess-Playing Programs and the Problem of Complexity,” Shannon was the first person to recognize that a chess game consists of a finite series of moves that will ultimately terminate in one of three states for a player: a win, a loss, or a draw. As such, a game of chess can be viewed as a decision tree in which each node represents a specific board layout and each branch from that node represents a possible move. By working backwards from the bottom of the tree, a player would know the best move to make at any given time. This concept, called minimaxing in game theory, would conceivably allow a computer to play a perfect game of chess every time.
Of course, as we already discussed, chess may have a finite number of possible moves, but that number is still so large that no computer could conceivably work through every last move in time to actually play a game. Shannon recognized this problem and proposed that a program should only track moves to a certain depth on the tree and then choose the best alternative under the circumstances, which would be determined by evaluating a series of static factors such as the value and mobility of pieces — weighted based on their importance in the decision-making process of actual expert chess players — and combining these values with a minimaxing procedure to pick a move. The concept of evaluating the decision tree to a set depth and then using a combination of minimaxing and best value would inform all the significant chess programs that followed in the next decade.
Partial Chess-Playing Programs (1951-1956)
Paul Stein (seated) plays chess against a program written for the MANIAC computer
The complexities inherent in programming a working chess-playing AI that adhered to Shannon’s principles guaranteed it would be nearly another decade before a fully working chess program emerged, but in the meantime researchers were able to implement more limited chess programs by focusing on specific scenarios or by removing specific aspects of the game. Dr. Dietrich Prinz, a follower of Turing who led the development of the Ferranti Mark 1, created the first such program to actually run on a computer. According to Copeland and Diane Proudfoot in their online article Alan Turing: Father of the Modern Computer, Prinz’s program first ran in November 1951. As the computer history museum explains, however, this program could not actually play a complete game of chess and instead merely simulated the “mate-in-two problem,” that is it could identify the best move to make when two moves away from a checkmate.
In The Video Game Explosion, Ahl recognizes a 1956 program written for the MANIAC I at the Los Alamos Atomic Energy Laboratory by James Kister, Paul Stein, Stanislaw Ulam, William Walden, and Mark Wells as the first chess-playing program, apparently missing the Prinz game. Los Alamos had been at the forefront of digital computing almost from its inception, as the lab had used the ENIAC, one of the first Turing-complete digital computers, to perform calculations and run simulations for research relating to the atomic bomb. As a result, Los Alamos personnel kept a close watch on advances in stored program computers in the late 1940s and early 1950s and decided to construct their own as they raced to complete the first thermonuclear weapon, colloquially known as a “hydrogen bomb.” Designed by a team led by Nicholas Metropolis, the Mathematical Analyzer, Numerical Integrator, and Computer, or MANIAC, ran its first program in March 1952 and was put to a wide variety of physics experiments over the next five years.
While MANIAC was primarily used for weapons research, the scientists at Los Alamos implemented game programs on more than one occasion. According to a brief memoir published by Jeremy Bernstein in 2012 in the London Review of Books, many of the Los Alamos scientists were drawn to the card tables of the casinos of nearby Las Vegas, Nevada. Therefore, when they heard that four soldiers at the Aberdeen Proving Ground had published an article called “The Optimum Strategy in Blackjack” in the Journal of the American Statistical Association in 1956, they immediately created a program on the MANIAC to run tens of thousands of Blackjack hands to see if the strategy actually worked. (Note: Ahl and a small number of other sources allude to a Blackjack game being created at Los Alamos on an IBM 701 computer in 1954, but I have been unable to substantiate this claim in primary sources, leading me to wonder if these authors have confused some other experiment and the 1956 blackjack program on the MANIAC). Therefore, it is no surprise that scientists at the lab would decided to create a chess program as well.
Unlike Prinz’s program, the MANIAC program could play a complete game of chess, but the programmers were only able to accomplish this feat using a simplified 6×6 board without bishops. The program did, however, implement Shannon’s system of calculating all possible moves over two levels of the decision tree and then using static factors and minimaxing to determine its next move. Capable of performing roughly 11,000 operations per second, the program only played three games and was estimated to have the skill of a human player with about twenty games experience according to Shaw. By the time Shaw’s article was published in 1961, the program apparently no longer existed. Presumably it was lost when the original MANIAC was retired in favor of the MANIAC II in 1957.
The Bernstein Program (1957)
Alex Bernstein with his chess program in 1958
A complete chess playing program finally emerged in 1957 from IBM, implemented by Alex Bernstein with the help of Michael de V. Roberts, Timothy Arbuckle, and Martin Belsky. Like the MANIAC game, Bernstein’s program only examined two levels of moves, but rather than exploring every last possibility, his team instead programmed the computer to examine only the seven most plausible moves, determined by operating a series of what Shaw labels “plausible move generators” that identified the best moves based on specific goals such as king safety or prioritizing attack or defense. After cycling through these generators, the program picked seven plausible continuations and then made a decision based on minimaxing and static factors just like the MANIAC program. It did so much more efficiently, however, as it considered only about 2,500 of over 800,000 possible permutations. Running on the faster IBM 704 computer, the program could handle 42,000 operations per second, though according to Shaw the added complexity of using the full 8×8 board rendered much of this speed advantage moot and the program still took about eight minutes to make a move compared to twelve for the MANIAC program. According to Shaw, Bernstein’s program played at the level of a “passable amateur,” but exhibited surprising blind spots due to the limitations of its move analysis. It apparently never actually defeated a human opponent.
The NSS Chess Program (1958)
Herbert Simon (left) and Allan Newell (right), two-thirds of the team that created the NSS program
We end our examination of 1950s computer chess with the NSS chess program that emerged from Carnegie-Mellon University. Allan Newell and Herbert Simon, professors at the university who consulted for RAND Corporation, were keenly interested in AI and joined with a RAND employee named Cliff Shaw in 1955 to fashion a chess program of their own. According to their essay in Computers and Thought, the trio actually abandoned the project within a year to focus on writing programs for discovering symbolic logic proofs, but subsequently returned to their chess work and completed the program in 1958 on the JOHNNIAC, a stored program computer built by the RAND Corporation and operational between 1953 and 1966. According to an essay by Edward Feigenbaum called “What Hath Simon Wrought?” in the 1989 anthology Complex Information Processing: The Impact of Herbert A. Simon, Newell and Shaw handled most of the actual development work, while Simon immersed himself in the game of chess itself in order to imbue the program with as much chess knowledge as possible.
The resulting program, with a name derived from the authors’ initials, improved upon both the MANIAC and Berstein programs. Like the Bernstein program, the NSS program used a combination of minimaxing, static value, and a plausible move generator to determine the best move to make, but Newell, Simon, and Shaw added a new important wrinkle to the process through a “branch and bounds” method similar to the technique that later researchers termed “alpha-beta pruning.” Using this method, each branch of the decision tree was given a maximum lower and a minimum upper value, alpha and beta, and the program only considered those branches that fell in between these values in previously explored branches. In this way, the program was able to consider far fewer moves than previous minimaxing-based programs, yet mostly ignored poor solutions rather than valuable ones. While this still resulted in a program that played at an amateur level, the combination of minimaxing and alpha-beta pruning provided a solid base for computer scientists to carry chess research into the 1960s.
They Create Worlds 