Debord AI

I'm working on a project right now that's so strange and perverse that I simply have to divulge my experiences, although I'm not yet sure what they amount to. Several years ago I worked on a strange episode from the late Guy Debord, the notorious French author and filmmaker and founding member of the Situationist International. In the 1970s Debord designed and released a game called the Game of War. I wrote about it and ported the game to the computer a few years back. The computer version is offline at the moment. But now and again I return to the game, spending time trying to rebuild it using today's technologies in the hopes of getting it back online.

Discovering that Debord had released a commercial board game was a surprise to me. Researching this game in great detail was revelatory. But what I'm doing now is truly strange... I'm trying to author the AI for the computer version. In essence I'm trying to convert Debord into an algorithm. I'm building my own Debord AI.

A perverse undertaking, to be sure. But I was never a member of the Cult of Debord. I have no qualms about remaining true to the master, and this project is, in a way, a means for me to exact revenge on this particular historical figure, who, we know, took great pleasure in taking his revenge on other people. Rolling in his grave, Debord may be. Nevertheless this restless spirit will rise again as a computer algorithm.

I won't summarize the game here. You can read a short description, or a longer scholarly take. I want to jump right in and describe each aspect of Debord AI. Much of what I'll describe is very rudimentary, and in fact would be applicable to many different kinds of games. This is all simple stuff that one might encounter in any introductory textbook on game AI. I'll add a few things at the end about if and why this matters for Debord in particular.

connected

Like chess or go, Debord's game is highly structured. The game is played on a grid system. Each position in the grid may be occupied by one or more units. Thus the first task in creating Debord AI was to set up what's called a graph. A graph is a data structure, which is to say it's a way of arranging together different pieces of data. The graph consists of a series of nodes. These nodes are connected through various links (also called edges). A simple metaphor might be the streets in a city: plazas and intersections are nodes, which are connected through various avenues and streets. Some roads are one-way only, while other roads are bi-directional. Graphs are very useful. They represent spatial relationships between multiple entities. But more generally graphs represent any form of dynamic relationship. (For instance a decision tree could also be represented using a graph even if it isn't directly spatial. The various questions in the decision tree are nodes; answers to questions are links to subsequent questions in the tree.) So the first step for Debord AI was to set up a graph containing nodes, where each node is a position on the gameboard able to accommodate the various tokens of the game (arsenals, infantry, mountains, etc.). At the same time, it's necessary to have rudimentary methods for basic utilities relating to the graph, tasks like adding new nodes to the graph, removing existing nodes from the graph, and moving graph elements from one node to another. So, for instance, if a cavalry unit advances one space, it will be necessary to delete that unit from one node in the graph while adding it to another node in the graph.

Graphs become most useful not simply in static form but when they are dynamically parsed and analyzed. Thus, once the graph is set up it becomes advantageous to move through the graph in various ways. Luckily computer scientists have devised rudimentary algorithms for doing what's called graph traversal. These are techniques that allow one, for instance, to move from any arbitrary position in the graph to any other arbitrary position in the graph along the most efficient path. (Graph edges can be given various weights, and these weights can affect the calculation for how much it costs to move through the graph. For instance a game character might move easily over land but more slowly through water.) Overall such approaches come under the heading of pathfinding. Pathfinding simply refers to the technique of finding viable paths through a graph. There are many different approaches to pathfinding, some more efficient than others, some more suitable to a particular task than others. For instance one might wish to start at an origin node and then proceed outward in concentric circles (the so-called “breadth-first” graph traversal). Or one might wish to start at an origin node and then explore as far as possible in one line before trying all the other directions (a “depth-first” traversal). Breadth-first graph traversals are very common in games for determining proximity. Is the player near an enemy? Given one unit, what is the nearest other unit?

screenshot
Pathfinding through a complex landscape

With a graph established, plus a few rudimentary pathfinding algorithms at hand, one may move game tokens through an imaginary landscape in a somewhat plausible fashion. This allows game characters to target a particular location in the graph, then move toward it. That's all well and good, however it won't suffice for most games. The decision making in Debord AI is more complex than that and it will require an additional technique. How are targets identified to begin with? Why choose one target, as opposed to another target? We need another AI component that will supplement what pathfinding is able to accomplish.

There are many different approaches to decision making. For complex, open-ended games like first-person shooters, it often makes sense to create behavior heuristics. These are essentially simple rules governed by state variables. For instance, an environmental trigger might move a monster or other non-player character (NPC) from an idle state into an aggressive state.

But Debord's game isn't like this. The Debord AI necessitates a different approach. The Game of War is not open-ended. In fact the game is rigidly structured, highly rule-bound, and even somewhat deterministic. From an AI perspective, the Game of War is similar to chess or tic-tac-toe, and thus calls for a specific sort of AI suitable to such games. This kind of AI is called min-max optimization. For min-max optimization two things are required at the outset. First, it is necessary to identify every possible move for any given state of the board game. (For an open-ended game like soccer that involves bodies and objects moving continuously through space, it is very hard if not impossible to itemize every possible move; for a highly structured game like chess, it is trivial to log every possible pawn advance, every possible tour of the knight, every possible translation of the rook, and so on.) Second, one must be able to compute a numerical score for any given state of the game board. To continue with the example of chess: one might count the scores of each piece, giving a relatively high score at the beginning of the match; but if a player loses a queen that player's score would drop precipitously, and likewise for other pieces. The score itself is not so important. What's crucial is that any given configuration of pieces could, at least in principle, be assigned a specific score. With these two technologies in place -- logging all possible moves and assigning each move a score -- min-max optimization proceeds in the following way: the AI creates an identical duplicate of the game board on which to experiment; the AI executes every possible move in sequence; a score is calculated for the new configuration produced by each move; finally the AI ranks each move based on its calculated score. With the process of optimization now concluded, one may simply select the highest ranked moved, knowing that this will be the most optimal move. (Here, “optimal” is defined exclusively through the configuration score; the design of such a metric will thus have profound consequences.) In common parlance, min-max optimization is also called “brute forcing” because it relies on no special finesse or intuition, simply an exhaustive calculation of all possible moves for any given state of the game board.

At this point I can't help but editorialize a bit. I've been a coder for a long time but I've never written AI before. Frankly I found the task daunting and omitted AI from the original beta launch of the game. So this experience has been revelatory even as I remain something of an amateur with AI. (As I mentioned above, all the techniques I just described are extremely common, the kind of stuff one might learn in a beginning course on game AI.) Still, I've noticed some superficial details about AI that reveal more fundamental truths about coding and computation. First is that code lends itself to a particular outcome: it lends itself to other code. I don't quite know how to put this. But in some ways AI is the ideal format for all coding. Code is designed in a way to be manipulated, not by humans per se, but by other pieces of code. In authoring AI, one essentially must create a secondary machine designed to play the primary machine. AI consists in grafting a secondary bit of code onto a primary bit. It's robots playing against robots. What's surprising however is the notion that code is already designed with this in mind. A fitting example might be functions. Functions contain interfaces, and these interfaces are pre-designed to accept only certain kinds of input. If you have a function wired to accept a floating-point number, you can't send it a bouquet of roses. That's what I mean by code being optimized to interact with other code. (And when one writes code, one doesn't, as it were, “bring a human touch” to the machine; quite the opposite, one must annul one's analogical, off-line humanity and translate it into a special symbolic, logical universe.)

Consider unit testing, the practice of writing code snippets that help to stress test your project and find bugs. Unit testing is, in the sense I'm describing here, merely a microcosm of the tendencies of all code. I've only recently come to this realization. Code wants to be executed by other code. And in a larger sense, coding tends toward unit testing and AI; these are the ideal conditions for all coding. A robot wants to be touched by another robot.

Image result for cow clicker

Many games reveal this fact. Many games essentially play themselves. The player is the mere attendant who clicks now and again, as the game more or less plays on its own. AI is a more plausible scenario than human input, at least from the perspective of code. In other words, no game is truly complete until it has its own AI; and any kind of game design is implicitly a way of designing how a symbolic machine might play the game, and win it. Symbolic systems don't really need the world, and in fact often actively lobby against it whether in word or in deed. (This is one of the reasons why Silicon Valley often has such screwy politics.)

This is about as far as I've gotten in authoring the Debord AI. I have the graph set up, I have pathfinding, and I have a rudimentary min-max algorithm in place. With this, game units can successfully move around the board on their own without cheating or making illegal moves. I was speaking with an acquaintance over the weekend and an important next step for me would be to incorporate some additional ways of analyzing the graph. For instance it would be very useful to know where the enemy units are in the landscape and at what concentration. Is the enemy clustered together in one large group? Or has the group split into two discrete factions? Have any stray units wandered too far away? A possible answer to such questions would be to incorporate what are called clustering algorithms. The “k-means” algorithm is one popular way to divide up a data set into various clusters. So in the future I might try to add some sort of clustering algorithm.

Why is this interesting? And what does this have to do with Debord? The most obvious answer is that it's not interesting at all. Or at least that these various techniques are really only interesting to computer programmers, but not particularly relevant to the discussion of Debord or his Game of War. Of course we know that games lend themselves well to the kind of numerical structures and logics native to computers. Not all games, of course, but this is certainly true for the highly structured and rule-bound games that Roger Caillois clustered under the heading of “agôn” games in his book Man, Play, and Games. These kinds of games have scores (numbers). They have clearly defined win states (logical conditions). They have rules (algorithms and control structures). It's no wonder that these kinds of games work so well on computers. Games already are computers. At least some kinds of games already are, Debord's included.

debordpsychogeo

For this reason I suspect that Debord AI is more interesting than it might seem at first glance. Recall some of the most famous strategies and techniques described by Debord in his writings, many which were also characteristic of the Situationist International more generally. I'm thinking of the techniques of psychogeography and “drifting” (dérive). I'm thinking of plagiarism and hijacking (détournement). I'm thinking of that iconic SI map of Paris in which various neighborhoods are cut up and rearranged and linked together in a rhizomatic structure.

Debord AI seems totally incompatible with all of this. There's no psychological geography at play here, only a highly rational and deterministic one. Debord's play style -- which we can glean from the documentation of a match he played with his wife -- is in fact highly structured into regular shapes that have been optimized for best play.

Figure8

We're left with two possible conclusions, both of which make reasonable sense to me. The first is that computers are less rigid than we think they are. As a data structure, graphs are in fact highly flexible. That famous SI map of Paris already looks a lot like a graph. And it wouldn't be too difficult to apply a clustering algorithm to Debord's psychogeographic itinerary. (I'm not implying that the results would be fruitful, merely that the material already lends itself to this form.)

The second conclusion is that Debord is not the person that we thought he was. It would be wise not to try to psychoanalyze an author through his works. But the evidence from this particular work is overwhelming. Debord's Game of War is not about drifting or hijacking. The game is highly structured, rational, and deterministic. Several years ago I labeled this a “nostalgic algorithm” given Debord's affection for a kind of soldiering that went out with the pith helmet. Although with Debord AI, one might characterize it in another way as well: a tactical algorithm, a way of using code to think about strategy and structure in its most unadulterated form. Or as Debord once confessed in a conversation with Giorgio Agamben, I'm not a philosopher...I'm a strategist.