The Angel Problem
February 16, 2012 11:43 AM Subscribe
The Angel Problem. The Angel and the Devil play a game on an infinite chess board...
Sounds an awful lot like spleef, actually...
posted by LN at 11:45 AM on February 16, 2012 [1 favorite]
posted by LN at 11:45 AM on February 16, 2012 [1 favorite]
(I like to imagine it as these two, for what it's worth.)
posted by Wolfdog at 11:49 AM on February 16, 2012 [2 favorites]
posted by Wolfdog at 11:49 AM on February 16, 2012 [2 favorites]
Yea, but when God goes to sue the devil for cheating (as he inevitably will, duh he's the devil) and murdering his angle, who wins?
[C'mon, fill in the punchline... you know you want to!]
posted by RolandOfEld at 11:50 AM on February 16, 2012 [1 favorite]
[C'mon, fill in the punchline... you know you want to!]
posted by RolandOfEld at 11:50 AM on February 16, 2012 [1 favorite]
*or Angel instead of angle.... whatever works
posted by RolandOfEld at 11:50 AM on February 16, 2012
posted by RolandOfEld at 11:50 AM on February 16, 2012
The greatest trick the Devil ever pulled was eating the square under the Angel. And like that... *poof* He wins.
posted by It's Raining Florence Henderson at 11:51 AM on February 16, 2012 [3 favorites]
posted by It's Raining Florence Henderson at 11:51 AM on February 16, 2012 [3 favorites]
That's a pretty great problem. Very similar to the board game Blokus, which I've also wondered about the math of.
posted by DU at 11:59 AM on February 16, 2012
posted by DU at 11:59 AM on February 16, 2012
Something about the lawyers being devilish.
posted by Obscure Reference at 12:17 PM on February 16, 2012
posted by Obscure Reference at 12:17 PM on February 16, 2012
Seems like a good problem for Go players to think about.
posted by michaelh at 12:17 PM on February 16, 2012
posted by michaelh at 12:17 PM on February 16, 2012
There is a mathematical detail here that the game is determined only because the devil wins only if he can do so in finite time. See the Axiom of Determinacy and Projective Determinacy for more mathematical fun.
posted by jeffburdges at 12:20 PM on February 16, 2012 [3 favorites]
posted by jeffburdges at 12:20 PM on February 16, 2012 [3 favorites]
Presumably eating the square the Angel occupies is a non-valid move.
A very nifty little problem. As in Go there's going to be a lot of pre-planning and long term thinking for both parties.
The Devil's problem is that for any sufficienly high K value, the Devil must begin by eating squares a goodly distance away from the Angel, which is compounded by the Angel's ability to simply run away from any prepared ground. That forces the Devil to prepare multiple locations surrounding the Angel, eating at least a square or two in many widely spread areas so as to be able to expand on that as the Angel moves.
Very nifty problem/game. Thanks Wolfdog!
posted by sotonohito at 12:22 PM on February 16, 2012 [1 favorite]
A very nifty little problem. As in Go there's going to be a lot of pre-planning and long term thinking for both parties.
The Devil's problem is that for any sufficienly high K value, the Devil must begin by eating squares a goodly distance away from the Angel, which is compounded by the Angel's ability to simply run away from any prepared ground. That forces the Devil to prepare multiple locations surrounding the Angel, eating at least a square or two in many widely spread areas so as to be able to expand on that as the Angel moves.
Very nifty problem/game. Thanks Wolfdog!
posted by sotonohito at 12:22 PM on February 16, 2012 [1 favorite]
> Presumably eating the square the Angel occupies is a non-valid move.
It's not quite clear from the rules, but this case is explicitly considered in the first linked paper. It seems to only require that the angel move on his next turn.
posted by Horselover Fat at 12:36 PM on February 16, 2012 [1 favorite]
It's not quite clear from the rules, but this case is explicitly considered in the first linked paper. It seems to only require that the angel move on his next turn.
posted by Horselover Fat at 12:36 PM on February 16, 2012 [1 favorite]
... When the devil gets the subpoena he laughs and writes a reply to God, [hover for punchline]
posted by RolandOfEld at 12:37 PM on February 16, 2012 [4 favorites]
posted by RolandOfEld at 12:37 PM on February 16, 2012 [4 favorites]
The way that the problem is described, the Angel doesn't actually ever win. The Angel "wins" if the game is infinitely long.
Which means it is reminiscent of the Stopping Problem. You can't ever look at the game and say, "The Angel just won it." All you can really say is, "The Angel hasn't lost yet."
posted by Chocolate Pickle at 12:38 PM on February 16, 2012 [2 favorites]
Which means it is reminiscent of the Stopping Problem. You can't ever look at the game and say, "The Angel just won it." All you can really say is, "The Angel hasn't lost yet."
posted by Chocolate Pickle at 12:38 PM on February 16, 2012 [2 favorites]
Well, you can also say "The angel has presented a verifiable proof that he can continue the game indefinitely", which is what winning is really about here.
posted by Wolfdog at 12:48 PM on February 16, 2012 [3 favorites]
posted by Wolfdog at 12:48 PM on February 16, 2012 [3 favorites]
So the angel wins by perpetual uncheck.
posted by TheRedArmy at 12:54 PM on February 16, 2012
posted by TheRedArmy at 12:54 PM on February 16, 2012
#netherworldproblems
posted by notmydesk at 12:56 PM on February 16, 2012 [10 favorites]
posted by notmydesk at 12:56 PM on February 16, 2012 [10 favorites]
Reminds me a bit of the Mefi projects with the DARPA thing.
This solution shows that an Angel of an unstated, but apparently rather high, power can win. Unfortunately, I have not found the time and energy to examine it thoroughly, as the argument contains quite a lot of details
There's your win right there.
posted by Smedleyman at 1:14 PM on February 16, 2012
This solution shows that an Angel of an unstated, but apparently rather high, power can win. Unfortunately, I have not found the time and energy to examine it thoroughly, as the argument contains quite a lot of details
There's your win right there.
posted by Smedleyman at 1:14 PM on February 16, 2012
I'm reasonably certain that the Devil is a rules lawyer and noticed that there's no restriction on how many squares he can eat on each turn...
posted by MrMoonPie at 1:27 PM on February 16, 2012 [1 favorite]
posted by MrMoonPie at 1:27 PM on February 16, 2012 [1 favorite]
Nor is there any stipulation that a square that is eaten cannot be one huge square comprised of many smaller squares.
Qix?
posted by maxwelton at 2:28 PM on February 16, 2012
Qix?
posted by maxwelton at 2:28 PM on February 16, 2012
Wait, sorry. Who goes first?
posted by jwhite1979 at 3:16 PM on February 16, 2012 [1 favorite]
posted by jwhite1979 at 3:16 PM on February 16, 2012 [1 favorite]
Effectively, the devil goes first no matter what, because if the angel goes first then nothing changes about the game state.
posted by NMcCoy at 3:26 PM on February 16, 2012 [9 favorites]
posted by NMcCoy at 3:26 PM on February 16, 2012 [9 favorites]
This made me want to post about snaky, the game, but sure enough Wolfdog already did. Well, I'll repost his link to a snaky discussion here, and point out that it is still unsolved. It's tantalizingly close to the angel problem (just change the rules so that the angel must make a certain snake-like shape before it dies) so now's our chance to win the $50!
posted by TreeRooster at 3:27 PM on February 16, 2012
posted by TreeRooster at 3:27 PM on February 16, 2012
There is a mathematical detail here that the game is determined only because the devil wins only if he can do so in finite time.
Do you mean the devil has to say before the game starts that he can disable the angel in X moves, for a specified X? Otherwise Chocolate Pickle's observation still stands.
jcreigh - If you like this puzzle, and haven't yet seen ""Winning Ways ...", I recommend getting it from a library. It's really cool, and they way they use Hackenbush to derive the surreal numbers is great.
posted by benito.strauss at 4:54 PM on February 16, 2012
Do you mean the devil has to say before the game starts that he can disable the angel in X moves, for a specified X? Otherwise Chocolate Pickle's observation still stands.
jcreigh - If you like this puzzle, and haven't yet seen ""Winning Ways ...", I recommend getting it from a library. It's really cool, and they way they use Hackenbush to derive the surreal numbers is great.
posted by benito.strauss at 4:54 PM on February 16, 2012
Okay, so supposedly the devil's winning strategy for k = 1 is given in the book "Winning Ways for your Mathematical Plays" but I can't find the text online.
I have a copy. It's in the third volume, page 644 for others who have it on-hand.
It looks like it's based on Chessgo, where a player controls a chess piece and another tries to pen her in. It's not clear to me from the text what the strategy is, but what follows is a big case analysis of finite board sizes with non-divine chess pieces. The Authors mention that Blass and Conway showed the Angel ends up forced closer and closer to the center of the board. I'll keep looking for the actual strategy.
posted by monkeymadness at 4:54 PM on February 16, 2012
I have a copy. It's in the third volume, page 644 for others who have it on-hand.
It looks like it's based on Chessgo, where a player controls a chess piece and another tries to pen her in. It's not clear to me from the text what the strategy is, but what follows is a big case analysis of finite board sizes with non-divine chess pieces. The Authors mention that Blass and Conway showed the Angel ends up forced closer and closer to the center of the board. I'll keep looking for the actual strategy.
posted by monkeymadness at 4:54 PM on February 16, 2012
Ah, my mistake. The Angel-with-power-1 is just what they call Kinggo, and it is indeed a large case analysis. The gist is that the Devil eats a bunch of squares in the beginning moves and continues to force the Angel back toward the center whenever she heads in any direction.
Winning Ways is a great book. It's about 1000 pages of this sort of thing.
posted by monkeymadness at 5:04 PM on February 16, 2012 [1 favorite]
Winning Ways is a great book. It's about 1000 pages of this sort of thing.
posted by monkeymadness at 5:04 PM on February 16, 2012 [1 favorite]
TIL that you can fill up a whole whiteboard thinking about reducing a problem to vectors and realize that the reason is probably the law of sines. Hence if k>=2 the angel may always find a vector that allows an escape because triangle 2R
posted by humanfont at 5:05 PM on February 16, 2012
posted by humanfont at 5:05 PM on February 16, 2012
Reminds me of the Chat Noir flash game featured in this MeFi post, except that this would somehow imply that cat != devil.
posted by HeroZero at 5:16 PM on February 16, 2012
posted by HeroZero at 5:16 PM on February 16, 2012
The Wikipedia article describes the proof that the Angel wins when k = 2, but not the proof that the Devil wins when k = 1. I'd be interested in seeing the latter.
posted by savetheclocktower at 12:51 PM on February 17, 2012
posted by savetheclocktower at 12:51 PM on February 17, 2012
This was really fun to think about. Thanks for posting it.
posted by humanfont at 4:29 PM on February 17, 2012
posted by humanfont at 4:29 PM on February 17, 2012
Effectively, the devil goes first no matter what, because if the angel goes first then nothing changes about the game state.
Oh yeah. :)
posted by jwhite1979 at 10:00 AM on February 20, 2012
Oh yeah. :)
posted by jwhite1979 at 10:00 AM on February 20, 2012
« Older "Go back to Seattle and behave," | Bloopatone Newer »
This thread has been archived and is closed to new comments
posted by Fizz at 11:45 AM on February 16, 2012 [3 favorites]