The prolific mathematician John Horton Conway, well known for his contributions to set theory, knot theory, number theory, game theory, and coding theory, proposed the so-called “angel problem” in 1982. It involves two players—the angel and the devil—and is played on an infinite chessboard. The rules are very simple, and the devil must try to confine the angel while the angel avoids being captured. But the true difficulty of this problem lies in determining whether there exists a strategy that ensures one of the two opponents can always win.
When it comes to board games, it seems that the simpler the rules, the more attractive they become. Chess, one of the most complex board games in existence, has rules so simple that anyone can learn them in five minutes. However, applying them correctly or finding a strategy that ensures victory is an enormously complex task.
The angel problem
The angel problem, proposed by mathematician John Horton Conway in 1982 in the book Winning Ways (Maneras de ganar), belongs to this category. Despite being better known for creating the “Game of Life” in 1970, Conway is a prolific mathematician who has made very important contributions to set theory, knot theory, number theory, coding theory, and game theory. The angel problem belongs to the latter category.
In this game, which is sometimes called “Angels and Demons”, two players participate, respectively named “the angel” and “the devil”. It is played on an infinite chessboard, and both players have completely different characteristics. The angel has “power k”, where k is a natural number equal to or greater than 1, agreed upon between both participants before the game begins. At the start, the board contains only two pieces: the angel in the center (although, being infinite, it doesn't make much sense to talk about a “center”) and the devil on any other square. On each turn, the angel jumps to another empty square, with the condition that said square—moving like a king in chess—is at “k” squares from its previous position and is not marked. When it is the devil's turn, he can “mark” any square not occupied by the angel. In his moves, the angel can jump over blocked squares but cannot land on one. The devil wins if he manages to make the angel unable to move, and the angel wins if he can survive indefinitely. The million-dollar question is: Can an angel with sufficiently high power win?
To ensure that a winning strategy exists, we should demonstrate either that the devil can force a victory in a finite number of moves, or that the angel always has a move he can use to avoid losing, in which case his “winning strategy” would be as simple as always choosing this move. Unfortunately, the solution is far from easy to find.
Conway himself offered a reward for a general solution to this problem, which, although not exceptionally attractive—about $100 for a winning strategy for the angel and $1000 for a proof that the devil can win regardless of the angel's power—made hundreds of enthusiasts of this type of pastime sweat blood trying to find it. As with other board games, it is possible to apply the rules of the angel problem to higher-dimensional boards. Indeed, although the original game was designed for two-dimensional boards, the first demonstrations of successful (but partial) strategies were found for dimensions greater than two.
In three dimensions, it was proved that if the angel always increases its Y coordinate, and the devil can only play on two planes, then the angel has a winning strategy. Of course, no one playing “for real” with the devil would limit themselves to moving in a more foolish way, so the angel was far from having a safe strategy. Shortly afterward, it was shown that the good guy could win in 3D, as long as his power was greater than or equal to 13, regardless of how the devil moved.
As for the original problem in two dimensions, it was Conway himself who made the first progress toward the sought demonstration. In 1982, he proved that an angel with k=1 always loses against the devil. That same year, he also found that if the angel never decreases its Y coordinate, then the devil can always win. Finally, in 1996, he proved that if the angel always increases its distance from the starting point, then the devil has a winning strategy. The situation, obviously, does not look good for the angel.
Despite all efforts, there is no proof that, playing on a 2D board, either opponent can force a win. This, which might be seen as a failure by some pessimist, is in reality proof of how entertaining a simple game like this can be. The non-existence—at least so far—of a winning strategy ensures that both players have the opportunity to win, something indispensable for a game to be viable. While thousands of players enjoy their games of “Angels and Demons”, hundreds of mathematicians strive to find a proof that—perhaps—does not even exist.
