Red and Black Knights
Numberphile has recently published a video on YouTube called "Red & Black Knights". The idea is to explore what happens when knights of two factions are placed on a chessboard according to a few simple rules.
I wrote some python code so I could see it in action for myself.
Start with a chessboard where the squares are numbered in a spiral pattern.
Two factions begin to take turns placing knights on the chessboard, where:
- knights must be placed on a safe square that is not attacked by the opposing faction's knights, and
- knights must be placed on the lowest-numbered safe square.
That's it! Those are the only rules — they produce a deterministic pattern.
Let's say we have black and red knights, and a black knight is placed first. Since there are no red knights, all squares are safe. That first black knight must then be placed on the 0 square. A red knight is placed next. The 1 square is the lowest numbered square not attacked by the existing black knight piece, so that's where the first red knight must go. This then continues forever.
This animation shows the sequence of valid moves on a 9x9 chessboard:
The 9x9 board looks a bit chaotic, and it's hard to tell what would happen if we expand the board.
On a 99x99 board, we see patterns emerge. Overall, it appears to be mostly orderly but with a little chaos mixed in:
But of course, we must zoom out even more!
In my opinion, a board around 499x499 squares looks the best. You can see all sorts of unexpected things going on, and bizarre asymmetry in general:
The "islands" are particularly interesting: small regions of opposition that are embedded in a large area of solid color. They appear to form on the main diagonals. If we look at the bottom right corner of a smaller 99x99 board, as it plays out (shown below), you can see the black team is able to place a knight out beyond the corner of the entirely red bottom-right region. This must be similar to how the islands are formed.
Since the two factions alternate placing knights, and they generally place them in an ever-growing spiral pattern around the board, there are limited opportunities for a team to place a piece out beyond the corner of enemy territory like that. In other words, the squares out beyond the corners of enemy territory are always safe squares that could form an "island" but in most cases they are not the lowest-numbered safe squares available.
Boards larger than 500 squares on a side do not appear to have any more chaos in store. An unbroken pattern emerges at that point. To see that, and for more background and exploration, see the original sequence on the OEIS.