| Angel Problem |
Article Index for Angel |
Website Links For Angel |
Information AboutAngel Problem |
| CATEGORIES ABOUT ANGEL PROBLEM | |
| combinatorial game theory | |
| unsolved problems in mathematics | |
|
The Angel problem is a question in Game Theory proposed by John 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 moves like a chess king, but depending on each game may have a different power (a natural number 1 or greater). The board starts empty with the angel at the origin. On each turn, the angel jumps to a different empty square at most squares away, that is, a square which could be reached by at most moves of a chess king. (The distance from the starting square is at most in the Infinity Norm .) The devil, on his turn, may add a block on any 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. ''The Angel problem is'': Can an angel with high enough power win? The answer is unknown, and Conway has offered a reward for a general solution to this problem ($100 for a winning strategy for an angel of sufficiently high power, and $1000 for a proof that the devil can win irrespective of the angel's power). Progress, however, has been made in higher dimensions, with some Beautiful Proof s. There must exist a winning strategy for one of the players. If the devil can force a win then he can do so in a finite number of moves. If the devil cannot force a win then there is always an action that the angel can take to avoid losing and a winning strategy for her is always to pick such a move. More abstractly, the "pay-off set" (i.e., the set of all plays in which the angel wins) is a closed set (in the natural Topology on the set of all plays), and it is known that such games are Determined . PROGRESS MADE TOWARDS SOLVING THIS PROBLEM In two dimensions, it is known that:
In three dimensions, it is known that:
FURTHER UNSOLVED QUESTIONS In 3D:
SKETCH PROOF THAT IN 3D A HIGH POWERED ANGEL HAS A WINNING STRATEGY The proof of this makes use of guardians. For each cube of any size there is a guardian that watches over that cube. The guardians decide at each move whether the cube they're watching over is unsafe, safe or almost safe. This decision is based purely on the density of blocked points in that cube and the size of that cube. If the angel is given no orders then it just moves up. If some cubes that the angel is living in cease to be safe then the guardian of the biggest of these cubes is instructed to arrange for the angel to leave through one of the borders of that cube. If a guardian is instructed to escort the angel out of her cube to a particular face this guardian does this by plotting a path of subcubes that are all safe. The guardians in these cubes are then instructed to escort the angel through their respective subcubes. The proof works because the time it takes the devil to convert a safe cube in the angel's path to an unsafe cube is longer than the time it takes the angel to get to that cube. The definitions of safe and almost safe need to be chosen to ensure this works. Note: The angel's path in a given subcube is not determined until the angel arrives at that cube. Even then the path is only determined roughly. This ensures the devil cannot just choose a place on the path sufficiently far along it and block it. This proof is due to Imre Leader and Béla Bollobás . A proof that is substantially similar has been published by Martin Kutz . EXTERNAL LINKS REFERENCES
|
|
|