The Angel Problem
_{Oddvar Kloster}


ContentsThe problem 
The solution by András MáthéThis solution shows that an Angel of power 2 can win. The trick is to introduce the Nice Devil, who is an easier opponent and relatively easy to beat. However, if the Nice Devil can be beaten, then so can the real Devil. The full details can be found in Máthé's paper. The Nice DevilThe Nice Devil is a Devil who is handicapped, in that he may never eat a square that the Angel has already visited, or that the Angel might have moved to in a previous turn. It is obviously not possible for the Nice Devil to trap the Angel in the sense that the Angel has no uneaten square to jump to: the Angel may always return to his previous square. However, if the Nice Devil is able to build a wall that confines the Angel in a finite area, we will count this as a win. If the real Devil manages to so confine the Angel, he can subsequently eat away the area's interior to immobilise the Angel. The important fact about the Nice Devil is this: (*) If the Devil can confine the Angel within a finite area, then so can the Nice Devil. From this follows:
The Nice Devil's strategyTo prove (*), we assume that the Devil has a strategy that confines the Angel. That is, there is some finite area, A, such that if the Devil plays properly, the Angel cannot leave A without having stepped on at least one eaten square. Given a fixed winning strategy for the real Devil, we derive a winning strategy for the Nice Devil (which also confines the Angel within the same area A). Consider the state of play as the Devil is about to eat a square. Define the path to be the ordered sequence of squares that the Angel has visited so far. The path completely describes the game up to now, and the Devil's strategy can be expressed as a function whose input is the path and whose output is the next square that the Devil eats. The Angel's path need not be an efficient one. That is, it may contain a strict subsequence that the Angel could have taken instead, to reach the same square more quickly. The figure below shows an example of this for an Angel of power 2. The yellow path is the Angel's actual path. The red and blue paths are two different efficient paths derived from the yellow path. The blue path has an additional property: Whenever the Angel arrives at a square v from the previous square u along the blue path, then u is the earliest square (in the original, yellow path) from which v can be reached. This property uniquely determines an efficient path, which we call the reduced path. We can now define the Nice Devil's strategy. In any situation, the Nice Devil play as the Devil would have done if the Angel were efficient. That is, the Nice Devil considers the Angel's actual path so far and derives the corresponding reduced path. He then eats the square that the real Devil would have eaten for the reduced path. Of course, if the Angel has already been on or close to this square, the Nice Devil is not allowed to eat it. In this case, he can instead just pass or eat some other arbitrary square that he is allowed to eat. Now, for any path P that the Angel can play against the Nice Devil, there is a corresponding reduced path P'. If the Angel plays P' against the real Devil and escapes from A, he must at some point have stepped on an eaten square. This square is also part of P, and it turns out that it will also be eaten before the Angel steps on it if he plays P against the Nice Devil. Thus the strategy lets the Nice Devil win. In more detail, let s be the eaten square that the Angel steps on, and let Q' be the Angel's path up to the point at which the Devil eats s. Q', is an initial segment of P'. Q' is also the reduced path of Q, an initial segment of P. This means that when the Nice Devil is faced with an Angel that has followed Q, he will also eat s, unless the Angel has already been able to reach s in an earlier move. But this would contradict the fact that P' is the reduced path of P. If s can be reached from any square r in Q, then r must be the last square in Q, and r and s must be adjacent along P'. A strategy against the Nice DevilWith (*) established, it only remains to be shown that the Angel can beat the Nice Devil. If the Angel's power is large enough, this is easy. The Angel can simply head in some chosen direction at full speed. If the bumps into any eaten squares, he traces around their outline anticlockwise until he can continue in the chosen direction. The Nice Devil can only contain the Angel by building a wall that surrounds all parts of the board that the Angel has visited. But because, for large powers, the Angel moves so much faster than the Nice Devil can build walls, this cannot be done. A similar strategy works even for the Angel of power 2, but some careful bookkeeping is required to make the argument watertight. 