NP-hard problems regularly come up in video games, with interesting connections to real-world problems. In the game Minecraft, players place torches on the ground to light up dark areas. Placing them in a way that minimizes the total number of torches to save resources is far from trivial. In this paper, we use Quantum Computing to approach this problem. To this end, we derive a QUBO formulation of the torch placement problem, which we uncover to be very similar to another NP-hard problem. We employ a solution strategy that involves learning Lagrangian weights in an iterative process, adding to the ever growing toolbox of QUBO formulations. Finally, we perform experiments on real quantum hardware using real game data to demonstrate that our approach yields good torch placements.
Intriguing scientific problems pop up when you would rather take your mind of them for a while, e.g., when playing video games — although, of course, it comes as no complete surprise to encounter them in this domain. Video games, by nature, pose a wide range of problems that players are expected to solve in order to progress, such as slaying enemies, traversing mazes or solving logical puzzles. Some games have even been shown to be NP-complete [1]. It is, however, a mild surprise to encounter them in Minecraft, which is an exceptionally serene open-world sandbox game developed by Mojang and first published around 2010 1. In Minecraft, players can roam around a vast world containing mountains, oceans and caves made up entirely of cubic blocks, giving the game its unique and slightly retro visual quality (see Fig. 1). The game has been praised for fostering creativity in children (and adults) and has even been used as a tool for teaching [2].
However, in the darkness of a cave, hostile monsters can spawn on top of blocks that are insuficiently lit, either by the sun or a light source such as a torch or lantern. These monsters will attack the player, who therefore wants to light up dark areas as best as they can while exploring. At the same time, building torches requires valuable resources, which is why the (a) Players approaching a village (b) Dimly lit cave with hostile creature player wants to use them sparingly, which leaves us with an interesting constrained optimization problem: Where should we place torches to properly light up an area using as few torches as possible?
The first key observation is that, given the discrete nature of Minecraft, solutions to this problem can be described by binary variables ∈ {0, 1} =.. B, where = 1 indicates that (a) 20 × 15 (b) 20 × 15 (c) 40 × 30 (d) same as above, with torches (e) same as above, with torches (f) same as above, with torches we should place a torch at location . Problems of this kind can be approached with Quantum Computing, which has been a promising focus of research in recent years. Quantum Computers use Qubits to perform computations, which can take values 0 and 1, but also be in a superposition of both at once. In particular, Quantum Annealers are being built that can be used to find the ground state of Ising models by means of quantum tunneling efects [ 3, 4]. This model is equivalent to a class of quadratic binary optimization problems called Qubo: Given an upper triangular weight matrix ∈ R× , we want to find a binary vector * such that * = arg min ()
∈B with () ..= ⊤ =
∑︁
1≤ ≤ ≤
,
(
In this paper, we derive a formulation for the TorchPlacement problem. Due to the large number of constraints, our method involves a learning procedure for Lagrangian weights. This is performed in an iterative fashion on a real quantum computer, similar to [17]. We demonstrate our method in a range of experiments, using both generated and actual game data from a Minecraft world. Further, we discuss the surprising connection to another optimization problem that we uncovered in the process of working on this article.
In Section 2, we give a formal description of the TorchPlacement problem. In Section 3, we develop a Qubo formulation that attempts to solve it, combining quantum-enhanced optimization with an iterative learning scheme. In Section 4, we use our method to solve a range of example instances of TorchPlacement and discuss our observations. Section 5 puts our work in the context of similar work and related problems. Finally, in Section 6 we summarize our ifndings.
As input, we are given a heightmap of a room, consisting of a rectangular grid of tiles, as shown in Fig. 2. The grid has integer width and height ℎ. Additionally, each grid site = (, ) ∈ [ℎ] × [] has an elevation value () ∈ N0 ∪ {∞}, where N0 denotes the set of natural numbers including 0. We use the notation [] ..= {1, . . . , }. Intuitively, () is the “floor level” of . If () = ∞, the tile is considered to be a wall. Let = { ∈ [ℎ] × [] | () < ∞} the set of all grid sites that are not walls.
Intuitively, the height map describes the top-down view of a 3-dimensional room consisting of cubic blocks that can be either empty or non-empty (see Fig. 4). Assuming a discrete coordinate system, each block has a location (, , )⊤ ∈ Z3. If (, ) = , then ∀′ < ≤ ′′ : (, , ′′)⊤ is empty and (, , ′)⊤ is non-empty. Let the predicate E() ≡ ⊤ (true) if and only if the block at is empty. Two blocks at and ′ are considered neighbors if ‖ − ′‖1 = 1, i.e., if they 1 min
| | subject to ( | , torch) ≥ min with ⊆ ∀ ∈ .
In this article, we set torch = 14 and min = 8, which are the same values as in Minecraft. share a face. The set of empty neighbors of is () = { + | ∈ Z3, ‖‖1 = 1, E( + )}. Finally, the distance between two sites = (, ) and = (′, ′), denoted by (, ), is the shortest path from (, , ())⊤ to (′, ′, ())⊤ moving through empty neighboring blocks: (, ) = {︃0
if = , 1 + min′∈ () (′, ) otherwise If there is no path between the two blocks, we set (, ) = ∞. Examples of heightmaps with distances are shown in Fig. 3.
Given a heightmap, our objective is to place torches on some of the tiles in such a way that
all tiles have a minimal light level of min, using as few torches as possible. Light levels are
integers ∈ N0, where 0 indicates complete darkness. If a torch is placed on a tile, the tile itself
receives a light level of torch. The light spreads to surrounding tiles and decreases gradually
with distance described in Eq. (
∈
If = ∅, then we set ∀ : ( | ∅) = 0. Overall, the problem we are trying to solve can be
formalized as
(
as
As hinted at in the introduction to this article, TorchPlacement lends itself to Qubo as its
candidate solution space is the set of binary vectors B. In order to derive a Qubo formulation
for TorchPlacement, we need to (
We firstly arrange the elements of in an arbitrary but fixed order , such that denotes the location of the -th tile for all ∈ [] with ..= ||. A subset ⊆ binary vector ∈ B via ∧= (1{ ∈ })⊤∈[], where 1{·} is the indicator function defined then corresponds to a 1{B} ..= {︃1 if B ≡ ⊤ ,
0 otherwise . min ‖‖1
with ∈ B .
for some Boolean expression B. Equation (
Embedding the constraints from Eq. (
There are two problems with this set of inequalities: Firstly, max is a non-linear operation, and Qubo can only represent quadratic energy functions. Secondly, Qubo is unconstrained by definition, which is why we need to employ techniques to embed the constraints directly into the weight matrix such that the unconstrained solution still obeys our constraints. In the following subsections we describe how we approached both of these challenges.
There are several smooth approximations of the max functions, such as the LogSumExp, -norm or the Boltzmann operator. As an example, consider the first-mentioned function LSE (1, . . . , ) ..=
log ∑︁ .
1
=1
We can re-write our inequality constraints in Eq. (
⇔ ⇔ 1
log ∑︁ (− (,))− ∑︁ − (− (,)) ≥ min − torch ≥ (min− torch) + ∑︁ − ( (− (,)) − 1) ≥ (min− torch) ⊤() + ≤ 0 , constraint Thanks to all being binary, we can re-write as ( − 1) + 1, which yields a linear where () = − −
− (,) and = (min− torch) − . LSE approaches max better the larger we choose . We implemented these constraints and found that approximations of max lead to numerical instability due to the large magnitude diferences between the coeficients, rendered solutions output from the Qubo solvers useless.
However, there is a simpler formulation that exploits the binary nature of our constraints. For that, we define the matrix ∈ {0, 1}× with entries to be = 1{(, ) ≤ torch − min}, ∀, ∈ [] .
In order to ensure that min (, ) ≤ torch − min, we can check whether which immediately yields linear constraints and circumvents the max function entirely.
Using Eq. (
min
1⊤
subject to ≥ 1 ,
(
Proof. In SetCover, we are given a set and a collection of subsets with ⊆
for
⋃︀
each ∈ , and ⋃︀
∈ = . Given a heightmap with tiles and distance function as defined in Eq. (
The question remains how to obtain a Qubo from the constrained formulation in Eqs. (
min ∈{0,1},∈Z
1⊤ + 1⊤Θ()
subject to (, ) = 0 ,
min
and (
Using this formulation, however, comes with the overhead of introducing additional binary variables leading to a total Qubo dimension of ( + 1). As we are still in the era of noisy intermediate-scale quantum (NISQ) computers [19], it is better to resort to a Qubo formulation that uses fewer qubits.
To this end, we use an iterative method called Alternating Direction Method of Multipliers (ADMM) [20]. Firstly, we establish a new problem formulation with >
0, (, ) ..= − 1 − , and Θ being an element-wise step function defined
as Θ() ..= (1{1 < 0}, . . . , 1{ < 0}). The term 1⊤Θ() penalizes vectors ∈ Z with
negative entries, since we want ∈ N0. Note that optimal solution vectors ∈ {0, 1}, ∈ Z
of Eq. (
(
∈Z arg min (, , , ) = arg min 1⊤Θ() + ⊤ (, ) + ∈Z ∈Z = arg min 1⊤Θ() + = max{0, − 1} , where 0 is the -dimensional vector consisting only of zeros and max is taken element-wise.
For solving our original problem in Eqs. (
1, following [20]. In place of a convergence criterium in line 9
We conduct experiments on diferent exemplary heightmaps. Some heightsmaps are randomly generated from 2D Perlin noise [23], others are created from cave sections within a Minecraft world. We compare four diferent Qubo solvers utilizing the D-Wave Ocean2 Python package: Simulated annealing (SA), Tabu search (Tabu), a combination of those two (TabuSA) and a real quantum annealer (QA), namely a D-Wave Advantage System 5.4 with 5614 qubits and 40,050 couplers. The combination of SA and Tabu is achieved by using the D-Wave Hybrid3 Python package, parellelizing both methods, leading to better performance. For all solvers we use the standard parameters. As a pre-processing step we perform parameter compression [24], which leads to improved results for QA. The ADMM is repeated 10 times for every solver and heightmap and we plot the mean performance along with the 95%-confidence intervals. We found the hyperparameters 0 = 0.01 and = 1.1 to yield the best results, hence we fix these values for the upcoming experiments.
In Fig. 5, we compare the performances of the diferent Qubo solvers for one real Minecraft cave from Fig. 4 (right) with = 67. For this, we plot the number of torches as well as the number of violated constraints over the iterations of ADMM. We can see that the four Qubo solvers converge to fulfilling all constraints, while QA places the most torches. This indicates that its solution quality falls behind the other methods, which is a common problem of NISQ devices. However, in Fig. 6 we depict the result of ADMM with QA for a particular run, after 2, 5 and 10 iterations. After 10 iterations, an optimal solution is found, such that every block is lit.
From now on, we use TabuSA, since the dimension of the upcoming problems is too large to obtain useful results with QA. Fig. 7 depicts solutions after a certain number of ADMM iterations on the heightmaps of the other real Minecraft cave from Fig. 4 (left) with = 195. Again, we can see that with more iterations, more torches are placed and the constraints become fulfilled. In Figs. 8 to 11 we depict ADMM solutions for randomly generated heightmaps of varying sizes, using the TabuSA solver. For every map, two intermediate results during the Lagrangian learning phase are shown. We can see that fewer and fewer constraints are violated, until finally all tiles are lit with a small number of torches.
2https://docs.ocean.dwavesys.com/en/stable/ 3https://docs.ocean.dwavesys.com/projects/hybrid/en/stable/
Tabu
TabuSA
Analyzing games in terms of their computational complexity has been part of computer science research for decades [1, 25, 26]. Minecraft, in particular, has been used as a tool for research [2].
As mentioned in Section 3.1, it turns out that TorchPlacement is a special case of SetCover, where the subsets have a spatial interpretation in discrete 3D space. A Qubo formulation of SetCover is given in [27], where auxiliary qubits are used to encode inequality constraints. We chose a diferent strategy by employing ADMM [ 20] to learn the Lagrange multipliers iteratively in a hybrid quantum-classical fashion, which leads to smaller Qubo instances with fewer qubits. A similar approach is followed in [28] using a custom iterative Lagrangian algorithm, which we tried and found not to yield good results with our inequality constraints. ADMM, which we chose instead, is more firmly grounded in theory.
We also find that TorchPlacement and SetCover are similar to other problems such
(b) 2 iterations (23)
(c) 5 iterations (
In this article, we showed that the TorchPlacement problem arising from the video game
Minecraft can be solved on quantum computers. To this end, we used an ADMM-based procedure
to learn Lagrange multipliers in a Qubo formulation, which we then solved on a quantum
(b) 2 iterations (243)
(c) 10 iterations (
While we considered TorchPlacement from a video game perspective, it generalizes to similar setups, where we want to cover a certain area by using as few resources as possible: Sensors or surveillance cameras with a fixed finite set of possible locations come to mind. When we can define a distance between these locations, and we require a maximum distance from each location to the nearest resource, our method is applicable.
To the best of our knowledge, this article is the first instance of quantum computing being applied to solving a problem arising from Minecraft. While this is a more lighthearted context to employ this relatively new computing resource, it has the potential to grant us insights that may be useful for applications to real-word problems, and serve as an illustrative example of how to approach problems from a quantum computing perspective.
This research has been funded by the Federal Ministry of Education and Research of Germany and the state of North Rhine-Westphalia as part of the Lamarr Institute for Machine Learning and Artificial Intelligence. annealing optimization, in: Quantum Technology and Optimization Problems: First International Workshop, QTOP 2019, Munich, Germany, March 18, 2019, Proceedings 1, Springer, 2019, pp. 11–22. [19] J. Preskill, Quantum computing in the nisq era and beyond, Quantum 2 (2018) 79. [20] S. Boyd, N. Parikh, E. Chu, B. Peleato, J. Eckstein, et al., Distributed optimization and statistical learning via the alternating direction method of multipliers, Foundations and Trends® in Machine learning 3 (2011) 1–122. [21] M. J. Powell, A method for nonlinear constraints in minimization problems, Optimization (1969) 283–298. [22] D. Gabay, B. Mercier, A dual algorithm for the solution of nonlinear variational problems via finite element approximation, Computers & mathematics with applications 2 (1976) 17–40. [23] K. Perlin, An image synthesizer, ACM Siggraph Computer Graphics 19 (1985) 287–296. [24] S. Mücke, T. Gerlach, N. Piatkowski, Optimum-preserving QUBO parameter compression, arXiv preprint arXiv:2307.02195 (2023). [25] G. Kendall, A. Parkes, K. Spoerer, A Survey of NP-Complete Puzzles, ICGA Journal 31 (2008) 13–34. doi:10.3233/ICG-2008-31103. [26] L. Gualà, S. Leucci, E. Natale, Bejeweled, Candy Crush and other match-three games are (NP-)hard, in: 2014 IEEE Conference on Computational Intelligence and Games, 2014, pp. 1–8. doi:10.1109/CIG.2014.6932866. [27] A. Lucas, Ising formulations of many NP problems, Frontiers in Physics 2 (2014). doi:10.
3389/fphy.2014.00005. [28] H. N. Djidjev, Quantum annealing with inequality constraints: The set cover problem, 2023.