From:           wpt@princeton.UUCP (William Thurston)
Newsgroups:     sci.math
Subject:        Re: angels and devils
Date:           21 Oct 86 13:30:25 GMT
Organization:   CS Department, Princeton University
Keywords:       game

Since there hasn't been much response yet to the angels and devils question
I posted a few days ago, I'll add a little more.  The original question
is probably very difficult:

    Imagine a universe consisting of planets arrayed at the grid points
    of an infinite plane.  On one of the planets, an angel is sitting.
    Every day, the angel can fly off to another planet, but the angel's
    range is limited to a distance of (say) 100.

    Unfortunately, there is a devil in the universe.  Every day, the devil
    can destroy a planet, anywhere in the universe.

    Can the angel forever avoid being trapped?

``Fools rush in where angels fear to tread''

There is a variation of the angel, called a fool, who, at the advice of the
hobgoblin of small minds, only travels forward through the stars:
the fool only travels in directions between north-east and north-west.
[Any resemblance to well-known people alive or dead is purely accidental.]

Find a strategy for the devil to trap the fool.  Hint: for maximum jump-size

                                   4*100*100
100, the devil needs no more than 2            rounds to trap the fool.

    Bill Thurston    ...!princeton!wpt
    Mathematics Department
    Princeton University
    Princeton NJ 08544

From:           eppstein@garfield.columbia.edu
To:             princeton!wpt
Subject:        Beam detectors etc

...

Finally, on a totally different subject, namely angels and devils.
Winning Ways says that it has not been proven that any generalized
chess piece can escape.  However it is easy to find an escaping
strategy for the rook even when the devil can move twice for every
rook move.  I find it hard to believe Conway et al didn't know this;
am I misinterpreting what they mean by generalized chess piece?

Date:           Sunday, 16 November 1986  15:38-EST
From:           seismo!princeton!wpt at columbia.edu
To:             eppstein at garfield.columbia.edu

I'll ask Conway about the rook.  What is meant by a generalized chess piece ---
does it have an unbounded motion?

Bill Thurston

From:           wpt@princeton.UUCP (William Thurston)
Newsgroups:     sci.math
Subject:        Re: Angel/devil problem
Summary:        How to catch a fool
Date:           17 Dec 86 03:04:19 GMT
Organization:   CS Department, Princeton University

>From: ilmanen@brahms (Tom Ilmanen)
>Here is algorithm for the angel in the angel/devil problem. I would be
>interested in seeing how the devil can counter it.
>
>     1. Every stride of the angel is within ten degrees of due east.
>
>     2. Of all possible one-degree visual sectors within this twenty-degree
>    range, the angel selects the one with the least total "visual darkness"
>    and heads in that direction.
>
>     3. The angel attemps to go 100 units in the chosen direction, choosing
>    the nearest legal (and unextinguished) star.
>
>"Visual darkness" means the total amount of "black light" emitted by 
>extinguished stars, as perceived by the angel according to the 1/r law
>of attenuation. To be precise, the total visual darkness in a one-degree
>sector S is defined to be 
>$$Darkness(S) = \sum_i 1/{r_i}$$
>and the sum is taken over all stars in the sector S.
>
>     That's it.

The type of angel who always goes with a certain sector is called a fool.
The devil (S) can catch the fool (F), as follows.  For the definiteness,
assume that the angel can skip 100 planets in either in each step, and goes
within 45 degrees of north. (any angle < 90 works equally well;
it just changes the constants.)

S's strategy is to go sufficiently far away from F, choose an east-west line l,
and defend it.  Whatever time it takes for F to get from where
he is halfway to l,  in that time S can eliminate every 400th planet on l
(since the relevant part of l is twice as long as the distance from S's
starting postion to l).

S calculates a position for l which will allow this thinning process to
continue long enough to make an impenetrable barrier, of thickness 100
planets: S needs 400*100 iterations.  Each time F gets halfway from his
current position to l, S reassesses where F might attempt to cross l.
By that time the relevant portion is only half as long, so before F halves
his distance again S has time to thin out 1/40,000 of the planets.

Clearly, a starting east-west line l which is $2^40,000$ planets north of
F is sufficient!

Bill Thurston   Mathematics Department, Princeton   princeton!wpt