How chess became AI's model organism

AI Histories #8: The royal game is a testbed for machine intelligence. Why is that?

The Chess Players by Honoré Daumier from 1863

2001: A Space Odyssey is a film about astronauts getting put through the wringer. Our protagonists are forced to deal with zero-gravity plumbing and made to jog on a giant hamster wheel to stave off muscle loss. They’re trapped outside their ship, bundled into exploration pods, and even eke out a lifetime in bed with a cuboid whose bedside manner leaves something to be desired.

But there’s another point where one of our heroes finds himself in a bind, one less visually arresting but in some ways just as unnerving.

That moment is when the HAL 9000 computer handily beats Frank Poole in a game of chess. Modern viewers are unlikely to bat an eye, but we ought to remember the film was released almost 30 years before the 1996 six-game chess series between world chess champion Garry Kasparov and IBM’s Deep Blue.

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 by Ukrainian-born American chess player and author Irving Chernev.

Aside from the fact he loved chess, director Stanley Kubrick included the scene to show the machine could out-think the crew should they find themselves at odds. It comes across as foreboding enough, but only because chess had long been used as a proxy for the ‘I’ in ‘AI’.

One of the great figures in the history of thinking machines agreed. Marvin Minsky, a key player in AI Histories #7, was the man who acted as the principal scientific consultant advising Kubrick. Like many of his colleagues, he saw the game as part proving ground and part experimental medium for efforts to build intelligent machines.

Today, we see a chess-playing AI and shrug. It’s a sight so familiar we’d probably roll our eyes if we saw it in a modern flick. But it wasn’t always this way.

Our story begins in the 18th century with the Hungarian engineer Wolfgang von Kempelen, who constructed the Mechanical Turk for the Empress Maria Theresa. As we saw in AI Histories #4, 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 and the United States. The machine (or rather, the chess grandmaster hiding inside the device) allegedly bested Benjamin Franklin and Napoleon Bonaparte. By 1818, when the Turk was under the ownership of the budding mechanist and musician Johann Mälzel, a young Charles Babbage (who we discussed in the introduction to AI history) saw it in London.

Long before digital computers, Torres Quevedo’s El Ajedrecista electrically sensed each piece and delivered a forced mate every time, making it the first genuine chess-playing machine when it was built in 1912.

These moments represent a conceptual starting point, but they don’t really tell us anything about how chess shaped AI development. For that, we need to jump ahead to Alan Turing. In the late 1940s, the British mathematician designed a chess-playing programme called Turochamp (though no computer could run it), and he included the royal game in the thought experiment used to introduce what would become known as the Turing test.

Not long after, Claude Shannon wrote a 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.

But Shannon was dreaming bigger than sandboxes. 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’.

Unfortunately, building a formidable computer-playing machine was easier said than done. In the early 1950s, Dietrich Prinz’s chess system was the first to run on a stored-program computer — but it could only solve mate-in-two problems rather than playing full games.

A machine couldn’t yet play a full game because the numbers involved in constructing even a partially complete decision tree quickly became astronomical.

So, what to do with a chess programme that was unable to compute all possible moves in a game? The answer was simple. Instead of calculating the scope of all eventualities, the machine would be programmed to evaluate a limited number of promising turns.

To put this idea into practice, Shannon introduced two solutions. First, the 'Type-A' method: inspect every legal move out to a fixed depth. Second, the 'Type-B' approach, which uses heuristics to prioritise certain moves that its makers thought looked good.

While Shannon favoured the human-like Type-B method, his work focused primarily on the Type-A strategy. Both approaches centred the minimax algorithm whose goal was to minimise the worst-case potential loss, which we can think of as the disadvantage a player might face in a game due to a particular move. This was the approach that became dominant in computerised chess in the 20th century.

Around this time, Allan Newell, Herbert Simon, and Clifford Shaw rediscovered and bolted on alpha–beta pruning, a technique concurrently developed by others (including Dartmouth workshop organiser John McCarthy).

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. Together, the techniques dramatically increased efficiency and made it possible to play chess on practically any computer.

Elo Elo

In 1965 the Russian mathematician Alexander Kronrod, when quizzed about expending precious compute cycles on chess at the Soviet Institute of Theoretical and Experimental Physics, gave an explanation that sheds light on the relationship between chess and AI.

It was essential that Kronrod, as an influential researcher at the top of his game, 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, 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 more complex like Dota 2, StarCraft or Pokémon. But therein lies the rub. If all games share these fundamental qualities, why was it that computer scientists used chess specifically?

One obvious answer is that chess — unlike say, Go — was popular with American and European researchers. The ability to play chess well was also traditionally considered to be an indicator of intelligence, and the game has long been associated with intellectuals, artists and other high-status 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.’

For these reasons, lots of 20th century AI researchers played chess. As the historian Nathan Ensmenger puts it, ‘many of the mathematicians who worked on computer chess, including Turing and Shannon, were avid amateur players.’

Chess also came with the Elo system, a ranking approach named after the Hungarian-born physicist Arpad Elo. While I won’t spend time on the details, the point is that the Elo system provided clear numerical benchmarks for measuring performance and improvement — a very helpful quality when designing computer systems that get better over time.

Endgame

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 AI’s model organism.

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 early chess engines. The Elo system offered a stable means of assessing performance and chess matches provided public spectacle at the height of Cold War competition.

While AI research has moved on from chess, 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 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 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.