Balls and Stuff

Balls, eh?

And now for something a little different. My other articles so far have been about stuff I get up to in the workshop, generally woodwork (with a notable excursion into pyromania). But I also like computer programming, and recently I did something that's (hopefully) not entirely coma-inducing to others. Well, see what you think.

So there's a game on Facebook called Chain Rxn. It works like this: you start with a (2-D) box containing a number of balls, with random positions and random speeds (and random colours, not that it matters). They bounce off the edges of the screen but not each other. You get to place a single explosion somewhere in the box, and if this explosion hits a ball (or if a ball runs into the explosion) the ball explodes, which could cause other balls to explode and so on. The objectives of the game are:

1. To clear a certain number of balls from the screen. For example, there are 30 balls on the screen and you have to get rid of 15 of them.

2. To get as high a score as possible. Here's how scoring works: let's say the first explosion (the one you place manually) is 0th-generation. Any balls which hit that create 1st-generation explosions. Balls which hit those cause 2nd-generation explosions and in general, if a ball hits an nth-generation explosion it causes an (n+1)th-generation explosion. And the number of points you get for an nth-generation explosion is n³. Well, actually it's 100 times this in the Facebook game but it's not like the common factor matters. The point is: suppose you place your first explosion and six balls hit it and blow up. That's six 1st-gen explosions so you get 1³ + 1³ + 1³ + 1³ + 1³ + 1³ = 6 points. Now suppose you place the initial explosion and a ball hits it and blows up, then a ball hits that explosion and so on, in a chain (hence the name "Chain Rxn". Ta da!). In that case you score 1³ + 2³ + 3³ + 4³ + 5³ + 6³ = 441 points. Better! Bit abstract-sounding? Not to worry, there are videos of these things below. Stay with me.

So there's a fun game on Facebook. Is that it?

No. I decided I wanted to investigate this game a bit. After playing for a while I started to consider a few questions:

1. What's the best strategy for clearing lots of balls off the screen?

2. What's the best strategy for getting a really high score?

3. How big a part does luck play in this game?

4. What does it look like if you manage to clear all the balls off the screen?

5. What does a really high-scoring round look like?

6. Would a pointlessly in-depth analysis of this game make a good hairybrain article?

The solution was obvious: rewrite the game in C++ and OpenGL, and build in facilities to analyse different scenarios and tweak parameters and record games to video and stuff like that. So I did. I wrote the first version at about 6:30 in the morning after staying up all night getting off my face on cider, so it wasn't very optimal code, but all things considered it worked surprisingly well. Anyway, enough text, time for some pretty pictures. Here are the two scenarios described above. First the thing that only scores 6 points:

And here's the one that gets you 441 points. I've colour-coded the explosions - the first one is white and the rest go from red through the spectrum to blue as they progress through the generations, where red is 1st-gen and blue is the highest generation number it's possible to get to (i.e. the number of balls you start with).

So what do we do now?

Because it's fun to try to guess what will happen beforehand, and because someone out there might just be gullible enough to believe that I'm writing this without already knowing how it all turns out, I'm going to predict the answers to the above questions:

1. Clearing lots of balls requires that each explosion have the best possible chance of being hit by a ball. This seems most likely to happen if the explosions are in the middle of the area, where they can be approached from all sides. So, first prediction: to clear the most balls, place the first explosion in the middle.

2. Getting a high score is different - you want to clear lots of balls but you want each explosion to give birth to as few others as possible, because that way you progress along the generations more quickly and you get into the really high-scoring explosions that way. This means you want the explosions to propagate across the screen in a single direction instead of spreading out in all directions (exactly like in the clips above). So: to get a high score, start at the edge or in the corner.

3. It's pretty much pure chance.

4. It looks really cool.

5. It looks awesome.

6. Absolutely.

Can we have a detailed technical description of your analysis?

If you insist, yes. To find the answers to these questions, I simply had my computer play the game squillions of times. Or, more accurately, I had my computer play the game 28,800,000 times. For each of 30,000 randomly generated starting positions (always starting with 60 balls) I simulated 960 runs of the game, based on 960 possible starting positions for the first explosion, i.e. every point of a 40 x 24 grid more or less evenly spaced over the game area. Each randomly generated scenario and each starting position results in a score and a number of balls cleared. By averaging these figures out over the 30,000 scenarios, you end up with a 40 x 24 grid of values showing how well you can expect to do, on average, if you place the first explosion in different parts of the game area. Make sense? So now we're ready to answer my questions...

1. What's the best strategy for clearing lots of balls off the screen?

Average number of balls cleared

Right. The horizontal plane represents the game area and the height of the bars represents, on average over my 30,000 random scenarios, how many balls get cleared if you put the initial explosion in that position on the game area. So, for example, going with the bottom right gets you around 13 balls on average, whereas going for the middle gets closer to 40. So, we have our first answer: you clear the most balls by going for the middle. On average, that is - there are of course scenarios where the middle doesn't work at all well and scenarios where starting in the corner clears a huge number of balls. The graph just shows the average tendency over all 30,000 scenarios considered.

2. What's the best strategy for getting a really high score?

Average score

Average score isn't as "smooth" as the last graph, probably because of the n³ scoring rule, which causes huge standard deviation in score distribution. Doesn't matter; we can see a clear trend here. Corners suck; the middle sucks; the edges are great. The middle sucks because although you clear lots of balls, you don't get long chains of explosions - you don't progress along the generations very far, so the explosions don't score much. The corners suck because you just don't clear many balls in the corners. And the edges are great because they have the best of both worlds; they cause plenty of balls to be cleared but because the explosions propagate in a single direction across the screen, they progress along the generations and get to the high scores. Second answer: the best scores come from the middles of the edges.

Further interesting thing to look at: average score per ball. In the graph above the corners are crap because you don't clear many balls in the corners. But when you do, do you get good explosion chains, i.e. do you score lots per ball on average? Well, here's the answer:

Average score per ball

Although the corners don't look nearly so bad here, the midpoints of the edges still do better. So, for some reason, starting in the middles of the edges results in better progression down the generations of explosions than the corners. Clearly, the middle is still rubbish for getting high-scoring explosions.

3. How big a part does luck play in this game?

To answer this question, I ran the same starting configuration of balls for each possible starting point in a 1,280 x 800 grid, producing the following 1,280 x 800 piccy:

Number of balls cleared based on initial explosion position (lighter = more)

In this piccy the lightness of a pixel shows the number of balls cleared if the initial explosion starts at that point on the screen. Black means no balls cleared and white means all of them. In this particular scenario there are no starting positions that clear all 60 balls so there are no pure white pixels. Note that by and large the middle performs best (consistent with our answer to Q1 above) and the corners are rubbish. However note also the presence of very thin slivers of bright pixels amongst dim ones. This means that being off by as little as a single pixel can result in a radically different score. Although the general trend that the middle produces better scores could be anticipated by a human player, it seems clear that no person (certainly not one who isn't an autistic savant) could possibly predict where these small zones lie. Having said that, the fact that the upper part of the area is more profitable in this scenario than the lower part might be predictable, e.g. by a player who notices that the initial overall trend of ball movement is upwards. So, the answer to question 3 is: luck plays a very large part, but there is an element of skill, i.e. it is not a game of pure chance.

4. What does it look like if you manage to clear all the balls off the screen?

Like this:

This is a scenario where all of the balls get cleared but each explosion on average gives creates many others; so we don't get to high generation numbers (as shown by the fact that the explosions never get further along the spectrum than orange). The total score in this run is only 7,718. Cool-looking, huh? Compare this to below...

5. What does a really high-scoring round look like?

Here we go:

This scenario leaves 12 balls on screen, but the explosions happen in much more of a chain rather than a big flurry; note the bluey-green colour of the explosions toward the end, showing that they're very high-generational. This scenario scores a whopping 658,874 points. And, as we foretold, it looks awesome! And finally...

6. Would a pointlessly in-depth analysis of this game make a good hairybrain article?

Well, I hope so, but that's for you to judge, not me :-)