Editing Angel problem (section)

{{Short description|Question in combinatorial game theory}}
[[Image:Angel problem.svg|thumb|200px|The blue dotted region shows where an angel of power 3 could reach]]

The '''angel problem''' is a question in [[combinatorial game theory]] proposed by [[John Horton Conway]]. The game is commonly referred to as the '''angels and devils''' game.<ref name="conway1996">John H. Conway, ''[https://library.slmath.org/books/Book29/files/conway.pdf The angel problem]'', in: Richard Nowakowski (editor) ''Games of No Chance'', volume 29 of [[MSRI Publications]], pages 3&ndash;12, 1996.</ref> The game is played by two [[player (game)|players]] called [[demon (thought experiment)|the angel and the devil]]. It is played on an infinite [[chessboard]] (or equivalently the points of a 2D [[lattice (group)|lattice]]). The angel has a power ''k'' (a [[natural number]] 1 or higher), specified before the game starts. The board starts empty with the angel in one square. On each turn, the angel jumps to a different empty square which could be reached by at most ''k'' moves of a [[King (chess)|chess king]], i.e. the distance from the starting square is at most ''k'' in the [[Chebyshev distance|infinity norm]]. The devil, on its 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.

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 it 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 it 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 [[topological space|topology]] on the set of all plays), and it is known that such games are [[Axiom of determinacy#Types of game that are determined|determined]]. Of course, for any infinite game, if player 2 doesn't have a winning strategy, player 1 can always pick a move that leads to a position where player 2 doesn't have a winning strategy, but in some games, simply playing forever doesn't confer a win to player 1, so undetermined games may exist.

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 [[mathematical proof|proof]] that the devil can win irrespective of the angel's power). Progress was made first in higher dimensions. In late 2006, the original problem was solved when independent proofs appeared, showing that an angel can win. [[Brian Bowditch|Bowditch]] proved that a 4-angel (that is, an angel with power ''k''&thinsp;=&thinsp;4) can win<ref name="B">[[Brian H. Bowditch]], "The angel game in the plane", ''[[Combin. Probab. Comput.]]'' 16(3):345-362, 2007.</ref> and Máthé<ref name="M">András Máthé, "The angel of power 2 wins", ''Combin. Probab. Comput.'' 16(3):363-374, 2007</ref> and Kloster<ref name="K">O. Kloster, ''A solution to the angel problem.'' [[Theoretical Computer Science (journal)|Theoretical Computer Science]], vol. 389 (2007), no. 1-2, pp. 152&ndash;161</ref> gave proofs that a 2-angel can win.