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 (or equivalently the points of a 2D lattice). The angel has a power k (a natural number 1 or higher), 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" (i.e., the set of all plays in which the angel wins) is a closed set (in the natural topology on the set of all plays), 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 ($100 for a winning strategy for an angel of sufficiently high power, and $1000 for a proof that the devil can win irrespective of the angel's power). 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 (that is, an angel with power k = 4) 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 cannot 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:
If the angel has power 1, the devil has a winning strategy (Conway, 1982). (According to Conway, this result is actually due to Berlekamp.) This can be read at section 1.1 of Kutz's paper. If the angel never decreases its y coordinate, then the devil has a winning strategy (Conway, 1982). If the angel always increases its distance from the origin, then the devil has a winning strategy (Conway, 1996).
In three dimensions, it was shown that:
If the angel always increases its y coordinate, and the devil can only play in one plane, then the angel has a winning strategy. If the angel always increases its y coordinate, and the devil can only play in two planes, then the angel has a winning strategy. The angel has a winning strategy if it has power 13 or more. If we have an infinite number of devils each playing at distances then the angel can still win if it is of high enough power. (By "playing at distance " we mean the devil is not allowed to play within this distance of the origin).