From:wpt@princeton.UUCP (William Thurston)Newsgroups:sci.mathSubject:Re: angels and devilsDate:21 Oct 86 13:30:25 GMTOrganization:CS Department, Princeton UniversityKeywords: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.eduTo:princeton!wptSubject: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-ESTFrom:seismo!princeton!wpt at columbia.eduTo: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.mathSubject:Re: Angel/devil problemSummary:How to catch a foolDate:17 Dec 86 03:04:19 GMTOrganization: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