Probability of rolling $n$ dice that are each are greater than or equal to $x$ with a given pool of possible positive modifiers applied on each dice

binomial distributiondiceprobabilityprobability distributionsstatistics

I am currently analyzing a tabletop games probabilities. Successful rolls in the game are determined by rolling $n$ number of dice and counting the number of dice that are greater than or equal to a certain value (some pre-determined threshold $x$; for instance, values could be between 1 through 6 from a six sided die).

For example, suppose my threshold $x=3$; if I roll $10$ six sided die, what is the probability that $4$ dice would land on a $3$ or greater?

Additionally, the game allows for a positive pool of modifiers to be applied on the dice after they are rolled, such that it can bring them over the determined threshold $x$ and have it count as a success.

For example, suppose I roll three six sided die. Let $n_i$ represent the value of the die, and let $n_1=2$, $n_2=3$, and $n_3=6$ . Suppose I have a threshold of $x=4$ have a pool of $+3$ points to apply on any one of those die. I would be able to distribute all those points on both $n_1$ and $n_2$ such that I now have three successes instead of only one (where now $n_1=2+2=4$, $n_2=3+1=4$, and $n_3=6$.)

How are the probabilities of rolling $n$ dice that are each are greater than or equal to $x$ affected by the number of points in the modifier pool?

I have attempted to develop a formula specifically to answer the last question above so that I can analyze the distribution of a certain number of dice with different thresholds. I started with thinking of it as a binomial distribution, however, I am uncertain how it is affected by the modifiers.

EDIT:
After almost a year since asking the question I think I have something close to a solution, but not exact. From my analysis, the probability computation for a combination of the number of dice, modifiers, successes required, and dice sides is incredibly complex to generalize.

Here is a dropbox link of my analysis (very informal), where I attempted to find a distribution I've labeled $tdw(n,f,d,s)$ (to answer probability statements such as $Pr(X=x_{2}|n=7,f=4,d=4,s=3)$, where $x_{2}$ denotes getting 2 successes – here I defined the threshold to be $d$, the number of sides of the dice to be $s$, and the total number of available modifiers to be $f$) which in effect is a modified binomial distribution with extra parameters. I have no understanding of how to create a discrete distribution like this formally, however.

The framework I attempted to create used two 3 dimensional matrixes of different sizes depending on the value of $f$ and $n$. These would track the probabilities of a certain combination of $n$,$f$,$d$, and $s$. This idea, however, is completely made up and may have no basis in solving this kind of problem, however, for the $i=0$ case, the method always correctly solves the probability when compared to the probability I calculated manually.

Best Answer

What is an optimal strategy for allocating Focus points?

Since each Focus point can be allocated independently, you can achieve an optimal allocation by upgrading the dice that are the closest to the DN first, since they are the cheapest to turn into successes.

This produces the following procedure for evaluating a roll:

  1. Sort the dice in descending order.
  2. Count all the ones that passed the DN outright.
  3. Of the remaining dice, spend Focus on the dice in descending order until you run out of Focus.

Between each die, you only need to keep track of how many successes you have so far, and how many Focus points you have remaining.

Computing the result

In fact, it turns out that this "single-pass" formulation of the evaluation is all you need to compute the solution efficiently using my Icepool Python library. Here the game mechanic is defined in next_state, which receives the number of 6s rolled, then the number of 5s, 4s, 3s, 2s, and finally 1s.

from icepool import d6, MultisetEvaluator, Order

class SoulboundEvaluator(MultisetEvaluator):
    def __init__(self, dn, focus):
        self._dn = dn
        self._focus = focus
    
    def next_state(self, state, outcome, count):
        if state is None:
            success, focus = 0, self._focus
        else:
            success, focus = state
        
        if outcome >= self._dn:
            success += count
        else:
            # Upgrade as many dice as possible to successes.
            focus_per_die = self._dn - outcome
            focus_dice = min(focus // focus_per_die, count)
            success += focus_dice
            focus -= focus_per_die * focus_dice
        return success, focus
    
    def final_outcome(self, final_state):
        # Return just the number of successes.
        success, focus = final_state
        return success
        
    def order(self):
        # See outcomes in descending order.
        return Order.Descending

result = SoulboundEvaluator(dn=5, focus=3).evaluate(d6.pool(10))
output(result)

You can try it in your browser here. (API subject to change. This is based on Icepool v0.27.0.)

Result:

Die with denominator 60466176

Outcome Quantity Probability
0 1 0.000002%
1 64188 0.106155%
2 926855 1.532849%
3 4573072 7.563025%
4 11264720 18.629787%
5 16259004 26.889420%
6 14777568 24.439396%
7 8650560 14.306445%
8 3197184 5.287558%
9 686720 1.135709%
10 66304 0.109655%

Chance of at least 4 successes:

Die with denominator 60466176

Outcome Quantity Probability
False 5564116 9.202031%
True 54902060 90.797969%

You can try it in your browser using this JupyterLite notebook.

The algorithm itself combines the decomposition of a multinomial distribution into binomials and dynamic programming to produce a solution efficiently---even 50 dice is no issue. If you are curious to learn more, you can read my paper on the subject.

@inproceedings{liu2022icepool,
    title={Icepool: Efficient Computation of Dice Pool Probabilities},
    author={Albert Julius Liu},
    booktitle={Eighteenth AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment},
    volume={18},
    number={1},
    pages={258-265},
    year={2022},
    month={Oct.},
    eventdate={2022-10-24/2022-10-28},
    venue={Pomona, California},
    url={https://ojs.aaai.org/index.php/AIIDE/article/view/21971},
    doi={10.1609/aiide.v18i1.21971}
}
Related Question