How can a Devil catch a Fool in the Angel and Devils game?

Question

The Angel and Devils game (http://en.wikipedia.org/wiki/Angel_problem) is a two-player game, played on an infinite chessboard (i.e. the integer coordinates of $\mathbb{R}^2$). One player is the angel, and the other is the devil and they alternate turns. The angel starts at the origin, and on its turn is allowed to move up to $k$ squares, combining horizontal, vertical and/or diagonal moves. That is, it can reach every square at most $k$ chess king moves away. The devil on its turn chooses any square (not currently occupied by the angel) and eats it. After a square is eaten, the angel may never land on it anymore. The devil now wins if after a certain amount of moves the angel is unable to move. The angel wins if it can survive indefinitely. It has been proven that the angel can win this game iff $k \ge 2$.

Now, on to my question. In this paper: http://library.msri.org/books/Book29/files/conway.pdf John Conway proves that the devil can, irrespective of $k$, catch a fool: an angel who is always required to increase his y-coordinate. The thing is, I don't understand the proof. Or, if I do, it's wrong. You can read the proof of this theorem in the pdf-file (it's Theorem 3.1, on page 3 of the pdf-file). Although it's fairly short, for the sake of convenience, I'll copy the first few lines here, which already confuse me:

If the Fool is ever at some point P, he will be at all subsequent times in the "upward cone" from P, whose boundary is defined by the two upward rays of slope $\pm$ 1/1000 through P. Then we counsel the Devil to act as follows: he should truncate this cone by a horizontal line AB at a very large height H above the Fool's starting position, and use his first few moves to eat one out of every M squares along AB, where M is chosen so that this task will be comfortably finished when the Angel reaches a point Q on the halfway line that's distant H/2 below AB.

Now, the thing is, isn't M a function of H? That is, how can you choose M at all so that you can eat all those M squares before the angel is at Q? Because the angel can reach Q in H/2k turns, and M is, if my calculations are correct, equal to 2Hk+1, which is more than H/2k for all $k$. The conclusion of this proof is (assuming for the sake of concreteness $k = 1000$), that if H is chosen to be $1000 * 2^n$ where $n > 1000M$, then the devil will win. But I completely fail to understand how you can choose $H$ larger than some function of $M$, if $M$ itself depends on $H$. Can anyone shed some light?

Answer 1

Yes, M is a function of the height. You choose a height sufficiently high, relative to the fool going up 1,000 each turn, with the ends determined as described in the paper; you then know how many turns M it takes at this maximum vertical progress to come to 1/2 that height, and mark M squares (equi-distant) of the horizontal line determined by the left and right triangular increases. After this first step, of the horizontal line, the devil has blocked $\frac{1}{M}$ of all squares on this line.

You then redraw, from the fool's current position, a new line within the original line of length 1/2 of the original length. You have at least 1/2 the original time to work on a line of 1/2 the original length, until - in a worst case - the fool arrives at 3/4 the height of the horizontal line (worst case being going straight up). This means, you can remove an additional every $\frac{1}{M}$ (equi-distant) of the squares on this shorter line segment: half the time; half the length.

Continuing, at relative distance of $1- {(\frac{1}{2})}^k$, a fraction of $\frac{k}{M}$ of the possible target area of the fool is covered; and so after M steps, the entire possible target area.

It's playing with infinities, so it's a bit confusing: but the argument should hold. I hope I managed to express it somewhat helpfully. This is at least my reading of the proof.