Sunday, December 25, 2016

Cloud Giant Damage

A general method for converting range notation to dice notation.

My first copy of the game was a Holmes edition with geomorphs.

The rules have staying power. This summer I met a Holmes player born after they went out of print!

And so the questions we asked thirty-five years ago are still getting asked. A classic is how to roll the 6–63 damage that cloud giants deal out:


The experienced referee makes this roll with a 3d20+3, but—and this is another example of the ambiguity of range notation—a 19d4-13 will also work.

One wonders whether there are other ways to make the roll. Also, is there an easy way to find those ways?

If we use a single type of die, then we must use a d20 or a d4 as above. If we allow more than one type of die in the roll, then 6d10+d4-1 works.

In fact, if we use more than one type of die, there are 164 ways to roll cloud giant damage.

To find them all, observe a fact about the difference between the largest and smallest value of each die; a d6 produces results in the range 1–6 and has a difference of 5. When multiple dice are summed, the difference of the sum is the sum of the differences of each die used; 2d6 has a range of 2–12 and a difference of 10; 3d6 has a range of 3–18 and a difference of 15.

The rule holds if we use more than one type of die: a d4 has a range of 1–4 and a difference of 3. A d4+d6 roll has a range of 2–10 and a difference of 3 + 5 = 8.

To find out how many ways there are to roll 6–63, we ask ourselves how many ways there are to sum to the difference of 57 given the differences we have available: 3 (d4), 5 (d6), 7 (d8), 9 (d10), 11 (d12), and 19 (d20). This is the unbounded knapsack problem where we are only interested in solutions which fill the "knapsack" completely.

The complete list of ways to roll cloud giant damage is here.

Code for finding ways to roll an arbitrary range is here.

Saturday, December 24, 2016

Binomial Parameter Estimates

More on estimating class qualification probabilities.

Choosing a Character Attribute Generation Method

On p. 11 of the DMG four alternatives for generating character attributes are given. How should a referee decide which one to use?

The referee might have a sense for how easy it should be to roll up a prestige class. Does he want the players all playing paladins and rangers instead of fighters? If so, he should consider the chances listed in the previous post. The 4d6kh3 with re-arrangement method gives the best chances overall.

Did the Designers Know the Odds?

If you asked the designers forty years ago to guess the chance of rolling a paladin, how close would they have been? The calculation requires writing code and running it on a modern computer, so the exact chance was probably unknown in the 1970s. Still, the designers could have made a reasonable guess just by rolling lots of characters.

Monte Carlo Method

To estimate the chance of rolling a class, the designers could have rolled 100 characters and counted how many of them qualified. If 35 of them qualified, the estimated chance is 35%. This is the Monte Carlo method applied to the binomial parameter estimation problem.

The Monte Carlo method is slick! It is easy to understand. Complicated mathematics is avoided.

Monte Carlo can be used to verify complicated mathematics. After writing code to do the exact calculation, I wrote code which uses Monte Carlo to make sure the exact code is in the right ballpark.

Often it isn't enough to get an estimate; we also have specify how accurate it is. We can increase our accuracy by doing more rolls. For example, we will get a better estimate of the chance of a paladin if we roll 1000 characters instead of 100 characters. It is natural to ask how many characters must we roll to get an answer which is accurate enough for our purpose.

Normal Approximation Interval

One way to represent the accuracy of an estimate is with a confidence interval. For binomial parameter estimation, one way to get a confidence interval is with the normal approximation:
$$p \pm z_{1 - \frac{α}{2}} \sqrt{\frac{p \cdot (1 - p)}{n}}$$Here n is the number of characters generated, p is the observed fraction, and α is the chance of being outside the confidence interval. When α is 5%, z1-α/2 is 1.96.  In R one can compute z1-α/2 with

  qnorm(1-alpha/2)

The normal approximation suggests that if we increase the number of simulations 10-fold, the length of the confidence interval will shrink to about 0.32 of its previous size.

The normal approximation doesn't work well when the observed fraction p is close to zero or 1.  For example, when n is 100 and p is .01, the 95% confidence interval is [-.95%, 2.95%] even though we know a negative value is not possible. This is a consequence of using the normal distribution as an approximation for a distribution with non-negative support.

In the extreme cases where p is exactly 0 or 1, the normal approximation gives an obviously invalid interval with zero length. The usual advice is to never use the normal approximation when there are fewer than 5 successes or 5 failures. That is, there should be at least 5 characters which qualify as a paladin and 5 characters which don't.

Wilson Score Interval

At the cost of some extra complexity, there is a formula which works better when p is near zero or one:
$$\frac{1}{1 + \frac{1}{n}z_{1-α/2}^2} \bigg[p + \frac{1}{2n} z_{1-α/2}^2 \pm z \sqrt{\frac{1}{n} p (1 - p) + \frac{1}{4n^2} z_{1-α/2}^2}  \bigg]$$

Beta Distribution

We can look for a distribution which describes the possibilities for the parameter we are estimating. This is more informative than a confidence interval. Bayesian statistics gives us a way to do this, but we must start with an initial distribution, the prior, which is somewhat arbitrarily chosen. We use the data we observe and the prior to compute the posterior distribution, which is the distribution we seek.

When estimating a binomial parameter, the beta distribution is convenient because it makes computation of the posterior easy. The beta distribution has two parameters. If the prior has parameters α and β and we observe m successes in n trials, then the posterior is a beta distribution with parameters α + m and β + n - m. We can think of the parameters as tallies of the number of successes and failures we observe.

How should α and β be chosen for the prior? If we set them both to 1, then the prior is identical to the uniform distribution. That is, we are saying that before we look at the data we think each possible value for the parameter is equally likely. For those who know information theory, the beta distribution with parameters (1, 1) is the beta distribution with highest entropy. Such a prior, incidentally, was how Laplace solved the sunrise problem.

Suppose we decide to start with a beta (1, 1) prior. We roll 100 characters and 35 of them qualify. Then the posterior parameters are (36, 66). We can use R to compute the chance the actual probability is within any interval. For example that chance that the true probability is inside [.32, .38] is 47.4%:

  > pbeta(.38, 36, 66) - pbeta(.32, 36, 66)
  [1] 0.4739478

If we think we already know the mean and variance for the distribution, we can use them to set the parameters of the prior. Here is how to use Mathematica and the formulas for the mean and variance to solve for the parameters:

  Solve[{μ == α/(α+β),
         σ^2 == α β/((α+β)^2 * (α+β+1))},
        {α,β}]

Here are the formulas for the parameters, given mean μ and variance σ2:
$$α = \frac{μ^2 - μ^3 - μ σ^2}{σ^2}$$ $$β  = \frac{(-1 + μ) (-μ + μ^2 + σ^2)}{σ^2}$$

Hoeffding's Inequality

Hoeffding's Inequality is invaluable when doing Monte Carlo estimates. It directly tells us how much data we need to ensure our estimate is near the true value with a given probability:
$$ \mathrm{P}\big(\big|p - \mathrm{E}[p]\big| \geq t\big) \leq 2 e^{-2nt^2}$$
Here p is the estimate, E[p] is the true value, t is half the length of our confidence interval, and n is the number of observations. If we know the probability and interval we want, we recast the inequality as:
$$ \frac{\mathrm{ln} \frac{2}{\mathrm{P}(|p - \mathrm{E}[p]| \geq t)}}{2 t^2} \leq n$$ If we want to be 95% certain the estimate is within a tenth of a percent, we get this lower bound on n:
$$ \frac{\mathrm{ln} \frac{2}{.05}}{2(0.001)^2} \approx 9.22 \times 10^5 \leq n$$ The number might seem discouragingly large, but generating a million characters is feasible on modern computers; just write code to do it!

Friday, December 16, 2016

Chance of Rolling a Class

e.g. how hard is it to roll up a paladin?

It's an obvious question. What is the chance of rolling a character that qualifies for a given class?

Minimum Attributes

The chance depends on the minimum attributes for the class. Let's use the first edition values:

minimum attributes per Players Handbook (1978)

            Str Int Wis Dex Con Char
cleric:       3   3   9   3   3   3
druid:        3   3  12   3   3  15
fighter:      9   3   3   3   7   3
paladin:     12   9  13   3   9  17
ranger:      13  13  14   3  14   3
magic-user:   3   9   3   6   3   3
illusionist:  3  15   3  16   3   3
thief:        3   3   3   9   3   3
assassin:    12  11   3  12   3   3
monk:        15   3  15  15  11   3
bard:        15  12  15  15  10  15 

Odds by Class: 3d6

The original method of rolling up attributes is to use 3d6 for each attribute. The attributes are generated in the order of strength, intelligence, wisdom, dexterity, constitution, and charisma. No rearrangement is allowed.

The odds of a character qualifying for a given class by this method are:

  assassin:      7.031%
  bard:          0.002%
  cleric:       74.074%
  druid:         3.472%
  fighter:      67.215%
  illusionist:   0.429%
  magic-user:   70.645%
  monk:          0.040%
  paladin:       0.099%
  ranger:        0.176%
  thief:        74.074%

We knew that rolling up a paladin was a long shot, but rolling up a monk is harder still. Your chance of rolling up a bard are 1 in 58,140.

Odds by Class: DMG Methods

Some prestige classes might seem pointless, given how unlikely it is to roll a character that qualifies to be one. However, the DMG allows, at referee discretion, one of four methods for rolling attributes, each producing higher attributes on average. For example, in method I the player rolls the six attributes with 4d6kh3 and then rearranges the attributes as desired.

The chances of rolling up a character according to these four methods are:

  (METHOD I) 4d6kh3 PLAYER-ARRANGED:
  assassin:      93.616%
  bard:           1.581%
  cleric:       100.000%
  druid:         78.245%
  fighter:      100.000%
  illusionist:   35.782%
  magic-user:   100.000%
  monk:          13.641%
  paladin:       25.169%
  ranger:        30.470%
  thief:        100.000%

  (METHOD II)  3d6 BEST-OF-12 PLAYER-ARRANGED:
  assassin:      96.180%
  bard:           1.887%
  cleric:       100.000%
  druid:         68.206%
  fighter:      100.000%
  illusionist:   24.302%
  magic-user:   100.000%
  monk:           9.231%
  paladin:       18.704%
  ranger:        33.984%
  thief:        100.000%

  (METHOD III) 3d6 BEST-OF-6 EACH ATTRIBUTE:
  assassin:      87.053%
  bard:           3.572%
  cleric:        99.970%
  druid:         41.544%
  fighter:       99.970%
  illusionist:   10.936%
  magic-user:    99.970%
  monk:           8.487%
  paladin:        8.324%
  ranger:        29.788%
  thief:         99.970%

  (METHOD IV) BEST-OF-12-CHARACTERS 3d6:
  assassin:      58.309%
  bard:           0.021%
  cleric:       100.000%
  druid:         34.562%
  fighter:      100.000%
  illusionist:    5.024%
  magic-user:   100.000%
  monk:           0.475%
  paladin:        1.179%
  ranger:         2.097%
  thief:        100.000%

Overall, method I is the best, though method II is best for an assassin or ranger and method III is best for a bard.

Code

The code for calculating the probabilities is on GitHub.

Sunday, December 11, 2016

The Arch-Mage Casts a Fireball

Fireball damage: its calculation and its distribution.

The spell components are ready:


This is what the game is about. I cast the spell:


Look at all the damage! But how much damage, exactly? My enthusiasm is tempered by the prospect of adding up the pips.

Fortunately, as a wizard I am familiar with the arcane rule of tens. Prestidigitation ensues and the hidden number is revealed:


Apropos of nothing, I timed myself on a few more rolls:
  • 65 hit points: 22.2s
  • 63 hit points: 19.6s
  • 56 hit points: 28.3s
  • 63 hit points: 28.3s
  • 62 hit points: 24.9s
An average of 24.7s spent to get a number that was usually within a couple hit points of 63.

A Shortcut?

When younger I was tempted to roll a single d6, multiply it by 18, and be done with it. That is, use a d6 × 18 roll in place of the 18d6. However, even then I couldn't escape the feeling that this was not an equivalent roll. I could see that the latter method always produces a multiple of 18, but I wondered if it wasn't close enough all the same.

Both methods cause 63 hit points of damage on average, so in that respect they are the same. But if the mean is all we care about, why roll dice at all?

Plotting the probability mass distributions is a good way to show how different rolls are. Here the 18d6 distribution is in red and the d6 × 18 distribution is in blue:
The standard deviations are 7.2 and 30.7, a large difference.

Chebyshev's Inequality

At this point, I'm going digress in an attempt to make the standard deviation seem useful.

According to Chebyshev's inequality, the chance of being more than k standard deviations from the mean can never be greater than 1/k2. Thus, in the case of the 18d6 distribution, the chance the value is less than 49 or more than 77 is no more than 25%. The same probability for the d6 × 18 distribution is 66⅔%.

Chebyshev's inequality is a rough upper bound that works for any distribution for which we know the mean and standard deviation. If we know the distribution, we can do a summation or integration to get the exact probability; for the 18d6 distribution the exact probability is less than 5%.

A Better Shortcut?

Back to rolling fireball damage.

What if we allow two rolls of a d6? I wrote some code which searches for an expression with the same mean and the nearest standard deviation. To keep things simple the first d6 always gets multiplied by a non-negative integer and the second d6 is taken as is. With those constraints here are the best approximations:

   1d6: d6 × 0 + d6 +  0
   2d6: d6 × 1 + d6 +  0
   3d6: d6 × 0 + d6 +  7
   4d6: d6 × 1 + d6 +  7
   5d6: d6 × 2 + d6 +  7
   6d6: d6 × 1 + d6 + 14
   7d6: d6 × 2 + d6 + 14
   8d6: d6 × 3 + d6 + 14
   9d6: d6 × 2 + d6 + 21
  10d6: d6 × 3 + d6 + 21
  11d6: d6 × 2 + d6 + 28
  12d6: d6 × 3 + d6 + 28
  13d6: d6 × 4 + d6 + 28
  14d6: d6 × 3 + d6 + 35
  15d6: d6 × 4 + d6 + 35
  16d6: d6 × 3 + d6 + 42
  17d6: d6 × 4 + d6 + 42
  18d6: d6 × 3 + d6 + 49
  19d6: d6 × 4 + d6 + 49
  20d6: d6 × 5 + d6 + 49
  21d6: d6 × 4 + d6 + 56
  22d6: d6 × 5 + d6 + 56
  23d6: d6 × 4 + d6 + 63
  24d6: d6 × 5 + d6 + 63

Here is how well the approximation works for the arch-mage; the 18d6 distribution is in red and the d6×3 + d6 + 49 in blue:

Wednesday, December 7, 2016

A Nod to the Original Dice

We've been running a campaign using the Holmes rules for several years now. I've put some effort into getting the feel right.

An important touch is the dice. I have a few sets of the Creative Publications dice, but I don't want to use them and wear them out!

Here's what I've been able to put together in the way of a proxy:

Sunday, December 4, 2016

Dice Notation

What our group sees as the essentials of dice notation.

Here are examples of dice notation: d4, d6, d8, d10, d12, and d20.

The notation refers to a die, but more often a roll of a die. The rules might say that a weapon causes d8 of damage, which is equivalent to saying it does 1–8 hit points of damage.

The notation has been extended in a couple of ways: 3d6 means to roll three 6-sided dice and sum them, generating a number in the range 3–18. 1d4+1 means to roll one 4-sided die and add one to it, generating a number in the range 2–5.

The Introduction of Dice Notation

The notation isn't used in the original box set or the Monster Manual.

The Players Handbook (June 1978) was the first TSR publication to use it. Jon Peterson suggests the PHB was written as if players were already familiar with the notation, but the occurrences I've found are used in a parenthetical manner. For example, consider this spell description:
A fireball is an explosive burst of flame, which detonates with a low roar, and delivers damage proportionate to the level of the magic-user who cast it, i.e. 1 six-sided die (d6) for each level of experience of the spell caster. Exception: Magic fireball wands deliver 6 die fireballs (6d6), magic staves with this capability deliver 8 die fireballs, and scroll spells of this type deliver a fireball of from 5 to 10 dice (d6 + 4) of damage.
The November 1978 printing of the Holmes rulebook appends the following text:
In some places the reader will note an abbreviated notation for the type of die has been used. The first number is the number of dice used, the letter "d" appears, and the last number is the type of dice used. Thus, "2d4" would mean that two 4-sided dice would be thrown (or one 4-sided would be thrown twice); "3d12" would indicate that three 12-sided dice are used, and so on.
The blurb suggests that dice notation is used elsewhere in the Holmes rulebook, but it isn't!

The Dungeon Masters Guide (August 1979) also explains the notation:
Before any further discussion takes place, let us define the accepted abbreviations for the various dice. A die is symbolized by "d", and its number of sides is shown immediately thereafter. A six-sided die is therefore "d6", d8 is an eight-sided die, and so on. Two four-sided dice are expressed by 2d4, five eight-side dice are 5d8, etc. Any additions to or subtractions from the die or dice are expressed after the identification, thus: d8 + 8 means a linear number grouping between 9 and 16, while 3d6 - 2 means a bell-shaped progression from 1 to 16, with the greatest probability group in the middle (8, 9). This latter progression has the same median numbers as 2d6, but it has higher and lower ends and a greater probability of a median number than if 2d12 were used. When percentage dice are to be used, this is indicated by d%.
As Jon Peterson has discussed, essentially the same notation, albeit with a capital D, was being used in the fanzines for several years before TSR embraced it. It appears, amazingly, in the first issue of Alarums & Excursions from 1975.

The Old Notation Isn't Good Enough

Looking through the older texts, you can see a couple of different ways for specifying dice rolls: "5 + 1", "3-8 sided", and "2–24".

This notation is inferior in various ways. The first doesn't make clear which die to use: a 5d6+1 roll is intended. Of course, ambiguity can sometimes be advantageous. The way hit dice are specified in the Monster Manual might have made the book more appealing to players still using d6 hit dice for monsters.

The third example, range notation, looks like a concise way to specify rolls, but it also can be ambiguous. For example, 3–12 can be either d10+2 or 3d4. The first method is uniform, whereas the second starts to approximate a bell curve.  If you roll it the first way, the chance of getting a 3 is 10%; if you roll it the second way the chance of getting a 3 is 1 in 64 or about 1.6%.

3–12 is the smallest range which can be ambiguous, and it is used in the PHB! A bardiche inflicts 3–12 hit points of damage on large opponents.

The New Notation Isn't Good Enough

On p. 10 the DMG explains dice notation and on the following page it describes a method for rolling attribute scores which can't be expressed with that dice notation: rolling 4d6 and dropping the lowest die!

The site roll20.net has some notation for this. The roll can be written as 4d6d1 to indicate the lowest die is dropped, or 4d6k3 to indicate the highest three dice are kept.

There is alternate notation which make it explicit that the lowest die is dropped: 4d6dl1 and the highest three dice are kept: 4d6kh3.  One could call for the highest die to be dropped: 4d6dh1 or the lowest three dice are kept: 4d6kl3.

The lowercase L seems like an opportunity for confusion with a numeral one, so we just use 4d6kh3 for a 3d6 with negative skew and 4d6dh1 for a 3d6 with positive skew.

Code

We don't like laptops, ipads, or even phones at the table. Nevertheless it was convenient to implement a command line tool which understands dice notation—including the "keep high" and "drop high" extensions:

  $ roll 6d6
  16
  
  $ for i in $(seq 1 6); do roll 4d6kh3; done 
  14
  8
  7
  14
  15
  10

The code is on GitHub.

Factor Rolls

One can use the dice to generate other ranges of integers:

1–2  ⌈d6/3⌉
1–3  ⌈d6/2⌉
1–5  ⌈d20/4⌉
1–10 ⌈d20/2⌉

In case the notation on the right is not clear, one rolls the indicated die, divides by the following number, and then rounds up. The most practical notation is d2, d3, d5, d10. I'm not aware of a standard term for this type of roll; we've been calling them factor rolls.

Product Rolls

Percentile dice are an example of what we've been calling a product roll. We could use two d6 to create a d36, for example. This is not multiplication, but more like working with base 6 numbers. The percentile dice make the process easier by using zeros and distinguishing the tens die from the ones die. One formula for getting a range 1–36 is

    6×(d6 - 1) + d6

Dice of different colors are needed for a product roll. Our convention is to use a white die for the ones die. If dice of different colors are not available, a single roll is not possible; roll the most significant die first.

The dice do not have to have the same number of faces. If you wanted the use the 30 sided dice gaming tables published by the armory, you could generate d30 rolls with a d6 and a d10.

If factor rolls and product rolls are allowed, then the only numbers we cannot generate are ones containing a prime larger than 5 as a factor.

Re-rolling

Thus there is no way to generate d7 uniformly using a single roll. One could roll a d8 and re-roll if the result is 8.  Simply writing d7 is the best notation.

Seven sided dice have been manufactured. One design is a pentagonal prism, and another "is based on spacing points as equally as possible on a sphere and then cutting planar slices perpendicular to those directions."  It would be interesting to test these dice and see whether the distribution is uniform.