Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!lll-crg!nike!sri-spam!sri-unix!hplabs!pyramid!decwrl!labrea!navajo!avg
From: avg@navajo.STANFORD.EDU (Allen Van Gelder)
Newsgroups: sci.math
Subject: Re: angels and devils
Message-ID: <1056@navajo.STANFORD.EDU>
Date: Sun, 2-Nov-86 22:58:58 EST
Article-I.D.: navajo.1056
Posted: Sun Nov  2 22:58:58 1986
Date-Received: Tue, 4-Nov-86 04:14:10 EST
Reply-To: avg@navajo.UUCP (Allen Van Gelder)
Organization: Stanford University
Lines: 53

References:


This problem seems to center on the issue of connectivity and separators.
For the angel, any two planets within a certain distance are connected
by an edge.  So far, no one has clarified "distance".
Three possible definitions are
(1) Euclidean distance, sqrt(dx^2 + dy^2);
(2) Manhattan distance, |dx| + |dy|, in which a diagonal move has length 2;
(3) "max" distance, max(|dx|, |dy|), in which a diagonal move has length 1.

Let's consider some small-distance cases first.  Say the angel can move
distance 1.  In Euclidean and "max" this means only rectilinear moves.
The connectivity is 4.  The devil can trap the angel in about 10 moves
by the well-known go tactic of playing a diagonal away.  Here is an example.
Let a be the angel's initial position, 1 be the devil's first move;
let b be the angel's 2nd position, 2 be the devil's 2nd move; etc.
		. . . . . . . . .
		. . . 1 . . . . .
		. 6 . . a . . . .
		. . f . b . . . .
		. 5 e d c 2 . . .
		. . 4 . 3 . . . .
		. . . . . . . . .
The rest is clear, and it is easy to try the other alternatives for the
angel and see that they are fruitless.

The situation is not so clear with manhattan distance; now the connectivity
is 8.  Going to distance 2, the connectivity jumps to 12 or 24,
depending on which "distance" you use.  I suspect that if you find a
way to trap the angel when it can go manhattan distance 2, it will
generalize to 100.

Now a theorem:
If the devil can always force the angel to move to a planet in 2 or more
moves that she was already on or could have reached in 1 move,
then the angel can be trapped.
Proof:
If the angel has an escaping strategy, then assume that she uses an
optimal escaping strategy.
Suppose the angel travels from P1 to P2 in 2 or more moves, and could
have arrived there in 1 move; then the strategy is not optimal because
the devil has gotten at least 1 "free" move.  Similarly, if P1=P2,
then the devil has gotten at least 2 free moves.  Thus, if the devil
can always force this to occur, then the angel has no escaping strategy.
QED
That isn't supposed to be rigorous; it's just supposed to convince you.

This theorem at least reduces the search space; an angel strategy can be
considered to fail as soon as a non-optimal move occurs;  you don't
have to grind it out to the bitter end.

To formalize this a little more, say the angel can "see" a planet if
she can move to it in one turn.  Keep track of planets the angel has seen
and when they were FIRST seen.  At each turn the angel must move to
a planet she sees but has never seen before.