The angel problem is a question in

combinatorial game theory Combinatorial game theory is a branch of mathematics and theoretical computer science that typically studies sequential games with perfect information. Study has been largely confined to two-player games that have a ''position'' that the players ...

proposed by

John Horton Conway John Horton Conway (26 December 1937 – 11 April 2020) was an English mathematician active in the theory of finite groups, knot theory, number theory, combinatorial game theory and coding theory. He also made contributions to many branches ...

. The game is commonly referred to as the Angels and Devils game.John H. Conway,
The angel problem
', in: Richard Nowakowski (editor) ''Games of No Chance'', volume 29 of MSRI Publications, pages 3–12, 1996. The game is played by two players called the angel and the devil. It is played on an infinite

chessboard A chessboard is a used to play chess. It consists of 64 squares, 8 rows by 8 columns, on which the chess pieces are placed. It is square in shape and uses two colours of squares, one light and one dark, in a chequered pattern. During play, the bo ...

(or equivalently the points of a 2D

lattice Lattice may refer to: Arts and design * Latticework, an ornamental criss-crossed framework, an arrangement of crossing laths or other thin strips of material * Lattice (music), an organized grid model of pitch ratios * Lattice (pastry), an orna ...

). The angel has a power ''k'' (a

natural number In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country"). Numbers used for counting are called ''Cardinal n ...

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 Chess King was a United States men's clothing retailer created by the Melville Corporation. From its founding in 1968, it grew to over 500 locations by the mid-1980s, before an eventual decline, sale, and closure of the chain in 1995. History ...

, i.e. the distance from the starting square is at most ''k'' in the

infinity norm In mathematical analysis, the uniform norm (or ) assigns to real- or complex-valued bounded functions defined on a set the non-negative number :\, f\, _\infty = \, f\, _ = \sup\left\. This norm is also called the , the , the , or, when th ...

. 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 Determinacy is a subfield of set theory, a branch of mathematics, that examines the conditions under which one or the other player of a game has a winning strategy, and the consequences of the existence of such strategies. Alternatively and simil ...

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 geometry, topology, and related branches of mathematics, a closed set is a set whose complement is an open set. In a topological space, a closed set can be defined as a set which contains all its limit points. In a complete metric space, a cl ...

(in the natural

topology In mathematics, topology (from the Greek language, Greek words , and ) is concerned with the properties of a mathematical object, geometric object that are preserved under Continuous function, continuous Deformation theory, deformations, such ...

on the set of all plays), and it is known that such games are 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 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. Bowditch proved that a 4-angel (that is, an angel with power ''k'' = 4) can win Brian H. Bowditch, "The angel game in the plane", '' Combin. Probab. Comput.'' 16(3):345-362, 2007. and MáthéAndrás Máthé, "The angel of power 2 wins", ''Combin. Probab. Comput.'' 16(3):363-374, 2007 and KlosterO. Kloster, ''A solution to the angel problem.''

Theoretical Computer Science Theoretical computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory. It is difficult to circumsc ...

, vol. 389 (2007), no. 1-2, pp. 152–161 gave proofs that a 2-angel can win.

Basic strategies and why they don't work

Many intuitive escape strategies for the angel can be defeated. For example, if the angel tries to run away from near blocks, the devil can make a giant horseshoe far to the north, then prod the angel into the trap by repeatedly eating the square just to the south of the angel. If the angel tries to avoid traps set very far away, the devil can make a small horseshoe to the north, then prod the angel into the trap by eating the squares far to the south. It seems that the angel should be able to win by moving up as fast as he can, combined with occasional zigzags to the east or west to avoid any obvious traps. This strategy can be defeated by noting that this angel's possible future positions lie in a cone, and the devil can build a wall across the cone in the distance in a certain manner, so that when the angel finally arrives at the distance, the devil has created an impenetrable wall, and since the angel insists on moving north, the angel cannot move at all.

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

(Conway, 1982). (According to Conway, this result is actually due to Berlekamp.) This can be read at section 1.1 of Kutz's paper.Martin Kutz, The Angel Problem, Positional Games, and Digraph Roots
PhD Thesis
FU Berlin, 2004 * 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 it 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 it 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 of

Peter Winkler Peter Mann Winkler is a research mathematician, author of more than 125 research papers in mathematics and patent holder in a broad range of applications, ranging from cryptography to marine navigation.Information listed oPeter Winkler's homepag ...

'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'sbr>proof
works for the 4-angel, while Oddvar Kloster'
proof
and András Máthé'
proof
work for the 2-angel. Additionally, Péter Gács has
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 ''Combinatorics, Probability and Computing'' is a peer-reviewed scientific journal in mathematics published by Cambridge University Press. Its editor-in-chief is Béla Bollobás (DPMMS and University of Memphis). History The journal was esta ...

''. The proof by Kloster has been published in ''

''.

Further unsolved questions

In 3D, given that the angel always increases its ''y''-coordinate, and that the devil is limited to three planes, it is unknown whether the devil has a winning strategy.

Proof sketches

Kloster's 2-angel proof

Oddvar Kloster discovered a constructive algorithm to solve the problem with a 2-angel. This algorithm is quite simple and also optimal, since, as noted above, the devil has a winning strategy against a 1-angel. 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 square 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). Note that 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.

Máthé's 2-angel proof

Máthé introduces the ''nice devil,'' which never destroys a square that the 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: #he shows that if the angel wins against the nice devil, then the angel wins against the real devil; #he gives an explicit winning strategy for the angel against the nice devil. Roughly speaking, in the second part, the angel wins against the nice devil by pretending 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 maze and runs alongside the wall. One then proves that a nice devil cannot trap an angel that adopts this strategy. The proof of the first part is by contradiction, and hence Máthé's proof does not immediately yield 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.

Bowditch's 4-angel proof

Brian Bowditch Brian Hayward Bowditch (born 1961
Bowditch's personal information page at the

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^_ (\sigma_i \cup \gamma_i)

where

\sigma = \cup^_ \sigma_i

is a semi-infinite arc (a non self-intersecting path with a starting point but no ending point) and

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_

.) 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.

3D version of the problem

"Guardian" proof

The proof, which shows that in a three-dimensional version of the game a high powered angel has a winning strategy, 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 are watching over is unsafe, safe, or almost safe. The definitions of "safe" and "almost safe" need to be chosen to ensure this works. 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 occupying 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 its 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 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. 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. This proof was published by

Imre Leader Imre Bennett Leader is a British Othello player, employed as a professor of pure mathematics at Cambridge University. As a child, he was a pupil at the private St Paul's School and won a silver medal on the British team at the 1981 Internatio ...

and

Béla Bollobás Béla Bollobás FRS (born 3 August 1943) is a Hungarian-born British mathematician who has worked in various areas of mathematics, including functional analysis, combinatorics, graph theory, and percolation. He was strongly influenced by Paul E ...

in 2006.B. Bollobás and I. Leader, ''The angel and the devil in three dimensions.'' Journal of Combinatorial Theory, Series A. vol. 113 (2006), no. 1, pp. 176–184 A substantially similar proof was published by

Martin Kutz Martin may refer to: Places * Martin City (disambiguation) * Martin County (disambiguation) * Martin Township (disambiguation) Antarctica * Martin Peninsula, Marie Byrd Land * Port Martin, Adelie Land * Point Martin, South Orkney Islands Aust ...

in 2005.Martin Kutz, Conway's Angel in three dimensions, ''Theoret. Comp. Sci.'' 349(3):443–451, 2005.

References

{{reflist

External links

The Angel problem by John H Conway

Combinatorial game theory 1996 introductions Pursuit–evasion John Horton Conway