Obscure details in d20

I was wondering, what’s the probability that you’ll land AT LEAST some number of hits in d20. Turns out, it’s a lot easier to ask the question than to answer it. Start with at least 1 hit…easy enough:

P(at least 1 hit) = 1- P(all misses) = 1 – ∏_i(1 – P_i(hit))

That was so easy! Plus, it makes it super duper easy to calculate P(at least 2 hits):

P(at least 2 hits) = P(1 hit) × (1 – P(all the rest misses)) = ∑_iP(hit)×[1 - ∏_j≠i(1-P_j(hit))]

And so on, until you exhaust all of your BAB-(5 per swing), at which point you get

P(all hit) = ∏_iP_i(hit)

Which is again easy. So, computing that stuff is very time consuming, but straightforward. It’s not as bad as it could be, though, because your max hit chance is P(hit) = .95, and min is P(hit) = .05, and at -0.25 per swing, you’ll only have at most 6 distinct P_i(hit), including several easy swings at P(hit) = .95 and hard swings at P(hit) = .05, at one each of the other 4. So if you get many many attacks per round, many of the terms in those sums will be identical. Maybe I’ll write a program to compute these things, maybe I’ll work out a rough approximation that’ll be easier to compute. /shrug

Mass Effect on PC…

But will it work on my PC, I wonder. I’ve been quite a fan of Bioware’s games in the past, so I’ll give it a shot one of these days.

DPS in d20

Damage per combat round in d20 almost looks simple, until you know the rules. Which I don’t, thankfully. However, I know some of the rules of the Neverwinter Nights games, which while simpler than the pen and paper version of D&D, are still pretty arcane. But in a nutshell, what we need to know to calculate DPR(ound) is that you get one attack per round, plus one for every 5 points of BAB above 1. So you get 2 attacks for BAB on [6,10], 3 if BABε[11,15], and so on. Each additional attack has an additional -5 penalty to the to-hit roll, i.e. -5 on the second hit, -10 on third hit, -15 on 4th hit and so on. So if you like, you get to keep attacking at -5 more per attack until your remaining BAB is 0, at which point you can’t attack any more. You may also get off-hand weapon attacks, which are penalized in a complicated way depending on various feats you’ve earned and the size of the weapon you’re wielding in the off-hand. It can go from -6 main hand, -10 off hand to -2 each hand in; getting from the worst case to the best takes one more feat in NWN than in NWN2. Additional off-hand attacks will cost more feats.

Once we know all that, we can describe the chance to hit a target as:

P(hit|on the s^th swing) = min[19/20, max(1/20, 20 + (∑ to hit bonuses and penalties) - AC - 5s)]

for main hand attacks. Then add those up over the S = int[BAB-1/5]+1 swings, and you’re set! Putting that together with the expected damage calculation from last post, it looks like:

DPR = d ∑_BAB-5s>0 {min[19/20, max(1/20, 20 + (bonuses and penalties) - AC - 5s)]×[1 + (n-1)×min(w/20, P(hit|s^th swing)]}

not accounting for feats like power critical (+4 to confirm critical) and so on. Adding in additional damage from extra attacks is straightforward.

Of course, we probably don’t care in particular how we’ll do against opponents with a specific value of armor class, and would like a measure of our effectiveness overall. Well, if you want, you can average that beast above over all armor classes, 1-∞…or up to some reasonable number, say 1-your character level, or character level +20, or something, depending on your environment. Of course, that’s overkill…there is a built in cut-off point, any AC > 19 more than your BAB+bonuses you’ll only hit on on a roll of 20, so you don’t need to give extra consideration to AC > 20 more than BAB+bonuses. Similarly, but more complicatedly, any AC < BAB – 5S will be hit on all but a roll of 20 (on every attack in a round), although you might allow some slack for those awful occasions when you’re debuffed by an enemy spell. Ideally, if you can assign a reasonable estimate, you could weight each AC by the likelihood of encountering that AC, like so:

<DPR> = ∑_AC P(AC) DPR_AC

and even better, would be to weight it not just by probability of encountering that particular AC but also by the threat that an opponent with that AC represents. That is, an opponent with an AC of 8 is likely a level 1 pauper who can’t afford any armor, and probably can’t afford anything deadlier than a stout cudgel (i. e. broken table leg), and will barely be able to touch your level 18 weapon master in enchanted plate armor let, so do you really need to worry about taking him out as fast as mathematically possible? So the best calculation we can do is probably something like:

<ΘDPR> = ∑_AC <Θ>_ACP(AC) DPR_AC

where Θ is the measure of the threat that the target represents, which I will talk about in a future post.

Anyway, short of being able to put all that information together, I recommend plotting your expected damage out in a spreadsheet. Maybe I just suck with spreadsheets, but the use of the min and max functions seems to me to make it a pretty cumbersome thing to enter into the spreadsheet…the contents of the cells won’t vary in an orderly way.

Critical Hits in d20

Since of course there’s nothing more important to write about, such as states full of people who’d refuse to nominate a black HARVARD LAW GRADUATE for President of the United States just because he’s black (and therefore inferior to all the white people who’ve GRADUATED FROM HARVARD LAW SCHOOL magna cum laude–oh, well there ya go, a white person would’a graduated suma…)

Anyway, since there’s nothing like that to blog about this week, I’ll move on to how to weigh critical hit properties of weapons in d20. Is a broader threat range better or a higher multiplier? I’ll denote critical hit properties in d20 like so:

{w|×n}

where w is the width of the threat range, such as 18-20, 19-20, or just 20, and n is the threat multiplier. The threat chance is the width of the threat range divide by 20, or the chance to hit–whichever is smaller. Once you roll a critical threat, you roll d20 again to “confirm” the critical, with the goal to simply roll a hit this time. If you fail this roll, you hit the target, but don’t get the critical multiplier to your damage. Therefore, the expected damage on an attack looks like:

<D> = ∑ P(D) × D = d×P(regular hit) + nd×P(crit) = d[P(hit) - P(threat) + P(threat)P(miss) + nP(threat)P(hit)]

= d×P(hit)[ 1 + (n - 1) P(threat) ]

where d is the expected value of the damage roll, d = (min damage + max damage)/2, and P(threat) = w/20 (or hit probability if it’s lower) is the probability of rolling a critical threat. Note that for typical threat ranges (19-20 for sword, 20 for axe) and multipliers (2 for sword, 3 for axe), you get about 10% of your damage from critical hits; while with some feats, keen weapons, weapon master perks, it might get up to 20% or more (unless you fight a lot of undead, etc. with critical hit immunity).

So, we have

(1/d×P(hit))<D+> = w(n-1)/20

(1/d×P(hit))Δ<D> = [w/20] × Δn

(1/d×P(hit))Δ<D> = [(n-1)/20] × Δw

with <D+> the extra damage that comes from critical hits, which depends on 1 less than n because you were going to do some damage anyway. When weighing critical hit properties, you are mostly concerned about the product (width of threat range)×(crit multiplier – 1). A sword with {19-20|×2} is worth 2×1=2, an axe with {20|3} is worth 1×2=2, and a falchion with {18-20|×2} is the same as a scythe with {20|×4}, both equal 1.5. Keen weapon or improved critical both double the threat range, which doubles the value of critical hits. Adding one the the critical damage multiplier doubles the value of a sword, but only increases the value of a scythe by 1/3.

The exception is if you expect to be fighting enemies with ACs so high you’ll only hit them on rolls of 20, or if you are acquiring feats or magic weapons that give extra damage on critical hits. Extra critical threat range is just wasted in that situation. Also, since you’ll rarely hit such a beast, you’ll want to get the most out of every hit. Therefore, the scythe, if available, is the way to go…except that really, you’ll only be hitting one in every 20 swings, and critical hitting one in every 400 swings, so maybe you should just run in that situation. Except that, of course, advancing the plot probably depends on winning the fight, and the designers have probably locked you in a room with him. /sigh

Anyway, there are some annoying discrepancies in my notation, which I’ll straighten out in a future edit.

Hitting a Target in d20

In the current (version 3.5, anyway, I think ver. 4 is out now) edition of Dungeons & Dragons, hitting (or missing) a target is pretty easy. It is, after all, meant to be done by people playing on a tabletop with dice, a pencil, and paper…not necessarily on a 3GHz microprocessor pushing a few billion floating point operations per second. So all you do is roll a 20 sided die, you always miss on a 1, always hit on a 20*, and otherwise, if your hit roll plus “base attack bonus(BAB)” ± other modifiers is greater than your target’s Armor Class (AC), you hit your target! The BAB depends on your character’s class and level, you’ll look it up in a table. Other modifiers are any applicable strength or dexterity bonuses, weapon enchantment bonuses, buffs or debuffs, and about a hundred other details in the D&D rules. Armor class depends on the type of armor, be it plate armor, chain mail, leather, whatever, and dexterity (for dodging), and some other things. Thus, the basic probability of a hit is

P(scoring a hit) = {MIN[19/20, MAX(1/20, (20 + BAB + to-hit modifiers - AC)/20)]}

All very linear and easy, no squaring, no roots, no exponentials. Yawn.

However, just to spice things up, Wizards of the Coast have also allowed you to roll a “critical hit (or crit, for short).” On a crit, your damage is multiplied by two, three, or more depending on the type of weapon you’re weilding and your proficiency with that weapon, as described by “feats” you have acquired. To roll a crit under the v. 3.5 rules, you must roll high enough to hit (including modifiers), and the number on the face of the d20 must be within the “critical threat range” of the weapon you’re swinging: 20 for a battle ax, 19-20 for most swords, and 18-20 for weapons such as scimitars. However, after rolling (a hit) within the critical threat range, you must then roll the d20 again, with the same modifiers (you may have a feat that gives an extra bonus to this roll), and score a hit. Failing this second roll still results in a hit, but not a critical hit. So, the probability of a critical hit given that you’ve rolled a critical threat is:

P(crit hit|crit threat) = P(scoring a hit)

or, with the aforementioned feat (Power Critical, gives +4 bonus to hit on this roll with a specific weapon)

P(crit hit|crit threat with power critical feat) = P(scoring a hit) + 4/20 (for 2/20 < P(scoring a hit) < 16/20)

The probability at the ends is still capped at 1/20 to miss and 1/20 to hit.

Thus,

P(crit) = .05×MIN(threat range, hit chance) × P(scoring a hit)

without Power Critical and

P(crit with power critical) = .05×MIN[threat range, hit chance] × [P(scoring a hit) + .2] .2 < P(scoring a hit) < .8

Now, what’s the chance of scoring a regular hit, but not a crit?

P(regular hit) = P(scoring a hit) – P(crit) = 1 – P(crit) – P(miss)

That’s straightforward enough.

Now that we can hit a target, which is worth more? A more damaging crit (higher crit multiplier) or a more accurate crit (broader threat range/power critical)? I’ll look at that next time.

*If for some reason you can’t see your target, say cuz your character is blinded or the target is invisible, there will be another d100 roll against a concealment percentage.

Hitting a Target: Overview

Video game combat broadly comes in two flavors: real-time action, or turn-based. The first category includes first person shooters, arcade games, dogfighting games, (hand-to-hand) fighting games, etc., in which a player uses hand-eye coordination to, say, keeping a targeting cursor over the enemy is determines whether you hit or not. The second category includes strategy games, like Civilization, traditional role-playing games like Final Fantasies I through X, and so on, where hitting the target depends on a character’s or unit’s statistics and usually a digital die throw. Hybrid systems are also widely used in MMORPGs like Everquest, World of Warcraft, and offline games including RTSs and TES3: Morrowind, or Fallout: Tactics. We can model the chance to hit a target for any type of game.*

A good to-hit model of an action game might include the size (or cross section) of the target, distance to the target, projectile speed, the “spread” or recoil of shots, target speed, cursor speed, player reaction time, and the time the target is vulnerable (for instance, the time it takes a target to move from cover to cover).

For a turn based game, a to-hit probability can usually be read off a character sheet, or maybe a table in a D&D instruction manual. That probability will usually be modified by a target’s “dodge” chance, or something like that. Often, there is a chance to land a critical hit, as well as more complicated and idiosyncratic results that depend on the game. Usually, you can find rules for a game online, but sometimes it may take some experimentation. D&D makes it easy, since the rules are available in great detail on-line or in bookstores, and the documentation that comes with the computer games is also pretty detailed. However, NWN does have some quirks that don’t apply to the pen and paper version.

Hit probabilities for hybrid games will typically involve a convolution of the calculations for action and turn-based games.

*Fighting game mechanics are exquisitely complicated, and I don’t have any plans at present to talk about them in detail.

Basics of DPS

Roughly, a video game warrior’s threat can be described by it’s ability to output damage (dps) and it’s ability take damage (total hitpoints, adjusted for armor and resistances, depending on the game and situation). Let’s parse dps:

The simplest measure of dps is average damage per attack times number of attacks opportunities per unit time. In a first person shooter, that might be

dps = (rate of fire) x (damage per shot)

In a Dungeons & Dragons game, like Neverwinter Nights 2, a fighter could expect something like

average damage per attack = d = (max damage) + (min damage)2 + (str bonus) + (other modifiers)

damage per round = d x (number of attacks per round)

= d x {1 + int([BAB-1]/5)}

= d x {1 + int([level-1]/5)}

In MMOs I’ve played, including WoW, Star Wars Galaxies*, Pirates of the Burning Sea, and maybe EVE Online,

dps = (average attack damage)/(attack speed)

because for some odd reason, attack “speed” in those games is actually the time between attacks, or the attack period, instead of the rate of attack, like “speed” would mean in the rest of the world.

These numbers can be useful for comparing small tweaks among similar characters, but they aren’t realistic approximations of the actual dps you’d see while you’re playing a game. First, of course, you have to actually hit your target, and these formulas don’t account for accuracy**. Then, some games award extra dps for critical hits or head shots. There are also area effect attacks, situational bonuses (like sneak attacks and backstabs), debuffing attacks that do less damage but tilt the battle in other ways, etc. Which is good, because if video games could be distilled to such simple equations, they wouldn’t be any fun.

*mathematically, this was the most muddled and egregiously unbalanced game I’ve ever seen. SOE has changed the rules drastically since I played, hopefully for the better.

**formulas accounting for accuracy will get pretty monstrous, of course