4 ms·
If the board is infinite, can't the angel just jump in one direction forever?
by Kiro 11y ago
If the board is infinite, can't the angel just jump in one direction forever?
- Willson50 11y agoBut what if I put a block where you are about to jump?
- joombaga 11y agoThe angel is not allowed to jump onto a block; it could not decide to jump where you placed the block.
- chias 11y agoNo. Lets say we're playing with a 2-angel. Lets place an angel, and without loss of generality assume the angel is moving left: _ _ _ _ _ A _ _ _ _ _ Then, perhaps the Devil goes here: _ D _ _ _ A _ _ _ _ _ Angel moves: _ D _ A _ _ _ _ _ _ _ Devil places: _ D D A _ _ _ _ _ _ _ The angel must now change direction. For any given direction and any given angel power, as long as the devil starts placing pieces far enough away he can force the angel to change direction.
- ewzimm 11y agoCouldn't the angel calculate when it's necessary to change direction and then do so, forcing the devil to begin constructing a new trap, and then keep repeating the same behavior? I'm sure there's a reason why this obvious strategy wouldn't work, but I don't quite see it.
- dragontamer 11y agoIt has been proven that a 2-Angel can. The difficult part of the problem is proving your argument to others. There-in lies the difficulty of mathematical proofs.
- ewzimm 11y agoI only read the part about pretending the left half is blocked and using the left wall as a guide, which seems a lot more specific than just "go in one direction until you're approaching a trap and then change." I understand that proofs are much harder than intuition, but it seems that the angel has such an advantage of choice that it would be easy to prove. At any point, the 2-angel can move to 8 spots on an infinite plane and the devil can block 1. I wonder how constrained the problem could get for the angel to have a winning strategy. Let's say the angel could only move in two directions. It would seem intuitively that this would still leave enough room to avoid traps. Devil starts creating a trap in the up direction, angel moves right. Devil starts constructing a trap in the right direction, angel moves up. If it were possible to constuct a trap that blocked both directions with an unknown rate of movement on an infinite plane, it might lead to some interesting applications to other things, but my intuition says it's not.
- eru 11y agoI think if the Angel was restricted to move top and right, it could not escape. Conceptually, the devil will start constructing both traps at the same time at half speed, and decide which one to put more work in as the angel approaches.
- nandemo 11y ago> Let's say the angel could only move in two directions. It would seem intuitively that this would still leave enough room to avoid traps. Nope. Even if you restrict the angel to 3 directions (up, left, right), the devil has a winning strategy. This is mentioned in the linked article: > If the angel never decreases its y coordinate, then the devil has a winning strategy (Conway, 1982). There's a simple, informal proof in the references: Conway, H. "The Angel Problem" http://library.msri.org/books/Book29/files/conway.pdf http://library.msri.org/books/Book29/files/conway.pdf
- ewzimm 11y agoThanks for the clarification. I do wonder what other kinds of things this math could apply to. It's pretty abstract, but if you want to direct an unpredictable agent toward a certain behavior, knowing where to place control mechanisms might be interesting.
- deleted 11y ago[deleted]
- jack9 11y agoEvery move increases the area needed to be blocked. Starting off, if the angel can move 1 every 1/9th of a turn, a devil could block off a 3x3. Every subsequent full turn would add 2 that the devil would have to block off. So for move rate M on an NxN grid (which can represent any wandering linear path) necessary to trap an angel is 8+2NM (interestingly, close to 13). If an angel moves at all, the devil cannot trap it without player error.
- deleted 11y ago[deleted]