How can I calculate 'advantage' and 'disadvantage' when multiple dice are included. For example:
I'm looking for a general formula, so that I can calculate: [highest x out of n y-sided dice] and [lowest x out of n y-sided dice]?
How do I calculate this? (not in a Python, etc. script, but in math.)
For the most part, AnyDice operates by enumerating all possible multisets that could come out of a pool of dice. For \$n\$ dice of \$y\$ sides each, the number of possible multisets is
$$\binom{n + y - 1}{n}$$
which is considerably faster than the \$y^n\$ possibilities if we were to enumerate the product of all the individual die rolls.
An example of how multiset enumeration could be implemented is given in the documentation for Python's itertools.combinations_with_replacement():
def combinations_with_replacement(iterable, r):
# combinations_with_replacement('ABC', 2) --> AA AB AC BB BC CC
pool = tuple(iterable)
n = len(pool)
if not n and r:
return
indices = [0] * r
yield tuple(pool[i] for i in indices)
while True:
for i in reversed(range(r)):
if indices[i] != n - 1:
break
else:
return
indices[i:] = [indices[i] + 1] * (r - i)
yield tuple(pool[i] for i in indices)
Each multiset should then be weighted according to the multinomial distribution, which also lets us account for dice that are not uniformly weighted, such as ability score distribution in D&D.
Multiset enumeration is easy to use since we can see the entire sequence of sorted rolls, and it's fast enough for most cases on the tabletop. However, it can struggle with large numbers of many-sided or exploding dice such as classic Legend of the Five Rings. The 5-second limit tops out for [highest 1 of Nd20] for N between 8 and 9, or between 4.5 and 7 million possibilities. Opposed pools where the pools can't be considered separately are also challenging since we need to consider the product of possibilities of each pool; for a RISK-like mechanic, AnyDice times out on 4d6 vs. 4d6.
Wikipedia has an explicit formula (permalink) for extracting a single ranked die from a pool, which computes the same result as AnyDice's @ operator with a single index. This is formally known as an order statistic. There are also formulas for joint order statistics (i.e. selecting multiple indexes at a time), but these get complicated quickly -- and once more than a few dice are kept, not especially computationally efficient either.
That the sum of a set of dice can be computed via convolution is a classical result in discrete statistics. Convolution (sometimes also framed in terms of generating functions) allows us to use the fantastically efficient fast Fourier transform (FFT). With some more work, FFTs can also be used the case where only some of the dice are kept. Approaches of this type have been proposed on StackExchange, with examples including:
However, my preferred approach is dynamic programming (sometimes also framed in terms of recurrence relations). Examples include:
The short of it is that we compute the answer to the problem to "roll \$n\$ d20, keep \$x\$" by considering how many dice \$k = 0 \ldots n\$ might possibly roll a 20, and then use the solutions to "roll \$n - k\$ d19, keep \$x - k\$" -- namely, the remaining pool after the \$k\$ dice that rolled a 20 are removed -- to complete the solution. In turn, the solutions for d19s use the solutions for d18s, and so forth until we reach d1s and all of the remaining dice must roll 1. While not as fast as FFTs, the dynamic programming approach is much more flexible, covering general "single-pass" functions over the order statistics: in addition to summing the dice, it can also be used to produce efficient solutions for matching sets, straights, RISK-like mechanics, and so forth.
If you are interested in learning more, you can check out my Icepool Python package or read my paper on the subject.
Various methods are available depending on how accurate you want to be and the sample space size. For fistfuls of dice, you can brute-force count them: manually, with a spreadsheet, or by writing custom bit of code (like anydice!).
So, for "the highest 2 of 3d10", we have a sample space of \$10^3\$ and an output range of 2-20. So we can get a:
Or you can use the formulas generated in response to this question on Math Stack Exchange - be warned, serious mathematics ahead:
Disadvantage is simply the mirror-image of advantage, so once you solved for one, the probabilities apply in the reverse order to the other.
The Stand-Up Maths Youtube channel has done an interesting video on this subject. I've summarized the findings below.
For rolling advantage with two N-sided dice, the probability distribution is linear with the probability of getting a 1 being \$ \frac{1}{N^2} \$, and it increases by double that for each higher value, so the probability of getting a 2 is \$ \frac{3}{N^2} \$, and for a 3 it's \$ \frac{5}{N^2} \$.
For the average result when rolling Y dice with N sides with advantage, you end up with \$ \frac{Y}{Y+1} N + \frac{1}{2} \$.
This doesn't fully answer your question, as it's only considering the highest 1 out of Y N-sided dice, but I thought it might still be useful.
