Season 11 Episode 5

It's Angels and Demons on the maths club this week, as Alice and James play a game on an infinite chessboard (there can only be one winner...)

Watch on YouTube

Further Reading

Angel problem

The Angel problem was first popularised in the book Winning Ways for your Mathematical Plays (chapter 19 in volume 2 of the first edition, or volume 3 of the second edition when the work was split into four volumes instead of three), by Elwyn R. Berlekamp, John H. Conway, and Richard K. Guy. You can maybe find a copy in a local library if you do a Google search for the name of the book.

In that book, it’s introduced as “the angel and the square-eater", and it’s part of a larger discussion of games that combine the rules of chess and go. The specific problem that we discussed on the livestream (without the ability for the devil to move any pieces) is one specific case of the class of problems discussed in the book.

More generally, Winning Ways is a fantastic source of "games of no chance" (combinatorial games). If you get a copy, you might recognise some of these games, because they’re often used to introduce the idea of strategy and game theory to people. One of the most famous is...

Nim

Suppose there are several piles of coins on a table; to start off with, let's say that there are two piles of three coins each. Two players take it in turns to remove any number of coins (at least one), provided that the coins are all taken from the same pile. So perhaps you go first and take two coins from the first pile, then I take all the coins from the other pile, and now it's your turn again. The player who takes the last coin loses, so in this hypothetical scenario I’ve described, I’ve just won (sorry, how rude of me). You might like to think about how to win this game! If you find a strategy, consider other starting combinations of sizes of piles of coins. Consider cases with more piles of coins, starting with small numbers and building up. See this NRICH page about the problem, but only after you’ve thought about it.

Angel vs Demon

John H. Conway describes various strategies that square-eating demon might use against foolish angels in this PDF.

For a strategy by which the demon can actually catch the angel that moves like a chess king (an angel of power 1 or a “1-angel”) I like the description in section 1 of Martin Kutz’s PhD thesis (2004), available here. Note that this description of the strategy leaves out some details, which is normal for this level of exposition. You might like to fill in the gaps to convince yourself that the demon really does win!

Kutz also proves that angels with “speed” between 1 and 2 can be caught (roughly speaking, this means that the angel is often, but not always, allowed to move two squares instead of one). See the section “The Need for Speed” in Kutz’s thesis.

More powerful angels

An angel that can jump to any square within 2 king-moves (an angel of power 2 or a “2-angel”) can escape from the square-eating demon forever. This is the fact that was proven by four different people almost simultaneously in 2006.

The solution by Oddvar Kloster has an approachable description at this webpage (archived from Kloster’s own website).

I should say that most of the links above are selected from the Wikipedia page!

Light cones

We had a brief discussion of light cones; this is an idea about causality that comes from physics.

The idea is that if speed is limited by the speed of light, then the set of places you can move to from your current position is limited. In particular, if we think about 2D space for a moment, the set of points you can reach lie in a growing circle. If you plot that with time as the vertical axis, then you get a cone (a stack of circles that grow as you move upwards).

If nothing can move faster than the speed of light (not even nebulous concepts like “information”), then the set of points that you can effect is the interior of the cone. Perhaps you’ve heard that it takes eight minutes for light from the Sun to get to the Earth. What happens if the Sun is suddenly deleted by aliens? One theory is that we won’t notice until eight minutes later when the light goes out.

In times like this, when we're getting close to thinking about causality, I like to link to the Stanford Encyclopaedia of Philosophy. At time of writing, the entire encyclopaedia appears to be offline. I’ll keep checking that link.