The Angel Problem is a famous unsolved problem proposed by renowned mathematician John H. Conway.

The Game

Imagine a chess piece (the Angel) on an infinite chessboard. On the Angel's turn, the Angel can move at most a distance of n squares, where n is a fixed positive integer. The Angel's power is defined to be n. The Angel is chased around on this infinite chessboard by a Devil. On the Devil's turn, the Devil can eliminate any one square on the chessboard. The Angel is allowed to leap over these 'holes' but cannot land on them. If the Devil succeeds in trapping the Angel on an 'island' surrounded by a hole of width n, the Devil wins. If the Angel succeeds in eluding the Devil indefinitely, the Angel wins.

The Problem

Stated quite simply, can the Angel escape the Devil? Obviously, to answer this, the problem must be divided into cases. Can the Angel always win if its power is sufficiently high? Can the Devil trap an Angel of any power? What kind of game is this, anyway? Is it fair or unfair?

Progress

Conway proved in 1982 that the Devil can defeat an Angel of power 1. Furthermore, Conway has proven that on a 2-dimensional lattice, the Devil can win if the Angel is required to always increase its y coordinate (such an Angel was defined by Conway as a Fool). Later, in 1996, Conway proved that if the Angel always moves away from the origin, the Devil can defeat the Angel.

Incentives

Conway, stating that this problem "has been alive too long," has offered a prize of $100 to anyone who can develop a winning strategy for an Angel of sufficiently high power, and $1000 for a proof that the devil can trap an Angel of any finite power. The difference in cash is due to the fact that Conway is biased toward the Angel and thinks it should win. In addition, mathematics is a fun and happy subject, for some people, at least.
I believe I have covered the basics of the Angel Problem without explaining the proofs in much mathematical detail. In composing this writeup I tried to stay away from that because my mathematical comprehension is far too weak, and any attempts to explain the proofs would inevitably result in gross inaccuracies. Suggestions for improvements of this writeup as well as more detailed writeups are not only welcome but would be greatly appreciated.
TenMinJoe says re Angel Problem: It would be interesting to know why mathematicians consider this a worthy problem. Why can't anyone just make up weird "games" and ask who should win? Why does this particular problem matter?

One of my friends at Princeton University had a discussion with Conway himself about this. Conway advised my friend not to work on the Angel Problem because it would be a waste of time since anything developed would have no practical application outside this particular game. My guess is that Conway thought of this problem one day when he was messing around and found its complexities particularly interesting. In any case, a devil chasing an angel on an infinite chessboard is pretty trippy, no?
Sources and extra reading:
One of Conway's papers on the Angel Problem can be found at http://www.msri.org/publications/books/Book29/files/conway.pdf (Actually, at the time of this writeup, this URL was broken. If anyone is interested in reading this paper and this URL is still no good I will gladly send it.)

A less detailed but more succinct description of the Angel Problem can be found at http://mathworld.wolfram.com/AngelProblem.html

Martin Kutz' dissertation on the Angel Problem can be found at http://www.mpi-inf.mpg.de/~mkutz/diss/kutzdiss.pdf

Log in or register to write something here or to contact authors.