( Cut for picture! )"The Angel and the Devil play a game on an infinite chess board. The Angel is a generalized chess piece that occupies a square on the board. In each turn, the Angel can move to any square that is reachable from his current square in
k chess King moves (but the Angel doesn't need to step on the intermediate squares).
k is called the Angel's power. The Devil does not have a position on the board. In each turn, the Devil may eat any square on the board, and from that point on, the Angel is not allowed to land on that square. If the Devil manages to trap the Angel, i.e. get the Angel into a position where all the squares that the Angel might fly to are eaten, the Devil wins the game. The Angel wins if he is able to fly to uneaten squares indefinitely.
For any given
k, there must exist either a strategy that guarantees the Angel to win, or a strategy that guarantees the Devil to win. The Angel Problem is to decide whether for some large enough
k, there exists a winning strategy for the Angel."