blog

75 Years of Games in AI

Written by David Palfrey | Oct 15, 2024 4:06:22 PM

Why did Turing's 1946 ACE Report mention a Jigsaw Puzzle?

One of the oddest features of 75 years of effort to produce intelligent machines is the persistent place of games and gaming in that history. This blog post dips a first toe into that story, by looking at a series of articles on machine capabilities written by Alan Turing in the late 1940s, just after the end of World War II. The two most important games mentioned in these papers are very different in kind: on the one hand, chess, and on the other hand, the 'imitation game'. Both of these games have a long afterlife in the general history of AI, and I plan to return to them in later posts. But, in this blog post, I want to spend time on what I think is the very first game mentioned by Turing in connection with computing: a jigsaw puzzle.

You wouldn't expect to find any mention of games in Turing's first post-war piece of writing on computing machinery. This was his 1946 technical report, 'Proposals for Development in the Mathematics Division of an Automatic Computing Engine'. The report contains the design for Turing's proposed electronic calculator, and Turing suggests reading it alongside von Neumann's 'First Draft of a Report on the EDVAC'. It's stuffed with engineering details like the physical behaviour of water or mercury delay lines.
So it's a bit surprising when games do turn up here. They make their brief entrance in a section entitled 'Scope of the Machine', where Turing considers potential applications for the machine he wants to build. The "class of problems capable of solution by the machine may be defined fairly specifically", says Turing: "those problems which can be solved by human clerical labour, working to fixed understanding." His first suggestions are just what one might expect: compiling mathematical tables (this had been Charles Babbage's aim in the nineteenth century), calculating physical quantities, solving simultaneous equations, multiplying matrices, etc. To emphasize that his calculator will have practical limitations on its input, Turing also lists a couple of tasks for which it won't be well-suited: integrating continuous curves, or processing large numbers of data cards. But then he makes space for two additional, non-numerical, suggestions. The first of these suggestions is a kind of jigsaw puzzle:
Problem 9.- A jig-saw puzzle is made up by cutting up a halma-board into pieces each consisting of a number of whole squares. The calculator could be made to find a solution of the jig-saw, and, if they were not too numerous, to list all solutions.
My focus on this jigsaw is to some extent a deliberate piece of whimsy on my part. But I think a series of points can be made about it which have enduring applicability to both AI and games. First, as Turing presents it here, note that this is a game made by cannibalizing the equipment of another game, halma. Though Halma isn't today as familiar as chess or checkers, it was well known in its day. If you keep the general rules of halma, but change the board slightly, you get the game marketed as 'Chinese checkers'. If you throw away the pieces entirely and cut up the board, you get a jigsaw puzzle. An important general feature of games, I think, is that they can be deformed and transformed to make other games. Games are routinely adapted from other games by inheriting particular components or mechanics or principles. This continues to be true of games and game design, and (as we'll see later in Turing's discussion of the imitation game) it's particularly characteristic of the way Turing thinks about games.
However, it's also worth noting that this kind of game was a real commercial product. The 'Sectional Checkboard Puzzle' , for example, had been patented by Henry Luers in 1880, and sold by the New York game publishers Selchow & Richter:

The promotional material on the game box here raises a couple of other general issues. First, there's always the question whether games are useful or useless. Rather clunkily, the publishers claim their puzzle to be "Interesting, Amusing, and at the same kind a useful game". This is presumably intended to forestall a criticism of useless activity as degenerate. The problem is that games, rather like art, lack obvious instrumental benefit. They are something done for leisure, where leisure is imagined to be something opposed to productive work. Are games, nevertheless, somehow indirectly useful? Should we think of them as training the player in a transferable skill? Or maybe, as the etymology of 'recreation' suggests, refreshing and restoring them to productive health? Or is this insistence on utility missing the point entirely? Should games be valued precisely for their indifference to usefulness? Here is how Turing negotiates the question:
 
This particular problem [the jig-saw] is of no great importance, but it is typical of a very large class of non-numerical problems that can be treated by the calculator. Some of these have great military importance, and others are of immense interest to mathematicians.
 
Turing's computer research at the National Physical Laboratory was government-funded, in a world turning with relief from the devastations of war. Maybe there was something especially beautiful in the mathematician's ability to declare that lacking 'great military importance' could nevertheless be 'of immense interest'. (At the start of World War II, the Cambridge mathematician G. H. Hardy had tried to argue that it was precisely the uselessness of pure mathematics which made it valuable, since it could not be used to cause harm.)
A second general question prompted by the game box is to do with the ways in which games are social. Conceptually, a puzzle is clearly a single-player recreation rather than a multi-player game. Yet the image on the box suggests that the enjoyment here is anything but solitary. Such puzzles, it promises, provide a shared focus for collaborative communication and enjoyment. Many of the participants concentrate their gaze on the puzzle pieces, but gesture and talk to each other as they do so. The promise here is that the shared task somehow makes possible an absorption of the individual into group activity, into an easy fluidity of social interaction. A paternal figure, his domestic importance emphasized by the size of his chair, puts aside his newspaper to regard this idealized scene benevolently: while it's possible that his gaze is at the puzzle pieces, it seems equally possible that his enjoyment is in contemplating the tableau as a whole. What's true of single-player puzzles is all the more true of the sociality of multi-player games: they are accompanied by communication flows which are both internal to the game, and external to it. (Oddly, it is two-player games which are most often carried out in relative silence, even when spectators are present.)
From the point of view of Turing's technical report, the jigsaw puzzle is just a search over a combinatorial search space. The same would be true of the final application which he suggests, following the jigsaw: chess. In later blog posts I promise to give chess and the imitation game some proper attention. But I want to end here by saying something about the way in which we keep re-encountering the three points I've made here at Mind Mage.
First, games are continually cannibalized from other games by re-using their components. The richer the game environment, the more ways in which this can happen. Characters, situations, narrative elements and tropes are all elements of game experience which can be adapted or extended from earlier games. In building a platform for game authors, and extensible structures allowing players themselves to co-create their own game environment, we need to make this kind of borrowing as frictionless as possible. As software developers, we are used to one paradigm for thinking about this: code modularity and separation of concerns, so that components and their interfaces are cleanly identified for ease of re-use. But generative AI presents alternative possibilities: using the flexibility of natural language to describe the components which are being re-used.
Second, games perpetually raise questions about the relationship between directed and undirected activity. In playing a game, players may have goals which are internal to that game. However, they will also have all kinds of motivation for playing the game at all. Though these two levels can be connected to each other, it's important not to confuse them. (While the game designer can constrain things at one of these levels, she needs to accept the other as an external constraint.) And it's equally true, at each of these levels, that understanding players as driven by definite goals may be just to misunderstand things. Whereas some games are driven by highly specific win conditions, sandbox games are sustained by the sheer enjoyment of undirected activity or exploratory curiosity. Narrative games can have different phases, in which goal-directedness takes greater or lesser priority. And this variety only reflects the richness and potential complexity in the structure of motivation which drives players to find games 'fun' in the first place.
Finally, and most importantly, games are embedded in circuits of social and communicative flow which co-exist at multiple levels. Agentic AI certainly only makes it harder to count the 'number of players' in a game. Artificial agents can be bots, substitutes for human players who compete against one or more human players. They can be storyteller guides to a game. They can be non-player characters, whether vividly present in the narrative foreground or receding into an environmental background. The communicative fluency of generative AI now allows language itself - and more especially, conversation - to be a medium in which games progress. It also radically expands the possibilities for meaningful cross-talk between the menagerie of agents. While this potentially allows game interaction to register a fabulous variety of social interaction, it creates all kinds of new challenges. Language's everyday flexibility invites a collision of levels: between in-game, 'diagetic' talk and talk maintained outside the game itself. (You can use a game controller to pick up a flagon of mead within a game world, but not to interact with the real-world smoothie at your side as you play. But it's all too easy to talk about both.) Maintaining a stable structure of game elements as constructs which give a world coherence, even as we give players and agents an unprecedented range and flexibility of communicative action. This is the area where we know we're having to push the boundaries at Mind Mage. Tearing up the old boards and putting them back together again.