In the classic version of Conway's Angel and the Devil problem, an angel starts off at the origin of a 2-D lattice and is able to move up to distance $r$ to another lattice point. The devil is able to eat a lattice point, preventing the angel from ever moving to that point. The angel and devil take turns, and the devil wins if the angel is at some point no longer able to move. The question then is for what values of $r$ does the angel win and for what values does the devil win? This problem was essentially solved completely by distinct proofs by Kloster and Máthé that the 2-angel can escape. (It is easy to see that a 1-angel can be trapped.) One can generalize this problem to higher dimensions; note that if for a given choice of $r$ the angel can escape in $d$ dimensions, then the angel will escape for any higher $d$.

What I'm interested in is the situation where the angel moves randomly (uniformly distributed among all possible legal moves) but the devil has a pre-determined strategy (allowed to depend on $r$ and $d$ but not allowed to depend on any choices the angel has made). For what $r$ and $d$ can the devil beat an angel with probability 1?

It isn't too hard to see that if $d=2$ the devil can win with probability 1. Here's the basic strategy the devil uses: Pick a very fast growing sequence of positive integers, $a_1$, $a_2$, $a_3 \cdots$. The devil works in stages: At each stage, the devil eats a square of side length $a_n$ centered about the origin, and with thick walls of thickness $r$. Each such square requires about $4ra_n+r^2 \sim 4ra_n$ moves by the devil. But by the standard result that a random walk is with probability 1 never much more than the square root of the number of steps away from the origin, in the time the devil has taken to eat the $a_n$ square, the angel with probability 1 will have only moved about $\sqrt{4r}\sqrt{a_n}$ steps from the origin. So, the devil just creates larger and larger squares of this sort, and eventually the angel will be trapped. (This by itself will put the angel in a finite region, but trapping in a finite region is essentially the same as being unable to move since the devil can go back and fill in these squares ever so slowly, say eating a single lattice point near the origin before moving on to start making each new large square.

This construction fails for 3 dimensions. To make a cube of that size takes about $6a_n^2$ steps, so the angel has a high probability of being near the boundary.

Question 1: can this strategy or a similar one be modified to work for $d=3$? My guess is yes for $d=3$, but I don't have a proof. I also don't have any intuition for higher dimension.

One standard observation which simplifies the analysis of the original problem is that one may without loss of generality assume that the angel never returns to the same lattice point. If it did, it would have used a suboptimal strategy, since it is back where it was earlier but with the devil having eating out a few lattice point. So, we can define another variant of the problem with an angel which chooses randomly, but only out of lattice points it has not yet reached.

Question 2: Given this non-repeating angel, is there a strategy for the devil to win with probability 1?

I suspect that the answer for $d=2$ is that the same basic strategy should still work; my suspicion here is that with probability 1, the angel's distance at $k$ steps should be bounded by $k^{(\frac{1}{2}+\epsilon)}$ in which case the same proof would go through. But I'm much less certain about what happens here if $d=3$.

weird.) $\endgroup$ – Oscar Cunningham Apr 13 '20 at 21:09weird, too...) $\endgroup$ – Mateusz Kwaśnicki Apr 14 '20 at 16:06alwayslose on their own! Oh wait, the devil can block moves that would lead the angel to a dead end. Plot twist: can the devil save the (non-repeating) angel with probability one? $\endgroup$ – Mateusz Kwaśnicki Apr 14 '20 at 17:225more comments