Angel problem

Angel problem

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 moves like a chess king, but depending on each game may have a different power k (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 k squares away, that is, a square which could be reached by at most k moves of a chess king. (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 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?

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.

Conway 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 was made first in higher dimensions, with some beautiful proofs. In late 2006, the original problem was solved when independent proofs appeared, showing that an angel can win.

History

The problem was first published in the 1982 book "Winning Ways" by Berlekamp, Conway, and Guy,under the name "the angel and the square-eater."In two dimensions, some early partial results included:

* If the angel has power 1, the devil has a winning strategy (Conway, 1982). (According to Conway, this result is actually due to Berlekamp.)
* If the angel never decreases its y coordinate, then the devil has a winning strategy (Conway, 1982).
* If the angel always increases its distance from the origin, then the devil has a winning strategy (Conway, 1996).

In three dimensions, it was shown that:

* If the angel always increases its y coordinate, and the devil can only play in one plane, then the angel has a winning strategy.
* If the angel always increases its y coordinate, and the devil can only play in two planes, then the angel has a winning strategy.
* The angel has a winning strategy if she has power 13 or more.
* If we have an infinite number of devils each playing at distances d_1 < d_2 < d_3 < cdots then the angel can still win if she is of high enough power. (By "playing at distance d" we mean the devil is not allowed to play within this distance of the origin).

Finally, in 2006, not long after the publication ofPeter Winkler's book "Mathematical Puzzles", which helped publicize the angel problem,there emerged four independent and almost simultaneous proofsthat the angel has a winning strategy in two dimensions.Brian Bowditch's proof [http://www.maths.soton.ac.uk/staff/Bowditch/papers/bhb-angel.pdf] works for the 4-angel, while Oddvar Kloster's proof [http://home.broadpark.no/~oddvark/angel/Angel.pdf] and András Máthé's proof [http://amathe.dyn.elte.hu/letolt.php?angel-mathe.pdf] work for the 2-angel.
Péter Gács's proof [http://www.cs.bu.edu/~gacs/papers/angel.pdf] , works only for a much larger constant. The proofs by Bowditch and Máthé have been published in "Combinatorics, Probability and Computing" (edited by Béla Bollobás and Imre Leader).

Further unsolved questions

In 3D:
*Given that the angel always increases its y coordinate, and that the devil is limited to 3 planes, it is unknown whether the devil has a winning strategy.

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, the guardian does so 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 strategy can be proven to work 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 substantially similar proof has been published by Martin Kutz.

Sketch of Máthé's proof

Máthé introduces the "nice devil," which never destroys a square thatthe angel could have chosen to occupy on an earlier turn. When the angel plays against the nice devil it concedes defeat if the devil manages to confine it to a finite bounded region of the board (otherwise the angel could just hop back and forth between two squares and never lose!).Máthé's proof breaks into two parts: (1) he shows that if the angel wins against the nice devil,then the angel wins against the real devil;(2) he gives an explicit winning strategy for the angel against the nice devil.

Roughly speaking, in part (2), the angel wins against the nice devil bypretending that the entire left half-plane is destroyed(in addition to any squares actually destroyed by the nice devil),and treating destroyed squares as the walls of a maze,which it then skirts by means of a "hand-on-the-wall" technique.That is, the angel keeps its left hand on the wall of the mazeand runs alongside the wall.One then proves that a nice devil cannot trap an angel that adopts this strategy.

The proof of part (1) is by contradiction, and hence Máthé's proof does not immediatelyyield an explicit winning strategy against the real devil.However, Máthé remarks that his proof could in principle be adapted to give such an explicit strategy.

Sketch of Bowditch's proof

Bowditch defines a variant (game 2) of the original game with the following rule changes:

# The angel can return to any square it has already been to, even if the devil subsequently tried to block it.
# A k-devil must visit a square k times before it is blocked.
# The angel moves either up, down, left or right by one square (a duke move).
# To win, the angel must trace out a circuitous path (defined below).

A circuitous path is a path pi = cup^{infty}_{i=1} (sigma_i cup gamma_i) where sigma = cup^{infty}_{i=1} sigma_i is a semi-infinite arc (a non self-intersecting path with a starting point but no ending point) and {gamma_i} are pairwise disjoint loops with the following property:

* forall i: |gamma_i|leq i where |gamma_i| is the length of the ith loop.

(Note that to be well defined gamma_i must begin and end at the end point of sigma_i and sigma_i must end at the starting point of sigma_{i+1})

Bowditch considers a variant (game 1) of the game with the changes 2 and 3 with a 5 devil. He then shows that a winning strategy in this game will yield a winning strategy in our original game for a 4-angel. He then goes on to show that an angel playing a 5 devil (game 2) can achieve a win using a fairly simple algorithm.

Bowditch claims that a 4-angel can win the original version of the game by imagining a phantom angel playing a 5 devil in the game 2.

The angel follows the path the phantom would take but avoiding the loops. Hence as the path sigma is a semi-infinite arc the angel does not return to any square it has previously been to and so the path is a winning path even in the original game.

See also

* The homicidal chauffeur problem, another mathematical game which pits a powerful and maneuverable adversary against a highly resourceful but less powerful foe

References

* Elwyn R. Berlekamp, John H. Conway, and Richard K. Guy, "Winning Ways for your mathematical plays, volume 2: Games in Particular", Academic Press, 1982.
* Brian H. Bowditch, The angel game in the plane, "Combin. Probab. Comput." 16(3):345-362, 2007.
* John H. Conway, The angel problem, in: Richard Nowakowski (editor) "Games of No Chance", volume 29 of MSRI Publications, pages 3&ndash;12, 1996.
* Martin Kutz, Conway's Angel in three dimensions, "Theoret. Comp. Sci." 349(3):443–451, 2005.
* Martin Kutz, The Angel Problem, Positional Games, and Digraph Roots, [http://www.diss.fu-berlin.de/2004/250/ PhD Thesis] FU Berlin, 2004
* András Máthé, The angel of power 2 wins, "Combin. Probab. Comput." 16(3):363-374, 2007.

External links

* [http://www.msri.org/publications/books/Book29/files/conway.pdf The Angel problem by John H Conway]
* [http://home.broadpark.no/~oddvark/angel/index.html Kloster's Angel Problem site]


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • Angel (disambiguation) — An angel is a supernatural entity in many religions.Angel may also refer to:In Literature* The Angel , a Hans Christian Andersen short story * Angel (novel), a 1957 novel * , a book about angels * Angel ( Meg series), the female megalodon of… …   Wikipedia

  • Angel: After the Fall — Cover of Angel: After the Fall #1. Art by Tony Harris. Publication information Publisher IDW Publishing …   Wikipedia

  • Angel Beats! — Anime Fernsehserie Produktionsland …   Deutsch Wikipedia

  • Angel Sanctuary — Originaltitel 天使禁猟区 Transkription Tenshi Kinryōku …   Deutsch Wikipedia

  • Angel sanctuary — (jap. 天使禁猟区 tenshi kinryōku) ist eine abgeschlossene Manga Serie der japanischen Zeichnerin Kaori Yuki, die auch als Anime verfilmt wurde. Figuren und Schauplätze entstammen der christlichen, jüdischen und vor allem kabbalistischen Mythologie,… …   Deutsch Wikipedia

  • Angel (Judaism) — For other uses, see Malach. Main article: angel In Judaism an angel (Hebrew: מַלְאָךְ‎ malakh, plural malakhim) is a messenger of God, an angelic envoy or an angel in general who appears throughout the Hebrew Bible, Rabbinic literature, and… …   Wikipedia

  • Angel (2007 film) — Infobox Film name = Angel caption = Angel Film Poster director = François Ozon writer = François Ozon, Martin Crimp(dialogue), Elizabeth Taylor (novel) starring = Romola Garai, Sam Neill, Charlotte Rampling, Lucy Russell, Michael Fassbender… …   Wikipedia

  • Angel Stadium of Anaheim — Infobox Baseball Stadium stadium name = Angel Stadium of Anaheim nickname = The Big A location = 2000 Gene Autry Way Anaheim, California 92806 broke ground = August 31, 1964 opened = April 19, 1966 closed = demolished = owner = The City of… …   Wikipedia

  • angel dust — AND angel hair; dust of angels n. the common name for phency clidine (PCP). (Originally drugs.) □ Angel dust is getting to be quite a problem in this town. □ I thought that angel hair and stuff like that was a problem of the sixties …   Dictionary of American slang and colloquial expressions

  • angel and demon — ▪ religion Introduction demon also spelled  daemon   respectively, any benevolent or malevolent spiritual being that mediates between the transcendent and temporal realms.       Throughout the history of religions (myth), varying kinds and… …   Universalium

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”