Contents

The problem        
Solutions
    Kloster
    Bowditch
    Máthé
    Gács
Variations
Demo

The solution by Brian Bowditch

This solution shows that an Angel of power 4 can win. The proof works by considering two transformations of the game. A winning strategy for the Angel is found for the second of these, and the strategy can be transformed back into winning Angel strategy for the original game. The full details can be found in Bowditch's paper.

Game 1

The first transformation consists of dividing the board into tiles, each containing 5 squares. We consider all squares in a tile equivalent. Game 1 is played on a board where tiles are the atomic units. Here, the Angel can move one tile horizontally or vertically, but not diagonally, in each turn. The Devil can only eat 1/5 of a tile in each turn, that is, he needs to eat the same tile in 5 different turns to make it inaccessible to the Angel.

Tiles ⇔ Game 1
Original game Game 1

If there is a winning strategy for the Angel in Game 1, it can be turned into a winning strategy for the Angel in the original game. When the Angel in Game 1 moves to a neighbouring tile, at least one of the corresponding squares in the original game must be uneaten, and the Angel of power 4 can reach this square in one turn from any square in the tile he's leaving.

Henceforth, in the context of Games 1 and 2, we will refer to the tiles as squares.

Game 2

Game 2 is a modification of Game 1, in which the Angel is always allowed to return to a square that he has visited earlier. Once the Angel has moved to a square, that square is safe. At the time that the Angel first moves there, the Devil must have eaten the square less than 5 times. The Devil may subsequently eat the safe square additional times and make it inaccessible under the rules of Game 1, but this has no effect in Game 2.

To win Game 2, the Angel employs a strategy that basically consists of heading in one direction as fast as possible. If he bumps into any eaten squares, he traces around their outline anticlockwise until he can continue in the chosen direction. In the figure below, eaten squares are dark gray, and safe squares, i.e. those visited by the Angel so far, are green.

Strategy for Game 2

It is perhaps unsurprising that in Game 2, the Angel can escape to infinity. Due to the rule about safe squares, the Devil must build a barrier that encompasses the Angel's current position, his starting position and all of the squares that he has visited so far, in order to contain him. As the Angel moves 5 squares in the time that the Devil needs to make one square inaccessible, this seems impossible.

Moreover, the following are shown in Bowditch's paper to be true of this strategy:

  • The Angel traces a semi-infinite path that is circuitous. Such a path is composed of a spine, which is a simple path in which no square is visited twice, and zero or more loops. Each loop starts at some square of the spine and ends at the same square. Except where the loops are attached to the spine, no loop has any square in common with either the spine or another loop.
  • There is a bound on the length of the loops: A loop that is attached to the i'th square along the spine cannot have length more than i.

The figure below shows an example, where the spine is blue and two loops are shown in red.

A circuitous path

Back to Game 1

Now that the Angel knows how to win Game 2, he can also win Game 1. He will pretend that he is playing Game 2, but in actuality, he will stick to the spine and not perform any loops that may arise from the Game 2 strategy.

When he is about to move, the Angel considers whether using the Game 2 strategy can make him perform a loop and return to the current square. Since there is a finite bound on the length of any loop starting from the current square, this will be decided in a finite number of moves, and within a finite region around the Angel's current square. Any play by the Devil outside this region does not affect whether or not a loop will arise from the current square nor how it will look. Thus the Angel only has to consider a finite number of possible game continuations under Game 2 rules.
If any of these futures contains a loop that leads the Angel back to the current square, he picks one that has maximal length and pretends to perform that loop. He also pretends that the Devil plays accordingly while he is traversing the loop, and the squares that the Devil eats during this phase will be considered actually eaten for the rest of the game. Once the Angel is back to the same square, he makes one actual move, to the next square that the rules of Game 2 would direct him to after the loop.

In his mind, the Angel is playing Game 2, but the moves he actually makes are legal according to the rules of Game 1 and follow the spine of the Game 2 path. He never returns to a square that he has visited before, for this would imply that he did not choose the loop of maximal length at some point. No square he moves to is safe in Game 2, and all his moves are therefore also legal in Game 1.

As noted above, a winning strategy for Game 1 yields a winning strategy for the original game.

Top