Angels & Demons (Open question)

Question

This puzzle was given to me by a friend of mine, who in turn heard it from someone else who neglected to provide the answer. The text of the puzzle as it was given to my friend is below:

Angels and Demons is a game I’ve made up. It’s played on an enormous chessboard, 100 squares by 100 squares. There are two pieces, the angel and the demon. The angel starts in the bottom right hand corner of the board, while the demon starts in the top left hand corner. The demon moves exactly like the king in chess. The angel moves the same way, except he must go two squares in any direction. He can’t change direction mid-move.

Capturing works in the same way as chess. The demon wins if he can capture the angel. The angel wins if he can devise a strategy to avoid the demon forever. If both players are playing perfectly, who will win the game?

Now my thinking is that the Demon will always win, regardless of the size of the chessboard. The way I look at it, if the board was 3x3 then the solution would be trivial. Similarly, if the board was 4x4, the Angel's two move advantage wouldn't help him. As soon as the Demon manages to get the Angel to the edge of the board, his two move advantage is effectively nullified, and from there it's only a matter of time until the Demon wins.

My friend, on the other hand, believes that the Angel will always be able to avoid the Demon. Unfortunately, neither of us can prove our answers mathematically. Is there a way to prove which piece would win?

Answer 1

Suppose the angel has an available diagonal move, as in the diagram above left, where the angel (queen) on f1 has the diagaonl move h1. If the demon attacks this square, say as depicted, where the the demon (king) on g1 attacks h1, then the angel will have h3 available as a safe move.

The demon can only win if it manages to eliminate the angel's diagonal moves. Ignoring the demon, the angel will always have at least one diagonal move, with equality when it is within one king move of a corner, as in the diagram below. The demon can block the angel's one diagonal move, as depicted, after which the angel has no safe move.

As long as the angel avoids these corners, it will avoid capture. Glorfindel demonstrates that this is possible on any rectangular board with each dimension at least $5$ by traveling in a diamond pattern with diagonal moves, as shown above right.

Answer 2

The Angel wins, already on a 5x5 board, as long as she avoids the corners (the edge itself is fine). We're using algebraic notation; imagine the Demon on the center square c3, then the Angel must make sure she's on a3, c1, e3 or c5. Without loss of generality, assume it's a3. The Demon can get one step closer to the Angel by moving to b2, b3 or b4, but the Angel moves away to either c1 or c5, whichever is further away from the Demon.

I just came back home and was about to draw a diagram illustrating this, but I can't do any better than @noedne already did.

Answer 3

Here is a proposed formal solution (after I was finally able to read the other answers, turned out it is almost the same as the one suggested in a post by Glorfindel above). I claim that Angel wins. To make things a little easier (just from terminology POV) I assume that the board size is odd -- 101-by-101, for instance (this does not really change much, as you will see).

A's algorithm is this:

Stage 1: first go to the center of the bottom side - square with "coordinates" (51,1) (originally A stands on (101,1) and D on (1, 101)). This will take 25 moves, and by the end of that stage D will be at least 70 (which is more than 20) squares away from the square occupied by A.

Stage 2: go 2 squares right, then with the next move -- 2 squares left, or vice versa, "waiting" for D to get closer than 20 squares. If D never does, then A continues doing that indefinitely.

Stage 3: when D is closer to A than 20 squares, A goes back to center of the side (if necessary) and then starts "running" diagonally either to (101,51) or to (1,51) depending on the half (left or right) of the board that D is in at that moment (choosing the half which does not have D in it; if D is exactly on the vertical centerline then A can choose any side). Obviously, D will not be able to intercept A. Moreover, distance between A and D will never be less than 20/4-1 = 4 squares.

Thus A will reach the center of the right (or left) side of the board in 25 or 26 moves. At this point D cannot be closer than 51 - 26 = 25 squares to this new position of A.

Repeat Stage 2, only with respect to that side of the board A is on. Basically, mentally turn the entire picture by 90 degrees and continue with the process.

This algorithm guarantees D will never be closer to A than 4 squares.