9
\$\begingroup\$

The game Neon City Overdrive uses the following resolution mechanic for checks:

  1. create a pool of Action Dice and (possibly) another pool of differently-colored Danger Dice (all d6, generally up to 5 or 6 dice in each pool)
  2. roll all the dice
  3. each Danger Die cancels out an Action Die with the same value - both are discarded
  4. the highest remaining Action Die (if there is any) is the result (the precise meaning of which is irrelevant for the purposes of this question)
    • each extra remaining Action Die showing a 6 (i.e. any second, third etc. "6" beyond the first "6" that is read as the result of the roll) provides one critical success (called a boon)

I'm struggling to find the proper way to model the probabilities of this mechanic in anydice.

I realize that a good starting point would be this answer to a very similar question regarding the mechanic in Technoir (which clearly was a source of inspiration for Neon City Overdrive). Unfortunately, despite my best efforts I can't say I fully comprehend how the code provided there works, and there's an important difference between the two games: in Technoir a single "negative die" eliminates all matching "positive dice", whereas in NCO this happens on a one-to-one basis.

I would be very grateful for any help.

\$\endgroup\$
0

6 Answers 6

9
\$\begingroup\$

The following anydice function will calculate the expected results for the mechanic you describe:

function: nco AD:s DD:s {
  if [count 6 in AD] > [count 6 in DD] { result: 6 + ([count 6 in AD] - [count 6 in DD] - 1)}
  loop X over {5,4,3,2,1} {
    if [count X in AD] > [count X in DD] { result: X }
  }
  result: 0
}

This function expects to be fed two dice pools (A and D a the start on the link) - the action dice, AD, and the danger dice, DD, which are cast to sequences in the function (:s) so as to fix and inspect them. The key feature is that for any given value X, we can easily determine if there are any uncancelled dice showing X in the action dice pool by counting how many dice showing X there are and comparing it to the number of similar dice in the danger dice pool. So, if [count X in AD] is greater than [count X in DD], we know there are uneliminated dice showing X in the action dice pool. The function iterates down over values of X starting at 6 down to 1 - so the first uneliminated die it finds is the result. (If all the action dice are eliminated, the result is 0.)

I've also added a special case for when the result would be 6 so we can count any possible boons - again simply calculated by comparing the number of 6s in AD to DD and adding 1 to the result for any extra 6s, so a final result of 7 should be read as 6 and 1 boon, for instance.

Unfortunately, though algorithmically simple, I've found that this function is falling afoul of anydice's 5 second calculation limit when given dice pools at the upper end of your specified ranges - the possibility space of sequences for pools of 5d6 or 6d6 is very large, and anydice will give up if both pools are 5d6 or larger. Ilmari's answer, however, describes a more conceptually complicated but computationally efficient approach which can handle larger pools than my naive script.

\$\endgroup\$
0
7
\$\begingroup\$

It is possible to calculate these results efficiently using AnyDice. It's just not very easy or intuitive.

First of all, this optimized version of Carcer's code works fine for up to 5d6 vs. 5d6, but times out for larger pools:

function: neon city overdrive ACTION:s DANGER:s {
  BOON: (ACTION = 6) - (DANGER = 6)
  if BOON > 0 { result: 5 + BOON }
  loop N over {5,4,3,2,1} {
    if (ACTION = N) > (DANGER = N) { result: N }
  }
  result: 0
}

output [neon city overdrive 5d6 5d6]

All I really did to speed Carcer's code up was replace calls to the built-in [count N in SEQ] function with (SEQ = N), which does the same thing but slightly faster. It's certainly possible to micro-optimize the code even further e.g. by unrolling the loop and returning early if the highest action roll isn't cancelled, but none of those optimizations actually helps break the 5d6 vs. 5d6 barrier. With more than 10 total dice, there are just too many combinations to enumerate.


Now, usually the best way to make AnyDice code handle large dice pools faster is to relabel the dice to merge equivalent sides, so that AnyDice will know not to waste time testing too many equivalent possible rolls. For example, if you want to calculate the number of rolls meeting or exceeding a certain threshold 1 ≤ T ≤ 6 in Nd6, then Nd(d6 >= T) is a lot faster than [count {T..6} in Nd6]. In general, these kinds of optimizations work great in any situation where, if rolling the dice physically, you would divide the rolled dice into a few coarse groups (like "at least T" and "below T") and count how many dice are in each group, or set aside some of the rolled dice as "these don't matter". But there's no obvious way to apply this kind of optimization here, since all the rolls potentially matter if all higher ones are cancelled.

…or is there?

Remember, low rolls in this mechanic only matter if all higher action die rolls have been cancelled. So let's imagine rolling the dice and counting them step by step, like this:

  1. Divide the rolled dice into two groups: "sixes" and "everything below six". If the "sixes" group contains more action dice than danger dice, stop: the result is 6 (plus boons equal to the number of uncancelled sixes minus one).

  2. Otherwise set aside all the sixes, and divide the rest of the dice into two groups: "fives" and "everything below five". If the "fives" group contains more action dice than danger dice, stop: the result is 5.

  3. Otherwise set aside all the fives, and divide the rest of the dice into two groups: "fours" and "everything below four". If the "fours" group contains more action dice than danger dice, stop: the result is 4.

…and so on until finally, if all dice that rolled 2 or higher have been cancelled, we end up simply comparing the number of remaining action and danger dice to determine if the result is 1 or 0.

Now, the important feature of this process is that, at each step, the actual numbers rolled on the dice in the "everything below N" group don't matter — they're all equivalent. In fact, we could reroll all the dice in that "everything below N" group after each step (making sure that all the rerolls are still below N, of course!) and the distribution of results wouldn't change.

Or, if we really wanted to be weird, we could start by rolling a bunch of custom six-sided dice with all the sides except 6 blank.

Then, after the first step above, we could replace all the blank rolls with custom five-sided dice, again with all sides except 5 blank, roll those dice and proceed to the second step.

And if the second step didn't yield a result either, we could replace the blank rolls with custom four-sided dice, with all sides except 4 blank, roll those dice, and so on…

Now, obviously, this would be a really weird and inefficient way to roll dice at the table. But it's a very efficient way to do it in AnyDice, since it means that e.g. for rolls that contain one or more uncancelled sixes we don't have to consider all the possible combinations of lower rolls.

All we need to do is write a helper function that calls itself recursively:

function: nco helper N:n AMAX:n DMAX:n AROLL:n DROLL:n {
  if AROLL > DROLL {
    if N = 6 { result: 5 + AROLL - DROLL }
    result: N
  }
  A: AMAX - AROLL
  D: DMAX - DROLL
  if N = 2 { result: A > D }
  X: d(N-1) = N-1
  result: [nco helper N-1 A D AdX DdX]
}

function: nco A:n D:n {
  X: d6 = 6
  result: [nco helper 6 A D AdX DdX]
}

loop A over {6} {
  loop D over {0..6} {
    output [nco A D] named "action [A]d6, danger [D]d6"
  }
}

In the code above, N is the highest possible roll at the current step (initially 6), and thus also the number we'll return as the result if we find an uncancelled action roll on this step (with the number of boons added to the result if N = 6). AMAX and DMAX are the total numbers of action and danger dice left at this step, respectively, while AROLL and DROLL are the numbers of those dice that rolled N.

The helper function first compares AROLL and DROLL: if the former is larger, then we've found an uncancelled action roll, and stop. Otherwise it calculates the numbers of remaining action and danger rolls, A and B, and constructs a custom N-1 sided die X with one side out of N numbered 1 and the rest numbered 0. This makes AdX match the distribution of the number of N-1 rolls in a pool of A dice with N-1 sides each, and similarly for DdX; these rolls are then passed recursively to another instance of the helper function as AROLL and DROLL, making AnyDice evaluate the recursive call for each possible combination of those rolls.

The loops at the bottom of the code call the [nco A D] function for varying numbers of action and danger dice and output the results. By default, I had the code use 6 action dice and a range of danger dice from 0 to 6, but you can of course edit the loop ranges as you like. The default output, graphed, looks like this:

AnyDice screenshot

How much faster is this recursive solution, by the way? Well, based on some testing, it runs fine up to 7d6 vs. 7d6, but will time out for 8d6 vs. 8d6. Which isn't too shabby, given that the number of possible combinations goes up exponentially with the number of dice. (It could be made a lot faster if AnyDice supported memoization, but alas, it doesn't.) In any case it's at least more than enough to meet the OP's requirement of "up to 5 or 6 dice in each pool".

\$\endgroup\$
6
\$\begingroup\$

This is a considerably hard analytical problem

The question you linked, although already quite hard, is easier because it can be computed as the probability of a dice being in one set, and not in the other. In your question, this is done in a one-to-one basis, as you mentioned, and this is a considerably hard problem.

Doesn't matter - do it the easy way

Unless you need the analytical expression for something, I recommend going with Monte Carlo: You basically run a random simulation a bunch of times, and then see the distribution of that. This code for MATLAB does it - I am sure someone can translate it to Python or something that doesn't need to be paid, but I'm more familiar with MATLAB haha

N_it = 10^5;

N_action = 6;
N_danger = 5;

bins = 1:6;

for i = 1:N_it

    Action_Dice = randi([1 6], N_action, 1);
    Danger_Dice = randi([1 6], N_danger, 1);

    Action_Dice_Count = hist(Action_Dice, bins);
    Danger_Dice_Count = hist(Danger_Dice, bins);

    Result_Count = Action_Dice_Count - Danger_Dice_Count;

    Result = find(Result_Count > 0, 1, 'last');

    if(Result)
        Result_Save(i) = Result;
    else
        Result_Save(i) = 0;
    end
end

So, what this code does is basically: roll a set number of action dice and danger dice, count how many of each dice you got, subtract the number of rolled danger dice from the number of rolled action dice, then find the last value which is greater than zero (i.e., the highest Action Dice remaining) and finally, if no such action dice exists, it sets the result to 0.

As an example, for 6 Action Dice and 5 Danger Dice, this is what it looks like: enter image description here

Why does it look like this? In the example, I used 6 action dice and 5 danger dice. The probability that there is no remaining action dice is, evidently, zero, since we will always have one remaining dice. But not only that, there is a high probability on 6, why? Because every time there is a 6 remaining, that 6 will be chosen. This is actually an easier analytical problem. Let \$X\$ denote the number of sixes appearing in the Action Dice pool, and \$Y\$ be the number of sixes appearing in the Danger Dice pool. We are interested in \$P(X > Y)\$. But what is nice in this case is that we know the exact distribution of both \$X\$ and \$Y\$, which are binomial distributions with the number of trials being equal to the number of dice in the pool, and probability in each trial equal to 1/6.

We can then compute \$P(X - Y)\$, which can be done by the convolution of \$P(X)\$ and \$P(-Y)\$, and finally compute \$P(X - Y > 0)\$. I won't bother with all this computation here, but if you do it, you will find out that the probability is 0.383367984110654. The probability found by code was 0.386, so, close enough, the code seems to make sense.

Note that this same strategy of analytically computing the other probabilities will not help for other values than 6, since, not only you need that, for example, the number of fives in the Action pool should be larger than the number in the Danger pool, you also need that the number of sixes in the action pool is smaller than or equal to the number in the danger pool. For 5 it is already a bunch of complicated conditional probabilities, and it will get harder and harder for lower numbers, since each time you need to consider the numbers above it.

Computing the Boons

The previous analytical concept can be used to find the probability of Boons. \$B\$ boons happens when \$X = (Y + B + 1)\$, that is, the number of sixes in the Action pool is larger than the number of sixes in the Danger pool by \$B\$. This can actually be computed the same way. So, in this example, we have the probability of one boon being 0.103599655450346, two boons being 0.024868242039980, three boons being 0.003491966042856, and others being irrelevant. Finding a general analytical expression is still hard, but for any given number of action dice and danger dice, it is easy to find the analytical expression.

Validating the Code

I can only think about one trivial case, so we can check whether the code makes sense for that case at least. Consider only 1 Action Dice and 1 Danger Dice. In this case, the probability that they are equal is 1/6, and in that case the result is 0 (i.e., no action dice remaining). Otherwise, we have an equal probability for any dice, which is 5/36. enter image description here

The values resulting from the code are, in fact, approximately 1/6 for 0 and 5/36 for the remaining.

\$\endgroup\$
2
  • \$\begingroup\$ @Trish Why is that? Since we are choosing the highest remaining dice, it is expected that the higher values have a higher probability. Since, in the example, there are more action dice than danger dice, we won't ever have a non-remaining action dice (thus p(0) = 0). \$\endgroup\$
    – HellSaint
    Jul 4, 2020 at 15:41
  • \$\begingroup\$ @Trish I have analytically computed the probability for Result = 6, and it does match the result given by the code. I hope that alone is enough for you to trust the remaining results, because the other values are really hard to compute and it would require lots of time and writing down equations. \$\endgroup\$
    – HellSaint
    Jul 4, 2020 at 16:13
3
\$\begingroup\$

I came across this post via a google search for something unrelated, but even though I'm not an RPGer, it's an interesting problem.

This is easily calculated directly for your specified domain using the multinomial distribution.

Taking the weak compositions of size (number of faces n) for (number of dice d), and letting the sequence of categories in the multinomial represent the faces {1, 2, 3..., n}, we subtract over all pairs of weak compositions, with pair members representing the action and danger dice respectively. We note the PMF of each pair member and multiply these for a total probability, saving the result along the the result of the subtraction clipped between [0,d].

It is then a simple walk over the {total probability, clipped result} pairs, picking the largest non-zero category (and if that category is the maximum face value n, noting that the category value less one is the number of boon).

Finally, we gather those results by same maximums&boons, and sum the probabilities within.

Less than a couple of seconds for the 5D6 & 6D6 cases for example, and not a problem for larger cases.

These are read as left numbers top->maximum face value remaining, left numbers bottom->number of boon, followed left-to-right with exact probability and same rounded.

5D6:

enter image description here

6D6:

enter image description here

\$\endgroup\$
2
\$\begingroup\$

For funsies, I decided to try to reproduce @Carcer's approach and a memoized version of @Ilmari Karonen's approach using dyce.

You can play around with it in your browser: Try dyce [source]

That environment is nice because it doesn't impose short computation time limits (like AnyDice does). What's even cooler is that—with memoization—Ilmari's version handles comparing [1-11] action dice vs. [0-11] danger dice in under a second. Wow!

The default run of that notebook enumerates anydyce's² line plot and burst graphs for a range of [1-5] action dice vs. [0-5] danger dice. Plots get pretty chaotic after that (and actually start to take longer to generate than computing the distributions themselves). Below are some screenshots.


¹ dyce is my Python dice probability library.

² anydyce is my visualization layer for dyce meant as a rough stand-in for AnyDice.


Neon City Overdrive line plots Neon City Overdrive burst graphs

\$\endgroup\$
1
\$\begingroup\$

Closed-form, polynomial-time solution

A strategy that can solve many dice pools in polynomial time:

  • Formulate the problem as a time-varying Markov chain where timesteps = faces, running from top to bottom.
  • The states of the Markov chain are defined by the following:
    • The number of dice from each pool (in this case, action and danger) that have been consumed so far.
    • The (running) outcome.
    • Any other information you need to compute future outcomes. (Only the running outcome is needed in this case.)
  • The initial state is:
    • Zero dice consumed from each pool.
    • Zero outcome.
  • The transitions out of each state at a particular timestep (face) are defined by:
    • For each pool, the number of ways a particular number of the non-consumed dice can roll the current face. This is just a binomial distribution.
    • For each pool, the new number of consumed dice = previous number of consumed dice + dice that rolled the current face.
    • The running outcome produced by rolling that many of the current face on each pool. If more action dice rolled the current face than danger dice, then that face is taken if it is better than the previous running outcome.

As long as the state space and outcome updates are polynomial, the algorithm as a whole will be polynomial-time. These gains are possible because this algorithm aggregates out information that is not relevant or no longer relevant, such as which specific dice rolled each number or exactly how many previously-consumed dice rolled each number.

Here is example code:

import numpy
from math import comb

def neon_city_overdrive(action, danger):
    """
    action: the number of action dice
    danger: the number of danger dice
    
    Returns:
    A vector of outcome -> ways to roll that outcome.
    Outcomes above 6 represent crits.
    """
    
    # number of consumed action, danger dice, outcome -> 
    # number of ways to roll this outcome with all consumed dice >= the last processed face
    # outcomes above 6 represent crits
    state = numpy.zeros((action+1, danger+1, 6+action))
    # initial state: 1 way to have rolled no dice yet
    state[0, 0, 0] = 1.0
    for face in [6, 5, 4, 3, 2, 1]:
        next_state = numpy.zeros_like(state)
        for (consumed_action, consumed_danger, outcome), count in numpy.ndenumerate(state):
            remaining_action = action - consumed_action
            remaining_danger = danger - consumed_danger
            # how many action and danger dice rolled the current face?
            for add_action in range(remaining_action+1):
                for add_danger in range(remaining_danger+1):
                    # how many ways are there for this to happen?
                    factor = comb(remaining_action, add_action) * comb(remaining_danger, add_danger)
                    next_count = factor * count
                    if add_action > add_danger:
                        if face == 6:
                            # add crits
                            next_outcome = 5 + add_action - add_danger
                        else:
                            next_outcome = max(face, outcome)
                    else:
                        next_outcome = outcome
                    next_state[consumed_action+add_action, consumed_danger+add_danger, next_outcome] += next_count
        state = next_state

    result = state[action, danger, :]
    return result

y = neon_city_overdrive(6, 6)

There's more optimization possible for this specific case. For example, since it goes from highest to lowest face, you could bail out as soon as you roll more of a face on the action than the danger dice, with an appropriate multiplier for the not-yet-consumed dice. But this shows the general strategy and is good enough for any practical pool size.

Here's an example plot of 6 action vs. 6 danger dice:

enter image description here

\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .