When Random Clusters Attack

Author and economics professor Gary Smith devotes a chapter in his book “Standard Deviations” to random clusters in data and how they are often misinterpreted as meaningful findings. Often the same thing happens in games: Random moves by players can sometimes be mistaken as strategy. “But surely all patterns observed in player behavior must have a purpose,” you say.

First of all, nobody talks like that. Stop it. Second, unlike unicorns, random patterns exist. Smith uses Germany’s bombing raids on London during World War II as an example:

During the final stages of World War II, the German army fired thousands of V-1s and V-2s at London. The V-1s were 25-feet long, pilot-less airplanes that used an internal gyroscope to control the flight path. The planes chugged along at 300 miles an hour and took 30 minutes to reach London from their launch sites in German-occupied France. A small windmill device mounted on the plane estimated the distance the V-1 had traveled based on the number of times the windmill revolved as the plane flew toward London. After a preset number of revolutions, the V-1 was sent into a steep dive toward earth.

If that sounds highly complicated and prone to problems, you guessed right: it was. According to Smith, the Germans basically aimed them at London’s Tower bridge and if it landed anywhere in London, the launch was considered a success. Because of the V-1’s limited accuracy, the bomb sites in London were random. But Londoners didn’t see it that way. Smith writes:

There seemed to be clusters of bombs in some areas and an absence of bombs in others, suggesting that the Germans were aiming at some neighborhoods and avoiding others.

Some theories were that the Germans were avoiding bombing certain neighborhoods because that’s where the German spies lived. But R.D. Clarke, a British statistician, proved that the clusters also could be random. Clarke drew a grid of London and calculated expected versus actual outcomes. The results matched.

What does that mean? If only there were a game that would help me demonstrate this point …

You Sunk My Battleship

Battleship is a game that actually dates back to the 1930s, when it was played using pencils and paper. You are probably more familiar with the Milton Bradley board game.

The game is simple: Each player has a 10×10 grid where they place (in one of the game’s variations) an aircraft carrier, a battleship, a submarine, a destroyer, and a patrol boat. The ships are five, four, three, three and two spaces long, respectively. An example of player 1’s setup is illustrated below.

battleship-clusters-fig-1

During each round, the players take turns calling out positions on the grid. If the other player has a ship in that position, he/she calls “hit.” Otherwise, it’s a “miss.” The goal is either to sink all of your opponent’s ships or sink the battleship first.

The opening moves in Battleship are as random as random can be. You’re really just trying to detect occupied spaces on your opponent’s grid. Once you start getting a couple of “hits,” then your moves become more calculated.

But let’s say player 2 decides to make all of his/her moves random — maybe using a 10-sided die to determine the grid letter and number. (In R, this is achieved using the sample function). After 20 moves, player 1’s grid will look like this:

battleship-clusters-fig-2

Doesn’t look random, does it? Player 1 could interpret those attacks as a strategy. There are large gaps in the grid where no attacks occurred, and groups of attacks, including a sunken patrol boat! A k-means cluster analysis shows there are actually three distinct clusters in this “random” data.

battleship-clusters-fig-3

[Technical Side Note on the Analysis: I used k-means clustering, which is typically used with continuous data, while k-modes clustering is used with categorical data like values attributed to a grid letter and number — such as A3 = 1. However, because in Battleship it doesn’t make sense to strike the same point on the grid twice, k-modes clustering doesn’t cluster the data correctly. To cluster the data with k-means, I converted the letters to numbers, which results in a numerical matrix. So the attack at A3 is actually (1,3). From the plot above, you can see that the data is clustered properly.]

In a 10×10 grid you have 100 possible locations for an attack. For the first attack, whether the space is occupied or not, each grid point has a probability of 1% that it will be hit. Because one space isn’t hit multiple times, the next attack reduces the probability for each point to 1.010101%, then 1.0204082%, then 1.0309278%.

If your opponent starts hitting your ships, the probability changes. Say one grid point is a “hit”. One of the eight surrounding points now has a 12.5% chance of being hit. But if your opponent is truly attacking at random, each point maintains the same probability of being attacked.

Run enough simulations and in some, you’ll see clusters. Sometimes you won’t.

Explaining the London Clusters

So how did Clarke figure out the clusters were random in the London bombings? If you’re not a fan of math, skip the rest.

Clarke divided a map of London into 576 squares and knowing the total number of bombs that struck the area was 537, he used what is called the Poisson probability distribution to figure out the expected number of bombs each square might receive.

If 537 bombs are dropped on 576 squares, the average hit each square receives is 0.9322917 (our \(\mu\)). Obviously the rules of warfare don’t match the rules of Battleship, so some areas received mutliple bombings. So using the formula below, he plugged in the number of hits per square (0,1,2,3,..) and figured out the probability a square would be hit by that number.

\[ f(x) = \frac{\mu^x e^{-\mu}}{x!} \]

Multiply the probability by the total number of squares and you get the number of squares you would expect to be hit by random bombs!

So the probability of a square receiving 0 hits would be 39%, which means the expected number of squares to receives zero hits would be around 227. I’ve recreated Clarke’s table in R below.

london <- data.frame(hits=c(0:5), actual=c(229,211,93,35,7,1))

london <- london %>% 
  mutate(`Expected Number of Squares`=((537/576)^hits * 2.718^-(537/576))/factorial(hits) * 576) %>%
  rename(`Bombs per Square` =  hits, `Actual Number of Squares` = actual)
Bombs per Square Actual Number of Squares Expected Number of Squares
0 229 226.764642
1 211 211.410786
2 93 98.548257
3 35 30.625239
4 7 7.137914
5 1 1.330923

As you can see, the expected numbers are close to the actual numbers. Clarke did some hypothesis testing and found the results to be statistically significant.