Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Path: utzoo!watmath!clyde!rutgers!husc6!mit-eddie!mit-trillian!vis From: vis@mit-trillian.MIT.EDU (Tom Courtney) Newsgroups: sci.math Subject: Re: angels and devils Message-ID: <1326@mit-trillian.MIT.EDU> Date: Fri, 24-Oct-86 16:42:14 EDT Article-I.D.: mit-tril.1326 Posted: Fri Oct 24 16:42:14 1986 Date-Received: Sat, 25-Oct-86 06:38:06 EDT References: <2056@princeton.UUCP> <5283@dartvax.UUCP> Reply-To: vis@trillian.UUCP (Tom Courtney) Distribution: net Organization: MIT Project Athena Lines: 81 Keywords: game In article <5283@dartvax.UUCP> kevins@dartvax.UUCP (Kevin M. Schofield) writes: > >After spending some time pondering this wonderful question, I concluded >that the angel can indeed forever avoid being trapped. There are 2 ways >that the angel could be trapped: > 1. by walking into a "trap", i.e. a region completely > enclosed except for 1 opening which the devil could remove in > 1 turn. > 2. by being completely enclosed by a wall on all four sides. Remember that it has be a thick wall, since the angel can jump over walls thinner than its range. > >Assuming the angel is intelligent, it will not "walk" on its own volition >into a trap. Also, it is impossible for the devil to "force" the angel to >move in any particular direction; thus we can forget about traps. > Not clear. Suppose the devil could almost build a wall around the angel by force, and that the angel escaped by one move. Then its subsequent moves are being forced by the devil: he can't go back the way he came. >Now still assuming the angel is intelligent, when it sees that a box is >being constructed around it, it heads at full speed towards the perimiter >of the box and then moves around it, it is not too difficult to prove >that the angel can get to the perimiter and find an opening before the >devil can complete the box. > >What seems like a much more interesting question is when the angel is >limited to moves to adjacent grid points. I'm still working on this one, >and any comments or suggestions would be appreciated... An angel with a range of one casts doubt on your escape the box assertion. Imagine the following situation: ...W... ..W.W.. .W...W. W2.A..W .W1..W. ..W.W.. ...W... A = angel; W = wall the devil would like to build; . = undestroyed planet; 1 = edge position; 2 = corner position. If the devil could blow up all the W planets, the angel would be trapped. Can this situation be achieved? Yes. First, the devil starts by detonating planets on the wall. If the angel stays, it gets trapped, so it moves to escape the prison. Suppose it moves to a section of wall remarkably devoid of detonations (remember I didn't require the devil to be clever about the first two). There are two possibilities: either the angel hits an edge or a corner. If he hits a edge (1), the devil blows up a piece of wall in front of him. If he hits a corner (2), the devil blows up the vertice. When the angel enters the wall the devil blows up the piece of wall nearest the angel not already detonated. So let the angel go for the southwest wall (they are of course, symmetrical). At worst, the situation will now look like: ...DOOOOOW ..N.AOOOW. .N...DOW.. N.....W... .N...N.... ..N.N..... ...N...... O = old prison attempt; N = new prison attempt. D = destroyed planet. Going back into the old prison attempt must be wrong, so the angel enters the new prison attempt, and this one traps him. Its hard to explain, but easy to see: 1) don't detonate the entrance to the old prison attempt until the end; 2) detonate any section of wall the angel gets to; 3) Don't detonate a vertice unless an angel gets to it; 4) when the angel is not next to a wall, detonate edge planets not next to detonated planets. I think I should probably tighten up rule 4 by having the devil blow up non-adjacent planets the angel is moving towards, but 5 minutes with a pieces of graph paper and a pebble are sufficient to get the method down perfectly. Now on to the case where the range of the angel is 2! Well, first I'm going to work out the case where the angel gets 2 1 range moves per detonation. But that will be some other night.