How do you handle weighted dice in your algorithm, concretely?

[ogregoire]

Hi,

I've been reimplementing the paper recently in Java, and I must say that it did wonders. I polished my implementation of the base algorithm and it just works perfectly. My library does exactly what I want it to do.

However I've advanced to the point where I want to add loaded dice. I've now been trying to implement weighted dice for a few days, but I couldn't find how.

I know your paper mentions

before adding the previous row to a copy of itself shifted to the right by 1, multiply the shifted copy by w.

But I just don't understand what you mean with "shifted copy".

Considering your Python implementation of the basic algorithm on page 4, I've been basically doing the following: (I don't know if it's valid Python, but the idea is there)

@cache
def solve(die, n):
  (outcome, w), die = die.pop()            # w is the weight of the outcome
  if len(die) == 0:
    state = next_state(None, outcome, n)
    return {state : w}                     # This line is modified
  result = defaultdict(int)
  for k in range(n + 1):
    tail = solve(die, n - k)
    for state, weight in tail.items():
      state = next_state(state, outcome, k)
      weight *= comb(n, k) * w             # This line is modified
      result[state] += weight
  return result

I'm testing with 2 basic loaded dice {1:1, 2:2} and a basic summing state and I can't never find the appropriate place to multiply by w to get the appropriate result {2:1, 3:4, 4:4}. I'm always getting the result {2:1, 3:2, 4:1}.

I now believe that my w is not the correct weight of the outcome, so which is it, if that's the issue?

I've tried to find out the answer by myself by reading the icepool codebase and understanding the difference between comb and comb_row, but my Python knowledge and my understanding of your implementation are both too brittle.

Do you have any pointers that could help me implement loaded dice?

Thank you in advance!

[HighDiceRoller]

Glad to get your question! The short answer is the first modified line should have pow(w, n) rather than w and the other modified line pow(w, k) instead of w.

---

The long answer: suppose that, rather than computing comb(n, k) * pow(w, k) for a single choice of $n$ and $k$, we want to compute it for all $0 \leq k \leq n \leq N$ for some $N$. (Indeed, the dice pool algorithm will visit every one of these coefficients at some point.) For the pure binomial case ($w=1$) it's well-known that we can do this using Pascal's triangle, where each entry is the sum of the two entries above it:

If you like, you can think of this in terms of vectors instead of individual elements:

One copy (blue) stays at the same $k$, while the other (red) shifts to the right by one element.

Okay, now what if we want to do the weighted version? We can just multiply the rightward-traveling (red) number by $w$ before we do each sum. For example, $w = 2$ looks like this:

We can vectorize this as well, in which case each element of the red vector gets multiplied by $w$ before summing.

[ogregoire]

Thank you for the explanation! I kind of needed it.

I feel so dumb. I was so sure that I was only indirectly concerned by the first part of the paragraph, and therefore focused on the second part of it, not understanding that the "triangle" of the general layout (when printing a solution, for instance) wasn't the Pascal triangle you mentioned.

Anyways you put back my neurons in marching order and I thank you! I'll consider using the optimization for comb(n,k) you mention, now that I understand all of this (much) better.