Source

shlomi-fish-homepage / t2 / MathVentures / 3d_outof_4d.html.wml

#include '../template.wml'

<latemp_subject "Combinatorics and the art of Dungeons and Dragons" />

<p>
I used to play “Advanced Dungeons &amp; Dragons” in the 8th and 9th grades. I
quit, though, but many of my friends continued to play a long time
afterwards. In AD&amp;D (that’s the commonly used acronym for the game’s name),
the amount a character is skilled in certain abilities is determined by a
number ranging from 3 to 18. This number is normally generated by rolling 3
dice and summing up the numbers on their sides. That way, high or low
numbers are considerably less frequent then mid-range ones.
</p>

<p>
Yet, this method, which is highly random, often results that the scores are
unsuitable for what the player planned the character to be or simply too
low. Therefore, there are several alternative methods to generate scores
which are better as far as the player is concerned. One of the common ones,
which is described in the game’s manual goes like that: instead of three
dice, four dice are rolled. Then, the three highest die-scores are summed
and together add up to the ability number.
</p>

<p>
One day, my friend who was a game-master at that time called and asked me if
I could tell him what was the average result which is generated by this
method. I couldn’t tell him right away, but he said that he wrote a computer
program to check it, and it ended up around 12.24 . He went on to say that in
his opinion this average was not too high, so he will probably allow the
members of the new team he was going to lead to use that method.
</p>

<p>
Anyway, he still wondered if anyone could think of a mathematical way to calculate
it. I didn’t know or heard of any at that time so I told him that I didn’t
know. He also said that he asked another acquaintance of us, who already
began his maths studies at the university if he could tell him, but he didn’t
know either.
</p>

<p>
In any case, I thought about it for a while and after a month or so came to a
solution. I presented this problem to other people who seemed interested at
solving maths riddles at various times since. Some of them managed to solve
it, but I didn’t find a more elegant way than what I thought of.
</p>

<p>
Before you see my answer, here is a summary of the problem. You may try to
figure it yourself, before looking at my solution:
</p>

<table border="1">
<tr><td>
<p>
<b>1.</b> Throw 4 dice, sum the numbers they generated and subtract the
lowest value from the sum. (if there is more than one die with the lowest
value, subtract it only once). What is the average number of such throws?
</p>

<p>
More generally, one can ask:
<b>2.</b> Throw n dice, each evenly generating values in the range 1 .. m,
sum them, and subtract the number of the lowest die. What is the average of
the solutions of this throw? (the expression is dependant on n and m.)
</p>

<p>
And yet more generally:
<b>3.</b> Throw n dice each in the range 1..m, sum them and subtract the p
lowest dice (p &lt; n). What is the average outcome of this throw?
</p>

</td></tr>
</table>

<p>
The solution can be found some space below:
</p>

<longblank />

<h2>Solution:</h2>

<p>
Like I said, it did not come to me right away and I had to think about it
for a while. I pondered various methods, and then came to think about the
question this way:
</p>

<p>
In each throw the numbers 1..6 can be subtracted. I first realized that I
could immediately subtract 1 from all 6^4 of the possible throws, because
one always subtract <b>at least</b> 1. Furthermore, when is another 1 point
subtracted from the final sum? Obviously this is the case when 2 or more
points are subtracted. When does it happen? It happens when all the dice
are bigger than 1. (or else 1 would have been subtracted.) Since all the
dice are in the range 2-6 there are 5^4 different possibilities for this
case.
</p>

<p>
The next point is subtracted when all the dice are in the range 3-6, hence
4^4 possibilities and so on. Now, to calculate the total, let’s start from
the sum of all possible throws of 4 dice, without the minimal die removed.
This sum is equal to 6^4 * 14 = 18144. Then, let’s remove 6^4 = 1296 because
of the first point removed, 5^4 because of the second point etc. Eventually
we get:
</p>

<p>
6^4 * 14 - 6^4 - 5^4 - 4^4 - 3^4 - 2^4 - 1^4 = 15869
</p>

<p>
To find the average, all one has to do is divide it by 6^4, which is number
of individual throws. 15869/(6^4) = 12.24, which is also the number that my
friend’s program returned.
</p>

<p>
To generalize it for n dice each having the numbers 1..m on its side (AD&amp;D
also involves using dice with 4, 8, 10,12, 20 and sometimes 100 sides. :-))
all one has to do is replace 6 with n and 4 with m where appropriate. One
should remember that the average throw for an individual die of 1..m is
(1+m)/m and for n such dice n*(1+m)/m. We eventually get to:
</p>

<pre>
( m^n * n * (1+m) / m ) - m^n - (m-1)^n - (m-2)^n - (m-3)^n ... - 1^n
---------------------------------------------------------------------
                              m ^ n
</pre>


<p>
Eliminating the next smallest die, and the other dice in order, is a bit
more tricky. As a matter of fact, it took me two more years to finally come
up with a solution. (not that I spent all my time thinking about it)
</p>

<p>
The basic idea is this: regarding the first point of the second least die,
it’s obvious that we still have to remove 6^4 from the total. About the
second point: it is removed only if all the dice, except maybe one has a
face value of 2 or more. Phrased in a different way it is removed:
</p>

<p>
1. If there are 4 dice in the range 2..6   OR<br />
2. If there are 3 dice in the range 2..6 and one die whose value is 1.
</p>

<p>
The conditions for the other 4 cases are similar: if the additional point
is the Kth than there could be either 4 dice in the range K..6 or 3 dice in
the range K..6 and one die in the range 1..(K-1). To evaluate it
mathematically, I’ll use the standard formulas and eventually get to:
</p>

<pre>
(6-K+1)^4  +  ( (6-K+1)^3 * (K-1) ) * 4
</pre>

<p>
If we subtract 6^4 and those 5 sums from the total sum that was acquired in
the previous stage, we’d get to the new total with the two least dice
removed on each throw. Divide it by the number of throws - 6^4 - and we get
the new average. The grand formula, then, is:
</p>

<pre>
          6            6
6^4*14 - SIGMA(i^4) - SIGMA [(6-i+1)^4 + ( (6-i+1)^3 * (i-1)) * 4 ]
         i=1          i=1
-----------------------------------------------------------------------
                    6^4
</pre>


<p>
From the 3rd least dice onward, this method gets more and more complicated
because we have to consider 3 different cases for every point we
subtract, 4 cases for the fourth die, and so on. If anyone has an idea
on how to improve this method, or can suggest an alternative method
which is simpler as more and more dice are removed by order, please let
me know and I’ll post it here.
</p>

<p>
I, for my part, am no longer interested in this problem, and do not deal
with it, at least not until I extend my knowledge in Combinatorics and the
Theory of Probability.
</p>

<p>
A final note: you can find a C program, not unlike the one my friend used,
that calculates the average of such throws
<a href="calc_dice_average.c">here</a>. It can do that for any number of
dice with any number of sides, and while eliminating any number of minimal
dice.
</p>

<p>
The program is quite stupid and merely iterates over all the
different throws, and adds the sum of every throw to the total. It
becomes less efficient as the number of sides and/or the number of dice
increases.
</p>

<p>
Writing a program that implements my method <b>for any number of removed
dice</b> is a bit complicated because the formula itself gets more and more
complicated. Maybe I’ll get to it one day.
</p>

<h2>Links</h2>

<ul>
<li>
<a href="http://carnalreason.org/2006/07/29/a-mathematical-diversion/">An alternate solution in the Carnal Reason blog</a>
</li>
</ul>