Chequered past: A short history of chess and AI
Chequered past: A short history of chess and AI
How chess became a testbed for AI research in the 20th century
In 2001: A Space Odyssey, the protagonist David Bowman finds himself in a few uncomfortable positions. He’s trapped outside of the Discovery One spaceship, hidden in an exploration pod inside the ship, and ekes out a lifetime as a prisoner (or guest, depending on your interpretation) of alien beings in a fantastically white hotel room.
But there’s another moment that I like to imagine was intended to be equally unnerving: the scene in which HAL 9000 handily beats Frank Poole in a game of chess. Modern viewers are unlikely to bat an eye, but we ought to remember 2001 was released almost 30 years before the 1996 six-game chess series between the then world chess champion Garry Kasparov and IBM’s Deep Blue supercomputer. As an aside, the board positions and moves depicted are identical to those in a real game played in Hamburg in 1910, which was reported in a 1955 collection of short games by Ukrainian-born American chess player and author Irving Chernev.
Aside from being an avid chess player himself, I suspect there are probably a few good reasons as to why Kubrick decided to include the moment in the film. First, and perhaps the more obvious, is that the scene was intended to draw into focus the gulf in intelligence between Frank, a human, and HAL 9000, the machine (though whether or not chess is a good proxy for intelligence is another matter entirely).
Second is that Kubrick, who stuck a Pan American Airways logo on the side of space shuttles in service of a realistic portrayal of the future, may have included the moment as a nod to the longstanding—and, as we shall see, symbiotic—relationship between chess and AI. Marvin Minsky, one of the great figures in the story of AI who I wrote about in my introduction to the field’s history, was one of the principal scientific consultants advising Kubrick on the film. He wanted HAL, which, we are reminded, stands for ‘heuristically programmed algorithmic computer’ to “have the best of both worlds” in reference to the use of case-based reasoning and heuristics representative of the symbolic approach to artificial intelligence. Minsky, of course, famously sunk the burgeoning field of machine learning (then known as connectionism) only a couple of years later in 1969 with his incendiary takedown Perceptrons: An Introduction to Computational Geometry.
Minsky was well aware of the relationship between chess and AI, which had long been used as both proving ground and experimental medium by AI researchers in their efforts to build intelligent machines. Today, we have systems like AlphaZero that play chess (as well as shogi and Go) from a tabula rasa state (that is to say, it teaches itself through a long and intensive process of self-play). But when exactly did the worlds of chess and AI collide, and what precisely was its significance?
Our story begins in the 18th century with the Hungarian engineer Wolfgang von Kempelen, who constructed the infamous Mechanical Turk for the Empress Maria Theresa, who ruled the Habsburg dominions (including Austria, Hungary, Croatia, Bohemia) from 1740 until her death in 1780. Kempelen’s machine used a series of levers, gears, and magnets, which allowed a human operator concealed within a cabinet to discreetly control the movements of the chess pieces on the board above.
For eight decades, the Mechanical Turk toured Europe. The machine (or rather, the chess grandmaster hiding inside the device) allegedly bested Benjamin Franklin and Napoleon Bonaparte (even when it was reported that the latter had cheated). By 1818, when the Turk was under the ownership of the budding mechanist and musician Johann Mälzel, a young Charles Babbage (who we also discussed in the introduction to AI) saw it in London and was said to be captivated.
Many attribute the beginnings of computerised chess, distinct from the mechanical chess exemplified by the Mechanical Turk, to the English mathematician Alan Turing. By 1946, Turing envisioned a computer capable of playing chess as a manifestation of his so-called 'thinking' machine (one of the hypothetical questions Turing asked as part of his Imitation Game involved chess). But the first article considering the process by which a computer could be programmed to play chess was written by the mathematician Claude Shannon (whose name allegedly inspired that of Anthropic’s chatbot). Shannon wrote a 1949 paper making the case that chess was the perfect testbed for AI: not only did it have clearly defined moves and an ultimate objective (checkmate), but it struck a balance between being neither overly simple nor insurmountably challenging.
Shannon’s motivations, however, weren’t just about creating a sandbox to test computing technology. The attraction of chess as a medium for AI research was bound up in notions about the relationship between chess and intelligence. As he explained: “chess is generally considered to require ‘thinking’ for skilful play; a solution of this problem will force us either to admit the possibility of a mechanized thinking or to further restrict our concept of "thinking"”.
But unfortunately for Shannon, a computer-playing machine proved to be unattainable at the time. According to the historian Nathan Ensmenger, “The numbers involved in constructing even a partially complete decision tree for chess quickly become astronomical – and intractable.” So, what to do with a chess programme that was unable to compute all possible moves in a game? The answer, according to Shannon, was simple. Instead of calculating the scope of all possible moves, the machine would be programmed to evaluate a limited number of turns. The rub, though, was in figuring out exactly what that option space looked like.
To answer this question, Shannon introduced two solutions. First, the 'Type-A' method, which involves reducing the moves the computer evaluates to a fraction of the total number of possible turns. Second, the 'Type-B' approach, which uses heuristics to prioritise certain moves with the goal of emulating the way in which humans play chess. While Shannon favoured the human-like 'Type-B' method, his paper focused primarily on the 'Type-A' strategy centred on the minimax algorithm whose goal was to minimise the worst-case potential loss (the disadvantage a player might face in a game due to a particular move). It was this second approach, which due to its simplicity and effectiveness, became the dominant method in computer chess in the 20th century.
Claude Shannon may have written a seminal paper on computer chess in 1949, but it took until 1957 for the first operational chess programme to be developed. While there were initial explorations into alternatives to the Type-A minimax algorithms, such as IBM's Alex Bernstein's Type-B strategy, minimax became the preferred method by 1958. That same year, Allan Newell, Herbert Simon, and Clifford Shaw enhanced the minimax algorithm with alpha-beta pruning, a technique concurrently developed by others, including Dartmouth workshop organiser John McCarthy. The significance here is that the collision of the minimax algorithm with the alpha–beta pruning technique significantly reduced the total number of branches of the decision tree that the system needed to consider, which dramatically increased efficiency and subsequently made it possible to play chess on practically any computer.
Elo Elo
While the minimax algorithm explains the direction that chess-focused AI research took in the middle of the 20th century, it does little to explain its popularity. To understand why chess became entangled with AI, we need to shift gears and take our story to the Soviet Union.
In 1965 the Russian mathematician Alexander Kronrod, when asked to justify the computer time he was using to play correspondence chess (that is, playing remotely) at the Soviet Institute of Theoretical and Experimental Physics, gave an explanation that sheds light on the relationship between game and discipline. It was essential that Kronrod, as an influential researcher in the new discipline of artificial intelligence, be allowed to devote computer time to the game because ‘chess was the drosophila of artificial intelligence’.
What Kronrod meant was that chess was well suited to its role as an experimental medium: Drosophila melanogaster (the common fruit fly) is used as a ‘model organism’ by researchers in various programmes of genetic analysis. For Kronrod and researchers like him, it was the internal characteristics of chess that made it ideal. It was, after all, a simple game with a well-defined problem domain and unambiguous rules, clear objectives, and straightforward measures of success. This is the reason that games have been used throughout the history of AI, even those that are orders of magnitude more complex like Dota 2 or Starcraft. While complexity scales, those fundamental characteristics remain in place.
But therein lies the interesting question. If all games—to varying degrees—share these fundamental qualities, why was it that computer scientists used chess as a medium around which to organise their research? Well, one simple answer is that chess was well-known by, and popular with, American and European researchers, which was not the case for games like Go or shogi. It was also the case that the ability to play chess well was widely considered to be a strong indicator of intelligence (not to mention that chess has long been thought of as a prestigious activity, associated with intellectuals, artists and other high status, creative types).
AI grandees Allan Newell and Herbert Simon, who were among the participants in the influential AI conference in Dartmouth in 1956, famously said that: ‘chess is the intellectual game par excellence.…If one could devise a successful chess machine, one would seem to have penetrated to the core of human intellectual endeavor.’ Perhaps more importantly, though, is that lots of researchers play chess. As Ensmenger explains, “many of the mathematicians who worked on computer chess, including Turing and Shannon, were avid amateur players.”
“You sit at the board and suddenly your heart leaps. Your hand trembles to pick up the piece and move it. But what Chess teaches you is that you must sit there calmly and think about whether it’s really a good idea and whether there are other better ideas” Stanley Kubrick
It’s also worth saying that an extensive historical and theoretical chess literature, combined with standardised symbolic notation, empowered computer enthusiasts to seed and refine their chess systems using reliable data and benchmarks. This foundation, paired with the widespread acceptance of correspondence chess, eased the adaptation to playing chess against computerised opponents.
Chess was also a public spectacle. The game was popular to watch as well as to play, which made it more attractive to interested third parties (especially in the context of the Cold War, where players from the United States regularly faced off against those from the USSR). Related to the trappings of competition was the game’s Elo system, which was named after the Hungarian-born physicist Arpad Elo and had been formally adopted by the US Chess Federation. While I won’t spend time on the details, the point I want to make is that the Elo system provided clear numerical benchmarks for measuring performance and improvement. These are all very helpful qualities when designing computer systems.
Endgame
From Kempelen's Mechanical Turk to Claude Shannon's foundational paper, chess proved to be an ideal (or at the very least, idealised) testbed for AI research in the 20th century. Its balance of complexity and simplicity, widespread popularity, codified rules, and quantitative performance metrics like Elo ratings made it the "drosophila of artificial intelligence."
But it wasn’t the technical form factor of chess that made it so appealing. The game was popular with the researchers designing AI systems, and the rich documentation of games, openings, and scenarios provided the information needed to design and develop the early chess engines. The Elo system offered a stable, universally understood means of assessing performance, while chess matches also provided public spectacle at the height of Cold War competition.
While research has moved on from chess—first to other games and eventually to more complex simulated environments and the real world—its history tells us that the artefacts through which technical practice takes place aren’t chosen by accident. That is not to say that chess is an inappropriate medium for building AI systems or that today’s testbeds are in any sense troublesome, but rather that the use of chess in AI reminds us that science doesn’t happen in a vacuum.
Just as the choices we make about which mediums to use shape the direction of research, so too are these decisions influenced by sources we don’t always recognise. The history of science and technology is replete with examples in this tradition, from the Lenna image on which the early standards for computerised colourisation depended to the international prototype kilogram that enabled the measurement of mass for hundreds of years.
The historian Dylan Mulvin calls these objects ‘proxies’. He argues that they mediate between the practicality of getting work done and the representation of the world. Perhaps chess does something similar. The board might be small, but you can pack a lot into sixty four squares.