math on initiative

[komi]

WARNING: I'm just geeking out with math here. It won't really help you build a better character or win more fights. But if this sort of thing interests you, keep reading.

I wrote a program that calculates the statistics for rolling initiative at the start of combat. It started over at Gleemax with people trying to figure out if Improved Init or Danger Sense was better. This was solved by looking at 1-on-1 statistics. But then someone asked what happens when you expand the problem to N people, how does the problem change. I thought this was an interesting math problem, so I found a solution (with help from people at xkcd) and wrote a program to calculate the odds. I worked hard on it and didn't want it to die with one post over there, so I thought I'd share here as well.

The problem is simply: After an initiative challenge among N creatures, what's the odds of Creature 1 going 1st, 2nd, ... last? I made the problem general enough where each creature can have any bonus value and can roll a d20 (or really a dR, where R is any integer) with arbitrary statistics. For example, you can work out the odds for rolling twice and keeping the best, rolling 2d10, rolling a cheat die where the '1' is replaced with a second '20', always rolling max, or anything else. In my python code there's a section that looks like this:

    ( 8, 'rolltwice'),
    ( 1, 'fair'),
    ( 0, 'fair'),
    ( 2, 'fair'),
    ( 3, 'fair'),
    ( 4, 'fair'),

Each line is a creature. The first number is its init bonus, the second column is the die statistics. 'fair' means a normal d20 with a uniform distribution. 'rolltwice' means roll two d20s and keep the higher number.

After running the code, you get a result like this:

 # | B |Statistics|    1      2      3      4      5      6   | Avg
---+---+----------+ ------ ------ ------ ------ ------ ------ +-----
 1 | 8 |rolltwice |  70.5%  14.7%   8.6%   4.4%   1.6%   0.3% | 1.53
 2 | 1 |fair      |   3.1%  12.9%  17.8%  19.2%  21.5%  25.5% | 4.20
 3 | 0 |fair      |   1.8%   9.4%  15.9%  18.6%  20.2%  34.2% | 4.49
 4 | 2 |fair      |   5.1%  16.9%  19.1%  19.5%  21.0%  18.4% | 3.90
 5 | 3 |fair      |   7.9%  21.0%  19.6%  19.4%  19.2%  12.9% | 3.60
 6 | 4 |fair      |  11.7%  25.1%  19.0%  18.9%  16.6%   8.7% | 3.30

Each row is a creature. B is its bonus. The second column are the die statistics.. 1-6 going across are the chances for that creature to achieve that position in initiative. Avg is the average ranking. For example if Creature 1 took note of what place in initiative order he got for every fight, then averaged them, he'd get a number close to 1.53.

The previous example modeled Creature 1 with Danger Sense. Here's the same example where he has Improved Init instead.

 # | B |Statistics|    1      2      3      4      5      6   | Avg
---+---+----------+ ------ ------ ------ ------ ------ ------ +-----
 1 |12 |fair      |  67.5%  15.7%  10.3%   4.9%   1.4%   0.2% | 1.58
 2 | 1 |fair      |   3.5%  12.9%  17.5%  19.0%  21.5%  25.5% | 4.19
 3 | 0 |fair      |   2.1%   9.4%  15.6%  18.5%  20.2%  34.2% | 4.48
 4 | 2 |fair      |   5.7%  16.7%  18.7%  19.4%  21.0%  18.5% | 3.89
 5 | 3 |fair      |   8.7%  20.7%  19.2%  19.3%  19.2%  12.9% | 3.59
 6 | 4 |fair      |  12.5%  24.6%  18.7%  18.9%  16.6%   8.7% | 3.29

Here's a last example for fun. It compares the same Creature 1 from above in a variety of situations. I ran the program for each case and stripped out just Creature 1 and combined them here. This compares how he does with the various feats, and I also threw in my extra dice statistics (cheat, reroll, and 2d10, rolls natural 20, rolls natural 1).

 # | B |Statistics|    1      2      3      4      5      6   | Avg
---+---+----------+ ------ ------ ------ ------ ------ ------ +-----
 1 | 8 |fair      |  47.8%  17.6%  15.3%  11.7%   6.1%   1.5% | 2.15 Normal
 1 |10 |fair      |  57.7%  17.0%  13.3%   8.2%   3.2%   0.6% | 1.84 QD
 1 |12 |fair      |  67.5%  15.7%  10.3%   4.9%   1.4%   0.2% | 1.58 II
 1 | 8 |rolltwice |  70.5%  14.7%   8.6%   4.4%   1.6%   0.3% | 1.53 DS
 1 |10 |rolltwice |  79.9%  11.2%   5.7%   2.4%   0.7%   0.1% | 1.33 DS+QD
 1 |12 |rolltwice |  87.4%   7.9%   3.3%   1.1%   0.2%   0.0% | 1.19 DS+II
 1 | 8 |cheat     |  52.8%  17.4%  14.4%  10.0%   4.5%   0.9% | 1.99
 1 | 8 |reroll    |  66.7%  14.7%   8.8%   6.0%   3.0%   0.8% | 1.66
 1 | 8 |2d10      |  49.4%  24.6%  15.3%   7.6%   2.6%   0.4% | 1.91
 1 | 8 |max       | 100.0%   0.0%   0.0%   0.0%   0.0%   0.0% | 1.00
 1 | 8 |min       |   0.5%   4.7%  18.1%  34.1%  31.4%  11.3% | 4.25

I wish I could provide some cool graphs that gave a comprehensive look at this problem with insight on what decisions to make in game, but the problem is basically open-ended because you can have any number of participants. And even if we fix that, each new creature adds another dimension to the result space, so it's impractical to graph. So I just have to leave you with examples and my code itself. Feel free to play with it. I hope someone else does. But if not, I still enjoyed working on the problem.

If you're curious about the math behind this, go to the xkcd thread I started. Yakk over there had a very clever way of setting up the math for this problem.

Here's my python code to run it. I tried to comment it as best as I could. Basically you just need to edit the creatureTable as I mentioned above. Change the bonus to model II and QD. Change the die statistics to model DS. This should handle about 20 creatures. I wrote this code to only be from one creature's perspective. To give lines for all the other creatures, I had to run it N times. So it runs N times longer than it would otherwise. You can improve this by only running for Creature 1 (change the comment on a for loop in the code as noted in the comments). It will give exactly the same statistics but only for creature 1. In this way you can have dozens of creatures if you want. I ran 60 in about a minute.

[sblock=init4e.py]

#!/bin/env python

# Die used in initiave contest.  20 is normal, but any value will
# generate valid statistics.
die = 20

# Dice statistics.  Each entry has a distribution for generating a
# 1-20 (or 1-die).
prob = {
  'fair'     : [1.0/die]*die,
  'rolltwice': [(2.0*d-1)/die/die for d in range(1, die+1)],
  'cheat'    : [0]+[1.0/die]*(die-2)+[2.0/die],
  'reroll'   : [1.0/2/die]*(die/2) + [3.0/2/die]*(die/2),
  '2d10'     : [v*4.0/die/die for v in range(die/2+1)+range(die/2-1, 0, -1)],
  'max'      : [0.0]*(die-1)+[1.0],
  'min'      : [1.0]+[0.0]*(die-1),
  }

## This code validates the dice statistics above.  It's commented
## here because these are all valid.  If you want to add your own,
## you can uncomment this to check the results.  Each distribution
## must satisfy three conditions:
## 1) 20 entries (or equal to value of die)
## 2) must sum to 1
## 3) must all be positive
#
#for k, v in prob.items():
#  tot = abs(sum(v)-1) < 0.000001
#  cnt = len(v) == die
#  pos = len([p for p in v if p < 0]) == 0
#  if not (tot and cnt and pos):
#    print "WARNING: Statistics '%s' are invalid!" % k

######################################################################
def main(args):
 
  ####################################################################
  # Each line of the creature table represents an initiave roll.  It
  # has the following format:
  #   (Bonus, 'Stats')
  #
  # Bonus is that creature's initiative bonus and 'Stats' are the
  # die statistics.  Here are the valid 'Stats' values
  #
  #   'fair'      = normal d20 roll
  #   'rolltwice' = roll twice, keep better result
  #   'cheat'     = cheat die where '1' is replaced with second '20'
  #   'reroll'    = reroll but must keep second.  Assumes reroll if
  #                 less than average
  #   '2d10'      = 2d10 instead of 1d20
  #   'max'       = always roll maximum
  #   'min'       = always roll minimum
  ####################################################################
  creatureTable = [
    ( 8, 'fair'),
    ( 1, 'fair'),
    ( 1, 'fair'),
    ( 2, 'fair'),
    ( 2, 'fair'),
    ( 3, 'fair'),
    ]
  ####################################################################

  # Each run through calcRanking below only gives results based on
  # creatureTable[0].  At first I was only going to deal with this
  # problem, but then I realized that I can rotate through the
  # creatures starting with a new one each time.  This way I can
  # calculate complete statistics.  Unfortunately this gives an O(n^2)
  # running time and becomes unwieldy after about 20 creatures.  You
  # can run many many more by not looping through all creatures.  To
  # do this, change the commented for loop line below.

  placeList = [] # stores the odds for each ranking.
  mplaceList = [] # stores the average ranking.
  for k in range(len(creatureTable)):
  #for k in [0]:
    # Run calcRanking on the list N times, each time appending the
    # results on the end of placeList.
    placeList.append(calcRanking(creatureTable[k:]+creatureTable[:k]))
    mplaceList.append(sum([n*p for n, p in enumerate(placeList[-1])])+1)

  # Generate a report.
  print
  if die != 20:
    print "Rolling d%d's for initiative!" % die
    print
  print ' # | B |Statistics|',
  for n in range(len(creatureTable)):
    print '   %-2d ' % (n+1),
  print '| Avg'

  print '---+---+----------+',
  for n in range(len(creatureTable)):
    print '------',
  print '+-----'

  for cn, ((b, p), place, mplace) in enumerate(zip(creatureTable,
                                                   placeList,
                                                   mplaceList)):
    print '%2d' % (cn+1),
    print '|%2d' % b,
    print '|%-10s|' % p,
    for p in place:
      print '%5.1f%%' % (p*100),
    print '| %4.2f' % mplace
  print

  ## Generate the table for one-on-one statistics.
  #creatureTable = [
  #  [ 0, 'fair'],
  #  [ 0, 'fair'],
  #  ]
  #res = []
  #for d in range(-die, die+1):
  #  creatureTable[0][0] = d
  #  res.append([d]+calcRanking(creatureTable))
  #
  #for d, p, q in res:
  #  print d, p



######################################################################


######################################################################
def calcRanking(C):
  """
  Calculates the statistics of creature C[0] ending in 1st through Nth
  place.  All statistics are based on C[0], so you don't find out
  anything about the other creatures.
  """

  # Creature C[0] is the main creature.  Pull it out of the list.
  B0, pkey = C[0]
  pR = prob[pkey]

  res = []

  # The strategy is assume creature C[0] rolls a value r.  For each r,
  # calculate the odds of each place.  Then at the end, weight each
  # result by the odds of C[0] rolling r.
  for r in range(die):

    # I'm not going to go into too much detail on the math.
    # Basically, I work out a distribution pair-wise for C[0] and each
    # other creature and then add them together (done through
    # convolution).  To properly deal with multi-way ties, I need to
    # keep track of win, lose, and tie conditions.  This makes it 2D
    # convolution.  The tie cases are broken up later.
    mat = [[1]];

    for B, pkey in C[1:]:
      p = prob[pkey]
      dB = B - B0
      extra = r-dB;
      P0 = sum(p[:max(min(extra,die),0)])
      Pt = 0
      P1 = sum(p[max(extra+1,0):]);

      if 0 <= extra <= die-1:
        if   dB > 0:
          P1 += p[extra]
        elif dB == 0:
          Pt = p[extra]
        else:
          P0 += p[extra]

      A = [ [P0, P1], [Pt, 0] ]
      mat = conv2(mat, A)

    pr = mat[0][:]
    ind = len(mat)-1
    for n in range(ind):
      z = conv(mat[n+1][:-n-1], [1.0/(n+2)]*(n+2))
      for i in range(len(pr)):
        pr[i] += z[i]

    res.append([v*pR[r] for v in pr])

  return [sum(li) for li in zip(*res)]

######################################################################


######################################################################
def conv(x, y):
  """
  1D convolution.  The resultant vector is of length len(x)+len(y)-1.
  """
  P, Q = len(x), len(y)
  N = P + Q - 1
  z = []
  for k in range(N):
    t = 0
    lower = max(0, k-(Q-1))
    upper = min(P-1, k)
    for i in range(lower, upper+1):
      t = t + x[i]*y[k-i]
    z.append(t)
  return z

######################################################################


######################################################################
def conv2(A, B):
  """
  2D convolution.  A and B are matrices stored as lists of lists.  The
  resultant matrix has a number of rows of nrows(A)+nrows(B)-1, and
  number of columns of ncols(A)+ncols(B)-1.
  """
  ar = len(A)
  ac = len(A[0])

  br = len(B)
  bc = len(B[0])

  cr = ar + br - 1
  cc = ac + bc - 1

  C = []
  for k in range(cr):
    C.append([])
    for j in range(cc):
      lrows = max(0, k-(br-1))
      urows = min(ar-1, k)
      lcols = max(0, j-(bc-1))
      ucols = min(ac-1, j)
      t = 0
      for kk in range(lrows, urows+1):
        for jj in range(lcols, ucols+1):
          t += A[kk][jj]*B[k-kk][j-jj]
      C[-1].append(t)
  return C

######################################################################


# Start.  Pass arguments into the main function at the top.
if __name__ == '__main__':
  import sys
  main(sys.argv[1:])

[/sblock]

 

[Mengu]

I'd be curious to see what the table looks like without one character upsetting the higher end of the chart. For instance what kind of results would we get for:

1. Goblin Blackblade +7
2. Wizard +6
3. Goblin Warriors +5
4. Ranger +4
5. Goblin Cutters +3
6. Warlock +2
7. Fighter +1
8. Cleric +0

 

[komi]

I removed the statistics column to remove scrolling in the Code box.

 # | B |    1      2      3      4      5      6      7      8   | Avg
---+---+ ------ ------ ------ ------ ------ ------ ------ ------ +-----
 1 | 7 |  31.8%  15.1%  13.0%  12.4%  11.6%   9.3%   5.3%   1.5% | 3.14
 2 | 6 |  23.5%  16.7%  13.2%  12.6%  12.4%  11.2%   7.7%   2.7% | 3.51
 3 | 5 |  16.8%  16.6%  13.6%  12.7%  12.7%  12.6%  10.3%   4.6% | 3.90
 4 | 4 |  11.5%  15.2%  13.7%  12.8%  12.8%  13.4%  13.0%   7.5% | 4.30
 5 | 3 |   7.5%  13.0%  13.4%  12.8%  12.8%  13.7%  15.2%  11.5% | 4.70
 6 | 2 |   4.6%  10.3%  12.6%  12.7%  12.7%  13.6%  16.6%  16.8% | 5.10
 7 | 1 |   2.7%   7.7%  11.2%  12.4%  12.6%  13.2%  16.7%  23.5% | 5.49
 8 | 0 |   1.5%   5.3%   9.3%  11.6%  12.4%  13.0%  15.1%  31.8% | 5.87

It has an interesting symmetry to it. This seems to happen when you have uniform steps between init bonuses.

 

[komi]

dupe

 

[Mengu]

My gut feeling says there is something wrong with the formula at the two extremes. The chance for the Goblin Blackblade to go first vs second should not have that big of a difference. Let me see if I can do some simulation testing.

Edit: Nevermind, my gut seems to be wrong.

 

[KingCrab]

Python is such a wonderful language. Nice code.

 

[ac_noj]

Komi, are you able to make a table showing Initiatives +0 to +10 with and without Danger Sense?

 

[komi]

Komi, are you able to make a table showing Initiatives +0 to +10 with and without Danger Sense?

This was first done graphically by someone else. I don't want to take credit for it. This is set up as a 1-on-1 contest where each curve shows improvement (in terms of additional percentage chance of success) over not having any feats. The x-axis is your init bonus minus your opponent's.

Since we, in D&D, are used to thinking in terms of pluses to your dice, I did a similar graph where I model Danger Sense's improvement as a bonus.

As an example, take Danger Sense (red curve) when your init bonus matches your opponent's (x value of 0). Danger Sense improves your chance of success by about 17% from the first link. According to this new graph, you get about the same chance of success without Danger Sense if you have a +3 to your roll.

(max(1d20, 1d20) vs. 1d20) ~= (1d20+3 vs. 1d20)

You could do all this with my program above, but since we're only dealing with 1-on-1, there's more efficient ways of doing it.

Here's the absolute chances of success for with and without:
[sblock]

delta  Normal  Danger Sense
-20     0.0%     0.0%
-19     0.0%     0.0%
-18     0.3%     0.5%
-17     0.8%     1.4%
-16     1.5%     2.8%
-15     2.5%     4.6%
-14     3.8%     6.8%
-13     5.3%     9.4%
-12     7.0%    12.2%
-11     9.0%    15.4%
-10    11.3%    18.9%
 -9    13.8%    22.7%
 -8    16.5%    26.7%
 -7    19.5%    30.9%
 -6    22.8%    35.3%
 -5    26.2%    39.8%
 -4    30.0%    44.5%
 -3    34.0%    49.3%
 -2    38.3%    54.2%
 -1    42.8%    59.1%
  0    50.0%    66.6%
  1    57.3%    73.6%
  2    61.8%    77.7%
  3    66.0%    81.3%
  4    70.0%    84.5%
  5    73.8%    87.3%
  6    77.3%    89.8%
  7    80.5%    91.9%
  8    83.5%    93.7%
  9    86.3%    95.2%
 10    88.8%    96.4%
 11    91.0%    97.5%
 12    93.0%    98.3%
 13    94.8%    98.9%
 14    96.3%    99.3%
 15    97.5%    99.6%
 16    98.5%    99.8%
 17    99.3%    99.9%
 18    99.8%   100.0%
 19   100.0%   100.0%
 20   100.0%   100.0%

[/sblock]

 

[Audrik]

Nice work. This sort of thing is EXACTLY why I majored in Mathematics my first semester. What a Mathematics major actually entailled is exactly why I majored in English Literature from my second semester on.

 

[ac_noj]

Thanks Komi you're a champion. It's stuff like this that brought me to this forum in the first place.