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.
