## Learning and Applying Mathematics using Computing

### 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.

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 ($\frac{1}{6}\times\frac{1}{6}\times\frac{1}{6}\times\frac{1}{6}\times\frac{1}{6} = 0.01\%$), 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 $0.15 \times 0.25 \times 0.35 = 0.013$ — 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

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

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.

#### Comments on: "Probability and People" (13)

1. Tyler said:

Worth noting that the default random number generator in most C libraries is actually significantly flawed (for performance reasons), and after graphing, say, 20 billion 1-6 results, you will see that certain numbers and sequences come up far more often than they should (the sequences being the very huge and end-user noticeable problem). I lean toward a lot of game programmers not being aware of this as much as confirmation bias.

• Unless those sequences produce numbers at the high end of the 0-100 range when made modulo 100, that wouldn’t explain a run of bad luck in XCOM. I’m happy to see references, but unless such a sequence comes up with very high frequency, it wouldn’t affect the average player.

• Tyler said:

http://www.pnas.org/content/61/1/25.full.pdf+html

There’s also visual representations of the patterns that appear in smaller modulo ranges out there somewhere, but I couldn’t find them.

This doesn’t establish specifically anything about the 0-100 range, of course, and I don’t have any experience with it, but I did run into issues with lots of improbably long high and low sequences in the 0-20 range that disappeared when switching to a different algorithm.
http://en.wikipedia.org/wiki/Mersenne_Twister

• Tyler said:

(I won’t discount the possibility I was seeing patterns in effectively random data, but I went from “Am I imagining these patterns?” to, “Ok, this feels random.” when I switched.)

2. ahnold11 said:

Great series of articles. I like your non-standard means of coming up with solutions.

I definitely agree that the perception of the game (from the players perspective) is just as, if not more, important then the actual reality of the game. If games are an entertainment medium, then the players experience should be paramount.

And so the game mechanics should take this into account. I wonder if many devs use the standard “ask the computer for a random number” idea, just because as game players (and “dice” users), that is what we are used to. Without too much thought regarding how the players will actually feel about the results?

What got me following all these posts was my own curiosity on how randomness in the game was “determined” as I was suffering a bit from the whole “this game feels unfair. Regardless of how accurate the %’s are, my luck is keeping me from enjoying it. Feels like the deck is stacked against me”. (This is after completing on normal, and starting on classic).

Which lead me to the idea: I wonder if it’d be as simple as switching from a uniform probability distribution, to a more normal one? The difference between rolling a single die, or rolling two (and averaging the value). Many table top games use more then one die, I assume to reduce the frequency of the “extreme cases” and beef up the middle cases. Presumably because this intuitively feels more “fair” to the players.

I’d love to see a mod that allowed us to tweak the RNG in the game (as simple as two rolls to hit instead of one) to see if that would indeed change people perception. And if that would make them enjoy the game more (or possibly even less?)

Keep up the good work, I’ll definitely be curious to see anything else you write on the topic.

3. xdv said:

DOTA uses a pseudo-random generation system for events with fixed probabilites. For example, say you have a 30% chance to crit. Instead of testing the 30% crit chance each time you hit, they do something else instead…

They use an incrementing series… pick a value X, say 10%. The first hit has a 10% chance to crit: if it doesn’t crit, then the second 20%, if it still doesn’t crit, then the third will be 30%. When a crit occurs, the counter resets to zero: your next hit will again be at 10% chance.

Value of X is chosen so that in the long run, the overall number of crits is 30%.

This means you will never have a streak of non crits longer than 9, since the 10th attack will have a 100% crit rate if you hadn’t landed a crit yet. And it also means that you’re very unlikely to land 3 crits in a row (under the normal system, you would need to roll the 30% 3 times in a row, in the pseudo random system you need to roll 10% 3 times in a row).

This is a clever way of retaining the overall intended crit chance while reducing the occurence of lucky and unlucky streaks.

HoN uses a pseudo-random distribution in providing gold bounties. In random loot generation games, it’s important that the coin that monsters drop is random. (Imagine in a D&D game, where every Orc you killed dropped EXACTLY 2 gold).

Part of the fun in those games is the randomness: in fact, it’s inbuilt into us to expect a degree of randomness. It would feel extremely out of place if every monster dropped the exact same amount of gold.

In a competitive game, however, the random gold drops can unintentionally favour one player over another. Just to cover all the bases… the designers in HoN add a counter that tracks if you’re above or below the expected gold gain rate per kill, and add a second adjusting variable that helps pull your next gold drops back towards the mean.

This provides the effect of allowing players to see the apparently “random” amount of gold coin bounty from mobs, at the same time invisibly ensuring the gold bounty trends to the mean.

As to my solution to the XCOM problem… Before you talk about how to mitigate the effect of randomness (and player rage) we need to ask WHY the randomness has to exist in the first place. Because randomness has a real cost to it, that acts to the detriment of gameplay, the benefits has to be proven to outweigh that cost.

Criticals exist for player gratification – it’s satisfying landing that gigantic critical hit that floors an enemy. It’s generally accepted that this tradeoff is worthwhile.

Random gold bounty is necessary for player immersion. It’s also accepted that this tradeoff is worthwhile.

What about randomness in XCOM? You could argue about it from the angle of immersion – you’re simulating a reality where some shots hit and some miss. But is this really necessary?

As a thought experiment, imagine an XCOM that was rebalanced around the idea that all shots are taken at 100% hit rate, and you take 66% damage if you’re in low cover, and 33% damage if you’re in high cover. Shots against cover also destroy it after a certain damage threshold. Would this be a better game, or worse?

I don’t think this would break immersion. Most weapons are rapid fire – from the ingame animation, they fire a sustained burst at the alien in one round of shooting. You could make the argument that these soldiers are the top trained soldiers in the world (which they are). Most of them, firing half a magazine at a human sized target 10 meters away, would land at least some hits. The only difference is how many hits are going to be absorbed by cover, and how many are not. In fact, I think the way it is now actually breaks immersion more – this is the “best” soldier in all of China (I assume China sends it’s most elite Soldier to the XCOM project because this is only the FATE OF THE WORLD AT STAKE) and he fires 10 shots at an alien 10 meters away and misses all 10…

Doesn’t quite work for bolt action sniper weapons, but you could either omit snipers completely (original XCOM didn’t have snipers) or just use rapidfire sniper weapons (which do exist).

TLDR, XCOM could get rid of randomness and still be a perfectly functional game. Again a key concept from Euro games, game mechanics are meant to be an abstraction, not a simulation.

• ahnold11 said:

Interesting ideas. With respect to X-com I think they like the randomness really to provide variety and a sense of the unknown. Xcom has a reputation to be “ball-bustingly” hard, and part of that is the mercy of the dice. The uncertainty of taking a gamble, the risk vs reward etc. But it’s a very tricky issue as you point out, there are downsides.

With respect to the “randomness with limits” that the other games provide, part of the discussion on the blog is that they don’t want you to be able to “Game” the system. Specifically in those games, if you notice you haven’t critted, then you theoretically could use that info (I am going to crit soon) to your advantage. (Don’t play the game myself, so not sure if it’s actually just another skill ie, “crit management” that players use. Ie. wait to attack a player until you’ve no-crit streaked on mobs, so that you will have a fast crit waiting to attack the player with). Since it’s PVP that at least balances out. In PvE games it can be a bit trickier as it can be seen as a way to “game” the system.

4. Lactose said:

A note on World of Warcraft’s quest drop percentages:
Since the Wrath of the Lich King expansion, the chance of getting a quest item when killing an enemy is not a static percentage. For every enemy you kill that does not drop the item, the chance to get it increases, until a drop is guaranteed. Upon dropping, the chance resets again.

See the following link for more detail:
http://www.shacknews.com/article/57886/blizzard-details-secret-world-of

• Interesting, thanks for that — looks like they already implemented the idea I discussed.

5. Many of the Fire Emblem strategy games use a system described as “True Hit”: http://serenesforest.net/general/truehit.html . Basically, whenever they check for hits, they choose two numbers between 1 and 100 instead of just 1, and average them together. This tends to make probability somewhat more in tune with what people expect; a displayed 80% hit chance becomes 92%, displayed 90% becomes 98%, displayed 5% becomes 0.55%… it’s crude, and it doesn’t handle streaks directly, but it does make results that go against intuition (80%, 90% shots missing, 10%, 20% shots hitting) less likely in the first place; so fewer such streaks appear.

6. A lot of this would be simplified by comparing independent randomness (a die) to dependent randomness (a card deck).

7. Black Rock Shooter said:

On the potential for “gaming the system” using a “randomness with limits” approach, I believe looking at the math to accomplish this even the simplest situations would be improbable enough and require enough time investment that overall there is not an appreciable gain for the “gamer”.

As an example (of course please anyone correct my math) let us assume a 20% chance to hit another player, increasing with every miss by 20% until %100. In order to exploit this system one decides to take swings at an accomplice until they reach the %100 chance so then can then go out and guarantee one hit (likely not a one-shot kill in any practical game) on their arch-nemesis. This would require 4 misses in a row. From the viewpoint of just starting their task, the chances of getting to the magic point are 0.8 * 0.6 * 0.4 * 0.2 = 0.0384, or roughly 1 out of 25 times. Of course, one could get lucky the first run, or one could go fifty runs and not achieve this, but the point is on aggregate. At varying run lengths (1 to 4, average 2.5 attacks) at say a cooldown of 1 sec this would take 62.5 secs > 1 min. Of course, presumably done far away from any action where they could be attacked. Now the player gets to travel for some time to attack his mark and make a guaranteed hit, which in any real game of equal players fighting should not kill.

Extend the changes to 10% increasing %10 every miss and the effort grows significantly. Other possible exploits like running around a large battlefield attacking enemies, somehow mentally counting the number of misses in a row in all the chaos (blackjack card counters can do this so I am not dismissing it) and then when reaching the magic state running off a looking for a high value target for that one attack (while not having been killed up till then or being killed while looking) are equally terrible returns on investment.

So I have not sat down to consider all the possible ways to exploit “a randomness with limits” system, but just thinking out loud at reasonable probabilities and in practical situations I cannot see gaming such a system as a realistic excuse against it. Of course, people with much more math than me might be able to suggest otherwise? Again, practically not just theoretically (of course, if the changes are %50 increasing to %100 it becomes somewhat valuable for the effort, but what game would ever implement that?)

• Black Rock Shooter said:

Sorry to reply to my own comment, but additionally in calculating the economics, the 1 minute of gaming effort has to be balanced against how many actual hits the gamer could have achieved if they just went out and played (or for that matter how many multiple enemies that player could have engaged).