Contents

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

The solution by Peter Gács

This solution shows that an Angel of an unstated, but apparently rather high, power can win. Unfortunately, I have not found the time and energy to examine it thoroughly, as the argument contains quite a lot of details. So this is my impression of it, and may not be entirely correct. You are invited to read the paper yourself.

The problem with hierarchies

In contrast to the three other solutions, this strategy is defined recursively in a hierarchy of boxes. In this, it is similar to successful strategies for the 3D case. The Angel's plan is, on every level in the hierarchy, to eventually escape his current box. To do this, he plots a path through the smaller boxes on the next lower level. If he manages to make sure that each box he uses will contain sufficiently few eaten squares by the time he gets to it, the strategy lets him move forever.

However, in 2D, there is a fundamental problem with hierarchical strategies, as pointed out by Kutz. When preparing to leave a box on some level of the hierarchy, the Angel must at some point decide which smaller box along the border, on the next finer level, he will leave through. And before leaving this smaller box, he must choose a tiny box on the next level, and so on. If the time from the Angel definitely decides on a box to leave through, to when he has actually left it, can be bounded below by a constant factor times the box' side length, then he can be caught in the same way as the Fool. So in order to be successful, a hierarchical scheme in 2D needs a mechanism that allows some path decisions to be made 'arbitrarily late'.

How to get around it

In the strategy proposed by Gács, this mechanism is provided by the concept of an attack. Most of the time, the Angel moves from one box to another without the need for attacks. Finding himself in a box (a box on some level is called a colony, and the boxes it contains on the next lower level are called cells) that is good (i.e. contains relatively few eaten squares), the Angel wants to move to the adjacent colony to the north that is also good. More specifically, the Angel starts in a good row of cells in the starting colony and wants to get to another good row in the destination colony. This is done by moving along the start row to a good column of cells and then along this column to the destination row in the destination colony. Of course, each step from cell to cell along this path is again implemented in a similar manner on the next lower hierarchy level.

However, sometimes there is no column that is good enough to guarantee that the Angel will get through it: every column has a cell that is 'bad', i.e. contains relatively many eaten squares. If these bad cells occur at fairly different heights, the Angel may be able to pass by switching column on the way, squeezing between two of the bad cells, but if they are at similar heights, this is not possible. This is where attacks come into play. Instead of choosing a single column to advance in, the Angel starts from the left and attempts to get through the bad cell in each column in turn. If he fails in one column, he simply retries in the next, and sooner or later, he succeeds. During this procedure, the Angel's path is not fixed in advance for any appreciable distance. Thus he avoids being trapped in the manner of a Fool.

It is interesting to note that during the attack procedure, the Angel's behaviour contains an element of 'trace along the border of the obstacle until you get around it'. This element is also present in the three other solutions and seems to be an essential ingredient for a successful strategy in 2D.

Top