Learning and Applying Mathematics using Computing

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, p, to hit the alien with a single shot. Should you fire one shot, or use rapid fire? One shot has the chance p 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 (p - 0.15) + (1 - (p - 0.15)) \times (p - 0.15), which we can multiply out to 2 \times (p -0.15) - (p -0.15)^2.
  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 (1 - (p - 0.15))^2, so the probability that at least one hits is 1 - (1 - (p - 0.15))^2, which also comes out to 2 \times (p -0.15) - (p -0.15)^2.

So, what we want to know is when 2 \times (p -0.15) - (p -0.15)^2, the chance of hitting with two rapid fire shots, is greater than p, the chance of hitting with one normal shot. For this, we can use a graph, plotting p as the red line and 2 \times (p -0.15) - (p -0.15)^2 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 0.1 + (0.9 \times 0.1), 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 p when p = 2 \times (p -0.15) - (p -0.15)^2. We’ll need to multiply out a bit:

p = 2 \times (p -0.15) - (p -0.15)^2
p = 2p - 0.3 - (p^2 - 0.3p + 0.0225)
p = 2p - 0.3 - p^2 + 0.3p - 0.0225
p^2 + p = 2.3p - 0.3225
p^2 - 1.3p + 0.3225 = 0

Now we have a quadratic equation for the variable p, where a=1, b=-1.3, and c=0.3225. We can plug these in to the quadratic formula:

\displaystyle\frac{-b \pm \sqrt{b^2 - 4ac}}{2a}

\displaystyle\frac{1.3 \pm \sqrt{1.69 - 1.29}}{2}

\displaystyle\frac{1.3 \pm \sqrt{0.4}}{2}

\displaystyle\frac{1.3 \pm 0.632}{2}

p = 0.966 or p = 0.333

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 d 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 p \times d — 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 (p - 0.15) \times d.

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 2 \times (p - 0.15) \times d. So the question then is, for what values of p is it true that 2 \times (p - 0.15) \times d > p \times d? 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

About these ads

Comments on: "Probability in Games: XCOM" (46)

  1. Very nicely done and concisely laid out. I love seeing people take apart things and show everyone just how they work.

    However, I know from experience that it is possible for you to wind up with a 100% chance to hit even with Rapid Shot. Might it be possible to extend that first graph up to a 1.15 probability of the normal shot hitting, so that we can see how it performs when extra bonuses offset some or all of the penalty that would be applied to a shot that normally has a 100% chance to hit?

  2. What software did you use to make the graphs?

  3. Awesome post, man. Loved the simple way the math was explained and the graphs are gorgeous.

  4. Great post! Lots of fun.

  5. Great. Thanks.
    Now how about the odds of the classic board game of Risk?
    Is it better to defend or to attack?

  6. Autoclave said:

    Very nice. Now i regreat that i did not try to figure this out my self before. Thanks for englightenment. I think there is room for analysis with other abilities related to overwatch aim penalty, dash increased defense against overwatch, usage of pistol with foundy buffs and gunslingers vs snap shot sniper rifle with the 20 aim penalty and so on..

  7. From my own experiences in XCOM, I also know it’s possible to miss even when you have a 100% chance to hit. Any idea how that could happen?
    As long as there are oddities like that in the game, I don’t think it’s possible to do a real probability study like this (because X-Com probabilities may not actually be accurate themselves).

    • Not saying I don’t believe you, but after playing enough to have a ton of 100% chances, I’ve never seen that happen.

      • jikavak said:

        It’s probably just aliens having a bullet dodge trait or something else not factored in the %

    • On the matter of the “100%” miss, I did have one thought: the game displays chances in integer percentages. I don’t know exactly how all the probabilities are calculated, but I wonder if sometimes the chance to hit is actually, say, 99.6% chance, and if this is rounded to the nearest integer, this might display as “100%”, but actually there’s still a chance of missing. Not sure if that’s possible, but that could be one explanation.

    • Bradlay FLock said:

      It’s true, I had it happen one time right after release with my sniper. It was on a thin man on a bomb defusal mission on that free-way with the huge half constructed tower-partition thing in the middle near the end. I had 100% chance to hit, but after the shot was fired, it didn’t show any damage (or MISS), just hung in the air for a few seconds, then zoomed to the next active character.

      Clearly a bug.

  8. i actually had this scenario with the end boss. the top ethereal on the ship. Wednesday my assault was my last char standing, my psionics expert was mind controlled by the boss. the boss had 12 life. do u use my cannon for one shot or risk two. i chose rapid fire. surprisingly she hit with both shots and a fair distance and k/o him and i won, my heart was in my butt but i did it.!

  9. Just before you take control of your squad, a series of checks are run which determine roll outcomes prior to your actions (So hit / miss is pre-determined unless you do something different, hence why you cannot reload a game a million times to finally make that perfect shot).

    So based on that, I fail to see how mathematics involving percentages, and not roll outcomes means anything at all. This also is the reason you can miss very high percentage shots… you rolled a 34 on that 100% shot, when you needed a 54 to score a hit. See my point?

    This was interesting though.

    • If you don’t reload, I don’t think it matters if the probability rolls are predetermined, as long as you don’t know the outcome. If somebody rolls a fair die but doesn’t show you the result until you’ve guessed the number, the chances of you being right are still 1/6 even though the die has already been rolled. I presume the same would hold for the way they predetermine the rolls.

    • It’s not “a series of checks”, and it’s not true that “hit/miss is predetermined”. Rather, XCOM uses one of the most standard ways of generating a series of random numbers — a Pseudo Random Number Generator, or pRNG. It picks a starting seed (usually based on current time or the like), sets up the pRNG, and then every generated number after that is determined by the state of the pRNG and the pRNG’s algorithm. If you include the state of the pRNG in the savefile, then players will get the same rolls at any given point of the game, and they can’t just savescum until a roll succeeds.

      What this means is, if you do the exact same moves in the exact same order, you’ll get the exact same outcome. Mix things up, and you’ll get the same dice rolls, but they’ll be for different orders this time.

      It’s still fair because it’s random, and it’s still perfectly subject to this sort of analysis. It’s only predetermined in the sense that your orders are predetermined — that is to say, “not at all”, unless you’re psychic. But if you reload and try to do the same orders again, yeah, you’ll get the same outcome.

      • I agree with some of what you said Wisq, but the system is certainly not just a random number generator (I would hope!) as that is really generic, the algorithm should certainly takes other aspects of the given situation into account prior to determining the roll -needed- to score a hit, based on distance to target, high or low cover, among other checks such as possible stat buffs (+defense), then the roll is performed (Think Shadow Run). Then, you get to choose your actions, with a predetermined roll based on the above. I am unsure if you get a new roll if say you move within the blue and fire, but from my experience it would seem that you do not, however if you use “Run and Gun” on the assaulter, I am unsure how this effects the original roll but it would appear when engaged it gives the character another roll.

        But as far as saying rolls are just “random numbers” is wrong. There “must” be checks to determine the roll needed to score the hit in the first place.

      • If it was simply a random number without checks, all stat modifiers would be useless, and all hit / miss would be completely random based on the random generated number or seed as you mentioned. Perhaps you can explain?

      • Wisq, I don’t think they would use the RNG to calculate to hit probabilites or damage done. The key advantage of using a pRNG instead of a RNG as far as I understand (someone please correct me if I’m wrong) is the seed. The seed state gives both speed (it saves cpu cycles) and the ability to reproduce the result. Randomness is rarely used in function or within processes computed in real time to save cpu power. But when it comes to calculate probabilites, a dice or percentile function it’s easy to make (calculation of probabilites should be a different function than the roll function). In a turn based game you should be able to only call the function when needed.

        It just seems really counterintuitive to me using the pRNG to calculate anything that should not be random. A good strategy game can’t rely on that kind of randomness, as it would make the strategic component (stats, moving troops closer, using abilities) useless -as Park noted.

        But why does xcom it calculate probabilities based on everything else I really don’t know, it just seems silly. If you’re using Ironman or don’t rely on saving/reloading it’s true you won’t find out, and it’s true that it kind of prevent save scumming, but it also feels weird to me. Having Col. Hitman with a 85% to hit shouldn’t be affected if Lt. Fubar has/hasn’t moved previously.

      • Inspired by these comments, I’ve written another post explaining what you’re discussing here — how XCOM uses random numbers and how it saves the pRNG state:

        https://sinepost.wordpress.com/2012/10/29/randomness-vs-canniness/

  10. [...] Probability in games: XCOM [WARNING: Contains graphs]: “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?” [...]

  11. Superbly fascinating, both as an XCOM fan and as a probability aficionado :)

  12. The problem here is that everyone is assuming the hit percentages displayed are correct.

    They are not.

    Like a previous commenter, I have missed 100% shots. I have also missed about 75-80% of shots described as “45%”, as calculated across a few hundred shots (excluding reloads due to seeding.) Easy enough to reject, with high confidence, the game’s claim that it is a 45% chance.

    The shot% in the HUD is not correct, end of story. Thus, we can’t make any of the conclusions drawn in this article.

  13. Great article. An aside: I’m not confident that it is true that a “shot either hits or it doesn’t, and then damage is randomly calculated thereafter.” From playing a while, I suspect that the probability of a hit is not independent of the damage dealt on hit. XCOM is not really presenting the likelihood of a hit so much as a shot’s chances of “success.”

    Sid Meier has spoken in the past about how presented probabilities often frustrate play-testers (likely because they’ve bad intuitions about how probabilities work: “It said I had a one in three chance, I shot three times, and none of them hit!”). To avoid these frustrations, he spoke of having altered the way likelihoods are presented (in the Civilization games, at least) so that they better match players’ expectations which are faulty, from the perspective of proper probabilistic analysis.

  14. [...] 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 [...]

  15. [...] answer lies in numbers, and those numbers were last week very helpfully explained by Neil Brown, who in a couple of blog posts breaks down not only the facts behind shooting percentages, but also [...]

  16. This doesn’t explain stuff like reloading 15+ times because an 85% sniper shot missed every single time. While your math looks interesting, I have also saved right before a rapid fire and reloaded many times, and the first shot would always hit and the second shot always miss. If you have two shots at 85% and the first one connects and second one misses, after reloading the game several times, you would expect, at some point, to see the first one miss and the second one hit or, better yet, both hit; especially with such high chances at 85%. I’m assuming that alien mitigations aren’t calculated into the perceived percentage to hit? But even still, in a rapid shot fire situation, you would think after reloading the game several times with 85%-like chances to hit, things would be different after every reload, not exact clones of the same playout of the shot. And then, for damage to be randomly generated, it’s rare that the damage of a certain shot will be different after reloads as well. I’ve even reloaded after criticals because a second shot from a sniper might not go as well and the first shot’s critical will happen again even at a low rate of it happening. It’s almost like the outcomes are determined and scripted.

  17. Great analysis and graphs, Neil.

    There’s one thing I think might be missing in your analysis of Rapid Fire. The probability of a Rapid Fire shot can be greater than 85%. I have had an assault move right next to an alien, use rapid shot, and have a 100% chance to hit with both shots.

    There are a couple of possibilities for this behaviour (additional analysis would be necessary to tell which one was true). It is possible that the system allows a hit chance of more than 100% during intermediary calculations. This is clamped on the last step, but would allow a skilled soldier to absorb some penalties and still have a guaranteed hit.

    The other possibility is that it is clamped at every step (or at least more than once) but that some modifiers are applied after the rapid shot penalty. For example, maybe something like this happens:

    Base chance due to skill/range/cover: 1.2 -> clamped to 1.0
    Penalty due to rapid fire: 0.85
    Bonus for scope: 0.95
    Bonus for plasma rifle: 1.05 -> clamped to 1.0

    Cheers!

  18. quillbreaker said:

    Something I was wondering on the autofire question:

    Does the chance of the second shot hitting improve if the first shot destroys the target’s cover? I am starting to field guys with plasma, and under those conditions one hit can wipe out the cover.

    • From my experience eliminating cover does nothing for the turn in which it is destroyed, the following turn, when the engine runs the checks and rolls, it will discover the cover is gone, decreasing the roll needed to score a hit, however the AI will have it’s chance to move prior to you getting to act which usually nullifies the fact that you destroyed the cover. I haven’t played in a few weeks due to some college courses. As Neil Brown detailed in his other post, sometimes which character you fire with, will garner different results, however I still do not see how a “mid-turn” recalculation of cover would take place. Simply not going to happen in my opinion until your next turn.

      • Technically it’s not the turn, but the action of the one character we’re talking about. If the Assault shoots out the cover with either shot, another character targeting the same alien would benefit from the cover being removed.

  19. [...] 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 [...]

  20. Greg Laabs said:

    Hey there, what program did you use to generate those graph images?

    • See the comment further up: gnuplot for most of the graph, output to SVG, then loaded into inkscape to add the neon effect and background.

  21. On multiple occasions regardless of percentages (replaying the same shots over and over again) from a save. It would seem on some shots you will hit regardless of percentile. One many of those occasions I have tested 92% shots and missed over 10 times. I should have hit 9 out of 10. Didn’t happen. I have also ran the same test where I only had a 52% shot and out of 10 times I hit all 10 times. It would seem to me that at some points of the game are set to happen regardless of what you do and does not follow the actual percentile chances given on the screen.

  22. Reblogged this on Alex in Space and commented:
    I play this game a lot. It is very interesting to see the math done for me.

  23. ColonelSandersLite said:

    This is actually slightly incorrect, but not for the typical reason people think it is.

    You have made a fallacious assumption that the to hit modifiers never add up to more than 100% chance to hit and the aim penalty is thus subtracted from a number which is never greater than 1. While the game never actually shows a hit percentage of greater than 100%, I have actually seen, mutliple times, an assault able to doubleshot with a 100% chance to hit on both shots.

    Take the following example:

    Soldiers aim skill is 85
    Range is 2 tiles +32% range bonus with the assault rifle
    No Cover Bonus for the alien 0%
    No Innate defense bonus for the alien 0%
    Double Shot aim penalty 15%

    85 + 32 – 0 – 0 – 15 = 102% chance to hit.

    In the code, they may or may not truncate that 102 to 100 before the to hit roll comparison is made, but I would guess not. Supposing that the to hit roll was 33: 33 <= 102 evaluates to true just the same as 33 <= 100 so it's a waste of time to code it and a waste of the computers resources to truncate it as well.

  24. [...] more you rely upon randomized results, the more your players will have to engage in analysis like this to understand your game’s mechanics. As developers, that is not what we should expect players [...]

  25. Great write-up, and it characterizes exactly why I don’t like the new XCom and find the original far better. In the original, your shots passed through the space of the game. They might hit trees, parked cars, your own team, etc. You had to reply plan your shots and the layout of the world was actually meaningful. In the new game, it’s just all decoration – when you take a shot the game rolls the dice and you either make the shot or not, even if it’s completely obscured by a brick wall. Combined with the other numerous ways the game has been dumbed down it left me very disappointed.

    • Visually that’s true. Let’s say that the alien is under full cover behind a structure, and your character is at the other end of the same structure on a straight line. What’s supposed to be shown is your character leaning around and shooting at the slightly exposed part of the alien.

      Unfortunately, it frequently displays you shooting through the wall, because it’s picked the center of the alient drawing to hit, rather than say their shoulder. It’s a graphical problem, not actually a game mechanics one… which leaves us with the impression they blasted through a wall when the intent was otherwise.

  26. Interesting. The way I was thinking about it, I just figured you find the sum of both shots’ chances to hit. So, if normal chance = 85%, then (85-15)+(85-15) = 140%. I found it pretty odd that the designers would choose to make Rapid Fire such a no-brainer in almost all situations.

    Feel a bit silly now (my college stats teachers would not be happy..), but I’m glad to see that the method above actually served me pretty well despite being wrong. It still finds a similar floor (30%), and the 96% ceiling isn’t all that relevant.

  27. [...] that the random number generator is cheating after missing an almost certain shot for the nth time. It doesn’t cheat though, but there are other quirks which can seem counter-intuitive at first. First of all, units can [...]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 253 other followers