11 ms·
Angel Problem
- vessenes 10y agoMathé's 2-Angel proof is really nice, or at least the summary is appealing -- he imagines a 'nice' devil, shows it can be beaten, then proves that if you can beat the nice devil, you can beat the mean one. This is one of my favorite problem solving strategies -- reducing to a more obvious solvable situation, then filling in the chinks and gaps to expand back.
- dsp1234 10y agoThe Kloster solution[0] solves it in a more direct way, by showing that for each action the devil takes the angel can take a counter action by limiting it's own moves. In the one proof is the realization that sometimes it's easier to solve a smaller problem then prove equivalence to a harder problem, and in the other is the realization that sometimes voluntarily reducing the number of actions can lead to a simpler solution. Both are pretty good tools to have under one's belt. [0] - http://home.broadpark.no/~oddvark/angel/kloster.html http://home.broadpark.no/~oddvark/angel/kloster.html
- Kiro 10y agoIf the board is infinite, can't the angel just jump in one direction forever?
- Willson50 10y agoBut what if I put a block where you are about to jump?
- joombaga 10y agoThe angel is not allowed to jump onto a block; it could not decide to jump where you placed the block.
- chias 10y 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 10y 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 10y 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 10y 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.
- nemo1618 10y agoThis is the 1-Angel Problem on a hexagonal grid, yes? http://llerrah.com/cattrap.htm http://llerrah.com/cattrap.htm Surprisingly tricky, even with a 1-angel!
- kefka 10y agoThe problem, with 1-angel, feels very go-like.
- hyperpape 10y agoHas a nice relation to the board game Hex: https://en.wikipedia.org/wiki/Hex_(board_game) https://en.wikipedia.org/wiki/Hex_(board_game)
- mmanfrin 10y agoManaged to find a strategy pretty quickly: begin from the outside, opposite of the direction you want the cat to go in; then fill until you have 1 exit in that direction and begin to fill in the exits while the cat travels to the one open route, and when it's one step away you close it. You then have many more moves before the cat can get back to open area, in which case you can repeat until you have a closed loop.
- chias 10y agoI eventually found a strategy of basically trying to fill every "even" space around the edge, and then only filling in the odd ones when the cat was 1 space away from entering the edge-ring. This would allow me enough time to enclose the entire board, after which trapping the cat into a single space is just a matter of time
- decwakeboarder 10y agoThe Angel (cat) in this example is incredibly naive which made it easy to realize that strategy would work. Would definitely make for an interesting 2 player game!
- thaumasiotes 10y agoI think it's worth noting here that the hex grid makes the devil's job significantly easier, since a square grid space borders 8 other squares for a 1-angel, and 24 squares (or 16 outer squares) for a 2-angel, where the equivalent hex grid figures are 6 and 18 (or 12). For a strategy based on constructing a perimeter and filling in its gaps as the angel approaches, it should be obvious why a smaller perimeter for the angel is an advantage. Also, it's pretty unsatisfying playing against that cat, since I can't shake the feeling that it's making some really dumb moves. I'd feel like I was actually learning something if I thought the cat knew what it was doing. :/
- wodenokoto 10y agoFrom the Wikipedia description it is bit vague how many blocks the devil put down each turn. Is it just 1? The same as angels power?
- eru 10y agoJust one.
- pc86 10y ago> The devil, on its turn, may add a block on any single square not containing the angel.
- wodenokoto 10y agoThat phrase can mean both 1 block and one block only, or it can mean one block per square, on as many squares as needed as long as the block is not placed on a square containing an angel or another block. Particularly when read without emphasis. I think I leaned towards an ambiguous reading because I couldn't understand how one block per turn was enough to ever win.
- mondoshawan 10y agoAmusingly, a variant of this is present in Beyond Zork toward the end of the game.