Hubbry Logo
Angel problemAngel problemMain
Open search
Angel problem
Community hub
Angel problem
logo
8 pages, 0 posts
0 subscribers
Be the first to start a discussion here.
Be the first to start a discussion here.
Angel problem
Angel problem
Angel problem
View on Wikipedia
from Wikipedia
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.[1] 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" (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. 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[2] and Máthé[3] and Kloster[4] gave proofs that a 2-angel can win.

History

[edit]

The problem was first published in the 1982 book Winning Ways by Berlekamp, Conway, and Guy,[5] 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.) This can be read at section 1.1 of Kutz's paper.[6]
  • 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.[7]
  • 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 then the angel can still win if it is of high enough power. (By "playing at distance " 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'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 Archived 2016-03-04 at the Wayback Machine 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.

Further unsolved questions

[edit]

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.

Proof sketches

[edit]

Kloster's 2-angel proof

[edit]

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 and up to . 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). 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

[edit]

Máthé[3] 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:

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

[edit]

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

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

A circuitous path is a path where 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:

  • where is the length of the ith loop.

(To be well defined must begin and end at the end point of and must end at the starting point of .)

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

[edit]

"Guardian" proof

[edit]

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 and Béla Bollobás in 2006.[8] A substantially similar proof was published by Martin Kutz in 2005.[6][9]

See also

[edit]

References

[edit]
[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Angel problem

View on Grokipedia
from Grokipedia
The Angel problem is a combinatorial game theory problem proposed by mathematician John Horton Conway, featuring a pursuit-evasion contest between an Angel and a Devil on an infinite chessboard represented by the integer lattice Z2\mathbb{Z}^2. First described in 1982 by John Horton Conway, Elwyn Berlekamp, and Richard Guy, the problem was highlighted by Conway at a 1994 Mathematical Sciences Research Institute workshop on combinatorial games—with k=1000k=1000 as a specific instance to emphasize the Angel's substantial mobility—the problem was published in Conway's 1996 paper and asks whether any finite-power Angel can evade the Devil forever, or if the Devil can always prevail against sufficiently patient play. For k=1k=1 (equivalent to a chess king), the Devil has a winning strategy, as established in analyses of finite-board variants and extended to the infinite case. The general case remained open for over a decade, inspiring research into winning strategies, variants (such as higher dimensions or random moves), and connections to percolation theory and graph theory. The Angel starts at the origin and has a fixed power k≥1k \geq 1, allowing it to move on its turn to any uneaten square within kk (i.e., max⁡(∣x′−x∣,∣y′−y∣)≤k\max(|x' - x|, |y' - y|) \leq k, where (x,y)(x, y) is its current position). The Devil, on its turn, permanently removes ("eats") exactly one uneaten square anywhere on the board. The Devil wins by trapping the Angel, meaning all reachable squares from the Angel's position are eventually eaten, isolating it in a finite region surrounded by an "impassable moat" of eaten squares at least k+1k+1 wide; the Angel wins by moving indefinitely without being trapped. The problem was affirmatively resolved in the mid-2000s, proving that Angels of power $2 or greater possess winning strategies.[](https://bhbowditch.com/papers/bhb-angel.pdf) In 2006, Brian Bowditch demonstrated a computable escape strategy for a **4-angel**, using a [recursive partitioning](/page/Recursive_partitioning) of the board into safe regions while accounting for eaten squares.[](https://bhbowditch.com/papers/bhb-angel.pdf) Independently, in 2007, András Máthé and Oddvar Kloster each provided proofs for a **2-angel**: Máthé's approach relies on the Angel maintaining progress toward infinity while avoiding potential traps via density arguments, and Kloster's strategy directs the Angel northward, detouring around obstacles with bounded extra cost to ensure long-term escape.[](https://www.researchgate.net/publication/220357906_The_Angel_of_Power_2_Wins)[](https://www.sciencedirect.com/science/article/pii/S0304397507006275) These results confirm that finite power suffices for the Angel's victory, though the minimal threshold remains $2, with ongoing interest in optimizing strategies and extensions like the 3D Angel problem.

Problem Definition

Game Setup

The Angel problem is played on an infinite represented as Z×Z\mathbb{Z} \times \mathbb{Z}, where each square corresponds to a pair of integers (x,y)(x, y), and all squares are initially uneaten and accessible to the Angel. The game involves two players: the Angel, who acts as the evader, and the Devil, who serves as the pursuer by eating squares to restrict the Angel's movement. The Angel begins at the origin square (0,0)(0,0). The is characterized by its power kk, a positive that determines the maximum distance it can move per turn; specifically, from its current position (x,y)(x, y), the Angel can jump to any uneaten square (x′,y′)(x', y') satisfying max⁡(∣x′−x∣,∣y′−y∣)≤k\max(|x' - x|, |y' - y|) \leq k, equivalent to up to kk steps in the manner of a (including diagonals). On each of its turns, the Devil eats exactly one uneaten square, which becomes an impassable barrier; the Devil may select any uneaten square without restriction to adjacency. The players alternate turns, with the Devil moving first in the standard , though some analyses show the question of whether the can escape indefinitely remains independent of the starting player.

Rules and Moves

The Angel problem is played as a two-player game on an infinite chessboard, with turns alternating between the and the , the moving first. Each full round consists of one action by the followed by one action by the . This turn order ensures that the attempts to restrict the 's mobility before the can respond. On its turn, the eats exactly one uneaten square in the standard formulation of the problem, removing it from the board to create obstacles. The eaten square can be any uneaten position on the infinite grid, though effective strategies typically involve selecting squares to block potential paths. A key constraint is that the cannot eat the square currently occupied by the , preserving the 's immediate position until its own turn. In some generalized variants, the may eat any finite set of uneaten squares per turn, but the original and standard version limits it to one to balance the game dynamics. Following the Devil's action, the Angel moves by jumping to any uneaten square within its power kk, defined using the king's move metric from chess. A single king's move allows one step in any of the eight directions (horizontal, vertical, or diagonal), so the Angel's reachable positions in one turn are all uneaten squares (x′,y′)(x', y') satisfying max⁡(∣x′−x∣,∣y′−y∣)≤k\max(|x' - x|, |y' - y|) \leq k, where (x,y)(x, y) is the Angel's current position. This Chebyshev distance permits the Angel to jump over any number of eaten squares, as long as the destination is uneaten and within the distance limit; the Angel cannot land on or pass through eaten squares in the sense of occupying them, but no path clearance is required beyond the landing constraint. The infinite nature of the board eliminates boundary restrictions, though the growing set of eaten squares effectively creates barriers that the Angel must navigate around.

Winning Conditions

In the Angel problem, the Angel wins by demonstrating a strategy that allows it to move indefinitely on the infinite chessboard, always finding an uneaten square within its power kk (measured in Chebyshev distance) regardless of the Devil's actions. This victory condition emphasizes the Angel's ability to evade capture forever in an infinite game, where no finite number of turns concludes the play. Conversely, the wins by forcing the into a stranded position, where no other uneaten squares lie within distance kk of the current position. Stranding occurs when the creates a surrounding barrier of eaten squares at least kk wide, effectively trapping the without legal moves to different squares. Formally, a strategy for the is winning if, for any sequence of moves, the can perpetually select uneaten positions within its power, ensuring perpetual escape. The core question of the Angel problem is to determine the minimal integer kk for which the Angel possesses a winning strategy against an optimal . This threshold kk balances the Angel's mobility against the Devil's ability to consume squares, with the game resolving in the Angel's favor for sufficiently large kk.

Historical Context

Conway's Original Formulation

The Angel problem was posed by mathematician circa 1976 during a discussion with Andreas Blass at Angell Hall, in Ann Arbor, drawing inspiration from pursuit-evasion dynamics on infinite grids. This formulation emerged as an open challenge in , pitting an "Angel" against a "Devil" on an infinite chessboard, and was first detailed in the book Winning Ways for Your Mathematical Plays, Volume 2: Games in Particular by Elwyn R. Berlekamp, John H. Conway, and , published in 1982. In the initial setup, the Angel begins at the origin and can move up to k squares in any direction (including diagonally) on its turn, where k represents the Angel's fixed power, while the Devil alternately removes one unoccupied square from the board to restrict the Angel's options. Conway believed that an Angel of sufficiently large finite power could evade the Devil indefinitely, though the outcome remained uncertain, especially for small values of k. Specifically, it was established that an Angel of power 1 loses, as the Devil can construct an enclosing barrier to trap it, but the outcome for power 2 remained unresolved, with Conway suspecting the Angel might evade capture indefinitely in that case. To spur research, Conway offered a wager: $100 for a proof that some sufficiently large finite power k enables the Angel to win by surviving forever, and $1000 for demonstrating that the Devil can always trap an Angel regardless of finite power. This framing highlighted the problem's intrigue, positioning it as a test of strategic depth in infinite positional games.

Early Investigations and Bets

The earliest analytical results on the Angel problem established that the Devil can decisively win against an Angel of power k=1k=1, equivalent to a chess king, by rapidly encircling and trapping it on the infinite grid. Berlekamp provided a strategy demonstrating that the Devil can confine the power-1 Angel on boards of size at least 32×3332 \times 33, ensuring capture in finite moves. Efforts to devise effective strategies for higher-power Angels often faltered under scrutiny. In particular, Conway and Blass analyzed "foolish" Angel behaviors, such as the Plain Fool (always moving away from the origin) and Lax Fool (prioritizing escape from immediate threats), revealing that even an Angel of power 1000 could be systematically diverted and trapped by the Devil in finite time. These findings underscored the challenge of crafting a robust, non-myopic strategy for the Angel, as suboptimal play allowed the Devil to exploit predictable patterns. The unresolved nature of the problem sparked notable wagers among mathematicians. John H. Conway offered a $100 for a proof that some finite-power has a winning and a $1000 for demonstrating that the can trap any finite-power . These stakes, publicized in the , highlighted the community's divided opinions and spurred further interest. By the late , partial theoretical advances showed that a sufficiently clever could evade capture for arbitrarily long durations against suboptimal play, though no guaranteed eternal survival for small finite powers. The Blass-Conway diverting forced the Angel to traverse arbitrarily large distances while avoiding traps, but it did not resolve whether the could eventually prevail. Computer-based explorations during this period reinforced these insights by simulating prolonged games, where Angels of moderate power evaded destruction for extensive turns, yet conclusive proofs remained elusive until later breakthroughs.

Resolution in Two Dimensions

Overview of Angel's Victory

The resolution of the Angel problem in two dimensions established that an angel of power k≥2k \geq 2 possesses a winning on the infinite 2D grid against any devil's play, thereby confirming that the angel can evade capture indefinitely. In contrast, an angel of power 1 inevitably loses, as the devil can systematically block all possible escape routes and trap the angel after finitely many moves. This threshold highlights that a modest increase in the angel's mobility—from king-like single-step moves to jumps of length up to 2—shifts the balance decisively in the angel's favor, with higher powers k>2k > 2 only simplifying the winning further. At a high level, the angel's revolves around perpetually maintaining access to an infinite evasion path, often conceptualized as an "escape route" in a preferred direction, such as northward along the positive y-axis. By prioritizing moves that preserve connectivity to unbounded regions of , the angel exploits the inherent robustness of the infinite lattice structure, ensuring that the devil's barriers—formed by eating up to a fixed number of squares per turn—cannot enclose it despite cumulative obstructions. This approach leverages the grid's directional persistence, allowing the angel to sidestep localized blockages while advancing toward . Independent proofs of the angel's victory for power 2 emerged between 2006 and 2007, resolving John Conway's longstanding conjecture and settling related historical wagers in the angel's favor. These results underscore percolation-like properties in the grid, where the angel capitalizes on the network's supercritical connectivity to navigate around eaten squares and sustain mobility over infinite time. The findings not only affirm the angel's resilience but also illuminate broader themes in combinatorial game theory regarding infinite graphs and adversarial containment.

Kloster's 2-Angel Proof

In 2006, Oddvar Kloster provided a proof that an angel of power 2 has a winning strategy against the devil in the two-dimensional angel problem. His approach, published in 2007, centers on a dynamic path-following strategy that allows the angel to escape indefinitely by prioritizing northward progress while systematically avoiding eaten squares. The core strategy involves the angel maintaining and updating an infinite path starting from its current position and extending northward to infinity, avoiding all eaten squares. The path is constructed such that the angel moves along it in jumps of at most length 2, ensuring legal moves under the power-2 constraint. If the devil eats a square that intersects the current path, the angel locally adjusts the path by detouring around the obstruction. These detours are bounded: the extra length introduced by any detour must not exceed twice the number of "evaded squares" associated with that segment of the path. Evaded squares are those previously safe positions that the angel has effectively bypassed in prior path versions, serving as a resource to "pay" for deviations and tracking the angel's evasion history. This mechanism ensures that the angel can detect and circumvent potential traps early, as the bounded detours prevent the devil from forcing the path into increasingly constrained regions. Kloster's for path updates is constructive and efficient: upon the devil's move, the angel recomputes the path by extending a new northward backbone while incorporating local reroutings only where necessary. The proof demonstrates that for any devil action, such an adjustment can be made in a constant number of steps relative to the power, preserving the infinite northward escape. Specifically, the detour bound is formalized as the additional path length ΔL≤2⋅e\Delta L \leq 2 \cdot e, where ee is the number of evaded squares credited to the detour, ensuring that the total deviation remains controlled even as the number of devil moves grows. This guarantees that the angel never becomes trapped, as the devil cannot accumulate enough eaten squares to block all viable northward paths without the angel having sufficient evasion credits to respond.

Máthé's 2-Angel Proof

In 2007, András Máthé published a proof establishing that the of power 2 possesses a winning strategy in the two-dimensional Angel problem. Máthé's approach begins with a key observation originally due to Conway: without loss of generality, the Devil can be restricted to a "nice" variant where it never removes a square that the Angel could have used to reach its current position in one move. This restriction simplifies analysis because the Angel's immediately accessible past positions remain uneaten, preventing the Devil from retroactively blocking recent jumps. Máthé proves that a winning strategy against this nice Devil suffices for the general case, as the nice Devil is at least as powerful as the arbitrary one in forcing a trap. Against the nice Devil, Máthé describes an explicit, intuitive for the Angel: follow the boundary of the uneaten region while keeping the boundary immediately to the Angel's left, akin to a in traversal but adapted for the grid and power-2 jumps. This involves moving along the edge of the safe area, occasionally making small perturbations (such as single-square adjustments) to avoid unnecessary diagonal jumps of length 2, ensuring the strategy aligns with the Angel's movement capabilities. The Angel thereby maintains adjacency to the uneaten , progressively exploring outward without entering potentially trapped interiors. To verify the strategy's success, Máthé employs a proof by contradiction. Suppose the Devil eventually confines the Angel to a bounded uneaten . The boundary of this region then forms a simple closed curve (a Jordan curve) on the grid. The Angel's path, starting from the unbounded exterior and ending in the finite interior, must intersect this curve an odd number of times by basic . However, under the boundary-following strategy, the Angel's trajectory remains tangent to the curve—never crossing it—yielding only even (or zero) intersections, which contradicts the assumption of entrapment. This impossibility implies the Angel escapes to infinity. Máthé's proof is notable for its brevity and reliance on classical rather than intricate combinatorial constructions, distinguishing it from contemporaneous path-optimization approaches like Kloster's.

Bowditch's 4-Angel Proof

In 2006, Brian Bowditch provided a proof demonstrating that an angel of power 4 possesses a winning strategy against the in the two-dimensional Angel problem. His approach reduces the infinite game on the Z2\mathbb{Z}^2 to a series of finite "guarded" subgraphs, where the angel can consistently identify safe moves despite the devil's efforts to trap it. Bowditch's method relies on the concept of blocking sets, which represent the devil's strategy of eating squares to form barriers that impede the angel's progress, and draws on ideas from to analyze how these barriers fail to contain the angel. The devil's eaten squares create potential obstacles, but the angel's power of 4 enables it to leap over barriers up to width 3, allowing navigation around or through these structures without becoming trapped. This wider mobility ensures that the angel can always find an escape route, treating the board as a network where percolation paths remain open despite localized blockages. The angel's strategy involves conceptualizing the board as a series of layered annuli—concentric regions expanding outward from the origin—to guarantee steady radial progress while avoiding devil-induced traps. By following a "spine" along circuitous trails and shortcutting loops when possible, the angel maintains access to uneaten squares in successive layers, ensuring it never runs out of valid moves. To extend this to the infinite board, Bowditch employs a compactness argument: any potential trapping strategy by the devil would fail on sufficiently large finite boards, and thus cannot succeed in the limit of the infinite game. This proof is notably simpler than those for the power-2 angel, as the greater leaping ability of power 4 reduces the complexity of bypassing barriers, avoiding the need for more intricate inductive constructions. Bowditch explicitly shows that the 4-angel has a computable winning , providing a constructive path for .

Variants and Extensions

Three-Dimensional Version

The three-dimensional version of the Angel problem adapts the original formulation to the infinite cubic lattice Z3\mathbb{Z}^3, where positions are identified by coordinates (x,y,z)(x, y, z). The Angel of power kk begins at the origin and, on its turn, moves to any unoccupied within kk, meaning it can change each coordinate by at most kk units, reaching up to (2k+1)3−1(2k+1)^3 - 1 possible adjacent cubes (excluding its current position) in the 3D of radius kk. The responds by permanently removing (eating) one unoccupied from each turn. The Angel wins by moving indefinitely without being confined to a position with no legal moves, while the aims to trap it in finite time. In contrast to the two-dimensional setting, the additional spatial dimension provides the Angel with greater mobility and evasion options but simultaneously empowers the Devil with enhanced blocking capabilities, as barriers can form closed hypersurfaces enclosing finite volumes rather than mere lines or walls. This increased surface area in 3D allows the Devil to potentially isolate regions more efficiently, complicating the Angel's compared to planar evasion in 2D. The question of whether a finite power kk suffices for the Angel to win remains resolved in the affirmative, with proofs establishing victory for sufficiently large kk. Martin Kutz demonstrated that a 13-Angel possesses a winning strategy, employing a constructive escape plan based on a hierarchical structure of expanding boxes that the Angel navigates to avoid encirclement indefinitely. Independently, and Imre Leader proved that an Angel of adequate power defeats the in three dimensions by maintaining directional progress while circumventing barriers. Partial results reveal that a power-1 loses in three dimensions, akin to its defeat in 2D, as the can construct enclosing barriers despite the extra . However, for small finite powers, the can employ strategies to survive for any prescribed finite duration, highlighting the 's challenge in achieving a rapid win even if eventual capture is possible. The minimal power kk for which the wins in 3D is unknown, though it is at least 2 and at most 13. One major challenge in 3D arises from the Devil's potential to build volumetric enclosures, which differ from 2D linear blockades by fully surrounding the in space and requiring multidimensional detours for escape—far more complex than sidestepping planar obstacles.

Proof Strategies in 3D

In the three-dimensional problem, proofs of the 's for finite power rely on constructive strategies where the maintains safe regions using hierarchical partitioning of the grid. Developed in mid-2000s on 3D variants, these approaches show that an of power at least 13 can ensure uneaten regions remain connected and expandable against the Devil's plays. By dividing the grid into hierarchical boxes of increasing size (e.g., side length 13 at the base level, expanding by factors such as 29 per higher level), the keeps each box "nice"—meaning it contains at most a bounded number of eaten cubes (such as ≤1157 in level-1 boxes)—preventing the Devil from enclosing the entire structure. This bounded density guarantees that clear subcubes (with ≤333 forbidden points in a 29×29×29 grid) always connect to form escape paths, leveraging the extra dimensionality to outpace the Devil's one-square-per-turn limitation. A central result is that the Angel can protect an infinite connected component from being eaten, demonstrating the Devil's inability to dominate the board. This holds because the 3D geometry allows for robust : for instance, between adjacent clear cubes, a path of at most 165 steps exists using axis-parallel planes, enabling the Angel to transition levels while preserving niceness via induction. The relates to methods in 2D Angel proofs, such as András Máthé's work, adapting recursive safety arguments to show that the Angel forces the Devil to leave infinite uneaten areas intact. The core tactic involves the Angel responding to the Devil's moves to reinforce box perimeters, ensuring the mass of uneaten points (tracked via a potential function) remains positive in protected regions. This, combined with the grid's infinite extent, forces the Devil into inefficient spreading, as any attempt to breach a level requires exponentially more moves than the Angel needs to reposition. Representative examples from the proofs illustrate scale: in a level-j box, the Angel limits eaten cubes to O(165^{j-1}), sustaining an infinite hierarchy where uneaten components grow unbounded.

Other Generalizations and Open Questions

The Angel problem has been extended to finite boards, where the devil can always win by systematically confining the angel to an ever-shrinking region until no legal moves remain. In such settings, the finite number of squares allows the devil to exhaust the angel's options over time, contrasting sharply with the infinite grid where escape is possible. Further variants include directed graphs, where the angel moves along outgoing edges from its current vertex, and the devil removes vertices to block paths; outcomes here depend heavily on the graph's connectivity and expansion properties. Extensions with multiple angels or devils introduce or competitive dynamics, such as teams of angels coordinating to evade a single devil or vice versa, altering the strategic landscape beyond the single-player infinite grid. The Angel problem also draws analogies to the problem on graphs, where agents (analogous to the angel) protect vertices from a spreading contamination (like the devil's eaten squares), highlighting shared themes of and in network structures. Open questions persist regarding the minimal power kk for which the angel secures a win in three dimensions, with known results showing the devil prevails against low-power angels but leaving higher kk unresolved. In higher dimensions d≥4d \geq 4, the angel's prospects remain unclear, with inquiries into whether sufficiently large kk guarantees victory or if the devil can exploit increased spatial . Variants with randomized devil moves introduce probabilistic elements, where the angel's survival may hinge on thresholds akin to in random removals, though exact behaviors are underexplored. As of November 2025, no major breakthroughs have resolved these extensions, and connections to algorithmic emerge in assessing the of optimal angel strategies, which may require non-recursive decision processes. A key unresolved issue is whether the angel wins on all vertex-transitive graphs or if victories are confined to structured grids like Zd\mathbb{Z}^d.
Add your contribution
Related Hubs
User Avatar
No comments yet.