Range to Dice Notation

2023-07-06

Before dice notation was adopted, early roleplaying games described dice rolls using range notation. For example, 3-18 indicated rolling three six-sided dice or 3d6 in modern notation. Converting a range to dice notation requires a little thought, so I’m going to describe a way to solve the conversion programmatically.

Background

Dice notation is a succinct domain specific language to represent discrete probability distributions and is heavily used in tabletop roleplaying games. For example, 4d10 + 3 means rolling four ten-sided dice, summing the result, and adding three. Over time, roleplaying systems have introduced many mechanics and esoteric distributions such that multiple attempts at a universal language have been developed (e.g. roll20, gnoll). Dice notation replaced an earlier system of specifying ranges.

Range specifications were compact but ambiguous and sometimes confusing. For example, the Holmes edition monster manual specified damages from different types of giants as:

When the gamemaster came to make a roll, they would need to translate these ranges into the number of dice to roll. Dividing the second number by the first yields some convenient solution – 2d8, 3d6, 4d6, 5d6, and 7d6 for all the giants but cloud. The range 6 to 63 violates this trend as 63 isn’t divisible by 6. The game designer probably expected the gamemaster to roll 3d20 + 3, but there are many possibilities. Weatherspud found 164 solutions if multiple dice types are allowed. The solution I describe below finds eight under a different set of constraints: 1d2*57-51, 57d2-51, 3d2*19-51, 19d2*3-51, 1d4*19-13, 19d4-13, 1d20*3+3, and 3d20+3.

Problem Assumptions and Constraints

A range is denoted by two integers, a and b, which define an inclusive range. The value a is less than or equal to b. (I’ll be following a convention where lower-case variables are known constants and upper-case variables are unknown.)

We will restrict solutions to:

$$ NdD \times Q + C $$

where:

• N is the number of dice to roll (a non-negative integer).
• D is the number of sides of the die and is restricted to the set {2, 4, 6, 8, 10, 12, 20, 30, 100}. Each die is numbered from 1 to the number of faces, inclusive.
• Q is a multiplication constant (typically equal to 1) and is restricted to positive integers.
• C is an additive constant and may be any integer (including negative).

Restricting solutions to a single type of die matches the game’s need to move along quickly without diverting the players into a long-winded math exercise. However, some studies of this problem have not imposed this restriction and allowed multiple types of dice.

A solution means that the dice roll’s minimum and maximum values will equal the range’s a and b value. A range does not need to be “dense”; for example, the range [1000, 4000] can be met by 1d4 * 1000, even though the values rolled will never equal 1001, 2052, or 3999.

Solutions may not be unique. For example, the range [3, 12] may be solved with either 3d4 or 1d10 + 2. Depending on the context, a game designer may strongly prefer a normal-like distribution over a uniform distribution, or vice versa, which is one of the reasons range notation was replaced by dice notation.

Minimum and Maximum Rolls

Given a solution of N, D, Q, and C as presented above, the minimum value that can be rolled is NQ + C and the maximum value is NQD + C.

So,

$$ NQ + C = a $$ $$ NQD + C = b $$

Exhaustive search?

In Weather Spud’s posting, they treat the problem as an unbounded knapsack problem. (Their solution does not include multipliers nor two-sided dice, but they do allow multiple dice of different types.) Can we use a simpler approach?

The equations:

$$ NQ + C = a $$ $$ NQD + C = b $$

have four unknown integer values and two known integer values. If we introduce a new variable, \(X = NQ\) and \(y = b - a\), then we can solve the parallel equations:

$$ a = X + C $$ $$ b = XD + C $$ $$ y = b - a $$ $$ y = XD + C - X - C $$ $$ y = XD - X $$ $$ y = X(D - 1) $$

which have two unknowns, one of which, D, is restricted to nine values. Iterating through all possible values that let X be an integer, we can then enumerate all possible N and Q values for X where N and Q are divisors of X.

The relevant Python code:

y = b - a
potential_nqs = [y // (side - 1) for side in SIDES if y % (side - 1) == 0]
for nq in potential_nqs:
    c = a - nq
    d = (b - c) // nq

    for n, q in _divisor_pairs(nq):
        if n != q:
            # yield both n, q and q, n pairs since the solutions are distinct
            yield Solution(n, d, q, c)
            yield Solution(q, d, n, c)
        else:
            yield Solution(n, d, q, c)

def _divisor_pairs(d: int) -> typing.Iterable[typing.Tuple[int, int]]:
    """
    Yield all (a, b) pairs such that a, b are positive integers, a <= b, and ab = d.

    >>> list(_divisor_pairs(1))
    [(1, 1)]
    >>> list(_divisor_pairs(2))
    [(1, 2)]
    >>> list(_divisor_pairs(4))
    [(1, 4), (2, 2)]
    >>> list(_divisor_pairs(12))
    [(1, 12), (2, 6), (3, 4)]

    :param d: a positive integer
    :return: an iterator of (a, b) tuples
    """
    assert isinstance(d, int), 'd must be an integer'
    assert d > 0, 'd must be positive'

    for a in range(1, math.floor(math.sqrt(d)) + 1):
        if d % a == 0:
            yield a, d // a

On Python Iterators

Iterators (continuation style) are great because they allow the consumer to pull the amount of data they need. This might reduce memory consumption versus building up a data structure of all solutions, but continuations are not free so, as usual, your use case matters.

Given the range (3, 18), the algorithm finds eight solutions:

1d2*15-12, 15d2-12, 3d2*5-12, 5d2*3-12, 1d4*5-2, 5d4-2, 1d6*3, 3d6

Of these, 3d6 is the “preferred” solution. d2 appear rarely in Dungeons & Dragons and multipliers are similarly rare for small numbers, so I’d expect players to only use 3d6 or 5d4-2. (Comparing these distributions on anydice.com we see a player might slightly prefer rolling 5d4-2 as the results are more likely to be in the safe mid area.)

Algorithmically, the run-time is dominated by the _divisor_pairs computation which requires the square root of y number of modulus checks. Modulus is one of the more expensive operators, but for realistic ranges in roleplaying games, this algorithm is quite fast. Python’s timeit timeit.timeit('list(range2dice.solve(1000, 4000))', setup='import range2dice') reported a little more than 17 seconds to execute one million times on my HP zBook G9.

The full code is available at my gitlab repository.