## The Angel Problem_{Oddvar Kloster} |
|||||||

## ContentsThe problem |
## The solution by Brian BowditchThis 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 1The 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.
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 ## Game 2Game 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 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. 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. ## Back to Game 1Now 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. 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. |