Contents

The problem        
Solutions
    Kloster
    Bowditch
    Máthé
    Gács
Variations
Demo

The problem

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.

The game was introduced in Berlekamp, Conway and Guy's 1982 book "Winning Ways for your Mathematical Plays". For more information, see the Wikipedia article and Conway's paper about the problem.

Solutions

A proof is given in Winning Ways that the Devil can trap an Angel of power 1, i.e. a chess King. Beyond this, little progress was made on the (2D) problem for a long time (although in 3D, it was known that a sufficiently powerful Angel could win). The 2004 PhD thesis of Martin Kutz improved this by proving that Kings with fractional speed between 1 and 2 can also be caught by the Devil. But recently, no less than four independent claims to having solved the problem have appeared, by:

The answer turns out to be that for k >= 2, there is a winning strategy for the Angel.

Top