Editing Angel problem (section)

== Proof sketches ==

=== Kloster's 2-angel proof ===

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 start out by drawing a vertical line immediately to the left of the angel's starting position, down to <math>y = -\infty</math> and up to <math>y = \infty</math>. This line represents the path the angel will take, which will be updated after each of the devil's moves, and partitions the board's squares into a "left set" and a "right set." Once a square becomes part of the left set, it will remain so for the remainder of the game, and the angel will not make any future moves to any of these squares. Every time the devil blocks off a new square, we search over all possible modifications to the path such that we move one or more squares in the right set which the devil has blocked off into the left set. 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). Note that when going clockwise around a corner, the angel will not move for one step, because the two segments touching the corner have the same square to their right.

=== Máthé's 2-angel proof ===

Máthé<ref name="M"/> 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:

#he shows that if the angel wins against the nice devil, then the angel wins against the real devil;
#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
(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.
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 ===

[[Brian Bowditch]] defines<ref name="B"/> a variant (game 2) of the original game with the following rule changes:

# The angel can return to any square it has already been to, even if the devil subsequently tried to block it.
# A k-devil must visit a square k times before it is blocked.
# The angel moves either up, down, left or right by one square (a duke move).
# To win, the angel must trace out a circuitous path (defined below).

A circuitous path is a path <math>\pi = \cup^{\infty}_{i=1} (\sigma_i \cup \gamma_i)</math> where <math>\sigma = \cup^{\infty}_{i=1} \sigma_i</math> is a semi-infinite arc (a non self-intersecting path with a starting point but no ending point) and <math>{\gamma_i}</math> are pairwise disjoint loops with the following property:

* <math>\forall i: |\gamma_i|\leq i</math> where <math>|\gamma_i|</math> is the length of the ith loop.

(To be well defined <math>\gamma_i</math> must begin and end at the end point of <math>\sigma_i</math> and <math>\sigma_i</math> must end at the starting point of <math>\sigma_{i+1}</math>.)

Bowditch considers a variant (game 1) 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 (game 2) 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 <math>\sigma</math> 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.

=== 3D version of the problem ===

==== "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.<ref>B. Bollobás and I. Leader, ''The angel and the devil in three dimensions.'' Journal of Combinatorial Theory, Series A. vol. 113 (2006), no. 1, pp. 176&ndash;184</ref>  A substantially similar proof was published by [[Martin Kutz]] in 2005.<ref name="kutz2004" /><ref name="kutz2005">Martin Kutz, Conway's Angel in three dimensions, ''Theoret. Comp. Sci.'' 349(3):443–451, 2005.</ref>