11
$\begingroup$

My question is about the computational complexity of the Angel's strategy in the Angels and Devils game, tl;dr does the Angel have a polynomial time strategy.

I'm a big Conway fan, so as you can guess I found myself looking through his works in April. One thing that occurred to me was it might be fun to implement the Angels and Devils game, as I have never actually played it / seen it played, and I figured it's not the kind of game you want to play with a human, since it seems likely that the interesting stuff happens only in very large-scale games.

Let me recall the $k$-angel game for completeness. Two players, Angel and Devil, playing alternately. The set of game positions is $$ X = \{(x, p) \in \{0,1\}^{\mathbb{Z}^2} \times \mathbb{Z^2} \;|\; x_p = 0 \}, $$ and the initial position is $(0^{\mathbb{Z}^2},(0,0))$. A move of the Angel consist in moving $p$ by $k$ chess king moves so that after the move the new pair $(x,p')$ is in $X$ (so the constraint on $p'$ is $|p - p'|_\infty \leq k$). A move of the Devil consists in turning a coordinate of $x$ to $1$, so that after the move the new pair $(x',p)$ is in $X$. The Devil wins if the Angel does not have a valid move after finitely many steps, and otherwise the Angel wins.

This is an open game so one of the players have a winning strategy for each $k$. Indeed, it was proved in 2007 that the $2$-angel wins in Máthé, András, The angel of power 2 wins, Comb. Probab. Comput. 16, No. 3, 363-374 (2007). ZBL1222.91012. and also in Kloster, Oddvar, A solution to the angel problem, Theor. Comput. Sci. 389, No. 1-2, 152-161 (2007). ZBL1210.91023. . (Two more papers from the same year proved this for larger $k$.)

Let's concentrate on the $2$-angel situation, I think it's the most interesting one, especially in light of how the solutions work. (Also, it turns out that there is a way to generalize this to real speeds so that any "$(2-\epsilon)$-angel" loses, so $2$ is the most interesting speed in that sense too.)

Quick descriptions of the $2$-angel solutions. The paper of Máthé is very short and easy: the strategy is "follow the left wall", up to a reduction to another game (where there are some additional requirements for the players). The reduction is also not much different than one already explained by Conway's 1996 advertisement paper for this problem. So obviously my first thought was to implement that. Unfortunately it seems that Máthé's proof does not actually easily give a computable strategy; you get an "explicit" strategy, but you can't actually compute moves from it algorithmically, or at least I don't see how to.

Kloster's paper has a similar strategy, but a longer proof. You walk along the left border of the set of positions you have deemed dangerous (I don't recall the exact terminology they use). Kloster's strategy is explicitly computable, as they themselves note, but you have to quantify over all / an exponential number of paths so it's not so great from a computational complexity perspective.

So let me state my questions now. Observe first that we may clearly base our strategies on only the current state of the board matters, so a strategy for either player is just a function that produces a new state from old, according to the rules. I am interested in computational complexity of strategies, so we have to be a bit more careful with encodings than for just computability considerations. I give two possible formulations that I think are in the correct spirit.

Define the list encoding of $(x,p) \in X$ as the word $w_0 3 w_1 3 w_2 3 ... 3 w_n$ where $w_i \in \{0,1\}^* 2 \{0,1\}^*$, and $w_0$ gives the coordinates of $p$ in binary, while other $w_i$ list the support of $x$.

Is there a polynomial time winning strategy for the Angel in the $2$-angel game? I.e., is there a function in FP that gives a winning strategy for the $2$-angel, when the current position is given with the list encoding?

More generally, "what is the complexity"? (One could obviously also ask things like, if the Devil is playing with a polynomial strategy, can the Angel win with a polynomial strategy, and so one.)

Another possibility is to define the $n$-finitary $2$-angel game as the same game played with $\mathbb{Z}$ replaced by the box $\{-n, -n+1, ..., n\}^2$, and the Angel wins by exiting the box. (There's a relevant compactness phenomenon so this captures the same game as the original in a sense.) Now we can give the complete board state explicitly to each player.

Is there a polynomial time winning strategy for the Angel in the $n$-finitary $2$-angel game?

More generally, "what is the complexity"? In this sense, Kloster's strategy is explicitly in EXPTIME if I'm not mistaken. You quantify over paths that minimize a certain cost function that I won't reproduce here. I don't know if this strategy can already be computed in polynomial time. I would not be surprised if it is possible to encode some NP-hard (or more) problem to it at the very least. (Also I think just from general considerations there is a PSPACE strategy.)

As for implementing the game, since this turned out to be a can of worms I ended up implementing Conway's Soldiers instead, as I hadn't played that either. It turned out to be the easiest game ever. If this question is not answered, I may later try implementing the obvious heuristic strategy based on Kloster's proof, i.e. pick random paths (with some reasonable distribution), optimize locally, take the path that minimizes the cost. If you have more intelligent practical suggestions you can share those too.

$\endgroup$
  • $\begingroup$ In the $n$-finitary case, I assume you're giving the board in unary (i.e., as a 0-1 sequence with a 1 denoting a destroyed square)? Then it seems that your list encoding could be exponentially more succinct than a unary encoding, and that could affect the definition of "polynomial time." Maybe this doesn't matter because things only get interesting when a large fraction of squares in the vicinity of the Angel have been destroyed, but at first glance the succinctness of the list representation seems to make the problem harder. $\endgroup$ – Timothy Chow Jun 3 at 13:47
  • $\begingroup$ You are correct about how I meant the board to be encoded in the $n$-finitary case. You are also correct about the exponential succinctness, and things could absolutely depend on these encoding issues. If someone can give an answer with some other encoding, or explain why some encodings give a silly or non-silly hardness result, that is already something. $\endgroup$ – Ville Salo Jun 3 at 14:12
  • $\begingroup$ The situation is actually a bit more subtle than just one encoding being more succinct than the other. By basic CS nonsense (it's a polylength game), for the $n$-finitary case there is an optimal "PSPACE-Angel", i.e. better than what I got from Kloster's paper. The Angel wins the infinitary game, so this PSPACE strategy wins all $n$-finitary games. Yet the CS doesn't imply there is any computable strategy as far as I can tell. It could be the for the first gazillion $n$ the Angel's winning strategy can start by walking upwards for two steps, but after that it has to start by moving diagonally. $\endgroup$ – Ville Salo Jun 3 at 14:21
  • $\begingroup$ (My guess is for practical purposes, the PSPACE-Angel provided by theory is worse than the EXPTIME algorithm I extracted from Kloster's paper. Maybe it's possible to do Kloster's algorithm in PSPACE by being a bit smarter. Of course we don't even know $\mathrm{PSPACE} \neq \mathrm{EXPTIME}$. And for practical purposes I guess PSPACE isn't much better than EXPTIME.) $\endgroup$ – Ville Salo Jun 3 at 14:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.