19

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$.

JoshuaZ
  • 6,090
  • 2
    Why did you restrict the devil's strategy to not know the angel's position? I can't see a winning strategy for the devil even if it knows where the angel is. – Oscar Cunningham Apr 13 '20 at 19:06
  • @OscarCunningham , That's a valid question. Presumably if the devil is allowed in this context to react, then it will have an easier time. I'd strongly suspect that if the devil is allowed to know the angel's position than for any r and d, the devil will win with probability 1. But I also don't have a proof for that situation either. – JoshuaZ Apr 13 '20 at 20:30
  • 1
    I think you're right. The tesseravore could use the strategy of always eating one of the squares in the angel's movement range diametrically opposed to the origin. My intuition is that this would be enough bias to cause the angel's random walk to always return to the origin. (My intuition isn't strong here though, high dimensional spaces are weird.) – Oscar Cunningham Apr 13 '20 at 21:09
  • 1
    What if the non-repeating angel reaches a dead-end: a point from where there is no move to a non-visited site? (Self-avoiding walks are weird, too...) – Mateusz Kwaśnicki Apr 14 '20 at 16:06
  • @MateuszKwaśnicki I would consider that functionally a loss for the angel in the non-repeating case. But maybe that's not the best response because that means that the non-repeating case isn't strictly better for the angel. Good point though that I hadn't thought about! – JoshuaZ Apr 14 '20 at 17:06
  • 1
    @JoshuaZ: This way the angel would always lose 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? – Mateusz Kwaśnicki Apr 14 '20 at 17:22
  • 3
    I think it should be possible to check that the devil can win in dimension $3$ by building a box, then building a much bigger box, then a much much bigger box... Since the angel's radius is typically on the order of the square root of the time, they have a positive probability of being trapped by each box, which adds up to probability $1$ over time. But I don't see any quick way to do the random-walk-outside-a-box central limit theorem that would prove this. If this is done, only $d=4$ is left. – Will Sawin Apr 16 '20 at 18:19
  • What if the devil just moves randomly? Wikipedia (the page "Random walk") just informed me that "Paul Erdős and Samuel James Taylor also showed in 1960 that for dimensions less or equal than 4, two independent random walks starting from any two given points have infinitely many intersections almost surely, but for dimensions higher than 5, they almost surely intersect only finitely often." Unless I'm missing something, doesn't this mean that the devil can win in dimensions 3 and 4 by moving randomly? – Will Brian Mar 16 '21 at 13:11
  • 1
    @WillBrian That would work if one was using the variant of the game in Will Sawin's answer below where the angel concedes if they randomly choose a square that the devil has already eaten (which incidentally given his comment gives a full characterization of that variant), but in this version the angel picks randomly from the non-eaten squares, so it isn't clear what happens. But the fact that a random method apparently does do so well in a very similar game seems like good evidence that the devil will win on d=3 or d=4. – JoshuaZ Mar 16 '21 at 13:59
  • @JoshuaZ: Oops -- I was indeed thinking of the other version of your problem, described by the other Will. You're right that it's not clear what a random devil can do in that version. Although my guess is that the devil never succeeds in trapping the angel in a finite region, and the angel escapes with positive probability. – Will Brian Mar 16 '21 at 14:21

3 Answers3

16

In dimension $5$ and above, a random angel escapes a blind devil with positive probability, as long as $r$ is sufficiently large.

To see this, let's replace the angel with one that chooses a point to move with from all points within a distance $r$, and if it chooses a point the devil has eaten, it instantly concedes the game. The winning probability of this angel is clearly less than the winning probability of the original angel, since the original angel is just this angel with an extra probability of surviving at certain times and possibly living forever.

Since this angel is just following an ordinary random walk, after $n$ moves it has an $O ( n^{-d/2})$ probability of being on any particular lattice point, by the central limit theorem. Thus it has an $O( n \cdot n^{-d/2})$ probability of touching a lattice point the devil has eaten. Summing over $n$, we get $O(1)$ as long as $d>4$. Because the constant goes to $0$ with $r$, the probability of never touching such a lattice point is positive with $r$ sufficiently large.

Will Sawin
  • 135,926
  • So this leaves just dimensions 3 and 4 open. – JoshuaZ Mar 15 '21 at 20:44
  • 2
    @JoshuaZ Indeed - in the comments, I sketch a possible approach to $d=3$. I suspect $d=4$ is the trickiest. – Will Sawin Mar 15 '21 at 20:50
  • 1
    I've added a bounty. I'll award it to anyone who either solves d=4 or anyone who can get the details of your d=3 to work. – JoshuaZ Mar 15 '21 at 20:55
  • 1
    Even $r=1$ should work for positive probability of escape: let the maximum pointwise probability of the (weakened) angel's location at a specific coordinate (given the devil's moves so far, which only decrease it) be $p_n<1$. Then the statement that $\sum_{i=1}^\infty p_i<\infty$, shown in this answer, is equivalent to $\prod_{i=1}^\infty (1-p_i)>0$, i.e. the devil has nonzero odds of all their moves failing. (Since we're conditioning on each failure, the probabilities at each step are independent.) – RavenclawPrefect Oct 06 '22 at 00:55
7

This long comment is to show that if the devil can see him, he can trap him. E.g. in 2-d, it takes (5r)^2 - (4r)^2 steps to build a box he can't get out of at a distance of 4 moves from his current local, that would be covering up all the moves between distance 4r and 5r into which he must step to escape. Wait unitl he has take 5r steps in the same direction into fresh space. The devil can force him to the border of empty space, and then as the 5 moves into it are legal moves, he makes them with some probablity. The point of waiting for him to move into fresh space is to make sure that these attempts to escape are all the same. His time to hit the inner edge of the devils box is not bounded, so with some probability he hasn't hit the inner edge before you are done. If he does, give up and start a new one. You get infinitely many tries.

mike
  • 1,174
3

Doesn't the non-repeating angel trap itself with probability 1 even without the devil's help? I mean there is always going to be some finite set of moves the angel can make that leave it nowhere to go. Since it has infinitely many tries, it should make this sequence of moves eventually.

Daniel Kane
  • 31