Editing Angel problem (section)

=== 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.