Angel problem
The angel problem is a question in combinatorial game theory proposed by John Horton Conway.
The angel has a power k (a natural number 1 or higher), specified before the game starts.
The devil, on its turn, may add a block on any single square not containing the angel.
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).
In late 2006, the original problem was solved when independent proofs appeared, showing that an angel can win.
The problem was first published in the 1982 book Winning Ways by Berlekamp, Conway, and Guy,[5] 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 (not long after the publication of Peter Winkler's book Mathematical Puzzles, which helped publicize the angel problem) there emerged four independent and almost simultaneous proofs that the angel has a winning strategy in two dimensions.
Additionally, Peter Gacs has a claimed proof Archived 2016-03-04 at the Wayback Machine which requires a much stronger angel; the details are fairly complex and have not been reviewed by a journal for accuracy.
The proofs by Bowditch and Máthé have been published in Combinatorics, Probability and Computing.
Oddvar Kloster discovered a constructive algorithm to solve the problem with a 2-angel.
This algorithm is quite simple and also optimal, since, as noted above, the devil has a winning strategy against a 1-angel.
We will only do this if the path increases in length by no more than twice the number of blocked squares moved into the left set.
Of such qualifying paths, we choose one that moves the greatest number of blocked off squares into the left set.
The angel then makes two steps along this path, keeping the path to its left when moving in the forward direction (so if the devil were not blocking off squares, the angel would travel north indefinitely).
Máthé[3] 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 (otherwise the angel could just hop back and forth between two squares and never lose).
Máthé's proof breaks into two parts: Roughly speaking, in the second part, the angel wins against the nice devil by pretending that the entire left half-plane is destroyed (in addition to any squares actually destroyed by the nice devil), and treating destroyed squares as the walls of a maze, which it then skirts by means of a "hand-on-the-wall" technique.
One then proves that a nice devil cannot trap an angel that adopts this strategy.
However, Máthé remarks that his proof could in principle be adapted to give such an explicit strategy.
He then goes on to show that an angel playing a 5-devil (game 2) can achieve a win using a fairly simple algorithm.
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".
The guardians in these cubes are then instructed to escort the angel through their respective subcubes.
This ensures the devil cannot just choose a place on the path sufficiently far along it and block it.
