Games of No Chance MSRI Publications Volume29, 1996
The Angel Problem
JOHN H. CONWAY
Abstract
. Can the Devil, who removes one square per move from an in-
nite chessboard, strand the Angel, who can jump up to 1000 squares per
move? It seems unlikely, but the answer is unknown. Andreas Blass and I
have proved that the Devil
can
strand an Angel who's handicapped in one
of several ways. I end with a challenge for the solution the general problem.
1. Introduction
The Angel and the Devil play their game on an in nite chessboard, with one
square for each ordered pair of integers (
x; y
). On his turn, the Devil may eat
any square of the board whatsoever; this square is then no longer available to the
Angel. The Angel is a \chess piece" that can move to any uneaten square (
X; Y
)
that is at most 1000 king's moves away from its present position (
x; y
)|in other
words, for which
j
X
?
x
j
and
j
Y
?
y
j
are at most 1000. Angels have wings, so
that it does not matter if any intervening squares have already been eaten.
The Devil wins if he can strand the Angel, that is, surround him by a moat
of eaten squares of width at least 1000. The Angel wins just if he can continue
to move forever.
What we have described is more precisely called an
Angel of power
1000. The
Angel Problem
is this:
Determine whether an Angel of some power can defeat the Devil.
Berlekamp showed that the Devil can beat an Angel of power one (a chess King)
on any board of size at least 32
33. However, it seems that it is impossible for
the Devil to beat a Knight, and that would imply that an Angel of power two
(which is considerably stronger than a Knight) will win. But can you prove it?
Well, nobody's managed to prove it yet, even when we make it much easier by
making the Angel have power 1000 or some larger number. The main diculty
seems to be that the Devil cannot ever make a mistake: once he's made some
moves, no matter how foolish, he is in a strictly better position than he was at
the start of the game, since the squares he's eaten can only hinder the Angel.
3
4 JOHN H. CONWAY
(
x
+ 1000
;y
+ 1000)
(
x
?
1000
;y
?
1000)
Figure 1.
Left: An Angel about to fly; he can fly to any point in the square.
Right: A Devil eating a square; three have already been eaten.
2. What's Wrong with Some Potential Strategies
Most people who think about this problem produce trial strategies for the
Angel of the following general type. They advise the Angel to compute a certain
\potential function" that depends on the eaten squares, and then to make a
move that minimizes (or maximizes) this function.
The Devil usually nds it easy to beat such strategies, by nding some feature
to which this function is too sensitive. Suppose, for instance, that the function
is very sensitive to eaten squares close to the Angel. Then the Devil should
build a horseshoe-shaped trap a light-year across, far to the north of the starting
position. This will, of course, cause the Angel to fly southwards as fast as
possible, but no matter. When the trap is set up, the Devil just goads the Angel
into it by repeatedly eating the square just to the south of him. The Angel feels
the pain of these \jabs at his behind" so strongly that he blindly stumbles right
into the trap!
If the Angel switches to a new function that places great emphasis on eaten
squares that are very far away, the Devil might build a mile-wide horseshoe and
then scare the Angel into it by eating just a single square a megaparsec to the
south of him.
The exact details of the Devil's strategy will of course depend on exact struc-
ture of the Angel's potential function. It seems to be impossible to get the
function just right, and if it isn't just right, the Devil builds a trap that the
potential function is insensitive to, and then steers the Angel into it using some-
thing to which the function is over-sensitive! A friend of mine, after hearing my
talk of horseshoe-shaped traps, dreamed up a wonderful potential function that
cleverly searched for horseshoe-shaped traps of all sizes and avoided them. I de-
feated it trivially by having the Devil use a modest little horseshoe that easily
frightened the Angel into a trap of another shape!
