Contents

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

The solution by Oddvar Kloster

This solution demonstrates an explicit strategy that lets an Angel of power 2 win. The full details can be found in my paper.

The strategy

The Angel's winning strategy works as follows1:

  1. The Angel declares part of the board forbidden (in the paper, the term Evaded is used). At the start of the game, one infinite half of the board is forbidden.
  2. At all times, the Angel stays on a square that is just next to the forbidden area. Thus (at least) one of the borders of the Angel's square is part of the perimeter of the forbidden area. We call this border the Angel's perch, and the perimeter is called the path. The Angel movingWhen it's the Angel's turn to move, he advances the perch two units (sides of a square) along the path and lands on the square that is next to the new perch. The perch should be moved in the direction that keeps the forbidden area on the Angel's left.

    The figure shows how the Angel might move for a few turns. The forbidden area is red (the dark red squares are forbidden and eaten), and the perch is shown in yellow. Note that around corners, the Angel doesn't always move as far as his power allows.
  3. Every time the Devil has eaten a square, the Angel considers making additional squares forbidden, thus also altering the path. Whenever there is an opportunity to do this while satisfying the following conditions, he must take it:
    • The forbidden area remains connected.
    • The path behind the angel (up to and including the perch) is unchanged.
    • The length of the path increases by no more than two units for each eaten square that is now made forbidden.

The effect of these rules is that whenever the Devil has placed a sufficient number of eaten squares sufficiently close to the Angel's path to constitute a threat, the angel will declare the area forbidden and walk around instead. Below are a few examples of updates to the forbidden area and the path (with eaten squares shown dark gray):

Before update 1     ⇒     After update 1
Before update 2     ⇒     After update 2

In some special cases, the path is allowed to become slightly degenerate. If the Angel is standing at an inner corner and the Devil eats the Angel's current square, the path will aquire a 180 degree turn, and the Angel will temporarily be standing in the forbidden area. In the rightmost figure below, the path is highlighted in green:

Before update 3
  update  
⇒
After update 3
  move  
⇒
After move

The following example also shows an update that leads to a degenerate path, though this situation can never occur in practice:

Before update 4     ⇒     After update 4

Why does it work?

To prove that the strategy wins, we must verify that it can never cause the Angel to land on an eaten square.

Firstly, it is straightforward to see that this is true for eaten squares outside the forbidden area. The Angel always stays next to the path, and any eaten square that is next to the path must immediately be made forbidden. This can lengthen the path by at most two units.

Before update 5     ⇒     After update 5

Secondly, we must show that the Angel can never step on an eaten square inside the forbidden area. In fact, the Angel will never enter the forbidden area at all.

In order to get the Angel to step on a forbidden square, the Devil must make some part of the path have forbidden squares on both sides. That is, the path must be degenerate and the Angel stranded on an island inside the forbidden area. We can imagine such an island being created inside a barrier of forbidden squares that grows clockwise around the Angel until it meets another part of the forbidden area behind the Angel. But this cannot be done. In order to create an island with a given perimeter length, the Devil must eat a certain number of squares in a nearby region (due to the last condition of rule 3). Considering the limited speed with which the Devil can eat squares, we can go back in time to when the Angel is about to enter this region, and find that already now, there are so many eaten squares in the region that the Angel must make it forbidden and will instead walk around the whole trap-to-be.

A potential barrier

 Failed trap

The figure above illustrates how this barrier-building fails. Suppose that the Devil wants to create a barrier by eating the squares marked in blue. It is clear that he can't start before the Angel has advanced from the position shown, as otherwise, the Angel is forced to make the area forbidden and walk around. But during the 9 turns that the Devil requires to eat these squares, the Angel has advanced 18 units along the path, which means that he escapes the trap before it is finished. The actual move sequence may look as in the figure on the right, where both the Angel's and the Devil's moves are numbered, with the Angel going first.

You can try the demo of the strategy to verify that the above sequence is correct and cannot be improved upon. Of course, this is just one example, but any attempt to trap the Angel is doomed to fail in a similar way.

1 The strategy is formulated slightly differently in the paper. There are a few additional technicalities, but the description given here is essentially equivalent.

Top