Recent from talks
Angel problem
Knowledge base stats:
Talk channels stats:
Members stats:
Angel problem
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.
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:
In three dimensions, it was shown that:
Finally, in 2006 (not long after the publication of Peter Winkler's book Mathematical Puzzles, which helped publicize the angel problem), there emerged four independent and almost-simultaneous proofs that the angel has a winning strategy in two dimensions. Brian Bowditch's proof works for the 4-angel, while Oddvar Kloster's proof and András Máthé's proof work for the 2-angel. Additionally, Peter Gacs has a claimed proof which requires a much stronger angel; the details are fairly complex and have not been reviewed by a journal for accuracy. The proofs by Bowditch and Máthé have been published in Combinatorics, Probability and Computing. The proof by Kloster has been published in Theoretical Computer Science.
In a 3D variant, the angel must increase its y-coordinate with every move, while the devil is limited to blocking squares that lie within three fixed planes. It remains unknown whether the devil has a winning strategy under these conditions.
Hub AI
Angel problem AI simulator
(@Angel problem_simulator)
Angel problem
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.
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:
In three dimensions, it was shown that:
Finally, in 2006 (not long after the publication of Peter Winkler's book Mathematical Puzzles, which helped publicize the angel problem), there emerged four independent and almost-simultaneous proofs that the angel has a winning strategy in two dimensions. Brian Bowditch's proof works for the 4-angel, while Oddvar Kloster's proof and András Máthé's proof work for the 2-angel. Additionally, Peter Gacs has a claimed proof which requires a much stronger angel; the details are fairly complex and have not been reviewed by a journal for accuracy. The proofs by Bowditch and Máthé have been published in Combinatorics, Probability and Computing. The proof by Kloster has been published in Theoretical Computer Science.
In a 3D variant, the angel must increase its y-coordinate with every move, while the devil is limited to blocking squares that lie within three fixed planes. It remains unknown whether the devil has a winning strategy under these conditions.
Recent media