A Game of Angels and Devils

[Amiel]

An Angel and Devil play their game on an infinite chessboard, with one square for each ordered pair of integers (x,y). On his turn, the Devil may eat any square of the board; this square is now no longer available to the Angel. The Angel is a "chess piece" that can move to any uneaten square (X,Y) that is at most 1000 king's moves away from its present position (x,y) – in other words, for which |X - x| and |Y - y| are at most 1000.
Angels have wings, so that it does not matter if any intervening squares have already been eaten.

The Devil wins if he can strand the Angel, that is, surround him by a moat of eaten squares of width at least 1000. The Angel wins just if he can continue to move forever.

Can the Angel defeat the Devil?

[Ichneumon]

I haven't thought about this long and I'm rather tired, but I'd say that as long as the Angel keeps moving to square 999 squares away the devil can never trap him/her. Mostly because the board is infinite and the angel can just continue to move away from any square the devil eats.

EDIT: the only way I see for the Devil to ever capture the angel is to first create a square fence of a 1000 squares thick around the angel, making it impossible for the angel to leave. If the angel can't leave the devil can just continue eating what's inside and the angel just has to wait and die. The production of such a "fence" however would take such a long number of turns that the angel would have to be very foolish to not discover the devil's plan and "walk around the fence".

[Quincunx]

Of course not--the Devil will cheat. It's what devils do. :smallamused:

[Delta]

Can the Angel defeat the Devil?

Yes, definitely. As long as the Angel only moves in two directions ("up" and "right", for example), he'll always have a 999x999 size rectangle of possible squares to move to, of which the Devil can only eat a single one.

[Zeb The Troll]

With a range as big as what's provided and an infinite playing field, I see no way for the devil to ever win this contest. All the angel would have to do is fly in a single direction in perpetuity and there's nothing the devil could do about it.

[Amiel]

Actually, as stated, the devil can move to any square (it is the Queen piece).
The angel can move to only one square at a time (it is the King piece).

[Zeb The Troll]

Actually, as stated, the devil can move to any square (it is the Queen piece).
The angel can move to only one square at a time (it is the King piece).
Actually...
The Angel is a "chess piece" that can move to any uneaten square (X,Y) that is at most 1000 king's moves away from its present position (x,y)This doesn't sound like one square at a time.

[Amiel]

C.f
AThe Angel is a "chess piece" that can move to any uneaten square (X,Y) that is at most 1000 king's moves away from its present position (x,y)

Emphasis added

You need to consider the sentence in its entirety

[Zeb The Troll]

C.f

Emphasis addedYes, but you said it can move up to a thousand "King's Moves" away from it's current position. The only difference, according to the original text, is that the Angel has limited range and the Devil does not.

EDIT: Unless you meant "present position" to mean "starting position". That's a whole different ball of wax.

EDIT EDIT: Note that you also said the Angel can fly over missing squares, implying range NOT limited to 1, as a King piece would be.

[Amiel]

Per chess, the King can only move to one square at a time; albeit in any direction. Contrast this with the Queen which can move to any number of squares, in any direction.

The wording should mean that the Angel is endeavoring to avoid the Devil, thus moving away from the "eaten squares."

[Eldan]

Yes, but the angel can do so 1000 times per turn, unless I'm misreading this.

[Zeb The Troll]

Yes, but I interpreted the "King's Move" text to be an explicit definition, meant to clarify, say, that it can't move up to a thousand Knight's Moves, for example.

[Ichneumon]

If you meant he can only make King's moves, that changes everything. And in that case, I don't understand with what you mean with the fact that the angel has wings.

[Amiel]

The Devil has infinite range on an infinite board.
The Angel can move only one square to a position 1000 squares from its current position.

EDIT: Ichneumon: I think it is meant to represent that angel can avoid certain situations where it would be considered an automatic loss.

[Zeb The Troll]

If you meant he can only make King's moves, that changes everything. And in that case, I don't understand with what you mean with the fact that the angel has wings.Indeed. Taking the original text at face value, it is explicitly declared that the Angel can move to any square within a thousand squared of it's "current location", that being the square where he started the turn.

[Eldan]

Well, still.

Demon eats any square.
Angel moves 1000 squares directly upwards.
Demon eats any square.
Angel moves 1000 squares directly upwards.


Continue for as long as you want. I don't see how the demon can win.

[Amiel]

Did you miss the part about King's moves?

[Zeb The Troll]

The point is that you're not being clear in your rules setup. If you meant "Starting Position" instead of "Current Position" that also drastically changes the understanding of the scenario.

[Eldan]

No. It says 1000 Kings moves per turn, no? And the Angel can move over eaten squares.

So I don't see the problem. Unless King's moves means somethign else I'm not aware of.

[hamishspence]

They still have to land on a valid square- two dimensional plane.

So they can jump over a zone of eaten squares 999 squares wide- but if they're surrounded by a zone 1000 squares wide, they lose.

[Amiel]

King's moves means it can move only one square a time; think of it as chess, this is how the King moves in chess. Thus, it will take the Angel 1000 moves to move 1000 squares away from its present position.
In other words, one move per turn to at most 1000 squares on an infinite board.

If the Angel can move to any square within 1000 squares, it's an absolute no-brainer . The tricky bit is the only ability to make King's moves.

[Zeb The Troll]

King's moves means it can move only one square a time; think of it as chess, this is how the King moves in chess. Thus, it will take the Angel 1000 moves to move 1000 squares away from its present position.
In other words, one move per turn to at most 1000 squares on an infinite board. Your verbage and your explanation are at odds with each other.

If the Angel can only move one square in any direction, why bother giving it wings? Why bother mentioning 1000 squares at all? What are the 1000 squares if not a range PER TURN, as is suggested?

[Amiel]

How? Have you never played or considered chess?

It is an infinite board. Also, it is a puzzle, if it wasn't obvious.
I addressed why giving it wings in an earlier post; they are to ensure that no automatic loss is viable; anyway, this puzzle isn't one I came up with, just something that I thought was interesting.

Note: it doesn't say 1000 king moves; which would mean 1000 king moves.
It says 1000 king's moves; 1000 moves to 1000 squares.

[Zeb The Troll]

The Angel is a "chess piece" that can move to any uneaten square (X,Y) that is at most 1000 king's moves away from its present position (x,y).How do you not understand that your exact wording suggests the Angel can move a thousand squares a way in one turn?

And I'm going to ask this again because you keep not addressing it.

DO YOU MEAN STARTING POSITION INSTEAD OF PRESENT POSITION IN YOUR SETUP? Because that changes everything. Present position means "location at the beginning of his turn". If he can only move 1 square per turn, on an infinite playing board, what is the purpose of mentioning the thousand squares at all?

[Amiel]

How can you not understand that the angel can only make king's moves. Why are you avoiding this fact?

The angel presumably gets to go first, since it is the one being chased. And starting position changes nothing, it is the ability to only make king's moves NOT king moves.

It is in fact a puzzle.

[KuReshtin]

If I've interpreted Amiel's clarification on the Angel's moves, he means that the angel can only move to an adjacent square from where he started the turn, but disregards eaten squares.

If I've understood it correctly, then the angel should be able to move only to the squares marked as yellow in the below picture:

http://lh3.ggpht.com/_7Tn9Kao9lf8/TDMCap3Z2lI/AAAAAAAAARU/PML5j99YeYw/s800/Angel.JPG

So even if a quare right next to the angel has been eaten, the angel can still make the move to the nearest available square in that direction, as long as it's within 1000 squares from the starting point of the round.

[Delta]

And starting position changes nothing, it is the ability to only make king's moves NOT king moves.

Actually, even that changes nothing. Even if the angel is only able to move one square at a time, I do not think the devil would be able to catch him.

[Quincunx]

It's comforting to see that I'm not the only person on this board who couldn't clarify my ideas if my life depended upon it. Either that or Amiel is the devil, cheating. :smallamused:

[Amiel]

Thank you, KuReshtin! You have definitely interpreted it correctly. Kudos and cookies. :smallsmile:

Delta, ah, don't forget, the devil can conceivably move to any position on the board. The angel then has to react to move away from the devil, presumably because of disagreements arising from close proximity.

Quincunx: :smallbiggrin: Heh, I admit nothing. Although the emphasis within the text may be a bit ambiguous, it was essentially cut and pasted from a different board verbatim.

[Delta]

in other words, for which |X - x| and |Y - y| are at most 1000.

Actually, that is a mathematically much more precise definition than the "king's moves"-thing, so that should settle it.

If that Angel is at square (0,0), he can move to any square within the rectangle of (1000,1000), (1000,-1000), (-1000,1000) and (-1000,-1000) that hasn't been eaten. There's no room for trickery in that sentence.

[Zeb The Troll]

Ku - That is most decidedly NOT a "King's Move" under any definition. Thought that is a clarification that would be important in the setup.

By the way, am I the only one who sees the semantics of the setup to not clearly convey what Ku describes?

If you don't actually mean "any uneaten square that is no more than 1000 squares away from where it is right now" then don't say "any uneaten square". Say "any adjacent square, ignoring eaten ones, so long as it is no more than 1000 squares away" or something more descriptive.

[Amiel]

Maths does take into account wording, the expressions are meant to the represent the extent of placement. King's moves are still in effect.

[Delta]

Delta, ah, don't forget, the devil can conceivably move to any position on the board. The angel then has to react to move away from the devil, presumably because of disagreements arising from close proximity.

It doesn't matter. The Angel will always have a square to his up or right (i.e. in a positive or neutral x/y direction) to move to, and as long as he moves up/right I'm quite sure it's impossible for the Devil to catch him.

[Amiel]

Zeb, what would you consider to be a king's move?
The ability to fly is possibly a caveat meant to place additional survivability within the angel.

Devil: Queen; Angel: King with caveat of ability to fly.

[Delta]

Maths does take into account wording, the expressions are meant to the represent the extent of placement. King's moves are still in effect.

Either what I said is right, or your wording of the puzzle is wrong. There's no other option in this case.

[Amiel]

Ah, the internet, where everyone is right :smallamused:
Can the numbers not represent limit of placings?

[Zeb The Troll]

Amiel, how do you not get that "any square" does not mean what you are using it to mean?

Delta - thank you for clarifying my position.

EDIT:
Ah, the internet, where everyone is right :smallamused:
Can the numbers not represent limit of placings?No, because the limit expressed does not convey, in any way, that the landing square must be adjacent. The simplest interpretation of your "King's Moves" is an expression of how to count out the thousand squares.

[Amiel]

coughKing'sMovescough, for possibly the upteenth time. Again, as I already said, you need to take the sentence in its entirety, rather than focusing on specifics. Anyone can twist wording to their benefit.

[KuReshtin]

Thank you, KuReshtin! You have definitely interpreted it correctly. Kudos and cookies. :smallsmile:

I have to say, though, that the initial description of the rules as of the original post made it sound as if the angel could move to any square within the 1000x1000 from where it started it's turn, and only after seeing the following discussion did I get to my conclusion that prompted me to start up Excel and make the viaual representation that I did.



Delta, ah, don't forget, the devil can conceivably move to any position on the board. The angel then has to react to move away from the devil, presumably because of disagreements arising from close proximity.

Wait a minute. Hang on. Are you changing the rules again? Do the angel have to stay away from the devil to get away from a 'check' position (if using chess terms), or does it only have to make a move?



Although the emphasis within the text may be a bit ambiguous, it was essentially cut and pasted from a different board verbatim.

A bit ambiguous? A BIT!?! I think that there was only one person in the thread that knew what you were talking about after reading the original post, and that was yourself. :smalltongue:
I believe that the clarification will now provide some further discussion on the problem of the angel.


Edit: ninja'd while typing the above.

Ku - That is most decidedly NOT a "King's Move" under any definition. Thought that is a clarification that would be important in the setup.

By the way, am I the only one who sees the semantics of the setup to not clearly convey what Ku describes?


I agree that it's not a king's move. I merely interpreted the resulting discussion and attempted rules clarifications from Amiel to try and make things make a bit more sense.

I agree that the initial description of the rules as posted in the original post were not clear enough to allow anyone to make the conclusion of how to play the game and it would have been much easier if the wording had been different.

[Delta]

Ah, the internet, where everyone is right :smallamused:

Got nothing to do with the internet, it's math and logic.


The Angel is a "chess piece" that can move to any uneaten square (X,Y) that is at most 1000 king's moves away from its present position (x,y) – in other words, for which |X - x| and |Y - y| are at most 1000.

It's that simple, everything else in the sentence is just clarification, if what you wrote in that sentence is correct, there's only one interpretation.

[The Rose Dragon]

Since I can't see KuReshtin's picture, and therefore cannot comment on his interpretation, I will say that if you can only move as a King, the number 1000, as well as the ability to fly over eaten squares, are essentially misleading.

[hamishspence]

If the devil starts a few million squares away from the angels, and then constructs a few miniwalls (each a few thousand by a few thousand squares) at each of the main compass points (N, S, E, W, NE, SE, SW, SW) then by the time the angel gets near any of them, the devil can simply keep extending the wall, until it meets up

Though I might be underestimating the problem. Maybe it doesn't work that way.

[Delta]

If the devil starts a few million squares away from the angels, and then constructs a few miniwalls (each a few thousand by a few thousand squares) at each of the main compass points (N, S, E, W, NE, SE, SW, SW) then by the time the angel gets near any of them, the devil can simply keep extending the wall, until it meets up

Though I might be underestimating the problem. Maybe it doesn't work that way.

The problem is that with every square away from the Angel's starting point that the Devil begins constructing his "wall", his wall will need to be around 2000 squares larger (if we round graciously), while the Angel needs only a single turn to move that square. It doesn't add up.

[Amiel]

I have to say, though, that the initial description of the rules as of the original post made it sound as if the angel could move to any square within the 1000x1000 from where it started it's turn, and only after seeing the following discussion did I get to my conclusion that prompted me to start up Excel and make the viaual representation that I did.

For clarity, maybe emphasis should have been added, again, it was copied verbatim from its, presumably, original source.


Wait a minute. Hang on. Are you changing the rules again? Do the angel have to stay away from the devil to get away from a 'check' position (if using chess terms), or does it only have to make a move?

Changing rules nothing, I would say 1000 squares is enough proximity :P This is the "check position" as it were.
Just clarifying for folks who are crying foul.


A bit ambiguous? A BIT!?! I think that there was only one person in the thread that knew what you were talking about after reading the original post, and that was yourself. :smalltongue:
I believe that the clarification will now provide some further discussion on the problem of the angel.

Heh, I actually didn't really make the mistake of arriving at a foregone conclusion probably because of some experience at playing chess.
I can't really excuse the fact that this wasn't ambiguous, as it was copied from another source.


Got nothing to do with the internet, it's math and logic.

Jokesinnit?


It's that simple, everything else in the sentence is just clarification, if what you wrote in that sentence is correct, there's only one interpretation.

Puzzles aren't really meant to be just that simple.
How would you denote King's moves in numerical qualifiers?


Since I can't see KuReshtin's picture, and therefore cannot comment on his interpretation, I will say that if you can only move as a King, the number 1000, as well as the ability to fly over eaten squares, are essentially misleading.

How? Explanation?

Move as king; straightforward
1000; limit on both horizontal and vertical axis
Fly; escape option

[The Rose Dragon]

Move as king; straightforward
1000; limit on both horizontal and vertical axis
Fly; escape option

If you can only move as a king, flying over squares is useless, since you will fall down the square at the end of your turn (so to speak). If you can fly over a square over to the square on the other side, you're not moving as a king.

[Delta]

Puzzles aren't really meant to be just that simple.

Yes, well I don't know what your puzzle is meant to say, I can only tell you what it says. If what I bolded in my quote is correct, there's no room for interpretation. If it is not, please correct it.

[Amiel]

If you can only move as a king, flying over squares is useless, since you will fall down the square at the end of your turn (so to speak). If you can fly over a square over to the square on the other side, you're not moving as a king.

I think the flying thing was an additional caveat to increase survivability. The angel should still be moving as a king. But can make use of flying as a lifeline.


Yes, well I don't know what your puzzle is meant to say, I can only tell you what it says. If what I bolded in my quote is correct, there's no room for interpretation. If it is not, please correct it.

It is not my puzzle. Again, how would you denote king's moves in numerical qualifiers?

[KuReshtin]

Since I can't see KuReshtin's picture, and therefore cannot comment on his interpretation, I will say that if you can only move as a King, the number 1000, as well as the ability to fly over eaten squares, are essentially misleading.

The image I punched up is basically just a grid with the angel in the middle and the possible squares it can move to highlighted.
If the square directly adjacent to the angel has not been eaten, the angel can only move to that single square in that direction.
If the square directly adjacent to the angel HAS been eaten, it can still move in the direction of the eaten square and will then land on the next available square in that direction, provided that that square is less than 1000 squares away.
There's still only 8 possible squares that the angel can move to with each move (N, NW, W, SW, S, SE, E, NE) as long as they're within 1000 squares from the angel's starting position of the round.

edit: I believe a major problem with the puzzle as presented is the use of the 'king's move' phrase, as it's not corect.
The person creating the problem would have been much clearer if he/she'd just said that the angel can only move to the nearest available square in any direction.

[Teddy]

I'm currently playing on the rule clarification that KuReshtin provided, since it's apparently the correct one...


Delta, ah, don't forget, the devil can conceivably move to any position on the board. The angel then has to react to move away from the devil, presumably because of disagreements arising from close proximity.

The empasized part wasn't included in the setup, and I have no idea on how it is supposed to work.

If I ignore it for a moment, I'd say that the devil has no chance, because it has to make a 1000 squares wide moat around the board at such distance from the angle that the angel cant make it to the edge and jump over the moat before it's finished. The moat has to be made equally wide around the angel in all directions so that the angle can't just make a sidestep and pass beside the moat, which requires a ridiculous amount of turns, and the devil wouldn't be able to build sufficiently large to trap the angel because while athe blocking of one movement direction from one square takes 1000 turns for the devil, moving to a new one only takes one turn for the angel.

If the rules are that the angel can't close his proximity to the devil on either axis, then the devil can simply move around in a circle and thus trap the angel in the middle while he slowly eats every square in the moat.

[The Rose Dragon]

The image I punched up is basically just a grid with the angel in the middle and the possible squares it can move to highlighted.
If the square directly adjacent to the angel has not been eaten, the angel can only move to that single square in that direction.
If the square directly adjacent to the angel HAS been eaten, it can still move in the direction of the eaten square and will then land on the next available square in that direction, provided that that square is less than 1000 squares away.
There's still only 8 possible squares that the angel can move to with each move (N, NW, W, SW, S, SE, E, NE) as long as they're within 1000 squares from the angel's starting position of the round.

That's not moving as a king. That's a whole new way of moving.

[Delta]

It is not my puzzle.

Then you have your answer. Even if the rest of the wording is ambiguous, you simply can't argue with the math.

The Angel is able to move from his square to any uneaten square in a distance of 1000 squares or less. That fact is quite clear, unless there's an error in your OP.

[Amiel]

To clarify, the angel is trying not to become stranded, which the devil can do by surrounding him by a moat of eaten squares of width at least 1000; feel free to ignore the above if you wish, it was meant to draw comparisons to chess, which the puzzle (not mine) makes use of.

[Amiel]

That's not moving as a king. That's a whole new way of moving.

Refer to posts that address this.


Then you have your answer. Even if the rest of the wording is ambiguous, you simply can't argue with the math.

The Angel is able to move from his square to any uneaten square in a distance of 1000 squares or less. That fact is quite clear, unless there's an error in your OP.

How would you numerically address King's moves?

[KuReshtin]

That's not moving as a king. That's a whole new way of moving.

Since my edit was ninja'd again:

edit: I believe a major problem with the puzzle as presented is the use of the 'king's move' phrase, as it's not correct.
The person creating the problem would have been much clearer if he/she'd just said that the angel can only move to 'the nearest available square in any direction'.

[Delta]

How would you numerically address King's moves?

A King's move is a move from a square (X,Y) to another square (x,y) (with (x,y) not equal to (X,Y) if "another square" isn't precise enough for you) so that both |X-x| and |Y-y| are equal to or less than 1.

[The Rose Dragon]

As the puzzle is written, ignoring the fact that "king's move" is essentially a very poor description for what you claim the angel is supposed to do, the angel moves far faster than the devil can eat squares.

KuReshtin's explanation is not how the puzzle is written, as he admitted he was only able to figure it out after an entire page of you trying to explain how the angel moves.

I understand it's not your fault the explanation is incredibly poor, but it's all we had to go on before KuReshtin came around to clarify.

[Amiel]

Since my edit was ninja'd again:

edit: I believe a major problem with the puzzle as presented is the use of the 'king's move' phrase, as it's not correct.
The person creating the problem would have been much clearer if he/she'd just said that the angel can only move to 'the nearest available square in any direction'.

I think it only has limited correctness, insofar as specifics are concerned. The additional caveat presumably offsets its uniqueness by allowing only for king's moves. I don't know why it was worded that way, but reading it as a full paragraph, it does make a little sense.


A King's move is a move from a square (X,Y) to another square (x,y) (with (x,y) not equal to (X,Y) if "another square" isn't precise enough for you) so that both |X-x| and |Y-y| are equal to or less than 1.

Thanks for that. For clarification, can you use |X - x| and |Y - y| are at most 1000 to denote limit, or in this case would it mean moves?

[Amiel]

I think the king's moves was really meant to represent its move ability, yes, it was under- and un-emphasised and an additional caveat was introduced; a shame, though understandable, as most depictions of angels have wings.


Anyway, enjoy the puzzle (it might be too annoying to enjoy) :smalltongue:
I'm off to study for exams

[Superglucose]

Thanks for that. For clarification, can you use |X - x| and |Y - y| are at most 1000 to denote limit, or in this case would it mean moves?
No. The limit is 1.

Now here, I think, is a better description of how the angel moves:

The angel may move one square in any direction. If the square he has moved into was previously eaten, the angel continues traveling in that direction until it reaches a legal square, unless |X-x| or |Y-y| > 1000, which makes the movement illegal. The devil wins when the angel no longer has legal moves.

Answer? I believe the angel wins. Why? Well it's pretty simple from a logical standpoint but my math for these purposes is terrible... the only way for the devil to win is to create a box first and must make this box 1000 squares thick in order to succeed... and must make this box before the angel travels to the edge of the box.

This is impossible no matter how big the box is.

The number of squares the angel has to travel to reach the edge of a box of length "y" will be exactly "y" turns. However, in order to make the impenetrable wall, the devil will need "y*1000" turns. The devil cannot complete a wall before the angel arrives at the wall by definition.

If the devil can manipulate the angel by moving next to it; however, and force the angel to move from a "check" position, then the devil will win. If I recall correctly it is possible to constrain a king with nothing but a queen to a limited area of a chessboard (I don't know enough about chess to confirm this). If that is true, then the devil must constantly herd the angel while building a large box... from the outside in. It is VERY IMPORTANT that it is from the outside in.

[The Rose Dragon]

If I recall correctly it is possible to constrain a king with nothing but a queen to a limited area of a chessboard (I don't know enough about chess to confirm this).

That is not considered a win in chess, though. That is specifically called a stalemate, and is considered a draw.

[Thufir]

That is not considered a win in chess, though. That is specifically called a stalemate, and is considered a draw.

No, he said 'A limited area', not 'One square'.
However, this doesn't work so well in this case, as the board is infinite, so the king is not constrained by the edge of it.
However, the devil can constrain the king to an area by moving to whichever edge of the area the Angel is about to cross when it's about to cross it. Does the devil have to move to a square to eat it? If not, and if the Angel has to avoid check from the Devil, and if KuReshtin's interpretation of the Angel move is the correct one, then the Devil wins easily (Though tediously).

[Superglucose]

That is not considered a win in chess, though. That is specifically called a stalemate, and is considered a draw.
It's irrelevant as to whether or not it is considered a win in chess. The only goal is to prevent the angel from escaping an area that is smaller than 1000x1000 for eight million turns.

Well, slightly less because you could make a more roughly circular box than a square, but it's 4:30 am and I don't feel like straining my brain that much. And since we're still talking about constraining the king for millions of turns it probably doesn't matter if you take one million or ten million.

EDIT: Now that I read thufir, yes. If the angel must not move into check then the devil wins easily. Every time. There is no way for the angel to win unless the devil must be at a square to eat it.

If the devil must be at a square to eat it or the angel can move into check then the angel wins.

EDIT the Second:
The solution holds true no matter how far the angel can "fly" so long as that distance is finite.

[Eldan]

I think I get it now.

Well, let's look at it mathematically.

The devil tries to make a moat around the angel, X squares away.
For now, I'm assuming that X is sufficiently large that the moat is approximately circular.
That leaves an area of (Pi)*X^2 free around the angel.
To make the moat 1000 thick, the devil has to eat every square between X and (X+1000) squares away. That should be approximately (Pi)*(X+1000)^2-(Pi)*(X)^2 squares, unless I'm mistaken (it's been a few years since my last math class, and I was never very good.)

(Pi)*(X+1000)^2-(Pi)*(X)^2=(Pi)*((X+1000)^2-X^2)=(Pi)*(2X+1000000) squares.

So the devil needs Pi*(2X+1000000) turns to eat a circular moat, with X being the inner radius.

The angel, instead, only needs X turns to reach the moat, and one more turn to fly across it.

However, and this makes things more complicated: as soon as the angel approaches a section of the moat, the devil can start eating only close to the point where the angel would approach the moat, thereby making the time needed to eat it clear much shorter.

Now idea how to incorporate that.

[Neon Knight]

No one has said it yet? Really?

A strange game. The only winning move....

:smallcool:

...is not to play.

Not that that is the actual solution to the puzzle, or that the angel can't win. But after that little hurricane of confusion, it became apparent to me that trying to solve this one might not be time well spent.

[KuReshtin]

The devil will always win.

As long as the devil starts far enough away from the angel and builds a wall/moat at least 1000 squares deep, he will make the 'infinite' board very finite, and then it's just a matter of systematically eating the remaining squares inside the box until they are all gone.

it needs to be an awfully big square to begin with, so it'll take a ridiculous amount of time to complete it, but the devil will always win.

[Tirian]

Actually, even that changes nothing. Even if the angel is only able to move one square at a time, I do not think the devil would be able to catch him.

That turns out to not be true. In fact, if you play the game with the king in the middle of a 35x35 board and award him the win if he can reach one of the edges, then the devil can manage to box the king in. If this is the sort of thing that interests you, you should track down a copy of Volume 3 of the second edition of Winning Ways by Conway, Berlekamp, and Guy (or Volume 2 of the original edition) which describes the strategy for an even harder problem, plus a lot of other interesting games as well.

However, John Conway could not (in 1982) prove that a knight could survive forever, as much as he felt that it should be the case. He went so far as to say that he could not prove that a 1000-angel, as defined in this puzzle, would survive forever. As much power as it seemed like, if you defined a naive angel strategy, then he could describe a square-eater strategy that would build a very large three-sided moat, drive the angel into it, and then close it off.

So the puzzle went unsolved until 2006, when a fresh wave of publicity brought forth several independent proofs that even a 2-angel could win the game. As you might imagine of any puzzle that would confound John Conway for 25 years, these proofs are not at all simple. You can find out more starting from the wiki page (http://en.wikipedia.org/wiki/Angel_problem).

[Astrella]

Haven't really put any thought in it yet, but:

The Angel moves at the same rate as the Devil. If it would take the Angel X steps to reach the edge of the "prison" the Devil is making, the Devil would already need (even if we pick a circle) Pi*2X steps to make a full circle of one square wide. (Of course you can't make a circle, but another figure would mean even more squares.)

Of course the Devil can pick the squares he intends to eat first depending on what direction the Angel is moving.

[Eldan]

Yeah. I even calculated how many you need to eat for a full moat a thousand wide. Answer: a lot.

Though I'm not sure if the devil can win if he only eats the squares the angel is moving towards.

That's the kind of thing a computer simulation would be nice for.

[Delta]

That turns out to not be true.

Yes, you're right there, I spent some time thinking about it and noticed that it would be possible to trap a normal king, my first thought was wrong because I only thought about the size of the whole "wall" the devil had to create.

But for the problem as it is, it seems my solution holds true, the Angel will win.

[Delta]

The devil will always win.

As long as the devil starts far enough away from the angel and builds a wall/moat at least 1000 squares deep, he will make the 'infinite' board very finite, and then it's just a matter of systematically eating the remaining squares inside the box until they are all gone.

it needs to be an awfully big square to begin with, so it'll take a ridiculous amount of time to complete it, but the devil will always win.

No, you're absolutely wrong there, I fear.

Because, the further away from the starting square the Devil starts to build his wall, the larger it will have to be, so the Devil will need a lot more turns to build the wall than the Angel will to get there.

You have to be a lot more tricky if you want to trap the Angel (the link Tirian provided contains more information on this)

[Reinboom]

Another large issue with the earlier wording of this game is that, it is not made very clear that the angel flies over the empty squares as a free space. In the event that they could fly over them, it is then not made clear that they could not do the same with a normal space.

This also failed to acknowledge the fact that the devil could not empty the square the angel was on.

There also comes the problem that the game given by the OP is not the same game given by the actual referred game (based on Ku's image, of course). In that, the OP is referring to (in the name of the original game) an angel with 1000 move sets. Which would mean that Zeb's first interpretation was correct. The real game is a much more complex problem that I will leave the linked Wiki page to solve.

In the modified game by the OP, as highlighted by Ku, it is seemingly impossible for the Devil to win. Since any stated square by the Devil is seemingly measurable compared to the Angel, any sufficiently large number would give a good way to showcase this. If the Devil starts at a non-measurable (that is, infinite) number of squares and tries to build an infinite moat... the angel has already won. That would take an infinite amount of time to even reach the moat, satisfying the win condition.

So instead, let's refer to say... 1,000,000 squares off (1,000^2).
When the Devil consumes the square and the angel moves, the first move should be away from the direction (and always opting for a corner move) from the Devil. From this point, for the quadrant of the board that matters, the Angel will always get the "proactive" move. The Devil always getting the "reactive" move.

After the first quadrant has been established, it would be a losing strategy for the Angel to not push towards the devil... simply because the devil can not hold the Angel if the Angel does so. Let's say that the chosen "quadrant" was up-right.

See, whenever the Angel moves up and right by 1, the devil can only consume 1 square. In order to have a moat in front of the angel, the devil need to honor a 1000 square deep direction in both straight (non diagonal) directions that the angel just opened.
In short, if an angel moves from position (0,0) to position (1,1), the devil needs to ensure (working at 1,000,000 squares from the base) that (1000001,1) through (1001000,1) and (1,1000001) through (1,1001000) are consumed. However, if the angel moves diagonally again.... suddenly the devil needs to ensure that (1000001,2) through (1001000,2) and (2,1000001) through (2,1001000) are consumed.
It will take 1,000,000 moves in order for this to end. It ends by the angel reaching square (1000000,1000000). At which point, the Devil could only have 1 square deep at that point. If the devil targeted the diagonal by filling it deep instead (that is, the area (1000001,1000001) through (1001000,1001000), at 1 million squares... well, the angel can just move 1 square straight (non-diagonal) at any given time during that movement in order to force the devil to include 1,000 more square within this problem.

[Fifty-Eyed Fred]

I think Amiel is the Devil here, because his devilish wording has made fools out of us all.

[Jokasti]

His wording is incorrect on another matter: it should be titled "A Game with an Angel and a Devil" unless there is something he's not telling us.
The Angel should take the fourth option and commit suicide. They don't have to play silly games, and they deny the Devil.

[Gryffon]

I believe you may be interpreting it wrong Amiel.

From Wikipedia:


The angel problem is a question in game theory proposed by John Horton Conway. The game is commonly referred to as the Angels and Devils game. The game is played by two players called the angel and the devil. It is played on an infinite chessboard (or equivalently the points of a 2D lattice). The angel has a power k (a natural number 1 or higher), specified before the games starts. The board starts empty with the angel at the origin. On each turn, the angel jumps to a different empty square which could be reached by at most k moves of a chess king, i.e. the distance from the starting square is at most k in the infinity norm. The devil, on his turn, may add a block on any single square not containing the angel. The angel may leap over blocked squares, but cannot land on them. The devil wins if the angel is unable to move. The angel wins by surviving indefinitely.

In this case, k would be 1000. The angel can move to any uneaten square within 1000. I believe that you're mixing two versions of the puzzle.



The angel problem is: can an angel with high enough power win?


Answers and proofs are available for those who do not wish to ponder themselves under Angel problem on Wikipedia.