Angel problem

Uses your system voice; voice and rate in settings.

Snapshot

≈ 7 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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. 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 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 chess king, i.e. the distance from the starting square is at most k in the 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.…

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. 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 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 chess king, i.e. the distance from the starting square is at most k in the 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" (that is, 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.

Of course, for any infinite game, if player 2 does not have a winning strategy, then player 1 can always pick a move that leads to a position where player 2 does not have a winning strategy, but in some games, simply playing forever does not 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 proof that the devil can win regardless 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. Bowditch proved that a 4-angel (that is, an angel with power k = 4) can win, and Máthé and Kloster gave proofs that a 2-angel can win. We start out by drawing a vertical line immediately to the left of the angel's starting position, down to y = -\infty and up to y = \infty .

This line represents the path the angel will take, which will be updated after each of the devil's moves, and partitions the board's squares into a "left set" and a "right set". Once a square becomes part of the left set, it will remain so for the remainder of the game, and the angel will not make any future moves to any of these squares. Every time the devil blocks off a new square, we search over all possible modifications to the path such that we move one or more squares in the right set which the devil has blocked off into the left set.

We will only do this if the path increases in length by no more than twice the number of blocked squares moved into the left set. Of such qualifying paths, we choose one that moves the greatest number of blocked off squares into the left set. The angel then makes two steps along this path, keeping the path to its left when moving in the forward direction (so if the devil were not blocking off squares, the angel would travel north indefinitely).

When going clockwise around a corner, the angel will not move for one step, because the two segments touching the corner have the same square to their right. 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.

(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, so the path is a winning path even in the original game.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1368398879 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

5 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.