Dice Probabilities for Tabletop RPGs

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

User avatar
kriel
Posts: 923
Joined: Thu Feb 07, 2008 2:58 pm UTC
Location: Somewhere I'm not.
Contact:

Dice Probabilities for Tabletop RPGs

Postby kriel » Tue Feb 01, 2011 5:11 pm UTC

I'm playing a tabletop RPG called world of darkness. It uses a d10 system (10 sided die) to make choices.

Many rolls are 'DC 8'. This means that rolls of 8 and above are considered successes. 1 is considered a botch, and removes a success. This leaves a 'die' of [-1, 0, 0, 0, 0, 0, 0, 1, 1, 1]. (an '8' success isn't worth any more than a '9' success, and a '2' failure isn't worse than a '7' failure)

Also, if you get negative successes, you 'botch' the entire thing. The number of negative successes doesn't matter, just that you botched it.




I made a py script (spoiled below) to go through all possible die rolls and add up the number of successes you got, trying to make probability tables based on the number of dice you rolled. (if you roll 9 dice, you have a >75% chance of getting at least one success, and the median number of successes you get is 2).

I generated a chart based on this (the .pdf), but it doesn't seem intuitive for some reason. the .xlsx that I generated the chart in is attached as well.

Here is the code that I used to generate the numbers for the .xlsx: (DO NOT RUN FOR MORE THAN ~>6 DIE unless you want to spend several minutes waiting for your computer to respond)
Spoiler:

Code: Select all

import itertools as it

dc = input("DC  ?")
dice = input("Dice?")

die = [-1]+[0]*(dc - 2)+[1]*(11 - dc)

poss = it.product(die, repeat=dice)

score = range(-dice,dice+(9 - dc))
scores = {}
for each in score:
    scores[each] = 0

total = 0
for each in poss:
    mysum = sum(each)
    scores[mysum] = scores[mysum] + 1
    total = total + 1
    #print each
   
for each in score:
    print "%2s" % each, scores[each]

print 'xx', total


tl;dr I ran the numbers, and they don't look right, did i do something wrong or are my intuitions wrong?

EDIT: The reason my 'intuitions are wrong' is because, well... if I roll 9 dice, each with a 30% success rate... I only get two successes on 'average' (median)? That doesn't seem right.
Attachments
iters.xlsx
(15.5 KiB) Downloaded 46 times
iters.pdf
(680.49 KiB) Downloaded 65 times
Last edited by kriel on Tue Feb 01, 2011 8:18 pm UTC, edited 1 time in total.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11128
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Dice Probabilities for Tabletop RPGs

Postby Yakk » Tue Feb 01, 2011 6:01 pm UTC

Because I enjoy writing this code, here is an alternative version:

Code: Select all

struct term {
  int degree;
  double arg;
  term(int degree_, double arg_):degree(degree_), arg(arg_) {}
  term operator*(term const& other) const
  {
    return term(degree+other.degree, arg*other.arg);
  }
  // for sorting!
  bool operator<(term const& other) const
  {
    if (degree < other.degree) return true;
    if (degree > other.degree) return false;
    if (arg < other.arg) return true;
    if (arg > other.arg) return false;
    return false;
  }
};

struct polynomial {
  typedef std::vector<term> Terms;
  Terms terms;
  polynomial& operator*(const polynomial& other) const
  {
    std::vector<term> result;
    // a naive n^2 product is fast enough for the sizes we are worried about:
    for(Terms::const_iterator it = terms.begin(); it!= terms.end(); ++it)
    {
      for(Terms::const_iterator jt = other.terms.begin(); jt!= other.terms.end(); ++jt)
      {
        result.push_back( *it * *jt );
      }
    }
    std::sort( result.begin(), result.end() );
    term retval;
    term accumulator(0,0);
    for(Terms::const_iterator it = result.begin(); it!=result.end(); ++it)
    {
      if (it->degree == accumulator.degree)
      {
        accumulator.arg += it->arg;
        continue;
      }
      if (accumulator.arg != 0)
      {
        retval.terms.push_back(accumulator);
      }
      accumulator = *it;
    }
    if (accumulator.arg != 0)
    {
      retval.terms.push_back(accumulator);
    }
    return retval;
  }
};

void main()
{
  polynomial roll;
  roll.push_back(term(-1, .1));
  roll.push_back(term(0, .6));
  roll.push_back(term(1,.3));
  polynomial result;
  result.push_back(term(0,1.0));
  for(int i = 0; i < 10; ++i)
  {
    result = result * roll;
  }
  for(polynomial::Terms::const_iterator it = result.terms.begin(); it!=result.terms.end(); ++it)
  {
    printf("%03.2f chance of %d\n", it->arg, it->degree);
  }
}

This is in C++ and uncompiled -- but do you see how this is slightly more efficient?

You are treating a roll of 2 differently than a roll of 6 until you hit the point where you count everything up. You aren't being forgetful enough. (the above takes about n^3 time where n is the number of dice rolls, and can "easily" be optimized down to about n^1.75 -- while yours takes about 10^n time, I'm quite surprised you got results for 9 dice!)

In any case, the above code path would give you a solution that is independently designed from yours. You can port the above to python, run it, and see if it gives the same answer. :)

Another way to attack this problem is to calculate statistical values like expectation and variance of one die. You are adding up repeated trials, and both of those are linear terms. Apply the same test to your output values of 9 dice (from first principles) and see if the result is linear compared to one die (both values being 9 times higher than for one die).

BTW, you didn't count things below -1 at some point? In the XLS? They can happen.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

User avatar
kriel
Posts: 923
Joined: Thu Feb 07, 2008 2:58 pm UTC
Location: Somewhere I'm not.
Contact:

Re: Dice Probabilities for Tabletop RPGs

Postby kriel » Tue Feb 01, 2011 8:01 pm UTC

Yakk wrote:BTW, you didn't count things below -1 at some point? In the XLS? They can happen.
In the background info, I mentioned that anything less than -1 has no significance in the game (well, other than as a negative number), so I just added up all the negative values and threw them in as '-1'. It made my graph prettier.

Yakk wrote:You are treating a roll of 2 differently than a roll of 6 until you hit the point where you count everything up. You aren't being forgetful enough. (the above takes about n^3 time where n is the number of dice rolls, and can "easily" be optimized down to about n^1.75 -- while yours takes about 10^n time, I'm quite surprised you got results for 9 dice!)
I'm having a hard time wrapping my head about how you did that. I realized that it's significantly easier to treat them all the same instead of distinct values, but I didn't have the maths knowledge to figure out how to do that, so... BRUTE FORCE AWAY!

(Also, I rewrote the .py so that it automatically spits out the values I need for the xls, I have it running now for dc 5-8, with 1-9 die... it'll take a while.)

Spoiler:
THIS WILL TAKE A BITCH OF A LONG TIME TO RUN

Code: Select all

import itertools as it

f = open('iters.csv','w')

maxdie = 9
mindc = 5
maxdc = 8

#automagic to fix off by 1
maxdie += 1
maxdc += 1

for dc in xrange(mindc,maxdc):
    f.write("DC %i" % dc+"\n")
    score = range(-1,maxdie)
    f.write(','+','.join(["%s" % a for a in score])+"\n")
    for dice in xrange(1,maxdie):
        die = [-1]+[0]*(dc - 2)+[1]*(11 - dc)

        poss = it.product(die, repeat=dice)

        scores = {}
        for each in score:
            scores[each] = 0

        for each in poss:
            mysum = sum(each)
            if mysum < -1: mysum = -1
            scores[mysum] = scores[mysum] + 1

        f.write('%s,' % dice)
        for each in score:
            f.write('%f' % (float(scores[each]) /(10**dice))+",")
        f.write("\n")
        print '.',

f.close()
f = open('iters.csv')
print f.read()

User avatar
Yakk
Poster with most posts but no title.
Posts: 11128
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Dice Probabilities for Tabletop RPGs

Postby Yakk » Tue Feb 01, 2011 8:24 pm UTC

Build a mapping from "value" to "count" instead of from "instance" to "value".

So one die is:
-1 maps to 1
1 maps to 3
0 maps to 6

This is compact and only has the information you need. I like to store it in a polynomial like this:
x^-1 + 6x^0 + 3x^1
for reasons that become apparent later on.

The beauty of this is that combing two rolls is easy. Make a chart:

Code: Select all

         -1  +0  +1
          1   6   3
  -1  1   1   6   3
  +0  6   6  36  18
  +1  3   3  18   9

36 is the number of ways the first die gets 0 and the second die gets zero (which equals 6*6, or the "weight" of zero on the left, times the "weight" of zero on the right).

That chart doesn't help much, but you can collapse it. The 3 that are +1 and -1? Their total weight is 0. Adding up the cells with total weight 0 gives you 36+3+3 = 42.

Now here is why I like the polynomial representation:
(x^-1 + 6x^0 + 3x^1) * (x^-1 + 6x^0 + 3x^1)
= x^-2 + 12x^-1 + 42x^0 + 36x^1 + 9x^1
See that 42 there? That is the number of ways you can roll a 0 on two d10 using your system. And instead of having to think about that above graph, I just have to write polynomial multiplication code that keeps track of coefficients and the degrees -- the result is exactly what we want!

We take our polynomial that represents our single die roll:
(x^-1 + 6x^0 + 3x^1)
and we raise it to the power of the number of die rolls:
(x^-1 + 6x^0 + 3x^1)^9
we then look at the coefficients -- of the terms x^-9 through x^9 -- and from that we have the count of the probabilities. For the total count, we just add up all of the coefficients.

Now, if you don't like thinking about it as polynomials, that is fine -- I just like doing so because I find writing a quick polynomial multiplication library easier to think about than the actual application I'm working on!
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

User avatar
kriel
Posts: 923
Joined: Thu Feb 07, 2008 2:58 pm UTC
Location: Somewhere I'm not.
Contact:

Re: Dice Probabilities for Tabletop RPGs

Postby kriel » Tue Feb 01, 2011 8:38 pm UTC

That... is a beautiful implementation. I didn't even think of that.

Hm. Yeah, I'd have to write a polynomial multiplier, but that still works amazingly.

Or I could just wait for my bruteforcer to run... It's at ~40% finished now.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11128
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Dice Probabilities for Tabletop RPGs

Postby Yakk » Tue Feb 01, 2011 8:51 pm UTC

You could possibly write the polynomial code before you implementation finishes. ;) Plus, with an independent verification of your result, you'll have more confidence.

Finally, note that the fun doesn't stop here. This works for pretty much any probability situation (and if you store probabilities instead of counts, it also works).

You can extend it to multinomial probabilities to deal with some really neat situations (ie, a situation where you need to find pairs and matches of dice -- have a 10-nomial and multiply it out, and you can extract information about pairs, triples, etc).

You can write a less inefficient multiplication engine (there are a number that are faster than naive) and deal with simply ridiculously huge models.

If you evaluate the resulting polynomial at 1, you get the total count.

If you take the derivative of the resulting polynomial, and evaluate at 1, you get the expected value.

If you take the second derivative of the resulting polynomial, then do a bit of addition, you get the variance. (I forget the formula, but it is something like f'(1) - f(1)).

BTW, isn't there a rule in WW games that a 10 counts as 2 successes, or did they get rid of that?
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

User avatar
kriel
Posts: 923
Joined: Thu Feb 07, 2008 2:58 pm UTC
Location: Somewhere I'm not.
Contact:

Re: Dice Probabilities for Tabletop RPGs

Postby kriel » Tue Feb 01, 2011 8:59 pm UTC

Yakk wrote:BTW, isn't there a rule in WW games that a 10 counts as 2 successes, or did they get rid of that?
The rule in WoD is that you can roll 10's again, to get a chance at another success.

That's... computationally complex, so I was just gonna leave it be.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11128
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Dice Probabilities for Tabletop RPGs

Postby Yakk » Tue Feb 01, 2011 9:17 pm UTC

Well, what you get is something like this:
f(x) = 1 /10 x^-1 + 6/10 x^0 + 2/10 x^1 + 1/10 x^1 * f(x)

Now, to approach this, replace f(x) with y in the above equation (see? A multinomial)
f(x) = 1 /10 x^-1 + 6/10 x^0 + 2/10 x^1 + 1/10 x^1 * y

Now, calculate f(x)^1 through f(x)^9. This is just multinomial multiplication -- a bit nastier than what we did before, but otherwise ok.

At this point you have a sequence with a bunch of y^0 through y^9 terms.

y^0 = 1
y^1 = f(x)^1
...
y^9 = f(x)^9

So ... substitute back in. Each time you do so, you spew out more y^0 terms, which go away.

When the total coefficients of all of the y^k where k!=0 terms has fallen low enough, you neglect them.

Now, you could just choose to do this at step 1. Start with this:
f(x) = 1 /10 x^-1 + 6/10 x^0 + 2/10 x^1 + 1/10 x^1 * y
now substitute in for y = f(x):
1 /10 x^-1 + 6/10 x^0 + 2/10 x^1 + 1/10 x^1 * (1 /10 x^-1 + 6/10 x^0 + 2/10 x^1 + 1/10 x^1 * y)
and expand:
1 /10 x^-1 + 6/10 x^0 + 2/10 x^1 + 1 /100 x + 6/100 x^1 + 2/100 x^2 + 1/100 x^2 * y
and repeat:
1 /10 x^-1 + 6/10 x^0 + 2/10 x^1 + 1 /100 x + 6/100 x^1 + 2/100 x^2 + 1/100 x^2 * (1 /10 x^-1 + 6/10 x^0 + 2/10 x^1 + 1/10 x^1 * y)
and repeat:
1 /10 x^-1 + 6/10 x^0 + 2/10 x^1 + 1 /100 x + 6/100 x^1 + 2/100 x^2 + 1/100 x^2 * (1 /10 x^-1 + 6/10 x^0 + 2/10 x^1 + 1/10 x^1 * (1 /10 x^-1 + 6/10 x^0 + 2/10 x^1 + 1/10 x^1 * y))
By this time, the y coefficient is next to a 1/10000 term, pretty unlikely. If you feel safe about neglecting that, stop. Otherwise, repeat a few more times!

The fun part, of course, is you can do the above programatically instead of manually. You can even do it in a loop.

Code: Select all

Let g(x) = 1 /10 x^-1  +  6/10 x^0 + 2/10 x^1
Let h(x) = 1/10 x^1
retval =  1 /10 x^-1  +  6/10 x^0 + 3/10 x^1
repeat enough times:
  retval = g(x) + h(x) * retval
return retval

The above generates a darn good approximation of f(x) to as high a precision as you want.

Then you take the resulting f(x), raise it to the 9th power.

And all you need to do is implement polynomial addition and multiplication. :) (note: you want negative powers, and non-integer coefficients).
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

User avatar
kriel
Posts: 923
Joined: Thu Feb 07, 2008 2:58 pm UTC
Location: Somewhere I'm not.
Contact:

Re: Dice Probabilities for Tabletop RPGs

Postby kriel » Tue Feb 01, 2011 9:21 pm UTC

You lost me. I've wrapped my head around Polynomials before (seem easy, now) but I've never grappled with multinomials.

EDIT: Recursion? In my recursive problem?

EDIT2: Bruteforce is done!

Spoiler:

Code: Select all

DC 5
,-1,0,1,2,3,4,5,6,7,8,9
1,0.100000,0.300000,0.600000,0.000000,0.000000,0.000000,0.000000,0.000000,0.000000,0.000000,0.000000,
2,0.070000,0.210000,0.360000,0.360000,0.000000,0.000000,0.000000,0.000000,0.000000,0.000000,0.000000,
3,0.055000,0.135000,0.270000,0.324000,0.216000,0.000000,0.000000,0.000000,0.000000,0.000000,0.000000,
4,0.041500,0.094500,0.194400,0.280800,0.259200,0.129600,0.000000,0.000000,0.000000,0.000000,0.000000,
5,0.031510,0.067230,0.143100,0.226800,0.259200,0.194400,0.077760,0.000000,0.000000,0.000000,0.000000,
6,0.023923,0.048789,0.105948,0.179820,0.233280,0.221616,0.139968,0.046656,0.000000,0.000000,0.000000,
7,0.018207,0.035826,0.079040,0.140843,0.200038,0.220450,0.179626,0.097978,0.027994,0.000000,0.000000,
8,0.013886,0.026556,0.059292,0.109680,0.166562,0.204120,0.195955,0.139968,0.067185,0.016796,0.000000,
9,0.010612,0.019825,0.044689,0.085136,0.136189,0.180769,0.195255,0.166282,0.105816,0.045350,0.010078,
DC 6
,-1,0,1,2,3,4,5,6,7,8,9
1,0.100000,0.400000,0.500000,0.000000,0.000000,0.000000,0.000000,0.000000,0.000000,0.000000,0.000000,
2,0.090000,0.260000,0.400000,0.250000,0.000000,0.000000,0.000000,0.000000,0.000000,0.000000,0.000000,
3,0.076000,0.184000,0.315000,0.300000,0.125000,0.000000,0.000000,0.000000,0.000000,0.000000,0.000000,
4,0.062900,0.136600,0.248000,0.290000,0.200000,0.062500,0.000000,0.000000,0.000000,0.000000,0.000000,
5,0.051760,0.104240,0.196500,0.260000,0.231250,0.125000,0.031250,0.000000,0.000000,0.000000,0.000000,
6,0.042534,0.080996,0.156720,0.225375,0.235000,0.168750,0.075000,0.015625,0.000000,0.000000,0.000000,
7,0.034962,0.063742,0.125723,0.192010,0.223563,0.192500,0.115938,0.043750,0.007813,0.000000,0.000000,
8,0.028763,0.050642,0.101362,0.162022,0.204680,0.200375,0.147000,0.076250,0.025000,0.003906,0.000000,
9,0.023691,0.040529,0.082068,0.135958,0.182921,0.197190,0.166613,0.106500,0.048516,0.014063,0.001953,
DC 7
,-1,0,1,2,3,4,5,6,7,8,9
1,0.100000,0.500000,0.400000,0.000000,0.000000,0.000000,0.000000,0.000000,0.000000,0.000000,0.000000,
2,0.110000,0.330000,0.400000,0.160000,0.000000,0.000000,0.000000,0.000000,0.000000,0.000000,0.000000,
3,0.103000,0.245000,0.348000,0.240000,0.064000,0.000000,0.000000,0.000000,0.000000,0.000000,0.000000,
4,0.092700,0.192100,0.296000,0.265600,0.128000,0.025600,0.000000,0.000000,0.000000,0.000000,0.000000,
5,0.082310,0.155250,0.251400,0.264000,0.172800,0.064000,0.010240,0.000000,0.000000,0.000000,0.000000,
6,0.072695,0.127905,0.214200,0.249840,0.198400,0.102144,0.030720,0.004096,0.000000,0.000000,0.000000,
7,0.064065,0.106793,0.183246,0.230440,0.209350,0.133504,0.056627,0.014336,0.001638,0.000000,0.000000,
8,0.056420,0.090045,0.157384,0.209453,0.210202,0.156155,0.083149,0.029983,0.006554,0.000655,0.000000,
9,0.049686,0.076500,0.135656,0.188700,0.204498,0.170473,0.107035,0.048906,0.015335,0.002949,0.000262,
DC 8
,-1,0,1,2,3,4,5,6,7,8,9
1,0.100000,0.600000,0.300000,0.000000,0.000000,0.000000,0.000000,0.000000,0.000000,0.000000,0.000000,
2,0.130000,0.420000,0.360000,0.090000,0.000000,0.000000,0.000000,0.000000,0.000000,0.000000,0.000000,
3,0.136000,0.324000,0.351000,0.162000,0.027000,0.000000,0.000000,0.000000,0.000000,0.000000,0.000000,
4,0.133300,0.264600,0.324000,0.205200,0.064800,0.008100,0.000000,0.000000,0.000000,0.000000,0.000000,
5,0.127360,0.223560,0.294300,0.226800,0.101250,0.024300,0.002430,0.000000,0.000000,0.000000,0.000000,
6,0.120286,0.192996,0.266328,0.234495,0.131220,0.045198,0.008748,0.000729,0.000000,0.000000,0.000000,
7,0.112953,0.169063,0.241145,0.233717,0.153600,0.067360,0.018881,0.003062,0.000219,0.000000,0.000000,
8,0.105745,0.149667,0.218778,0.227934,0.169011,0.088384,0.031843,0.007523,0.001050,0.000066,0.000000,
9,0.098834,0.133556,0.198960,0.219295,0.178625,0.106918,0.046373,0.014172,0.002893,0.000354,0.000020,

User avatar
WarDaft
Posts: 1583
Joined: Thu Jul 30, 2009 3:16 pm UTC

Re: Dice Probabilities for Tabletop RPGs

Postby WarDaft » Tue Feb 01, 2011 10:10 pm UTC

I was just about to start going crazy trying to figure out why the simple Haskell version I wrote was not agreeing with what W|A was saying, but then I realized I copied and pasted a typo into W|A - crisis averted.

Code: Select all

successes p e
   | e == 0 = 1 : [0,0..]
   | otherwise = f p k
   where
      k = successes p (e-1)
      f [] n = [0,0..]
      f (a:as) n = zipWith (+) (map (*a) n) (0: f as n)

toLose n = (sum $ take n $ successes [1,6,3] n, sum $ takeWhile (>0) $ drop n $ successes [1,6,3] n)
We can of course optimize this somewhat to:

Code: Select all

successes p e
   | e == 0 = 1 : [0,0..]
   | odd e = f p (successes p (e-1))
   | otherwise = f b b
   where
      b = successes p $ quot e 2
      f [] n = [0,0..]
      f (a:as) n = zipWith (+) (map (*a) n) (0: f as n)

toLose n = (sum $ take n $ successes [1,6,3] n, sum $ takeWhile (>0) $ drop n $ successes [1,6,3] n)
but it should only be about 120% faster. A naive polynomial squaring is an expensive operation, but it's still an improvement for very little effort. FFTs can be used to gain a much more substantial improvement... if you can use FFTs.

The odds of losing when rolling 1000 dice are less than 1 in 1.9*10^25
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11128
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Dice Probabilities for Tabletop RPGs

Postby Yakk » Tue Feb 01, 2011 10:32 pm UTC

That is why I pointed out the way to generate an accurate answer without multinomials. :)

Build a polynomial for your one die that takes into account the reroll.

Ie,
f(x) = 0.1 x^-1 + 0.6 x^0 + 0.2 x^1 + 0.1 x^1 f(x)
Nevermind the y trick -- just say "we'll ignore the chance of rolling more than 9 10s in a row off a single die". So we start with:
base = 0.1 x^-1 + 0.6 x^0 + 0.3 x^1
we then calculate:
iteration1 = 0.1 x^-1 + 0.6 x^0 + 0.2 x^1 + 0.1 x^1 * (base)
which describes "you can only reroll once" fully. We repeat this 9 times, and we get a polynomial that describes all of the probabilities of up to 9 rerolls off a single die. This is a polynomial with terms from x^-1 to x^9 or so -- you don't need to know what it is, you calculate it in your program!

Then you take this new stand-in for f(x) and you raise it to the 9th power.

---

For the Haskell programmer, you know how to write functional reals?

A real is a cauchy sequence of rationals.

From something like that, you can output a real number that is a coefficient of f(x) = 0.1 x^-1 + 0.6x^0 + 0.2 x^1 + 0.1 x^1 * f(x).

And then you can raise it to the power n, take derivatives, etc.

Now, in some cases, it becomes exceedingly hard to actually print out the resulting real as a decimal approximation.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

User avatar
WarDaft
Posts: 1583
Joined: Thu Jul 30, 2009 3:16 pm UTC

Re: Dice Probabilities for Tabletop RPGs

Postby WarDaft » Tue Feb 01, 2011 11:19 pm UTC

I've never heard of a case where a CReal is the fast way of getting the answer to something.

By hard, you mean computationally expensive yes? I'm pretty sure you can just have lazy digits take care of the printing work in Haskell.

I've never written a dynamic precision library before though, no. The last time I tried, I couldn't translate a satisfactorily amount of math (as in actually very little) to make it of any real use. Possibly because I was trying to take advantage of lazy digits to make printing them relatively easy and painless.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.

User avatar
Xanthir
My HERO!!!
Posts: 5413
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Dice Probabilities for Tabletop RPGs

Postby Xanthir » Wed Feb 02, 2011 1:34 am UTC

For virtually all non-trivial dice roll situations (like "exploding" 10s that can create more successes), it's faster and just as accurate (to within reasonable tolerances) to just run trials, instead of finding exact solutions. Just roll 10k times and log the results. Fast, easy, and accurate enough to make pretty graphs.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

Sagekilla
Posts: 382
Joined: Fri Aug 21, 2009 1:02 am UTC
Location: Long Island, NY

Re: Dice Probabilities for Tabletop RPGs

Postby Sagekilla » Wed Feb 02, 2011 4:56 am UTC

Xanthir wrote:For virtually all non-trivial dice roll situations (like "exploding" 10s that can create more successes), it's faster and just as accurate (to within reasonable tolerances) to just run trials, instead of finding exact solutions. Just roll 10k times and log the results. Fast, easy, and accurate enough to make pretty graphs.


This is probably the fastest and easiest way to do it. You can build a function
to do a test trial, and then just run a couple million trials and keep a running tally.

You have it run say, 10 million trials, and have it output data after every 250k trials.

Then you can see how your results converge too ;)
http://en.wikipedia.org/wiki/DSV_Alvin#Sinking wrote:Researchers found a cheese sandwich which exhibited no visible signs of decomposition, and was in fact eaten.

User avatar
WarDaft
Posts: 1583
Joined: Thu Jul 30, 2009 3:16 pm UTC

Re: Dice Probabilities for Tabletop RPGs

Postby WarDaft » Wed Feb 02, 2011 4:32 pm UTC

It's definitely not the fastest, particularly for larger checks.

For 10 roll checks, 500k trials (5 million rolls) was still only 3 digits accurate, and computing the exact results is effectively instant even in an interpreted environment. Computing the exact results on 100 rolls is still less than 1/4th of a second (again, interpreted environment) but randomly it would require at least doubling the number of trials, and each trial would be 10 times larger.

Now, practically, you might never need to know the odds for winning a 100 or 1000 die check, but when has that ever stopped anyone? If you trust the language's native RNG it does make for a quicker implementation, but if you don't, it's not that either.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11128
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Dice Probabilities for Tabletop RPGs

Postby Yakk » Wed Feb 02, 2011 4:53 pm UTC

The neat thing about the random trial is that the convergence rate doesn't go down as your model complexity goes up.

So you don't need more trials -- the trials are just more complex. (this is one of the reasons why ray tracers use randomized sampling on complex situations, rather than attempting to solve them exactly).
By hard, you mean computationally expensive yes? I'm pretty sure you can just have lazy digits take care of the printing work in Haskell.

I mean if you do things like divide at any point, you run into a problem that you cannot guarantee that the program will terminate before it gives you a digit. (computable reals cannot detect division by zero deterministically) Multiplication causes lesser issues (where you need an approximation to how big one side is in order to figure out how accurate your estimate needs to be in order to generate the proper amount of output precision. This requires that you poke each side to get an estimate, which could lead to n^2 execution time.)
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

User avatar
WarDaft
Posts: 1583
Joined: Thu Jul 30, 2009 3:16 pm UTC

Re: Dice Probabilities for Tabletop RPGs

Postby WarDaft » Wed Feb 02, 2011 6:08 pm UTC

Actually you do, in this case, because the probability of losing goes down with more dice added (with 100 dice, it's ~1 in 3000 to lose, 10 dice is ~1 in 10 to lose) so you're modelling a substantially less likely event. As such, you need more trials for the same accuracy.

Specifically, 50k trials for 10 dice gave me less than 1% error, while 50k trials for 100 dice gave me 15% error. (I didn't feel like compiling, so 50 million rolls was more than I had patience for off hand)




Division by zero and the like is good point.

If you implement them as lazy digit strings you don't actually need to do any approximation tracking, each digit simply knows what it is and can figure it out when needed to print, though it does make it more complicated in other ways.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11128
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Dice Probabilities for Tabletop RPGs

Postby Yakk » Wed Feb 02, 2011 6:13 pm UTC

It depends if you are counting absolute or relative accuracy.

Ie, is 0.00000 an accurate measurement of 0.000001, or is it horribly inaccurate?

I suppose there are more output events when you have more dice. And if you aren't just modeling the CDF and using something like L^2 for your error metric (instead of L^inf), you are going to find that more variables being output means you need more trials to get all of the variables to be sufficiently accurate.

Or is there something else going on I'm missing?
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

User avatar
WarDaft
Posts: 1583
Joined: Thu Jul 30, 2009 3:16 pm UTC

Re: Dice Probabilities for Tabletop RPGs

Postby WarDaft » Wed Feb 02, 2011 6:56 pm UTC

No, I just thought that as the chance of losing is roughly exponentially proportional to the number of dice, a relative error measurement was more appropriate than an absolute error measurement. Otherwise, almost all die counts will fall into the same category as far as chance of losing goes.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.

User avatar
kriel
Posts: 923
Joined: Thu Feb 07, 2008 2:58 pm UTC
Location: Somewhere I'm not.
Contact:

Re: Dice Probabilities for Tabletop RPGs

Postby kriel » Thu Feb 10, 2011 8:58 pm UTC

Hm. Question.

Earlier in the thread you mentioned using recursive polynomial multiplication to figure out how the 'roll 10s again' thing would work.

Would I be able to do that once, and then treat my single die as '-1, 0, 0, 0, 0, 0, 0, 1, 1, 1.26' (or whatever the probability of 'successes' on the d10 works out to) and then just use the above polynomial multiplication to figure the odds? Or would I have to re-figure it every time a 10 came up?

User avatar
Yakk
Poster with most posts but no title.
Posts: 11128
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Dice Probabilities for Tabletop RPGs

Postby Yakk » Thu Feb 10, 2011 10:29 pm UTC

That generates a decent approximation, but it isn't exact.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

User avatar
kriel
Posts: 923
Joined: Thu Feb 07, 2008 2:58 pm UTC
Location: Somewhere I'm not.
Contact:

Re: Dice Probabilities for Tabletop RPGs

Postby kriel » Fri Feb 11, 2011 4:22 pm UTC

Yakk wrote:edited 6 times in total.
Now I'm curious what it said before. >> but thank you.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11128
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Dice Probabilities for Tabletop RPGs

Postby Yakk » Fri Feb 11, 2011 4:23 pm UTC

kriel wrote:
Yakk wrote:edited 6 times in total.
Now I'm curious what it said before. >> but thank you.
Mu.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 4 guests