Numb3rs 523: Angels and Devils

In this episode there is unfortunately little mathematics. However, the "Angel and Devil" problem is mentioned (and is also the basis for the name of this episode). The Angel and Devil problem seems to originally been posed in a book by Berlekemp, Conway, and Guy in 1982, but only recently (2006 and later) has a solution appeared. We'll discuss the problem and some solutions and partial solutions to it.

The Problem

There are actually infinitely many versions of this game, one for each integer k. The game has 2 players, an Angel and a Devil, and is played on an infinite chess board. The Angel starts on one particular square and in one move is able to move to any square that a chess king could move to in k moves. Angels have wings, of course, so the Angel can "hop" from a square to the next one, and it doesn't matter if there are removed squares between the initial and final positions. The Devil, on its turn, is able to remove any square it wants to from the board, which means that on future turns, the Angel is not able to move to that square. The Angel wins the game if it has a strategy that will enable it to continue moving forever, and the Devil wins if it has a strategy that lets it "trap" the Angel, so that the Angel eventually doesn't have any legal moves. There is also a generalization of this game where the board that is used is 3-dimensional. To avoid convoluted grammatical constructions, we'll always use the female gender for the Angel (or other names for the player with the same role) and the male gender for the Devil (this was chosen by a flip of a coin).

This type of problem is dealt with in a field of mathematics called combinatorial game theory, which deals with the applications of the field of combinatorics to various types of games. Another problem that you might have heard of that is of the type that is dealt with in this field is the prisoner's dilemma.

One might think that since the board is infinite, it would be impossible for the Devil to trap the Angel even if the Angel can only move one square at a time. However, this intuition is incorrect, because in 1982 Conway showed that if k is 1 (i.e. the Angel can only move one square at a time), then the Devil has a winning strategy. Here is a list of some other partial results that were the best results known until recently (in the first 4, the value of k is arbitrary):

1. If the Angel always increases its y-coordinate, then the Devil can win.
2. If the Angel always increases its distance from the origin, then the Devil can win.
3. The Devil can force the Angel to follow a path that moves arbitrarily far in some particular direction.
4. The Devil can force the Angel to wind around a particular point an arbitrarily large number of times.
5. In the 3-dimensional version of the game, the Angel can win if k is sufficiently large.
The first four statements show that the Devil is surprisingly powerful, which might make one think that the Devil can win. A partial explanation for why the Devil is powerful is that he can never make a mistake, in the sense that at any point in the game, if the Devil "restarts" its strategy and pretends that the game is just beginning, it will be in a better position, because some of the squares have already been removed. We'll talk about a couple of these results, and then give the ideas behind a one of the proofs that the Angel can win if its power is 2 or more.

The Fool

In a 1996 paper, Conway proved some of the results listed above. The first one is about the Fool, which is an Angel who restricts herself to increasing her y-coordinate. It turns out that the Devil can beat a Fool of any power, and we'll summarize his argument here, assuming that the Fool has power k.

First, since the Fool is restricted to increasing her y-coordinate, the set of all possible positions the Fool can ever reach are contained in a cone whose point is at the Fool's initial position and whose sides have slope 1/k. The Devil's strategy will be to draw a horizontal wall at height H (which will be determined later) above the Fool's initial position and to remove squares along this wall in such a way that the Fool will eventually run into a solid, unpassable block of the wall. (This means that the Devil must eventually force the Fool to be right below a block of removed squares that is k blocks tall and wide.) Initially, the Devil will remove every Mth square along this top line (where we'll choose the constant M later).

The next observation is that when the Fool has travelled halfway up the cone (i.e. her height is H/2), then her possible positions are reduced to a smaller cone whose point is at her current position and whose sides have slope 1/k. Using basic geometry, we see that the base of this cone has half the length as the base of the original cone (in our view, the base is at the top). At this point, the Devil can restrict himself to this shorter segment of the wall that he is trying to build. We'll choose M in such a way that the Devil will finish removing every Mth square of the wall before the Fool can travel half the vertical distance up the original cone. The wall the Devil is trying to construct has width 2*H*k and height k, so the total number of blocks he has to remove is at most 2*H*k*k. It will take the Fool at least H/2k turns to reach the halfway point, so we must have 2*H*k*k/M less than H/2k, so we'll take M to be at least 4*k*k*k. Notice that M is indepedent of H, and that after the Fool reaches the halfway height, at least 1/M of the squares in the wall the Devil is trying to build that the Fool is still able to reach have already been removed. Now we can repeat this argument, so by the time the Fool reaches 3/4 of the height of the original cone, the Devil will have removed at least 2/M of the blocks that the Fool can still reach in the wall that he is trying to build. Now we just have to choose H to be large enough so that 2^H is greater than M.

The Not Quite So Foolish Fool
Can you modify this argument to show that the Devil can always win against an Angel who never decreases her y-coordinate? (Hint: How long will it take the Devil to build walls on the horizontal line that Angel starts on in such a way that the Angel must eventually increase her y-coordinate?)

The statement that the Devil can win against an Angel who always increases her distance from the origin was also proved by Conway in the same paper. We won't go through the proof here, but the basic idea is as follows. The Devil splits up the plane into N cones, all with the same angle and basepoint the origin. Then if the Angel is at any particular spot in one of these cones, the Devil pretends that the Angel is at that same spot in every one of the cones. He positions one Demon in each cone, and splits his moves evenly between all the Demons. Then a Demon thinks that he is trying to trap an Angel with power N*k who is always staying inside his cone, and he plays as the Devil does in the scenario above.

The Angel of Power 2 Wins

There are 4 recent proofs that an Angel of sufficiently high power can win, and one of them gives an explicit strategy for an Angel of power 2 to win. This paper is here, and we'll give a brief summary of the strategy. The actual argument is pretty detailed, but we'll skip the details.

If you're in a maze, one way to guarantee that you get out is to put your left hand on a wall and keep walking. If the maze has an exit, you will eventually find it. The strategy for the Angel is somewhat similar. She divides the board into Forbidden squares, Free squares, and Removed squares. At the beginning, she declares that the left half of the board is Forbidden and the right half is Free, and starts moving up the boundary between the Forbidden and Free halves. The boundary between the Free and Forbidden areas is the Angels path, which has a forwards and backwards direction. As the game progresses, the Angel will add squares to the Forbidden zone based on the actions of the Devil, and each of her moves will be along the boundary between the Free and Forbidden squares (so she's keeping her left hand on the wall and going forwards). After each move, she will change as many squares from Free to Forbidden as possible, subject to the following constraints:

1. The Forbidden area stays connected (i.e. there's just one "piece" of the Forbidden area, or any two points in the Forbidden area can be connected by a path that stays entirely in the Forbidden area).
2. The path behind the Angel is unchanged.
3. The length of the path increases by no more than 2 for each eaten square that is added to the Forbidden zone.
The idea is that the Angel just tries to go up, but if the Devil puts an obstruction in the way, the Angel will carefully go around it. The tricky part of the proof is showing that the Devil can't force the Angel to go in a circle, because if she went in a circle, then she would be surrounded.

References:
Wikipedia
The page of the author of one of the proofs.