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?

  • 4
    I am not sure if it matters, but will the angel or the demon always start the game or is the question independent of who will start? – jarnbjo Jun 13 at 17:42
  • 1
    I suppose the angel can't capture the demon? – noedne Jun 13 at 18:26
  • 1
    The logical thing to do in such a situation is for the two of you to play the game, you as the demon, and your friend as the angel. While it won't settle the matter definitively, it would be strong evidence, and useful in trying to think of a proof. – Acccumulation Jun 14 at 0:50
  • 2
    Sounds like the Angel is locked in a grid pattern by its two-move requirement and will only be able to land on 1/4 of the squares. Similar to how a bishop can only ever land on the same colour squares. Is that correct? – matt_rule Jun 14 at 8:44
  • relevant! link – SilverCookies Jun 18 at 12:21
up vote 16 down vote accepted

angel on f3, demon on g1 angel traveling between a3, c1, c5, and e3

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.

angels on a8, b1, g2, and g8; demons on b7, c2, f3, and f7

  • 1
    I think it's worth mentioning that the OP attempted to perform an inductive proof. The problem is that he really only showed it for an <X * X> board such that X <= 4. Secondly, I think once the board is long enough you could perform a similar inductive proof of board sizes over "B" even if White is limited by Rook-style movement. If you can show it is true for one quarter of the board, simply turning the board by 90, 180, or 270 can prove the other 3 quarters. – blurry Jun 14 at 14:24

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.

  • 1
    @jarnbjo Why can't the angel move to c1 or c5? – GentlePurpleRain Jun 13 at 17:49
  • @GentlePurpleRain You are of course right. – jarnbjo Jun 13 at 19:03

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.

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.