Before we go into details on how to show that Civ:BE,V, and VI are amongst the hardest games in existence, we should develop the language necessary for this. In particular, we will have a very nice definition of what does it mean to be "hard" from a computational perspective. We will also learn that computation is not limited to the silicon-based device with which you are reading this--it's far more ubiquitous than that!

What is computability? For us, it means that there exists some sort of machine that is able to execute some set of instructions, and maybe return a result. For example, a light switch ("when button pressed, let current flow to the lightbulb"), flipping a coin ("when flipped, return randomly heads or tails"), or DNA replication ("unzip molecule, read molecule, copy molecule...").

The mathematical model that we normally use to model this is called a Turing Machine (TM). It is a mathematical object, equipped with an infinitely-long tape (hence the mathematical part), a way to keep an internal state, and a head that reads from the tape and executes instructions based on a function called the transition function, or \(\delta\). A useful way to think about it is as a mathematical description of an algorithm, or computer program. For example, a TM adding two bits will have, say, an instruction saying "if I read \(1\) and my state is \(1\), write \(0\). Set the state to \(1\). Move the head to the right."

It turns out that TMs, although able to run for an infinite amount of time and space (e.g., "if you read any symbol on the tape, or if the tape is blank, move the head to the right"), have a finite description. This can be represented as a finite string, and passed in to another TM for execution. Kind of how your browser (a program), runs on your machine's operating system (also a program). A TM able to simulate any other TM is called a Universal Turing Machine (UTM).

Let me tie it back to what we are trying to do: showing that Civ is one of the hardest games. The proof consists on showing that the rules of the game have an analogue with an existing UTM. When we allow for infinite space and time (just as in any other TM), we will have have shown that Civ is able to simulate, in-game, a UTM. I'll elaborate more in the next section.

Before that, it might be worthwhile addressing another point: suppose you can build such a UTM inside Civ (and we'll see later, you can). That doesn't mean the game is "hard"! It just means the rules of Civ allow for any program to be ran.

It sounds like having infinite memory (or any unbounded resource) and the ability to simulate other computers means that a UTM is infinitely powerful. Yes and no. It turns out that the set of problems a computer can solve (call it R) is, in fact, rather small. A way to think about it is that there is no algorithm (TM) to decide whether an arbitrary, input TM will loop forever. This is known as the Halting Problem, and it is one of the central pillars of computation. Since there is no TM that can solve this problem, we say that the Halting Problem is undecidable.

Any mathematical or physical construct (a "model of computation") that is as powerful as a UTM is, in fact, equivalent to it. That means that it can compute everything in R: no more, no less. Models equivalent to an UTM are said to be Turing-complete. By this equivalence, it follows that a UTM could simulate any Turing-complete model of computation with some penalty to space or time. For example, your laptop is based off the Random Access model, and has limited memory. That means that a laptop, though amazing in its ability to run programs, is actually a lot weaker than a UTM. Then again, if you run out of memory, you could write a tiny program to prompt to you to add a new hard drive (i.e., you already ran out of RAM and are writing to disk instead). So it's not really a problem.

The last thing we'll do in this section, just to drive the point home, is to provide some examples of Turing-complete models of computation. Each and every one of these models has two things in common: one, they can simulate an arbitrary algorithm (i.e., you can build a UTM inside of them), and, second, they are not realisable without an unbounded resource.

I'll give three examples: the Game of Life cellular automaton, a class of neural networks, and Magic: The Gathering (MTG). The paper contains more examples (e.g., PowerPoint!), but I want to get right to the Civ stuff.

The Game of Life is a cellular automaton: an infinite grid where every cell takes in one of two states ("alive"/"dead"). It has some rules around evolution (e.g., if the current cell is alive but only one of its neighbours is alive, the current cell dies) which give rise to some very, very interesting patterns. It turns out that the rules, along with the grid, are able to build a UTM--so, the ruleset is Turing-complete. More interestingly, it is not possible to determine whether from a state of the grid, another state will emerge, so the Game of Life is undecidable!

Neural networks were shown in the 90s to be able to compute a function from a rather large class of functions (call it B). The model of computation is slightly different: you have a two-layer neural network, with some activation function, and it can approximate any element of B to an arbitrary precision. Since an alternative definition of R is "all numbers that can be approximated in finite time", it's simple to show that B and R are equivalent in a certain sense. In fact, (another) way to think of TMs is as (partial) functions. You need the partial part because the TM may not halt, but otherwise it's the same thing. Note that here the unbounded resource is the width of the neural network: you'll need a massively wide neural network to simulate most functions of interest--but what matters is that you can, and sometimes efficiently! I also showed on that paper that it's not possible to determine the best architecture to approximate a function, so in a certain sense they are also undecidable.

MTG is a card game. When I was a kid, I collected them because I liked the art. But turns out they are good for playing, too--and the rules are very, very intricate. More interestingly, one can build a UTM in-game, and this UTM itself exists physically. The rules for a MTG UTM are the same as the game (and are written in the cards themselves). The tape is expanded dynamically by placing tokens (so, formally, the UTM does use an unbounded resource). What is most remarkable about this construction, is that computation happens by forcing: it's a two-player construct and the execution of any TM happens by simply following the rules. You could sit there all day "playing" without actually being able to do much. This, in turn, also has some repercussions for regular MTG play: if you assume that there is no turn timer, and you have infinite tokens, you can run any TM. This means that MTG-UTM can compute R, and since it was built inside a game session, it follows that MTG is undecidable: there does not exist an algorithm to demonstrate a forced win given an arbitrary state of the game. Pretty cool, huh?

Civ is a rather complex, turn-based game, and explaining it in detail might warrant its own post. For our purposes, it suffices to note that you are in charge of an empire/extrasolar colony. It is played on a map divided in hexagonal tiles ("hexes"). You play against other players (usually the AI, in my case; I can't handle human interaction), and via diplomacy, economy, technology and culture, you win when meeting one of the multiple victory conditions. These conditions are slightly different on every game (domination victory means you hold all the other player's capitals, for example). We won't care much about them until our proof on decidability.

At every turn, you take most, if not all, of the actions available to you (e.g., moving a unit depends on the number of available moves), and focus on the overall management of your empire. The backbone of your empire are the cities, which are in charge of producing units, expanding your borders, and producing resources via citizens. This last part is kind of important: the citizens work the hexes and based on improvements you have built with a separate unit (the worker) the yields are altered. For example, a citizen could work a base plains hex, netting you \(+2\) food (say) every turn, but if you were to build an Academy on it, it will yield \(+2\) science as well.

The games are far more complex than this, but what we need to build UTMs is surprisingly little. By now you probably realised that building a UTM in Civ isn't as hard as showing that the rules are able to simulate an UTM. After all, The Game of Life is on an infinitely large binary grid, MTG is on an infinitely large number of tokens, and so on. So, all we need to do is assume an unbounded resource: for us, it will be the map size. We will also disable the turn timer (limit), which can be done from the setup screen. Proof-wise, we also should assume that the other players don't interfere with the computation, but if your map is infinite, that's a relatively simple thing to achieve. In practice, I just set the difficulty super low and played against nice opponents. The first time I did this I had Alexander the Great, and that guy is really trigger happy ):

We have three proofs: one for Civ:V, one for Civ:BE, and one for Civ:VI. The structure is very simple: We show that there exists a set of in-game rules and actions \((\Gamma, \delta)\) one can take that simulate the rules and actions of an existing UTM. Then, in order to ensure that the simulation is not too slow, we also show that \((\Gamma, \delta)\) is bounded for any instruction. This last part is not a strict requirement, but if the game mechanics interfere in any way--for example, by having a specific TM that will take forever to simulate in-game--it would leave our construction infeasible. Once we start talking about decidability, having a strict bound on the simulation time will also make more sense.

In Civ:V and Civ:BE, you have access to a worker. This unit is able to build and remove improvements indefinitely. Crucially, some of these improvements can be built outside of your borders. So, the plan is as follows: we use one worker to build and remove improvements on the "tape" (all of the map, minus a reserved section), and another worker to build and remove improvements as the "state" (the reserved section; suppose it's a city that you own). The tape worker is then the UTM head, and the state worker is, well, the way to update states.

In Civ:V, we will build roads and railroads. That means that instead of a binary symbol set (e.g., your laptop uses binary) we use a ternary symbol set on the tape. It makes no difference from a computational perspective. We also use roads in the state worker. The worker moves left or right on the map and writes or removes roads/railroads accordingly. Interestingly, the delay is constant: the slowest instruction you will ever have executed in our Civ:V UTM is "remove one railroad and write a road", which takes a fixed amount of turns. The actual UTM can be found in the links, and a full description of \((\Gamma, \delta)\) is in the paper.

In Civ:BE we can get a bit more creative, and make it also a ternary symbol set. Instead of building roads and railroads, we use roads (or magrails) and, along with the tape worker, we have a military unit (say, a rover). This unit executes parts of the instructions, and pillages an improvement. So we have as our tape alphabet "road, pillaged, no improvement." For the states, our state worker builds an improvement with a specific Culture yield (the Terrascape). We measure the state by checking the difference in total Culture yields every turn. Just as in Civ:V's UTM, the overhead is constant, so this construction is 1:1 with a conventional UTM. As before, the actual UTM can be found in the links, and a full description of \((\Gamma, \delta)\) is in the paper.

For Civ:VI we have to get really creative. This is because workers have limited charges and they can't modify resources outside of your borders, which severely limits our options.

Our tape is now going to be a chain of cities, and the symbols on the tape are going to be determined by whether a citizen is working a specific hex, or not. We can cap the growth of the cities to avoid complications; and we can use certain geographical features to ensure we actually have enough citizens (i.e., food). Just as in the MTG UTM, our tape is not infinite from the start: we need to grow it as-needed, so we will incur a penalty in simulation overhead. To see where in the tape we are located, we'll use a worker as the head. It won't do much outside of telling us where we should be reading.

Analogous to the Civ:BE UTM, our state will be given by a resource accumulation. In this case we assume the player can build an improvement called a monastery, which is nicely behaved and yields a (sort of) constant amount of faith every turn. We assume the player has already built them, so we can swap citizens as needed in order to encode the state.

All in all, this is a very large and complex UTM. Due to the tape expansion scheme, this UTM runs linearly more slowly than a regular UTM. It's also very brittle and hard to realise in-game. But it can be done! We could always use cities and forests (chop and plant) to encode states. We could also build a two-player UTM where one player pillages roads and the other repairs them. So, while this construction is straightforward, it's not the only or the simplest.

A diagram of the Civ:VI UTM construction. The top strip contains cities acting as the tape cells, with some cells being worked on (marked with an "x"). A tape worker is indicating which cell is being read. At the bottom we have two cities tracking the states with monasteries (denoted as M). Citizens that can't work a monastery are tasked to work on farms (F).

One thing you might have noticed is that all of our constructions used in-game rules and objects. In fact, there's nothing stopping you from implementing this by using the API. Or by manually executing it, as we will discuss in a bit. This also has an important implication: the states that are able to execute a computation arise naturally during gameplay. Of course, in generalised gameplay (infinite map, infinite turns), the states that one can observe are much richer: in fact, they are precisely R. So what does this mean?

It means that (from the last section) you can build TMs to run inside the game. It also means that you can build a special TM (the UTM) that can simulate any TM. Which means, that one of the questions one can ask to this UTM is "does this (arbitrary) TM loop forever?". As we saw earlier, this is the Halting Problem and it's undecidable.

More interestingly, suppose you want to know if, from a game state \(s\), there exists a sequence of legal moves \(A = (a_1, a_2, \dots)\) that yields a "forced win": i.e., if you execute \(A\), you win the game. Since you have to execute a series of steps to determine the answer, this is an algorithm. This is therefore a TM--call it \(M_A\). This TM can therefore be simulated in-game with your UTM. Then the question "Does \(A\) produce a forced win with \(s\)?" is equivalent to the question "Does \(M_A\) halt given \(s\)?"--a question we know very well: it's the Halting Problem!

So the problem of determining a winning sequence of moves in (generalised) Civilization V, VI, or Beyond Earth, is undecidable!

Or, in English:

You can't answer that question! There's no algorithm for that!

Or, cooler:

(Generalised) Civilization V, VI, and Beyond Earth are amongst the hardest games in existence!

I want to close this section with a short example of how closely related a TM is to an actual Civ state. For this, we'll be talking about a TM that "wins" the Busy Beaver game. The implementation and execution are in here, and a bit more detailed in the paper.

The Busy Beaver challenges the player (a human or a TM) to find the smallest \(n\)-state TM that outputs the most number of \(1\)s on the tape. The winner is called the \(n^{\text{th}}\) Busy Beaver, or BB-\(n\). In the link I implemented BB-\(3\) on a running Civ:BE session, and you can go over the paper for the details of the implementation. Here we'll discuss a few interesting things: one, commonality, and two, decidability.

For commonality I mean that there are many "theoretical" problems that actually appear very frequently in realistic applications. For example, BB-\(n\) can be thought of as a similar, Civ-like question. Imagine that you would win the game if you built the most roads in the map. Naturally, you would win if you wrote the most roads the fastest. So, you want a small TM that solves that problem. In particular, you would want to find a Busy Beaver. If you are constrained in resources (e.g., you can't afford to maintain all of these workers!) you would need to calibrate the "\(n\)" in BB-\(n\). While this is still somewhat unpractical, note that there's nothing stopping us from observing something similar in the game--and actually executing it, as I mentioned earlier.

More importantly, the problem of finding BB-\(n\) for arbitrary \(n\) is undecidable. So there are questions you can ask to the game that have no answer. In fact, although now I'm repeating myself, the problem of determining a forced win is undecidable. While this is not exactly surprising by now (consider the fact that the game is running on a computer; so everything that a computer/UTM can't do won't be able to be done by Civ) it is indeed surprising that cannot be answered by the rules of the game--no matter how powerful they are!

There are two things I'd like to talk about. One is how realistic our assumptions were. The second is whether there are any applications for this, or other work. I just spent like two hours writing about problems one can't ever solve (and infinite tapes and theoretical models of computation), so it might sound odd to talk about practicalities. You'll see what I mean by that in a second!

What about the non-generalised versions of Civ--i.e., the ones we play in the computer with finite memory and finite time? The results for Turing-completeness and undecidability change, but surprisingly not that much.

Regarding Turing-completeness, I mentioned earlier that in the case of a regular computer vs. a TM, a computer running out of memory can handle that with a small overhead by prompting the user to add more tape (e.g., a new hard drive). For example, back in the 90's you needed to install games by inserting \(1-4\) CDs in sequence; so the computation/tape expansion argument is rather general. This argument, originally given by Hopcroft, Motwani and Ullman in their book "Introduction to Automata Theory, Languages and Computation" (my second-best textbook friend in grad school), can be adapted to our UTMs without much hassle. For example, a very naïve implementation would just duplicate the state hexes (which are constant size) and use multiple computers and saves to simulate extended tapes. Note that this does not require a modification of Civ's code (e.g., in Civ:VI you could use the starting seed and some constant initial time to configure the state hexes; in Civ:V/BE you could use mods to pre-populate the maps), but any TM being simulated would have to include that little overhead. Then again, we already have samples of that intrinsically written as part of Civ:VI's UTM (or, e.g., MTG's).

Then again (following Hopcroft et al.'s argument), we can also measure how likely we will end up expanding a tape. We do this by estimating the number of internal states for a UTM. In the case of Civ:V, on a single Huge map size (as a loose upper bound) we have \(128 \times 80\) hexes, minus \(10\) for the state-tracking. Then the UTM for Civ:V has \(\vert Q\vert\vert\Gamma\vert^{(128 \times 80 - 10)} \approx 8.92 \times 10^{4,881}\) possible configurations (where \(\vert Q \vert=10\), \(\vert \Gamma \vert=3\) are the sizes of the state set and tape alphabet, respectively). That's not small potatoes!

Ok, it's kind of small--using Hopcroft et al.'s argument--since a computer with \(128\) Mb of main memory and a \(30\) Gb HDD has \(256^{30,128,000,000}\) states. But it's still quite a bit :) Kind of like a size-F potato.^{I can't believe I just spent 10 minutes learning about potato sizing.}

A large part of computer science involves studying how difficult computational problems can be. We saw that some of these problems lie in R, the class of all TMs that halt. Of course, we can subdivide R into different classes. One common subdivision is based on how much time (steps) it takes them to halt as a function of the size (in bits) of the input. E.g., a sorting algorithm normally runs in \(kn \log{(n)}\), where \(n\) is the size of the array, and \(k\) is any constant.

Let's consider the problem of writing AI to play the game effectively. We'll start with an "easier" problem: chess. You can take an arbitrary state of the (say) \(n \times n\) board, with the \(4n\) pieces in some arrangement, and then be tasked to determine whether you can win. Note that this is the same question as in Civ's proof of undecidability. To solve this problem, you must "play" some moves and rewind. This means that if you move a piece (call it \(x\)), you have \(2n\) possible outcomes. In your next turn, you will have \(2n\) available moves, but are conditioned on the previous \(2n\) moves, which is conditioned in the movement of \(x\dots\) Yikes. We can observe two things from that:

• It's a HUGE number of possible movements, and
• It behaves like a tree.

Trees are pretty cool (e.g., the sorting algorithm is also based on a tree). In here we can see that the number of possible movements (a.k.a. the "branching factor" of our tree) in \(n\times n\) chess is quite large. Too large to use conventional, tree-based search algorithms, like A*!

So what is the branching factor in non-generalised Civ? That's still an open question (see the next section). But for generalised chess, it's exponential. So to properly solve generalised chess, you will need exponential time on \(n\), something like \(2^{kn^p}\), where \(p\) is another constant. We call that class of problems EXPTIME. Generalised chess, some forms of Go, and other games are in EXPTIME. The difference between EXPTIME and, say, generalised Zelda games (which is in PSPACE, the class that is solvable by using \(kn^p\) tape cells) is a bit fuzzy for reasons we won't go into detail here, but your choice of algorithms to play the game are still dependent on its complexity.

What does this have to do with AI for Civ? Well, for one, the effectiveness of the algorithms used to "solve" or "approximately solve" a problem (a.k.a. a heuristic), are strongly dependent on how hard the problem is. Moreover, AI plays a game by solving problems, such as path-finding for first-person shooters. Here's an example of the then-groundbreaking AI used in Left 4 Dead 2. In general, it is safe to assume that an FPS is an "easier" game (in PSPACE), and path-finding heuristics would work well. Note that Civ does use a rudimentary path-finding heuristic: when you task a unit to move, it will try to find the shortest-path to the target.

But trying to solve a problem with such a large branching factor (the problem here being "how to win at Civ") suggests that using heavier algorithms would work best. For example, AlphaGo Zero smashed records (and humans, I suppose) for Go by using a combination of non-linear models (neural networks) as well as a heuristic for pruning the tree, known as Monte Carlo tree search. Nobody actually told the model how to win the game, but it knew the rules and eventually developed a very unique play style.

The AI in Civ currently uses a mixture of if-else statements, as well as "cheats" (bonuses) in higher difficulty levels. This makes the AI quite predictable, as well as slightly reducing immersion. Then again, training an AlphaGo Zero-level neural-network costs millions of dollars, so there's that. If Civ happens to be easier (e.g., in PSPACE), maybe an array of modified path-finding algorithms could work. But if it's harder than Go, we probably will be stuck in if-else land for a while.

Where computational complexity theory really shines--last thing I'll say about this, I swear--is in showing that some problems are equivalent to one another. For example, the famous Traveling Salesperson Problem (TSP) involves finding the shortest route that visits all cities in a graph without repeating itself. It turns out that this problem is equivalent to many other problems in computer science (most graph colourings, circuit optimization, some neural-network training, etcetera). We haven't talked about TSP's complexity class, but we have talked about PSPACE: turns out bounded Go is PSPACE-complete, so in a sense, an algorithm that solves bounded Go also solves Zelda games. This means that one could "solve" one problem by first transforming it (reducing it) to another, and then just solving that instead. But first we would have to show that Civ belongs to any of these classes!

I mentioned bounded Go as being PSPACE-complete and EXPTIME-complete otherwise. Hearn and Demaine show that two-player games with perfect information are in general EXPTIME-complete. So, generalised chess, generalised Go, and all these games where you can actually see your opponent's pieces are decidable (and relatively nice, since the "complete" means that they are reducible among problems within the same class). They also show that for imperfect information (like vanilla Civ without a turn limit) are in general undecidable; even when it is space-bounded in some cases.

But what does this mean with respect to Civ's undecidability and Turing-completeness? Well, if we lift the unbounded space assumption, but allow for unlimited turns, the game (now with a full-on opponent) is still very likely undecidable. But how can this be? This means that a very real game (I always play without a turn limit anyway) is able to manipulate bounded resources to perform arbitrary computation (that is, compute the infinite set R).

Civ is not the first game able to do this. As I mentioned before, MTG can do a similar thing (and is a lot more physical than Civ)! However, the number of tokens do put a potato in our computational tailpipe, in the sense that we are physically limited by their existence. Then again, what makes all of this interesting is that we normally look for loopholes in order to "free up" the theoretical requirement of unbounded space in TMs. Hearn and Demaine (and if you read this far, and are interested in this, you might want to look at their book; especially chapter 8) point out that this is more of a physics question. One could subscribe to the "many-worlds" interpretation of quantum physics, apply that to a quantum computer, and assume that the "you" that was able to execute arbitrary computation in polynomial time is the "real you". It's nearly impossible to show that this actually happens, so there's that.

Games-as-computers suggest an alternative: you execute arbitrary computation, and the players execute the moves. The space requirement is not part of the computation, but by having infinite memory (by the players) or maybe by forced wins (like in MTG) you can still do it in bounded space. While this might sound kind of weird, think of quantum entanglement: there, you transmit information seemingly faster than the speed of light. But, since information cannot travel faster than the speed of light, the entangled measurement will yield a uniformly random outcome until you have observed the other measurement (which cannot happen faster than the speed of light).

We learned in this post that generalised Civ can execute any algorithm, and that it is impossible to determine whether a sequence of moves yields a win within this game. However, our argument relies on having an infinite-sized map, and no-turn limits. In practice, these constraints may seem unrealistic, but I argued that even without one of these constraints--and, in fact, under regular, strategic play--the games are very likely undecidable, and hence amongst the hardest games in existence. This is not an exaggeration. All models of computation are equivalent, so it doesn't quite matter if you run Civ on a laptop, super computer, or DNA strands: R is still R.

The findings have interesting repercussions for Civ and for research in the computational complexity of games. Namely, it suggests that building effective AI for Civ and other similar games requires remarkably powerful, state-of-the-art algorithms. I conjecture that for an arbitrary map size (but still finite) and unbounded turn times, the games should be in EXPTIME-complete. That means that they must be at least as hard as (generalised) chess! This is a very realistic problem: when you set up your game, you have an arbitrary map size (with mods, even more so); and you can disable the turn timer. This is an interesting conjecture because while intuitively Civ does sound harder than generalised chess, Hearn and Demaine indicate that two-player games with imperfect information are, in fact, undecidable.

An effective reduction from Civ to a known problem in, say, EXPTIME-complete, will very likely also provide information about other games in this genre, known as 4X. The reason for that is that in spite of their very different mechanics (even between installments, most Civs are quite different) all 4X games have the same "multiple resources, multiple games, multiple victory conditions; but bounded space and multiple-actions per-turn" theme going on. So it is quite probable that they are also reducible amongst each other.

A minor nuance in this conjecture might be diplomatic victories for Civ:VI: a player can decrease or increase their "diplomatic score", and once this score reaches a certain quantity, you win. We know that if we lift the turn limit you can actually have an infinite loop where you increase-decrease your score, so they might be undecidable then.

All in all, I hope you liked this post. Like Fry would say, it took a few hours to write, so I thought it'd take a few hours to read. But hopefully you found it interesting. I particularly think that the addition of computational complexity theory to actual videogame play could yield some very interesting results. If not, you can think of it the other way: it's quite possible that the study of games will yield even more interesting results in theoretical computer science!

Cool, right?

Just to close this up I'd like to thank IEEE Transactions on Games' reviewers; as well as some folks on a Reddit post who asked very, very good questions. All of that improved the quality of the paper significantly!