Mathematics In Greenfoot

This blog features a lot of content on applying mathematics in Greenfoot. You can see an index of all the interesting content here. Unfortunately I don’t think I will have time to follow through on my plan to collect all the content into an e-book (nor my plan to write some more content on probability), but all the existing content is here for free anyway. There’s also a few popular posts on XCOM which you can see below, but the majority of the site content was all the Greenfoot material, which I hope will continue to prove useful.

Is XCOM Truly Random?

A huge amount of discussion about the game XCOM: Enemy Unknown pertains to the random number generation. Many people claim — either seriously, or in jest because they are so frustrated with their luck — that it is broken. Because I’m completely hooked on the game For science, I’ve been playing a lot of XCOM, and I have been recording my shots as I played. For every shot I actively took, I recorded the displayed chance of it hitting, and whether it actually hit or missed. (I ignored overwatch shots because I couldn’t see their probabilities, and also didn’t bother with rockets and other later-game non-gun weapons etc.) I’ve recorded over 1200 shots, and in this post I’ll examine the data to see if XCOM is fair.

The Psychology of XCOM

Keeping this record of hits and misses in XCOM taught me a lot about the psychology of playing the game. The longest streaks of hits that I noticed in the data was one streak with an incredible 18 hits in a row, and another with 19 hits in a row, with the following percentage chances to hit:

Streak 1: 65, 93, 85, 97, 100, 100, 73, 100, 95, 73, 57, 73, 86, 89, 94, 96, 81, 82
Streak 2: 95, 63, 94, 95, 73, 58, 100, 100, 100, 86, 84, 95, 98, 85, 84, 73, 100, 90, 95

What’s interesting is how I felt while playing the missions. I wasn’t sitting there shouting “amazing!” as hit after hit piled on. Both of the above streaks came in “very difficult” terror missions. In the first streak, all the aliens appeared on one turn, and I couldn’t kill the Chrysalids faster than they were turning the civilians into zombies. I downed 20 enemies in all, and lost 3 of my 6 men because I got so overwhelmed. So even when I had amazing positive luck with my shots, I didn’t even notice until I took stock of the spreadsheet after the mission.

On the other hand, here’s a (much more likely) streak from the third game I started, from the first mission, where I missed my first six shots with percentages:

45, 45, 54, 45, 45, 45

I ended up losing two of the four men, and since it was the first mission, I restarted in disgust. You really do notice only the negative streaks, and never the positive streaks.

The Fairness

Below is the best graph I could think of to represent the fairness of the random number generator. On the X axis is the stated chance to hit: the number that popped up in the box when I took the shot. I’ve grouped these into 5% bins, and then plotted a bar for each bin, showing how many of those shots actually hit. In an ideal world, with infinite data, the red line on the graph would pass through the tops of all the bars. It would actually be surprising if this happened exactly: it’s called random for a reason, and with the small amount of points I have in each bin (around 60), it’s likely that the proportions I observed are not perfectly in line with expectation.

That looks reasonably fair to me. I think that graph is the most comprehensible output you’ll get, but “looks about right” is not very scientific! Read on for a more precise methodology.

Significance Testing

The problem with determining whether something is truly random is that you can never be sure. Theoretically, any string of hits and misses is possible in XCOM (except 100% shots missing), so you can never know for sure if it was a broken random number generator or bad luck. The best you can do is collect a lot of data, and see if it’s an unlikely result, and then conclude whether you’re confident that the data came from a random generator.

Here’s the idea then behind testing for random generation. We pick the individual to-hit percentages, e.g. 65%, for which we have the most data (at least 20 shots). We then work out what the chance was of getting a result as extreme as the one we observed. If this chance is low (conventionally, 5% or less), the data is unlikely to have come from a random generator. For example, let’s say that we had fired 25 shots at 85%, and all of them had hit. The chances of this happening is only 1.7%, so unlikely if the generator was truly random.

However: one complication to this method is that if we check several percentages, we are likely to find one that’s extreme. On average, if we check 20 different percentages, we’ll find one that we are 95% sure is too extreme. This is known as a type I error (an awful name!). To control for this, we can use a procedure known as FDR, and your eyes are probably glazing over right now, so let’s get to the result.

The Result

The result is that, based on my data, there was no evidence (at the 95% confidence level) to suggest that the random generator is unfair. If you want to see the data and the working, it’s all available in this spreadsheet.

Caveats

There a few caveats to note. One is that my significance testing is very underpowered: despite recording a lot of shots, I don’t have enough shots for specific percentages to be likely to spot any deviations that aren’t large. (Specifically: at 80% power, for 50 hits, I could only have spotted 20% deviations in the shot percentage.) More data would solve this problem! One alternative would be to use Bayesian methods, where I could express my prior belief that the generator is fair:

The other caveat is a potential problem with the data, caused my own lack of XCOM ability! In the spreadsheet, Game 1 through Game 5 are “Classic”-difficulty Iron Man games. I’d completed Classic Iron Man quite smoothly once already, and figured I’d be fine. Five failures later, and I was left with the problem that I didn’t have enough data for high-percentage shots, which tend to occur later in the game when your soldiers are high-rank — but I got all mine killed! So Game 6 was non-Iron Man, so that I could use a little reloading to carry me safely through to the later game. Shameful.

Reloading causes two problems with the data. One is that if you record some shots, reload, then record again, you’re effectively recording the same thing (due to way the state of the random generator is saved in the game). So I was careful to wipe out any data up until the point I was reloading from. The other problem is that this can still introduce a bias to the data, because you’re more likely to have missed when you trigger a reload, and more likely to have hit when you don’t then choose to reload. I did not reload too often (and usually it was an alien’s hit that caused a reload, not my own miss), but there is that potential small bias in the data for Game 6. I also haven’t tested autocorrelation (“streakiness”), mainly because I’m not sure how to do so on this kind of data. But overall, I’m fairly confident that XCOM is indeed random.

Probability and People

Following on from recent posts on the “XCOM” game (here and here), I wanted to write about people’s perception of probability. A huge amount of posts on XCOM are from people accusing the random number generator of being broken. A few are not realising that the numbers are partly deterministic, but others accuse the probabilities of being plain broken. While I can believe there are one or two bugs, it’s not hard to make sure that the actual odds match with the displayed odds. Instead, it’s likely that there is a huge dose of confirmation bias, where players remember shots that go against them. But there’s also other problems to do with probability, randomness, and people’s conception of them, which is what this post is about.

The Dice Have No Memory

One famous problem with probability versus people’s expectations is known as the gambler’s fallacy. A simple phrase to sum it up is “the dice have no memory”. If you have a fair six-sided die, and you roll four sixes in a row, the chance of getting a fifth six is… one in six. It’s no more likely (the streak continuing) or less likely (some sort of cosmic balance) than at any other time. But people do tend to believe that streaks shouldn’t happen in random events, or should be somehow balanced out by a reverse streak.

Original photo CC BY-NC-ND 2.0 by Lynn Friedman

I think that part of the problem is that we tend to look at odds from a historical perspective, not based on our current knowledge. The chances of getting five sixes in a row is slim (), but once you’ve observed four sixes, the chance is down to one in six. However, we keep thinking of how unlikely it would have been at the start — that doesn’t matter now! What’s happened has happened, and in the case of independent events, it has no bearing on the future.

The wikipedia article mentions a famous case in Monte Carlo where a roulette wheel turned up black 26 times in a row. Lots of people lost money betting red during the streak, reasoning that red must come up soon. But red was no more likely than at any other time, so they lost their money while the streak continued. (The story is an example of confirmation bias, the event was partly reported because the black streak went on so long, but roulette is played all over the world every day without this streak happening, so we only collectively make note of a long streak.)

This has implications for playing a game like XCOM. Let’s say you have an alien in sight, with soldiers lined up to shoot it: one with 85%, one with 75% and one with 65% chance. The alien is dead, surely! You shoot with the 85% first, and miss. You shoot with the 75%, and also miss. So you line up the 65% — it must hit, right? The chances of all three shots missing was — about 1%. So I think many people choose to take that final 65% shot, effectively thinking that it must have a 99% chance to hit. But it doesn’t: it has a 65% chance to hit! What has already happened doesn’t matter: the events are independent, so by now you only have exactly a 65% chance to hit.

Shuffle The Deck

Original Photo CC BY-NC-ND 2.0 by Oliver Lavery

This problem of streaks and randomness cropped up in software design a few years ago. People complained that their iPod shuffle algorithm was not random enough: they were getting streaks of songs by the same artist, or somehow related songs. Steve Jobs said Apple would change the algorithm: “We’re making it less random to make it feel more random.” The problem is that the human brain is an amazing pattern recognition system. It can find patterns incredibly well, but also finds patterns when sometimes there are none. Presented with a stream of random numbers, the brain can probably pick out a pattern. So what people usually mean by “I want it to be random” is actually “I want there to be no discernible patterns” — different thing!

One way to “fix” a game like XCOM to aggravate the users less would be to alter the random number generator algorithm, to remove streaks of high numbers (or of low numbers). Technically, this makes it less random, and removes the independence of events. The advantage is that players would feel happier that the game wasn’t out to kill their soldiers — but the disadvantage is that players could start gaming the system. If you hit three unlikely shots in a row, you could know that the next shot is becoming likely to miss, and act accordingly. Much like the save-scumming strategies, a deviation from truly random events is an invitation to play the system. Plus, as soon as you actually deviated from truly random numbers, investigative players would decry the broken random numbers. Players want to win, but they want to win against a fair challenge. And no-one suspects foul play more than an aggrieved player.

Make It Explicit

Rather than fiddle the random number generator in the background, you could build anti-streak protection into the game mechanics. You could introduce a bonus into the game, called something like “Justice” or “Concentration” or “Determination”. Whenever any soldier misses a 90%+ hit, the next soldier to shoot receives a 10% bonus to hit. Miss two 90% shots in a row, and the third soldier gets the cumulative bonus of 20% (and so on). This protects against streaks of bad shots (by altering the probability of subsequent hits during a bad streak), and softens the blow of a high-probability miss. (It’s not even totally unrealistic: a team taking consecutive shots at an alien are probably not independent.)

Obviously, you would need to reduce your overall chance of hitting slightly to balance out this bonus, but it could make the players happier, while keeping the probabilities explicit and completely accurate. I wonder if there is some more mileage in this idea of using game design to balance out people’s flawed cognition — I can’t immediately think of any existing examples, but feel free to comment below if you know of tricks like this.

Grinding Down

Original Screenshot CC BY-NC-SA 2.0 by Zak the Fae

I also wonder about altering probabilities in cases like RPG collection quests. In games like World of Warcraft, or Borderlands, you are often given a quest to collect 10 of a particular item, like a hyena pelt. So you head out to the hyena grounds and start killing them. If every hyena dropped a pelt, you’d know exactly how long the quest would take: for 100 pelts, you’d need 100 hyenas. The games don’t tend to do this, perhaps to introduce variability into how long the quest would take, so instead they get you to collect 10 pelts, but each hyena has a probability to drop a pelt when you kill it: say, 0.1.

This is another kind of probability in a game that just frustrates players. The last pelt never seems to drop (confirmation bias again), and people get annoyed at not knowing how long the quest might take. The variance in how long it takes to complete the quest is worse for collecting fewer rare items than greater common items. If you want to collect one magic gem that drops every hundred beasts, you have about a 13% chance of still being there after killing two hundred beasts. And here’s the thing: after you’ve killed 200 beasts without a gem, your chance of getting one on the next beast is still 1 in 100!

If I was a game designer, I’d not make this a random drop with independent probability for each beast. Rather, pick a maximum number of beasts that you want the player to have to kill, say 150. At worst, the gem will drop on the 150th beast. You don’t want the gem to drop on the very first beast — you want the player to have a challenge. So you maybe pick a number between 50 and 150, and upon killing that many beasts, the magic gem will drop. Still random in a sense, but not as frustratingly random as a series of independent drop chances. We should be able to make less frustrating games through more careful use of probability.

Randomness vs Canniness, or Programmers vs Savescummers

I recently wrote a post on probabilities in the game “XCOM: Enemy Unknown”, in particular for the rapid fire ability. Lots of the discussion around the article (and XCOM in general) was about randomness, and pseudo-randomness. There’s an interesting post to be written about subjective observation of probability, but I’m interested in a practice known as save-scumming: repeatedly reloading the same saved game until you achieve your desired result (especially in a luck-based game). To do that, I first need to explain a bit about how randomness in games work.

I’m Soooo Random!

Original photo by Tomi Tapio, CC BY-SA 2.0

To implement a game like XCOM with a chance of a shot hitting, you can use a random number generator. If the shot has a 63% chance to hit, you generate a random number from 1-100, and if it’s less than or equal to 63, it’s a hit (this way, 63 of the 100 numbers will correspond to a hit). In the real world, you might roll a 100-sided die. But computers can’t roll actual dice, so they either need to use a hardware random number generator, e.g. measuring electrical noise inside the machine, or use a pseudo random-generator (PRNG). A PRNG has a current state from which it can generate the next “random” number. If you know the state, then by definition you can know the next number, but otherwise it appears random to you. For the purposes of games, a PRNG with unknown state is observably just as random as a hardware generator.

Random Chance

So then: implementing random shots is easy. Initialise your PRNG’s state using the time when the game starts, then when the user chooses to fire a shot, generate the next random number and decide whether the shot hits. But maybe the shot misses: the chance was 85% but you generated 93, meaning the shot misses. The player is annoyed: they wanted the shot to hit! So they have an idea: reload the game and try again. The PRNG state was altered by generating the number, so the next one is different: 41. A hit! The player is happy this time, and plays on. If they save before each shot, and are perseverant enough, they can now make any shot in the game a hit. It’s cheesy, but as players we’ve probably all done similar at some point. This technique is known as save-scumming.

So what can the designer do? I think the only perfect solution is to disbar reloading: the Ironman mode in XCOM has one save file per game, which is overwritten every time anything happens in the game. That’s probably the best solution, but it has downsides: accidental clicks in the game (I’m looking at you, XCOM’s wonky camera control) are permanent, corrupted save files are now hellish, and some players find Ironman too restrictive. In the rest of the post, I’ll explain alternate solutions.

Universal Memory

Remember that the next random number is dependent solely on the PRNG state. The reload “exploit” works because the PRNG state is different every time the player reloads, so the shot result differs every time you reload. But it doesn’t have to: what if you save the PRNG state in the save file? That way, every time you reload and take the shot, the same next “random” number will be generated, meaning that reloading is futile. This is using the property of the PRNG in our favour: by taking advantage of the hidden determinism of the PRNG, we can make sure that a reload doesn’t affect the result of the shot. So that seems like a solution to save-scumming: save the PRNG state.

XCOM definitely saves the PRNG state. I have a save file in the first mission on impossible, with one soldier able to take a 45% shot — every time I reload it and fire that shot, it hits:

Multiverse

Unfortunately, our solution isn’t as sound as we would like. The PRNG state is saved in the save game file, and next time a random number is generated, it will be,say, 93, and after that will come 32. The player doesn’t know this explicitly, but they do have the ability to reload. Inevitably, the player notices that every time they load that same game, their 85% shot misses. So they reload the game, and try a shot with a different soldier, who has a 65% chance. The 93 is secretly generated: still a miss. Frustrated, the player tries the original 85% soldier again: this time, the 32 is generated — a hit! So the player gets the idea that the first shot they make seems destined to miss, but the second will hit. So they reload the game, take the first shot with a spare soldier who’s far away, then take the second shot with their most powerful soldier. So our supposed solution, saving the PRNG state, won’t completely protect against reloading.

XCOM has this problem. In my save game, I have two soldiers with 45% shots that always hit if I take that shot first. With my other two soldiers, I can move to take a 42%, a 55% or 60% shot that will also always hit. However, several 25% shots, a 32%, a 38% and a 40% shot always miss when taken as the first shot. Therefore, my next random number from the save game generator is either 41 or 42. Scientific save-scumming:

Individualised Odds

What can be done about the reload-and-try-someone-else problem? One solution that comes to mind is to individualise the odds. To avoid letting the order of attempted shots matter, at the start of each turn, you could secretly assign a random number to each soldier (for each type of shot). So the 85% soldier gets assigned 93 in secret, and no matter which order you make your moves, that soldier will always miss on an 85% chance. So the player loads up the game, tries the shot… and misses. They reload, miss, reload, miss, and pretty quickly they realise that this shot is literally destined to miss. So they don’t make that shot: they move the soldier into hiding and try a different shot with a different soldier. With a bit of patience, the player can know exactly which shots will hit and which won’t. This effectively removes all randomness from the game, and replaces it with a sort of deductive meta-game where the player has to figure out which shots hit, which miss, and plan accordingly. It might be sort of fun, but it’s not the game that the designer intended!

XCOM does not do this. If I shoot once or twice with other soldiers and then try my 45% shot (which always hits as the first shot), it misses. Also, it matters whether the first shot hits or misses: a hit presumably consumes two random numbers from the generator (one for hitting, one to decide whether it’s a critical hit), whereas a miss consumes one number (for hitting). If I make a hit with the first shot, the result of a given second shot is always the same — but it is different if I miss with the first shot.

Mitigating The Problem

I’m not sure the reload-and-try-someone-else problem can be completely solved (except by banning reloading) without another exploit popping up. Two mitigations spring to mind. One is to make reloading annoying enough that the player won’t do it so much (more splash screens! annoying voiceover every time!). Hmmm, not ideal.

The other mitigation is to individualise the random chance. Remember that our original algorithm was to generate a number and see if it’s less than or equal to our percentage probability. If you generate a 97 as the first number, then pretty much every shot will miss, and the player can easily detect this.

Instead, for each shot, you can decide a set of numbers (for the programmers: e.g. by hashing the player and turn number) that will count as a success. Let’s make this simpler and say each shot has a chance out of 10. So one shot might have a 4/10 chance. Instead of generating a number from 1-10 and seeing if it’s less than or equal to 4, pick 4 numbers out of 10 for that shot: say, 1, 6, 8, 9. If any of those come up, it’s a hit. Meanwhile, another shot with a 7/10 chance, will be a hit on 1, 2, 4, 5, 6, 9, 10. If the next number is an 8, the 4/10 shot will hit, but the 7/10 will miss. Thus from the player’s point of view, the order of shots can still affect which ones miss and which ones hit, but not quite as simply as before (i.e. the first shot can’t always be destined to hit or to miss). This would make save-scumming harder.

I’m fairly certain XCOM doesn’t do this, based on the analysis above. I have five shots above 42% which all hit when taken as the first shot, and about seven below 40% which always miss as the first shot — the chances of this being the case with the above mitigation would be incredibly slim.

Summary

So, save-scumming is a hard problem to fix, without Ironman. Even without reverse engineering the code or the save game file, we were able to work out what must be happening under the hood, and with unlimited reload, it’s possible to exploit this. But ultimately, players can do what they like with their single-player game — I grew up playing the original XCOM (well, TFTD) by borrowing someone else’s hack of ASCII-editing the save game file to give myself piles of money. Those were the days…

A follow-up post discusses people’s perception of probability, and what can be done about it.

Probability in Games: XCOM

I’ve recently been playing XCOM, the new revamp of the classic alien-invasion turn-based strategy series. For those who don’t know the game: you are in charge of XCOM, a force put together to defend the Earth from alien invasion. There’s two aspects to the game: one is an overall management view, deciding what to invest in, what to research, how to equip your UFO interceptors and so on. The other aspect is a turn-based tactical game, moving your squad of soldiers around the battlefield and shooting at the aliens.

Each turn, each soldier has two actions, one of which can be to shoot at an alien. There’s all sorts of other abilities that override this simple rule, but that’s the basic rule: at most, one shot per turn. When you go to shoot, the game tells you the exact probability of your shot connecting:

Your shot either hits or it doesn’t, and then damage is randomly calculated thereafter. But the key thing is whether the shot connects. Waste your chances with 25% shots, and you’ll soon get overpowered. It’s better to maneuver around, destroy the aliens’ cover, and then shoot with an 85% chance. And when it misses, you can exclaim stupid things like “My 85% shot missed! What’s the chances of that!” (Spoiler: 15%).

The turn-based game is a mixture of moving carefully to cover, and managing your odds. Different soldiers may have different odds of hitting the same alien, so you choose who to take which shot on which alien in which order to maximise your chances of success. Effectively, you’re navigating a probability tree, and the skill is in finding the optimal path. Of course, it’s all still random, so even your best strategy can go horribly awry: when your 95% shot misses, and your backup 85% shot misses, you feel slightly aggrieved (exercise for the reader: what’s the chances of that, eh?)

Rapid Fire Chances

There’s also some interesting game mechanics that require a bit of consideration. One good example of this is the Assault class’s “Rapid Fire” ability. This allows you to take two shots instead of one, but at a 15% reduced chance to hit. Obviously, as the player, you want to know: when it is advisable to fire a single shot, versus firing two reduced aim shots? That depends on a couple of other factors: are you worried about using too much ammo at this stage, and will one shot be enough to kill the alien?

Let’s take the simplest case. The alien is infuriatingly still alive, despite having just 1 health, meaning any shot that hits will kill it. You’ve got full ammo, and your Assault has moved to a good location. You have some probability, , to hit the alien with a single shot. Should you fire one shot, or use rapid fire? One shot has the chance to hit. What’s the probability of one of the two rapid fire shots hitting? There’s two ways to think about this, which we can look at with a probability tree:

1. One is to add up the probability of the different branches: we’re interested in the branch where the first shot hits (and since this will kill the alien, no further shots will occur) and also the branch where the first shot misses and the second shot hits. They are highlighted in red on the tree above, and mathematically, we can calculate the probability of hitting to be , which we can multiply out to .
2. The other method, when you want to find out the probability of at least one event occurring, is to calculate the probability of no events occurring, then “invert” it by subtracting it from 1. The probability of both shots missing, highlighted in blue on the tree above, is , so the probability that at least one hits is , which also comes out to .

So, what we want to know is when , the chance of hitting with two rapid fire shots, is greater than , the chance of hitting with one normal shot. For this, we can use a graph, plotting as the red line and as the yellow line:

The straight red line is the chance of hitting with a normal shot, the curving yellow line is the chance of hitting with at least one rapid fire shot. As you can see, generally it’s better to use rapid fire, except at the extreme ends. What’s happening at those ends? Well, at the low end, say you have a 25% chance of hitting with one shot. The chance to hit with each rapid fire shot is then only 10%, so the chance of hitting with a shot is , which is only 19%: the chance to hit is so awful that you’re better off with a 15% higher chance on one shot. At the very top end, if you have a 100% chance to hit, then that is obviously better than two 85% chances. Of course, the crucial piece of information is what are the two points where the lines cross, which define the region where two shots are better?

To find out where the lines cross, we need to know the value for when . We’ll need to multiply out a bit:

Now we have a quadratic equation for the variable , where , , and . We can plug these in to the quadratic formula:

or

So there you have it: between 34% and 96% chance on a normal shot (inclusive), you’re better off using rapid fire if the alien only needs one shot to kill him (and ammo is not an issue).

Rapid Fire Damage

An obvious next question is what you should do if one shot will not be enough, and you just want to do as much damage as possible. Well, let’s say each shot that hits does an average of damage. It doesn’t matter about critical hits or how damage is calculated — each shot, normal or rapid fire, does the same average damage if it hits, so that’s all we need to think about. The average damage of a normal shot is — the chance of it hitting multiplied by the damage it will do if it hits. The average damage of a single rapid-fire shot is .

So how do you calculate the average damage of two rapid-fire shots? Well, it turns out that it’s quite easy. The two rapid-fire shots are independent events: the chance of the second hitting doesn’t depend on the first. So the average damage of two rapid-fire shots is simply . So the question then is, for what values of is it true that ? The graph this time has two straight lines:

So above a 30% chance for a normal hit, you’re increasingly better off to fire two shots, if what you care about is doing a lot of damage. And in XCOM, if you’re shooting anything with less than a 30% chance, you’re pretty desperate!

Design

As a player, it’s useful to know when rapid fire is actually going to be useful. But bear this in mind, too: the designers almost certainly produced that first graph when designing the game. They had free choice over the penalty being 15% for two shots. What would have happened if they had chosen a 30% penalty? The graph would have looked like this:

With that penalty, you always would have been better off using one shot for a single alien, and you would not have got much better damage when trying to hit with two — most players probably would have skipped the skill and written it off as useless. Thus the choice of the 0.15 reduction was important. Knowledge of probability comes in handy here, both for players and for designers.

You may also want to read a follow-up on how the randomness in XCOM works: Randomness vs Canniness, or Programmers vs Savescummers