{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Quantum Procedural Generation\n", "\n", "#### James R. Wootton, IBM Research - Zurich\n", "\n", "*Procedural generation is an interdisciplinary field which makes use of a variety of of computational methods. Since quantum computers promise advantages in a wide variety of computational problems, it is highly probable that this emerging technology will be able to make a significant impact on procedural generation in multiple areas. Here we will introduce the basic concepts of quantum programming, and use them to implement quantum methods for simple, proof-of-principle procedural generation. Specifically, we will introduce algorithms to generate terrain that are designed to be compatible with near-term quantum hardware.*\n", "\n", "## Section1: Introduction\n", "\n", "### The conflict at the heart of procedural generation\n", "\n", "Procedural generation is a term that can be used to describe any situtation in which some form of content is generated by an algorithm. If we restrict to uses relevant to computer games, procedural generation can be used to generate puzzles, levels, maps or even the entire life history of a character$^1$.\n", "\n", "Procedural generation typically creates content determinsitically from a seed, which itself is typically generated randomly. The combined process therefore results in the random generation of content. However, it is highly important to properly balance this randomness with some form of structure.\n", "\n", "One reason to constrain the randomness is motivated by the needs of the human player, often known as the \"10,000 bowls of oatmeal\" problem$^2$. It describes that fact that, though two samples of some random process can be extremely distinct from an information theoretic point of view, they might not differ in any way that humans care about. Though two bowls of porridge will have uncountable differences in the number, size and placement of oats, to humans they appear effectively identical. To provide interesting and engaging player experiences from each sample, the randomness must be reigned in by a degree of structure.\n", "\n", "Another reason comes from the needs of the computer used to implement the game. If we were to just take the basic elements of a game and randomly throw them together, we might hope to create new and unique challenges. However, it is very easy for this to result in puzzles that cannot be solved or levels that cannot be completed. Furthermore, analysing this content to assess solvability can be an extremely hard computational problem$^3$. The time taken for the analysis could then very easily surpass the time allowed for a loading screen.\n", "\n", "One way to avoid this problem is to generate content with some structure that an analysis process can make use of, allowing it to remain fast and effective. Alternatively, content could be generated such that it is certain to be suitable: such as creating a maze with a clear path from start to finish, and then adding branching points. This will again add some structure to the content: such as some remaining trace of what elements are present to ensure suitability and which are there to be random.\n", "\n", "Unfortunately, it can be that the human and computational needs for structure in content can be in conflict. For example, the illusion of having access to an infinite variety of possible experiences will be ruined if the player notices structure left there to help the computer. Also, having structure baked-in to allow easy computational analysis risks the player discovering the same methods of analysis themselves. Then playing the game would just become rote implementation of an algorithm, which does not make for an engaging experience.\n", "\n", "To overcome this issue, many methods for procedural generation have been created. By using, adapting and combining them, designers are able to create content that is tailored to the particular experience they wish to create, while satisfy the needs of both humans and computers. Nevertheless, new methods and new technologies provide new opportunities to do this in ever more sophisticated ways.\n", "\n", "### How quantum computers can help\n", "\n", "Quantum computation is a new architecture for computing. Once full-scale, fault-tolerant quantum computation is realized, it will provide a wide range of new algorithms to solve various problems in many different areas$^{4,5}$. These will provide significant reduction in computational complexity compared to algorithms for standard computers. For games, this means that many more different tasks will be acheivable within the timescale of a loading screen.\n", "\n", "One class of problems with for which a potential quantum advantage is known is that of constraint satisfiability problems. The problem of graph colouring, for example, is one that can emerge in problems related to game-related procedural generation. Indeed, the popular puzzle *Sudoku* is an example of graph colouring$^6$. For these problems it has been shown that quantum computers have the potential to drastically reduce the time required to find a solution. However, the extent of this speed-up depend greatly on as yet unknown specifications for the fully-fledged form of these devices$^7$.\n", "\n", "With this in mind, and given that the fault-tolerant era of quantum computers is still many years away, it is hard to speculate about the impact of these devices on procedural generation. However, we do not need to wait in order to see results. Prototype quantum processors are already available, and are already pushing the bounds of what even the largest supercomputers can keep up with$^{8,9}$.\n", "\n", "These near-term devices will not be capable of implementing textbook quantum algorithms. However, they will nevertheless be able to produce unique effects emerging from the dynamics of quantum systems. Such dynamics have already been of some use in procedural generation, in the form of the popular 'Wave Function Collapse' algorithm$^{10}$. Though not a quantum algorithm itself, its design was inspired by quantum dynamics. It will therefore be greatly interesting to see how genuine quantum dynamics will inspire new methods for procedural generation.\n", "\n", "### Procedural generation with near-term quantum computers\n", "\n", "Current and near-term quantum computers will be limited in their usefulness due to a range of factors. One is the number of *qubits*: the fundamental building block of quantum computers. These are the quantum equivalent of the bit, and so the number of qubits determines how much information can be stored in a quantum computer. Manipulations of qubits are also the means by which information in processed, and so they are in some sense also the quantum analogue of the transistor.\n", "\n", "Another limit is that caused by unwanted interactions and imperfectations in any manipulations of the qubits. These effects are collectively described as *noise*. Though the effects of this noise are relatively low for short quantum programs, they can easily become overwhelming.\n", "\n", "We must also contend with connectivity. This limits the set of operations that can be performed on the qubits. Prototype devices are always universal in principle. This means that any quantum program can be compiled down to their basic instruction set, even though the details of these instruction sets may differ from device to device. However, the exact nature of the connectivity in any device means that some processes cannot be implemented in a straightforward manner. Given the degree of noise that will build up in any process that is not straightforward, this provides a practical constraint on what processes are possible.\n", "\n", "Given these constraints, we are still some time away from useful implementations of textbook quantum algorithms. Near-term at quantum procedural generation must therefore be more limited in scope.\n", "\n", "In the rest of this paper, we will consider simple applications of quantum computing to the problem of generating terrain. Specifically, we will use it to make islands. The algorithms will be designed such that they can generate an interesting island, pass it to a game engine, and then render it ready for a player to explore, all within the time scale of a loading screen. Three different methods to to this are presented in the following three sections.\n", "\n", "[Section 2](2_SingleQubit.ipynb) presents a method that uses only a single qubit. This is intended as an introductory example, and is used to present the basic concepts of quantum computing to interested parties who have no background in anything quantum.\n", "\n", "[Section 3](3_FewQubit.ipynb) presents a method that is designed to squeeze as much performance as possible from devices of around 10 qubits. This method is therefore well-suited to using the prototype quantum devices that are currently publicly accessible, such as the 14 qubit *Melbourne* device available from the IBM Q Experience$^{11}$. Also, since devices of such sizes are easy to simulate using standard computers, this method is also well-suited to using simulators.\n", "\n", "[Section 4](4_ManyQubit.ipynb) presents a method that could be scaled up to quantum devices with an arbitrarily large number of qubits. The implementation is specifically tailored for the IBM devices with a heavy hexagonal connectivity graph, such as the recently released 53 qubit *Rochester* device$^{12}$.\n", "\n", "[Section 5](5_A_Combined_Approach.ipynb) puts it all together." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## References\n", "\n", "1. [\"Procedural Generation in Game Design\" Edited by T. Short and T Adams (2017)](https://www.crcpress.com/Procedural-Generation-in-Game-Design/Short-Adams/p/book/9781498799195)\n", "2. [\"So you want to build a generator…\", K. Compton (2016).](https://galaxykate0.tumblr.com/post/139774965871/so-you-want-to-build-a-generator)\n", "3. [\"Classic Nintendo Games are (Computationally) Hard\", Aloupis et al. (2012).](https://arxiv.org/abs/1203.1895)\n", "4. [\"Quantum Algorithm Zoo\", maintained by Stephen Jordan.](https://quantumalgorithmzoo.org/)\n", "5. [\"Learn Quantum Computing using Qiskit\", Qiskit Community (2019)](https://community.qiskit.org/textbook/)\n", "6. [\"Sudokus and Gröbner Bases: Not Only a Divertimento\", Gago-Vargas et al. (2006).](https://link.springer.com/chapter/10.1007%2F11870814_13)\n", "7. [\"Applying quantum algorithms to constraint satisfiability problems\", E. Campbell et al. (2019).](https://arxiv.org/abs/1810.05582)\n", "8. [\"Quantum supremacy using a programmable superconducting processor\", Arute et al. (2019).](https://www.nature.com/articles/s41586-019-1666-5)\n", "9. [\"On Quantum Supremacy\", E. Pednault et al. (2019)](https://www.ibm.com/blogs/research/2019/10/on-quantum-supremacy/)\n", "10. [WaveFunctionCollapse repository on GitHub.](https://github.com/mxgmn/WaveFunctionCollapse)\n", "11. [IBM Q Experience website.](https://quantum-computing.ibm.com/)\n", "12. [\"Quantum computation center opens\", D. McClure and J. Gambetta (2019).](https://www.ibm.com/blogs/research/2019/09/quantum-computation-center/)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.7.0" } }, "nbformat": 4, "nbformat_minor": 2 }