20
$\begingroup$

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

Improve this question
$\endgroup$
10
  • 2
    $\begingroup$ 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. $\endgroup$
    – Oscar Cunningham
    Commented Apr 13, 2020 at 19:06
  • 1
    $\begingroup$ 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.) $\endgroup$
    – Oscar Cunningham
    Commented Apr 13, 2020 at 21:09
  • 1
    $\begingroup$ 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...) $\endgroup$
    – Mateusz Kwaśnicki
    Commented Apr 14, 2020 at 16:06
  • 1
    $\begingroup$ @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? $\endgroup$
    – Mateusz Kwaśnicki
    Commented Apr 14, 2020 at 17:22
  • 3
    $\begingroup$ 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. $\endgroup$
    – Will Sawin
    Commented Apr 16, 2020 at 18:19

3 Answers 3

Reset to default
17
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ So this leaves just dimensions 3 and 4 open. $\endgroup$
    – JoshuaZ
    Commented Mar 15, 2021 at 20:44
  • 2
    $\begingroup$ @JoshuaZ Indeed - in the comments, I sketch a possible approach to $d=3$. I suspect $d=4$ is the trickiest. $\endgroup$
    – Will Sawin
    Commented Mar 15, 2021 at 20:50
  • 1
    $\begingroup$ 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. $\endgroup$
    – JoshuaZ
    Commented Mar 15, 2021 at 20:55
  • 1
    $\begingroup$ 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.) $\endgroup$
    – RavenclawPrefect
    Commented Oct 6, 2022 at 0:55
7
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ Excellent. That at least solves @Oscar Cunningham's quesiton above. $\endgroup$
    – JoshuaZ
    Commented Apr 14, 2020 at 11:57
3
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ I pointed this out in a comment, and asked whether in this case the devil can save the angel. :-) $\endgroup$
    – Mateusz Kwaśnicki
    Commented Jan 25, 2022 at 11:06

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .