Angel Problem

https://en.wikipedia.org/wiki/Angel_problem

by lukas • 10 years ago

128 32 10 years ago

en.wikipedia.org

vessenes• 10 years ago

Mathé'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• 10 years ago

The 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

eru3• 10 years ago

It sounds like these two strategies are dual of each other.

bduerst• 10 years ago

Seems like Kloster devised a mathematical proof for a kiting - a game strategy that involves staying just out of the effective range of an opponent while they chase you.

Kiro• 10 years ago

If the board is infinite, can't the angel just jump in one direction forever?

Willson50• 10 years ago

But what if I put a block where you are about to jump?

joombaga• 10 years ago

The angel is not allowed to jump onto a block; it could not decide to jump where you placed the block.

chias2• 10 years ago

No. 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.

ewzimm5• 10 years ago

Couldn'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.

nemo1618• 10 years ago

This is the 1-Angel Problem on a hexagonal grid, yes? http://llerrah.com/cattrap.htm

Surprisingly tricky, even with a 1-angel!

kefka• 10 years ago

The problem, with 1-angel, feels very go-like.

hyperpape• 10 years ago

Has a nice relation to the board game Hex: https://en.wikipedia.org/wiki/Hex_(board_game)

mmanfrin• 10 years ago

Managed 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.

chias2• 10 years ago

I 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• 10 years ago

The 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• 10 years ago

I 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. :/

wodenokoto2• 10 years ago

From 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?

eru3• 10 years ago

Just one.

pc86• 10 years ago

The devil, on its turn, may add a block on any single square not containing the angel.

wodenokoto2• 10 years ago

That 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• 10 years ago

Amusingly, a variant of this is present in Beyond Zork toward the end of the game.

Angel Problem

Related Stories