Angel problem


The angel problem is a question in combinatorial game theory proposed by John Horton Conway. The game is commonly referred to as the Angels and Devils game. The game is played by two players called the angel and the devil. It is played on an infinite chessboard. The angel has a power k, specified before the game starts. The board starts empty with the angel in one square. On each turn, the angel jumps to a different empty square which could be reached by at most k moves of a chess king, i.e. the distance from the starting square is at most k in the infinity norm. The devil, on its turn, may add a block on any single square not containing the angel. The angel may leap over blocked squares, but cannot land on them. The devil wins if the angel is unable to move. The angel wins by surviving indefinitely.
The angel problem is: can an angel with high enough power win?
There must exist a winning strategy for one of the players. If the devil can force a win then it can do so in a finite number of moves. If the devil cannot force a win then there is always an action that the angel can take to avoid losing and a winning strategy for it is always to pick such a move. More abstractly, the "pay-off set" is a closed set, and it is known that such games are determined. Of course, for any infinite game, if player 2 doesn't have a winning strategy, player 1 can always pick a move that leads to a position where player 2 doesn't have a winning strategy, but in some games, simply playing forever doesn't confer a win to player 1, so undetermined games may exist.
Conway offered a reward for a general solution to this problem. Progress was made first in higher dimensions. In late 2006, the original problem was solved when independent proofs appeared, showing that an angel can win. Bowditch proved that a 4-angel can win and Máthé and Kloster gave proofs that a 2-angel can win.

Basic strategies and why they don't work

Many intuitive escape strategies for the angel can be defeated. For example, if the angel tries to run away from near blocks, the devil can make a giant horseshoe far to the north, then prod the angel into the trap by repeatedly eating the square just to the south of the angel. If the angel tries to avoid traps set very far away, the devil can make a small horseshoe to the north, then prod the angel into the trap by eating the squares far to the south.
It seems that the Angel should be able to win by moving up as fast as he can, combined with occasional zigzags to the east or west to avoid any obvious traps. This strategy can be defeated by noting that this Angel's possible future positions lie in a cone, and the devil can build a wall across the cone in the distance in a certain manner, so that when the angel finally arrives at the distance, the devil has created an impenetrable wall, and since the Angel insists on moving north, the Angel can't move at all.

History

The problem was first published in the 1982 book Winning Ways by Berlekamp, Conway, and Guy, under the name "the angel and the square-eater."
In two dimensions, some early partial results included:
In three dimensions, it was shown that:
Finally, in 2006
there emerged four independent and almost simultaneous proofs that the angel has a winning strategy in two dimensions.
Brian Bowditch's works for the 4-angel, while Oddvar Kloster's and András Máthé's work for the 2-angel. Péter Gács's works only for a much larger constant. The proofs by Bowditch and Máthé have been published in Combinatorics, Probability and Computing. The proof by Kloster has been published in Theoretical Computer Science.

Further unsolved questions

In 3D, given that the angel always increases its y-coordinate, and that the devil is limited to three planes, it is unknown whether the devil has a winning strategy.

Proof sketches

"Guardian" proof

The proof, which shows that in a three-dimensional version of the game a high powered angel has a winning strategy, makes use of "guardians". For each cube of any size, there is a guardian that watches over that cube. The guardians decide at each move whether the cube they are watching over is unsafe, safe, or almost safe. The definitions of "safe" and "almost safe" need to be chosen to ensure this works. This decision is based purely on the density of blocked points in that cube and the size of that cube.
If the angel is given no orders, then it just moves up. If some cubes that the angel is occupying cease to be safe, then the guardian of the biggest of these cubes is instructed to arrange for the angel to leave through one of the borders of that cube. If a guardian is instructed to escort the angel out of its cube to a particular face, the guardian does so by plotting a path of subcubes that are all safe. The guardians in these cubes are then instructed to escort the angel through their respective subcubes. The angel's path in a given subcube is not determined until the angel arrives at that cube. Even then, the path is only determined roughly. This ensures the devil cannot just choose a place on the path sufficiently far along it and block it.
The strategy can be proven to work because the time it takes the devil to convert a safe cube in the angel's path to an unsafe cube is longer than the time it takes the angel to get to that cube.
This proof was published by Imre Leader and Béla Bollobás in 2006. A substantially similar proof was published by Martin Kutz in 2005.

Máthé's 2-angel proof

Máthé introduces the nice devil, which never destroys a square that
the angel could have chosen to occupy on an earlier turn. When the angel plays against the nice devil it concedes defeat if the devil manages to confine it to a finite bounded region of the board.
Máthé's proof breaks into two parts:
  1. he shows that if the angel wins against the nice devil, then the angel wins against the real devil;
  2. he gives an explicit winning strategy for the angel against the nice devil.
Roughly speaking, in the second part, the angel wins against the nice devil by
pretending that the entire left half-plane is destroyed
,
and treating destroyed squares as the walls of a maze,
which it then skirts by means of a "hand-on-the-wall" technique.
That is, the angel keeps its left hand on the wall of the maze
and runs alongside the wall.
One then proves that a nice devil cannot trap an angel that adopts this strategy.
The proof of the first part is by contradiction, and hence Máthé's proof does not immediately
yield an explicit winning strategy against the real devil.
However, Máthé remarks that his proof could in principle be adapted to give such an explicit strategy.

Bowditch's 4-angel proof

defines a variant of the original game with the following rule changes:
  1. The angel can return to any square it has already been to, even if the devil subsequently tried to block it.
  2. A k-devil must visit a square k times before it is blocked.
  3. The angel moves either up, down, left or right by one square.
  4. To win, the angel must trace out a circuitous path.
A circuitous path is a path where is a semi-infinite arc and are pairwise disjoint loops with the following property:
Bowditch considers a variant of the game with the changes 2 and 3 with a 5-devil. He then shows that a winning strategy in this game will yield a winning strategy in our original game for a 4-angel. He then goes on to show that an angel playing a 5-devil can achieve a win using a fairly simple algorithm.
Bowditch claims that a 4-angel can win the original version of the game by imagining a phantom angel playing a 5-devil in the game 2.
The angel follows the path the phantom would take but avoiding the loops. Hence as the path is a semi-infinite arc the angel does not return to any square it has previously been to and so the path is a winning path even in the original game.