Introducing: A Quantum Procedure for Map Generation
This is the blog version of a talk given at the IEEE Conference on Games 2020. Each slide is followed by what I say during that slide in the talk. You can find the paper here.
Hi, I’m James Wootton. I work at IBM Research. We build quantum computers and I used a couple of them to do some map generation for games. That’s what I’m going to tell you about today.
So what are quantum computers?
Well first let’s think about our normal digital computers for a moment. These express information in bits, and any algorithm can be compiled down into very simple operations on one or two bits. In saying this, I’m really thinking of the Boolean circuit model as a model for what a digital computer is. As an example, the simplest of these Boolean operations is the NOT gate, which just flips a single bit between 0 and 1.
Quantum computers are the same, except that the bits are stored in a way that can be described with quantum mechanics. Quantum mechanics is a more general theory than the usual Boolean logic that we use to describe bits. So this gives us more freedom, and allows us to manipulate the information in new and different ways. We get a set of basic quantum operations that we can use to build algorithms in very different ways. Some problems that are intractable for digital computers, because they need unreasonable time or resources to run, will become solvable with quantum computation.
This all requires much larger and better quantum hardware than we currently have. However, we do have prototype devices that can be used even now. Anyone can go to quantum-computing.ibm.com, create a quantum program, and send it off to our labs to run. It’ll go through control hardware which turns it into a series of microwave pulses. These then go into a fridge which cools a quantum chip down to nearly zero Kelvin, runs the program, and then sends back an output. This gets decoded by the control equipment and turned into nice, familiar 0s and 1s for you to look at.
So what does this hardware look like?
It is made up of ‘qubits’. These are quantum bits: quantum systems used to store bit values.
We can manipulate single qubits and also pairs of qubits in various ways. Some look like Boolean operations (like NOT and XOR), and others don’t. However, for the two qubit operations, we are limited in our choice of which pairs of qubits can be used. This is governed by the so-called ‘coupling map’ of the device. For example, in the device called Rochester that you can see here, the qubit labelled 0 can only directly interact with qubits 1 and 5.
Also, every manipulation we can perform, as well as the act of reading out the result, is subject to imperfections. Everything that can go wrong, will go wrong with some probability. This means that, if we were to attempt the arbitrarily long and complex processes found in most of the algorithms we know, we can expect to get nonsensical results.
To get sensible results from near-term hardware, we can try to base our algorithms explicitly on the things that quantum computers do naturally. One example is the generation of quantum interference effects. Doing this with a quantum computer is almost as easy doing it with water: like throwing a rock into a pond!
Another example is the simulation of quantum dynamics. Qubits are quantum particles, that evolve and interact according to the operations applied to them. If we want to study a process that acts like this, then it is trivially easy to get a quantum computer to help.
The application that we will look at now is exactly of this form. We will find something that we want to simulate for the purposes of procedural generation, argue that it is naturally captured by the dynamics of qubits, and then implement the simulation on a quantum computer.
To explain how, let’s have a closer look at qubits (although, admittedly, not close enough).
The contradiction at the heart of qubits (which we won’t have time to resolve) is that:
•They cannot store any more information than a single bit.
•Their internal state is more complex than that of a single bit.
So they are more than just a bit, while being no more than just a bit. Because of quantum!
The internal state of a qubit can be described in terms of three real numbers, ⟨X⟩, ⟨Y⟩ and ⟨Z⟩, each between +1 and -1. These are subject to the constraint that you can see here on the slide. This description is exactly the same as a much more familiar system: a ball. Any point on or in a sphere of unit radius can be described in terms of the cartesian coordinates: x, y and z. None of these may exceed the radius in either direction. And the distance from the center shouldn’t exceed the radius either. This is all exactly captured by these same conditions.
From this coincidence we get a nice spherical visualization of the qubit, which is known as the ‘Bloch sphere’.
Let’s just focus on the value of ⟨Z⟩. If we ask the qubit for an output, this value will tell us how likely we are to get a 0 or 1. For ⟨Z⟩=1, when we are at the north pole, we are certain to get 0. For ⟨Z⟩=-1 (the south pole) we are certain to get 1. For ⟨Z⟩=0 (any point along the equator) the outcome will be random. Anything else will be also random, but with a bias towards the closest pole.
The reverse of this is how we can calculate what the value of ⟨Z⟩ is for a qubit: run the process many times, determine what the probability is for the 0 and 1 outcomes, and use this to estimate ⟨Z⟩.
Note that the algorithm for map generation we present here depends on the values of the variables estimated in this way. Not on the random outcomes themselves. It is therefore a (mostly) deterministic process.
For n qubits we need 4ⁿ variables (which is exactly why these things are hard to emulate on standard digital hardware).
For example, ⟨ZZ⟩ describes how likely the outputs of two qubits are to agree. ⟨ZZ⟩=1 means definitely agree (both 0 or both 1). ⟨ZZ⟩=-1 means definitely disagree (so 01 or 10). The rest of the variables describe other important details regarding the way in which the qubits are correlated.
These correlations also satisfy constraints. Some are similar to the single qubit ones, allowing us to draw more spheres. There are also things like the monogamy of entanglement: Put simply, the more correlated two qubits are with each other, the less they can be correlated with other qubits.
We are going to use qubits to generate geopolitical maps. This will be done by simulating the sort of process you see in a game like ‘Civilization’: a bunch of settlers around the world all suddenly decide to found nations. These then grow and interact.
A quantum process is used to decide how the nations will act. Each nation will correspond to one qubit. The ⟨X⟩, ⟨Y⟩ and ⟨Z⟩ variables correspond to three different policies that a nation can pursue: attack, defend, and expansion into unclaimed territory.
We would expect that no realistic nation can maximally do all three things at once. Limited resources will mean that priorities need to be decided upon. In this way, the natural constraint on the state of a qubits automatically restricts the simulation to realistic behavior for nations.
Also, nations do not make their decisions independently. The variables describing correlations will cause their decisions to be correlated also. The constraints on correlations will also ensure that the behavior remains realistic. For example, the monogamy of entanglement will ensure that two nations at war with each other will focus their decisions on each other.
Admittedly, the constraints of quantum states are not a perfect reproduction of ‘The Art of War’. Someone not motivated by a love of quantum computing probably wouldn’t have come up with this method. But it seems to work quite nicely.
The quantum decision making process is embedded into a ‘game’. Nations get turns in which they can place a city on the map. Cities exert influence over surrounding territory. This then determines which nation controls territory, and can even result in cities changing loyalty.
These results are then fed back into the simulation. If a nation loses territory, for example, its qubit state will be manipulated to make it more defensive. If a city changes hands, the correlations between the two nations involved will be altered to reflect a state of war.
All of this is implemented in Python. The ‘qiskit’ framework is used to create and run the quantum jobs. More specifically, I built a package called ‘QuantumGraph’ on top of Qiskit, optimized exactly for these kinds of applications.
It is suitable for all your procedural generation needs! (or at least some of your quantum ones)
Put it all together, and we have a process that generates geopolitical maps growing over time.
If you hand over control of a nation to a player, you also have a game. The quantum process then serves as the AI for opponents (and also for an advisor to the player).
So how intelligent is this AI? Admittedly, it is not the best you will have ever seen. But it should at least be better than random decision making.
To test this, we ran a process in which all nations are are initialized in the state with ⟨X⟩=⟨Y⟩=⟨Z⟩. Since they have no bias to any particular policy, they make random decisions at first. Half of the nations (which we call the ‘standard’ nations) then undergo the standard process in which gains and losses of territory are fed back into the qubit states. This is not done for the other half (the ‘opponent’ nations). So these remain random, and insensitive to what is going on.
We’d expect to see the standard nations doing better, because they base their decision on what is actually happening. They should therefore gain more territory than their opponents. That’s exactly what we see when we emulate how the process would run on perfect quantum devices, using standard digital computers. This is only possible when we have small numbers of nations.
Note that I tried to use the word ‘simulate’ in the paper to refer to quantum computers being used for simulation tasks, and ‘emulate’ for when a digital computer is used to reproduce the results we would expect from quantum devices. But when doing this, I forgot about the titles of the figures, as you see here. They should actually refer to emulation.
Now for real hardware: 28 nations on the 28 qubit device called ‘Cambridge’, and 53 nations on the 53 qubit ‘Rochester. In both cases, evidence of the ‘intelligence’ remains. It is not quite as clear as before, perhaps due to the effects of noise.
What we have seen here is an initial and rudimentary example of current quantum devices doing a task that is relevant for procedural generation, and for games.
If we look to the history of using computers for games, what can we compare it to? The goal would be to develop a quantum milestone equivalent to 1962's Spacewar!: the first example of a novel and unique game that was made possible through the new technology.
Is this map generation process an example of novel and unique procedural generation, or an AI for a novel and unique game?
Probably not.
Perhaps a more realistic comparison is the Checkers AI developed at IBM in the 1950s: more about testing the capabilities of the new technology than giving users something that they need.
So, in conclusion, quantum computers exist. They are currently limited, but we can use their intrinsic ability to perform quantum simulations for procedural generation.
What about their ability to generate interference effects? Can that be used for procedural generation too? You can find out about that in my talk in the PCG workshop at FDG next month!
