The Angel Problem
This is a hypothetical mathematical game invented by John Horton Conway of Conway’s Game of Life fame. There are two players, the angel and the devil and it is played on an infinite grid of squares. Each turn the angel which has power x (where x is decided before the game and is fixed) jumps to anywhere that a chess king could reach in x moves. These jumps can go over stuff, but the end destination must be empty. In essence the angel can go to anywhere within a square of x around it.
Then it is the devil's turn and they place a wall on any single grid space. The aim of the angel is to carry on moving forever, while the aim of the devil is to trap the angel. The question is, who can win with best play? In fact, what does best play even look like?
When x=1 the angel moves just like a king in chess and the devil wins. The devil is just too fast and they can construct a square perimeter sufficiently far out from the angel. But for higher powers of angel the problem has taken longer to get a grip on.
One of the issues is that some of the common strategies for the angel can be taken advantage of by the devil. One common heurestic that people try when they program this up is to have the angel run away from nearby blocks. However, by first constructing a huge U shaped net in one direction and the placing blocks just to the other side of the angel to force it into the trap, the devil can win (on any power level).
If the angel never heads in one direction then the devil also has a winning strategy. Let's say the the angel heads generally South with excursions to the East and West, but never North. It is like the angel is moving outwards bound by a large triangle which covers a quarter of the plane. But by constructing a line which cuts the angel off suifficiently far along the triangle the devil can cover the height fast than the angel can get there.
However several breakthroughs were made on the problem in 2006 by four different teams attacking it in slightly different ways. Two had shown that there was a winning strategy for angels with power 4, but even better, two teams had also shown that the 2-angel can win (and thus every angel more powerful than it can win too).
The power 2 angel proof is complicated but it uses a concept called the nice devil. The nice devil never places a boundary in a square that the angel has previously visited. It was proved that if the angel could win against the nice devil then they could also win against the usual one.
The angel then treats one half of the plain as already blocked off and they use a keep-your-hand-on-the-wall strategy similar to people use in mazes. It turns out that the devil can never quite block off all of the exits to the ever growing maze.
For now a lot of work is being done on generalisations of this problem, particularly 3D cases.
