| |
| Author |
Message |
|
| Auriea |
 Posted: Sat Nov 29, 2003 8:46 pm |
 |
|
Site Administrator
Joined: 07 Jun 2002
Posts: 454
Location: at your fingertips
|
Games of No Chance
MSRI Publications
Volume 29, 1996
The Angel Problem
http://www.msri.org/publications/books/Book29/files/conway.pdf
JOHN H. CONWAY
Abstract. Can the Devil, who removes one square per move from an infinite chessboard, strand the Angel, who can jump up to 1000 squares per move? It seems unlikely, but the answer is unknown. Andreas Blass and I have proved that the Devil can strand an Angel who's handicapped in one of several ways. I end with a challenge for the solution the general problem.
1. Introduction
The Angel and the 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 whatsoever; this square is then 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.
What we have described is more precisely called an Angel of power 1000. The Angel Problem is this:
Determine whether an Angel of some power can defeat the Devil.
Berlekamp showed that the Devil can beat an Angel of power one (a chess King) on any board of size at least 32 x33. However, it seems that it is impossible for the Devil to beat a Knight, and that would imply that an Angel of power two (which is considerably stronger than a Knight) will win. But can you prove it? |
|
|
| Back to top |
  
|
| cyberdigitus |
| Posted: Sun Nov 30, 2003 9:09 pm |
|
|
Joined: 24 Nov 2003
Posts: 18
Location: Belgium
|
i might be stupidly wrong, but the answer seems painfully obvious to me, for any power (n) of angel.
the devil just has to take a piece away from 'the borders of infinity' at every turn. thus from positive infinity-1, all the way up to n-1, and negative infinity +1, all the way up to -(n-1); in both x and y.
it will take infinite moves, but theoretically it is possible this way, and he's a devil after all. if time (number of moves) comes into the equation, then i guess it is unknown if it is posiible and therefore assumed impossible. |
|
|
| Back to top |
|
| cyberdigitus |
| Posted: Sun Nov 30, 2003 9:20 pm |
|
|
|
Joined: 24 Nov 2003
Posts: 18
Location: Belgium
|
Cool!
just flipped quickly through the pdf, seems i have just earned 1000$... |
|
|
| Back to top |
|
| cyberdigitus |
| Posted: Sun Nov 30, 2003 9:25 pm |
|
|
|
Joined: 24 Nov 2003
Posts: 18
Location: Belgium
|
thinking further on this, i guess with the first thing 'solved' i guess the other question, 'can any sufficiently powered angle win for the devil, i guess there are two answers, one of wich might be true:
an angel of power infinite+1, thus able to move beyond what the devil takes away, but then he would be further then the game board, wich might not be allowed, and you could also argue the devil can take that piece away too.
then it would be an angle of power 0, thus always occupying the same tile, while still a valid 'move', assuming the devil can't take away the piece currently occupied by the angel. Hmm another 100$? |
|
|
| Back to top |
|
| Jonny Dark |
| Posted: Sat Feb 12, 2005 10:39 pm |
|
|
Joined: 02 Feb 2005
Posts: 18
Location: Toronto
|
The only real thing i comprehend about infinity is how fully i can't comprehend it. For me, infinity is a railroad track. it just goes on and on onto forever, where my eyes can't decipher the difference.  |
|
|
| Back to top |
 
|
| seve7 |
| Posted: Tue Apr 19, 2005 3:08 am |
|
|
|
Joined: 19 Apr 2005
Posts: 4
|
cyberdigitus wrote: i guess there are two answers, one of wich might be true:
an angel of power infinite+1, thus able to move beyond what the devil takes away, but then he would be further then the game board, wich might not be allowed, and you could also argue the devil can take that piece away too.
then it would be an angle of power 0, thus always occupying the same tile, while still a valid 'move', assuming the devil can't take away the piece currently occupied by the angel. Hmm another 100$?
I don't mean to detur you from the problem, but I think something less (numerous) is required for your devil solution. It might be easier to get a feel for why by looking at your angel solutions.
Sadly neither of these work at all, for Conway's form of the problem (he is the one offering a token reward for a proof, so I imagine he'll require someone to solve his formation of the problem). The first instance says "infinity+1", which is equal to infinity. But it is already given that an angel of infinite power can escape, the problem is to find a finite power for which an angel can win. It's easy to create any number of strategies with an infinite angel, here's one I prefer (because it reminds me of the 'soccer' game with three coins):
The first move, the angel simply moves to any near square. After the devil's move, the angel again moves to any near square. The angel now selects a direction, D. From here on. after the devil's move, the angel takes moves in the D direction a number of squares equal to the angel's distance to the farthest divet (devil's move) from the angel * the distance between the two farthest divets. The devil cannot even put a divet next to where the angel will next move, after her first D move!
The second instance does not leave the angel with a legal move, so the game cannot start. This is because the angel must move to a different square.
Your devil's strategy suffers from the same problem when taken too literally. A point at infinity-1 is strictly at infinity. This is not a cyclic field (like a sphere divided up into sections like the squares of this plane) so there is no finite point at infinity. By the way, if that wasn't an issue (on the plane), you wouldn't have to distinguish for negative and positive, nor for x and y. By simply counting backwards from infinity you would populate all four quadrants of the board.
If you look at the problem from a different perspective, for the devil to defeat some k-powered angel there is a bounds within which the angel cannot escape: a 1-powered angel cannot escape a 32x33 board if the devil plays well. Suppose the devil can best the k-angel: there exists some bounds beyond which that angel cannot escape (otherwise the devil's strategy takes an infinite number of moves and so the angel has won).
If you look at the 32x33 solution, simplified, it carves out a cross shape from a rectangle of the plane, just at the corners -- then fills the cardinal border the angel approaches. The devil can always place three consecutive squares above the point the angel attempts to escape, and so can bound the angel in this direction. Continuing this process for each of the four quadrants the angel visits, the devil eventually completes a moat around the 32x33 section.
Assuming both players maximizes their play, the point where all four cardinal borders has been visited has an interesting shape to it. It has gaps at all four borders (where the angel abandoned her strive in that direction), and is more dense of divets at the corner nearest the angel (the devil maximizes his play by placing divets near the angel whenever he has a spare move, after the borders have all been sufficiently populated).
I think that if you apply a good blur to an image of the board at this state, and you'll see a haze that looks somewhat like a polar inversion of a (slightly noisy) horizontal gradient, stretched to the same rectangle as the original image. That's a pretty picture, because it (very, very weakly) implies that the devil follows a similar pattern to the one you discribe, but in a way that manages to bound the infinity of the playing field to, for this angel, 32x33. (hobbists/mathletes: Think about the "point at infinity" for a Riemann Sphere, how this transcribes directly to a plane.) For a k-power angel, the same transposition f(k) provides the new outer bounds: the only things that change are the shape of the boundary the devil creates that for a 1-angel is three squares in a line, and the shape of the corners to start with. |
|
|
| Back to top |
|
|
|
All times are GMT + 2 Hours
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
|
|
