Combinatorics and the art of Dungeons and Dragons
I used to play "Advanced Dungeons & Dragons" in the 8th and 9th grades. I quit, though, but many of my friends continued to play a long time afterwards. In AD&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.
Yet, this method, which is highly random, often results that the scores are insuitable 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 concerened. 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.
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.
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 acquaintant of us, who already began his math studies at the university if he could tell him, but he didn't know either.
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 math 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.
Before you see my answer, here is a summary of the problem. You may try to figure it yourself, before looking at my solution:
|
1. Throw 4 dice, sum the numbers they generated and substract the lowest value from the sum. (if there is more than one die with the lowest value, substract it only once). What is the average number of such throws? More generally, one can ask: 2. Throw n dice, each evenly generating values in the range 1 .. m, sum them, and substract the number of the lowest die. What is the average of the solutions of this throw? (the expression is dependant on n and m.) And yet more generally: 3. Throw n dice each in the range 1..m, sum them and substract the p lowest dice (p < n). What is the average outcome of this throw? |
The solution can be found some space below:
Solution:
Like I said, it did not come to be 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:
In each throw the numbers 1..6 can be substracted. I first realized that I could immidiately substract 1 from all 6^4 of the possible throws, because one always substract at least 1. Furthermore, when is another 1 point substracted from the final sum? Obviously this is the case when 2 or more points are substracted. When does it happen? It happens when all the dice are bigger than 1. (or else 1 would have been substracted.) Since all the dice are in the range 2-6 there are 5^4 different possibilities for this case.
The next point is substracted 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:
6^4 * 14 - 6^4 - 5^4 - 4^4 - 3^4 - 2^4 - 1^4 = 15869
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.
To generalize it for n dice each having the numbers 1..m on its side (AD&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:
( m^n * n * (1+m) / m ) - m^n - (m-1)^n - (m-2)^n - (m-3)^n ... - 1^n
---------------------------------------------------------------------
m ^ n
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)
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:
1. If there are 4 dice in the range 2..6 OR
2. If there are 3 dice in the range 2..6 and one die whose value is 1.
The conditions for the other 4 cases are similiar: 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:
(6-K+1)^4 + ( (6-K+1)^3 * (K-1) ) * 4
If we substract 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:
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
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 substract, 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.
I, for my part, am no longer interested in this problem, and do not deal with it, at least not until I extend my knowldege in Combinatorics and the Theory of Probability.
A final note: you can find a C program, not unlike the one my friend used, that calculates the average of such throws here. It can do that for any number of dice with any number of sides, and while eliminating any number of minimal dice.
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.
Writing a program that implements my method for any number of removed dice is a bit complicated because the formula itself gets more and more complicated. Maybe I'll get to it one day.
Links
Back to the Math-Ventures Web page
