Reply to thread

Message

<blockquote data-quote="komi" data-source="post: 4392759" data-attributes="member: 60878">WARNING: I'm just geeking out with math here.&nbsp; It won't really help you build a better character or win more fights.&nbsp; 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.&nbsp; It started over at <a href="http://forums.gleemax.com/showpost.php?p=16398005&amp;postcount=106" target="_blank">Gleemax</a> with people trying to figure out if Improved Init or Danger Sense was better.&nbsp; This was solved by looking at 1-on-1 statistics.&nbsp; But then someone asked what happens when you expand the problem to N people, how does the problem change.&nbsp; 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.&nbsp; 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. <img src="https://cdn.jsdelivr.net/joypixels/assets/8.0/png/unicode/64/1f642.png" class="smilie smilie--emoji" loading="lazy" width="64" height="64" alt=":)" title="Smile&nbsp; &nbsp; :)"&nbsp; data-smilie="1"data-shortname=":)" />The problem is simply: After an initiative challenge among N creatures, what's the odds of Creature 1 going 1st, 2nd, ... last?&nbsp; 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.&nbsp; 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.&nbsp; In my python code there's a section that looks like this:[code]&nbsp; &nbsp; ( 8, 'rolltwice'),&nbsp; &nbsp; ( 1, 'fair'),&nbsp; &nbsp; ( 0, 'fair'),&nbsp; &nbsp; ( 2, 'fair'),&nbsp; &nbsp; ( 3, 'fair'),&nbsp; &nbsp; ( 4, 'fair'),[/code]Each line is a creature.&nbsp; The first number is its init bonus, the second column is the die statistics.&nbsp; 'fair' means a normal d20 with a uniform distribution.&nbsp; 'rolltwice' means roll two d20s and keep the higher number.After running the code, you get a result like this:[code] # | B |Statistics|&nbsp; &nbsp; 1&nbsp; &nbsp; &nbsp; 2&nbsp; &nbsp; &nbsp; 3&nbsp; &nbsp; &nbsp; 4&nbsp; &nbsp; &nbsp; 5&nbsp; &nbsp; &nbsp; 6&nbsp;&nbsp; | Avg---+---+----------+ ------ ------ ------ ------ ------ ------ +-----&nbsp;1 | 8 |rolltwice |&nbsp; 70.5%&nbsp; 14.7%&nbsp;&nbsp; 8.6%&nbsp;&nbsp; 4.4%&nbsp;&nbsp; 1.6%&nbsp;&nbsp; 0.3% | 1.53&nbsp;2 | 1 |fair&nbsp; &nbsp; &nbsp; |&nbsp;&nbsp; 3.1%&nbsp; 12.9%&nbsp; 17.8%&nbsp; 19.2%&nbsp; 21.5%&nbsp; 25.5% | 4.20&nbsp;3 | 0 |fair&nbsp; &nbsp; &nbsp; |&nbsp;&nbsp; 1.8%&nbsp;&nbsp; 9.4%&nbsp; 15.9%&nbsp; 18.6%&nbsp; 20.2%&nbsp; 34.2% | 4.49&nbsp;4 | 2 |fair&nbsp; &nbsp; &nbsp; |&nbsp;&nbsp; 5.1%&nbsp; 16.9%&nbsp; 19.1%&nbsp; 19.5%&nbsp; 21.0%&nbsp; 18.4% | 3.90&nbsp;5 | 3 |fair&nbsp; &nbsp; &nbsp; |&nbsp;&nbsp; 7.9%&nbsp; 21.0%&nbsp; 19.6%&nbsp; 19.4%&nbsp; 19.2%&nbsp; 12.9% | 3.60&nbsp;6 | 4 |fair&nbsp; &nbsp; &nbsp; |&nbsp; 11.7%&nbsp; 25.1%&nbsp; 19.0%&nbsp; 18.9%&nbsp; 16.6%&nbsp;&nbsp; 8.7% | 3.30[/code]Each row is a creature.&nbsp; B is its bonus.&nbsp; The second column are the die statistics..&nbsp; 1-6 going across are the chances for that creature to achieve that position in initiative.&nbsp; Avg is the average ranking.&nbsp; 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.&nbsp; Here's the same example where he has Improved Init instead.[code] # | B |Statistics|&nbsp; &nbsp; 1&nbsp; &nbsp; &nbsp; 2&nbsp; &nbsp; &nbsp; 3&nbsp; &nbsp; &nbsp; 4&nbsp; &nbsp; &nbsp; 5&nbsp; &nbsp; &nbsp; 6&nbsp;&nbsp; | Avg---+---+----------+ ------ ------ ------ ------ ------ ------ +-----&nbsp;1 |12 |fair&nbsp; &nbsp; &nbsp; |&nbsp; 67.5%&nbsp; 15.7%&nbsp; 10.3%&nbsp;&nbsp; 4.9%&nbsp;&nbsp; 1.4%&nbsp;&nbsp; 0.2% | 1.58&nbsp;2 | 1 |fair&nbsp; &nbsp; &nbsp; |&nbsp;&nbsp; 3.5%&nbsp; 12.9%&nbsp; 17.5%&nbsp; 19.0%&nbsp; 21.5%&nbsp; 25.5% | 4.19&nbsp;3 | 0 |fair&nbsp; &nbsp; &nbsp; |&nbsp;&nbsp; 2.1%&nbsp;&nbsp; 9.4%&nbsp; 15.6%&nbsp; 18.5%&nbsp; 20.2%&nbsp; 34.2% | 4.48&nbsp;4 | 2 |fair&nbsp; &nbsp; &nbsp; |&nbsp;&nbsp; 5.7%&nbsp; 16.7%&nbsp; 18.7%&nbsp; 19.4%&nbsp; 21.0%&nbsp; 18.5% | 3.89&nbsp;5 | 3 |fair&nbsp; &nbsp; &nbsp; |&nbsp;&nbsp; 8.7%&nbsp; 20.7%&nbsp; 19.2%&nbsp; 19.3%&nbsp; 19.2%&nbsp; 12.9% | 3.59&nbsp;6 | 4 |fair&nbsp; &nbsp; &nbsp; |&nbsp; 12.5%&nbsp; 24.6%&nbsp; 18.7%&nbsp; 18.9%&nbsp; 16.6%&nbsp;&nbsp; 8.7% | 3.29[/code]Here's a last example for fun.&nbsp; It compares the same Creature 1 from above in a variety of situations.&nbsp; I ran the program for each case and stripped out just Creature 1 and combined them here.&nbsp; 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).[code] # | B |Statistics|&nbsp; &nbsp; 1&nbsp; &nbsp; &nbsp; 2&nbsp; &nbsp; &nbsp; 3&nbsp; &nbsp; &nbsp; 4&nbsp; &nbsp; &nbsp; 5&nbsp; &nbsp; &nbsp; 6&nbsp;&nbsp; | Avg---+---+----------+ ------ ------ ------ ------ ------ ------ +-----&nbsp;1 | 8 |fair&nbsp; &nbsp; &nbsp; |&nbsp; 47.8%&nbsp; 17.6%&nbsp; 15.3%&nbsp; 11.7%&nbsp;&nbsp; 6.1%&nbsp;&nbsp; 1.5% | 2.15 Normal&nbsp;1 |10 |fair&nbsp; &nbsp; &nbsp; |&nbsp; 57.7%&nbsp; 17.0%&nbsp; 13.3%&nbsp;&nbsp; 8.2%&nbsp;&nbsp; 3.2%&nbsp;&nbsp; 0.6% | 1.84 QD&nbsp;1 |12 |fair&nbsp; &nbsp; &nbsp; |&nbsp; 67.5%&nbsp; 15.7%&nbsp; 10.3%&nbsp;&nbsp; 4.9%&nbsp;&nbsp; 1.4%&nbsp;&nbsp; 0.2% | 1.58 II&nbsp;1 | 8 |rolltwice |&nbsp; 70.5%&nbsp; 14.7%&nbsp;&nbsp; 8.6%&nbsp;&nbsp; 4.4%&nbsp;&nbsp; 1.6%&nbsp;&nbsp; 0.3% | 1.53 DS&nbsp;1 |10 |rolltwice |&nbsp; 79.9%&nbsp; 11.2%&nbsp;&nbsp; 5.7%&nbsp;&nbsp; 2.4%&nbsp;&nbsp; 0.7%&nbsp;&nbsp; 0.1% | 1.33 DS+QD&nbsp;1 |12 |rolltwice |&nbsp; 87.4%&nbsp;&nbsp; 7.9%&nbsp;&nbsp; 3.3%&nbsp;&nbsp; 1.1%&nbsp;&nbsp; 0.2%&nbsp;&nbsp; 0.0% | 1.19 DS+II&nbsp;1 | 8 |cheat&nbsp; &nbsp;&nbsp; |&nbsp; 52.8%&nbsp; 17.4%&nbsp; 14.4%&nbsp; 10.0%&nbsp;&nbsp; 4.5%&nbsp;&nbsp; 0.9% | 1.99&nbsp;1 | 8 |reroll&nbsp; &nbsp; |&nbsp; 66.7%&nbsp; 14.7%&nbsp;&nbsp; 8.8%&nbsp;&nbsp; 6.0%&nbsp;&nbsp; 3.0%&nbsp;&nbsp; 0.8% | 1.66&nbsp;1 | 8 |2d10&nbsp; &nbsp; &nbsp; |&nbsp; 49.4%&nbsp; 24.6%&nbsp; 15.3%&nbsp;&nbsp; 7.6%&nbsp;&nbsp; 2.6%&nbsp;&nbsp; 0.4% | 1.91&nbsp;1 | 8 |max&nbsp; &nbsp; &nbsp;&nbsp; | 100.0%&nbsp;&nbsp; 0.0%&nbsp;&nbsp; 0.0%&nbsp;&nbsp; 0.0%&nbsp;&nbsp; 0.0%&nbsp;&nbsp; 0.0% | 1.00&nbsp;1 | 8 |min&nbsp; &nbsp; &nbsp;&nbsp; |&nbsp;&nbsp; 0.5%&nbsp;&nbsp; 4.7%&nbsp; 18.1%&nbsp; 34.1%&nbsp; 31.4%&nbsp; 11.3% | 4.25[/code]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.&nbsp; And even if we fix that, each new creature adds another dimension to the result space, so it's impractical to graph.&nbsp; So I just have to leave you with examples and my code itself.&nbsp; Feel free to play with it.&nbsp; I hope someone else does.&nbsp; <img src="https://cdn.jsdelivr.net/joypixels/assets/8.0/png/unicode/64/1f642.png" class="smilie smilie--emoji" loading="lazy" width="64" height="64" alt=":)" title="Smile&nbsp; &nbsp; :)"&nbsp; data-smilie="1"data-shortname=":)" />&nbsp; But if not, I still enjoyed working on the problem.If you're curious about the math behind this, go to the <a href="http://forums.xkcd.com/viewtopic.php?f=17&amp;t=24889&amp;start=0&amp;st=0&amp;sk=t&amp;sd=a" target="_blank">xkcd thread</a> I started.&nbsp; Yakk over there had a very clever way of setting up the math for this problem.Here's my python code to run it.&nbsp; I tried to comment it as best as I could.&nbsp; Basically you just need to edit the creatureTable as I mentioned above.&nbsp; Change the bonus to model II and QD.&nbsp; Change the die statistics to model DS.&nbsp; This should handle about 20 creatures.&nbsp; I wrote this code to only be from one creature's perspective.&nbsp; To give lines for all the other creatures, I had to run it N times.&nbsp; So it runs N times longer than it would otherwise.&nbsp; 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.&nbsp; In this way you can have dozens of creatures if you want.&nbsp; I ran 60 in about a minute.[sblock=init4e.py][code]#!/bin/env python# Die used in initiave contest.&nbsp; 20 is normal, but any value will# generate valid statistics.die = 20# Dice statistics.&nbsp; Each entry has a distribution for generating a# 1-20 (or 1-die).prob = {&nbsp; 'fair'&nbsp; &nbsp;&nbsp; : [1.0/die]*die,&nbsp; 'rolltwice': [(2.0*d-1)/die/die for d in range(1, die+1)],&nbsp; 'cheat'&nbsp; &nbsp; : [0]+[1.0/die]*(die-2)+[2.0/die],&nbsp; 'reroll'&nbsp;&nbsp; : [1.0/2/die]*(die/2) + [3.0/2/die]*(die/2),&nbsp; '2d10'&nbsp; &nbsp;&nbsp; : [v*4.0/die/die for v in range(die/2+1)+range(die/2-1, 0, -1)],&nbsp; 'max'&nbsp; &nbsp; &nbsp; : [0.0]*(die-1)+[1.0],&nbsp; 'min'&nbsp; &nbsp; &nbsp; : [1.0]+[0.0]*(die-1),&nbsp; }## This code validates the dice statistics above.&nbsp; It's commented## here because these are all valid.&nbsp; If you want to add your own,## you can uncomment this to check the results.&nbsp; 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():#&nbsp; tot = abs(sum(v)-1) &lt; 0.000001#&nbsp; cnt = len(v) == die#&nbsp; pos = len([p for p in v if p &lt; 0]) == 0#&nbsp; if not (tot and cnt and pos):#&nbsp; &nbsp; print &quot;WARNING: Statistics '%s' are invalid!&quot; % k######################################################################def main(args):&nbsp;&nbsp; ####################################################################&nbsp; # Each line of the creature table represents an initiave roll.&nbsp; It&nbsp; # has the following format:&nbsp; #&nbsp;&nbsp; (Bonus, 'Stats')&nbsp; #&nbsp; # Bonus is that creature's initiative bonus and 'Stats' are the&nbsp; # die statistics.&nbsp; Here are the valid 'Stats' values&nbsp; #&nbsp; #&nbsp;&nbsp; 'fair'&nbsp; &nbsp; &nbsp; = normal d20 roll&nbsp; #&nbsp;&nbsp; 'rolltwice' = roll twice, keep better result&nbsp; #&nbsp;&nbsp; 'cheat'&nbsp; &nbsp;&nbsp; = cheat die where '1' is replaced with second '20'&nbsp; #&nbsp;&nbsp; 'reroll'&nbsp; &nbsp; = reroll but must keep second.&nbsp; Assumes reroll if&nbsp; #&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp; less than average&nbsp; #&nbsp;&nbsp; '2d10'&nbsp; &nbsp; &nbsp; = 2d10 instead of 1d20&nbsp; #&nbsp;&nbsp; 'max'&nbsp; &nbsp; &nbsp;&nbsp; = always roll maximum&nbsp; #&nbsp;&nbsp; 'min'&nbsp; &nbsp; &nbsp;&nbsp; = always roll minimum&nbsp; ####################################################################&nbsp; creatureTable = [&nbsp; &nbsp; ( 8, 'fair'),&nbsp; &nbsp; ( 1, 'fair'),&nbsp; &nbsp; ( 1, 'fair'),&nbsp; &nbsp; ( 2, 'fair'),&nbsp; &nbsp; ( 2, 'fair'),&nbsp; &nbsp; ( 3, 'fair'),&nbsp; &nbsp; ]&nbsp; ####################################################################&nbsp; # Each run through calcRanking below only gives results based on&nbsp; # creatureTable[0].&nbsp; At first I was only going to deal with this&nbsp; # problem, but then I realized that I can rotate through the&nbsp; # creatures starting with a new one each time.&nbsp; This way I can&nbsp; # calculate complete statistics.&nbsp; Unfortunately this gives an O(n^2)&nbsp; # running time and becomes unwieldy after about 20 creatures.&nbsp; You&nbsp; # can run many many more by not looping through all creatures.&nbsp; To&nbsp; # do this, change the commented for loop line below.&nbsp; placeList = [] # stores the odds for each ranking.&nbsp; mplaceList = [] # stores the average ranking.&nbsp; for k in range(len(creatureTable)):&nbsp; #for k in [0]:&nbsp; &nbsp; # Run calcRanking on the list N times, each time appending the&nbsp; &nbsp; # results on the end of placeList.&nbsp; &nbsp; placeList.append(calcRanking(creatureTable[k:]+creatureTable[:k]))&nbsp; &nbsp; mplaceList.append(sum([n*p for n, p in enumerate(placeList[-1])])+1)&nbsp; # Generate a report.&nbsp; print&nbsp; if die != 20:&nbsp; &nbsp; print &quot;Rolling d%d's for initiative!&quot; % die&nbsp; &nbsp; print&nbsp; print ' # | B |Statistics|',&nbsp; for n in range(len(creatureTable)):&nbsp; &nbsp; print '&nbsp;&nbsp; %-2d ' % (n+1),&nbsp; print '| Avg'&nbsp; print '---+---+----------+',&nbsp; for n in range(len(creatureTable)):&nbsp; &nbsp; print '------',&nbsp; print '+-----'&nbsp; for cn, ((b, p), place, mplace) in enumerate(zip(creatureTable,&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp; placeList,&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp; mplaceList)):&nbsp; &nbsp; print '%2d' % (cn+1),&nbsp; &nbsp; print '|%2d' % b,&nbsp; &nbsp; print '|%-10s|' % p,&nbsp; &nbsp; for p in place:&nbsp; &nbsp; &nbsp; print '%5.1f%%' % (p*100),&nbsp; &nbsp; print '| %4.2f' % mplace&nbsp; print&nbsp; ## Generate the table for one-on-one statistics.&nbsp; #creatureTable = [&nbsp; #&nbsp; [ 0, 'fair'],&nbsp; #&nbsp; [ 0, 'fair'],&nbsp; #&nbsp; ]&nbsp; #res = []&nbsp; #for d in range(-die, die+1):&nbsp; #&nbsp; creatureTable[0][0] = d&nbsp; #&nbsp; res.append([d]+calcRanking(creatureTable))&nbsp; #&nbsp; #for d, p, q in res:&nbsp; #&nbsp; print d, p############################################################################################################################################def calcRanking(C):&nbsp; &quot;&quot;&quot;&nbsp; Calculates the statistics of creature C[0] ending in 1st through Nth&nbsp; place.&nbsp; All statistics are based on C[0], so you don't find out&nbsp; anything about the other creatures.&nbsp; &quot;&quot;&quot;&nbsp; # Creature C[0] is the main creature.&nbsp; Pull it out of the list.&nbsp; B0, pkey = C[0]&nbsp; pR = prob[pkey]&nbsp; res = []&nbsp; # The strategy is assume creature C[0] rolls a value r.&nbsp; For each r,&nbsp; # calculate the odds of each place.&nbsp; Then at the end, weight each&nbsp; # result by the odds of C[0] rolling r.&nbsp; for r in range(die):&nbsp; &nbsp; # I'm not going to go into too much detail on the math.&nbsp; &nbsp; # Basically, I work out a distribution pair-wise for C[0] and each&nbsp; &nbsp; # other creature and then add them together (done through&nbsp; &nbsp; # convolution).&nbsp; To properly deal with multi-way ties, I need to&nbsp; &nbsp; # keep track of win, lose, and tie conditions.&nbsp; This makes it 2D&nbsp; &nbsp; # convolution.&nbsp; The tie cases are broken up later.&nbsp; &nbsp; mat = [[1]];&nbsp; &nbsp; for B, pkey in C[1:]:&nbsp; &nbsp; &nbsp; p = prob[pkey]&nbsp; &nbsp; &nbsp; dB = B - B0&nbsp; &nbsp; &nbsp; extra = r-dB;&nbsp; &nbsp; &nbsp; P0 = sum(p[:max(min(extra,die),0)])&nbsp; &nbsp; &nbsp; Pt = 0&nbsp; &nbsp; &nbsp; P1 = sum(p[max(extra+1,0):]);&nbsp; &nbsp; &nbsp; if 0 &lt;= extra &lt;= die-1:&nbsp; &nbsp; &nbsp; &nbsp; if&nbsp;&nbsp; dB &gt; 0:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; P1 += p[extra]&nbsp; &nbsp; &nbsp; &nbsp; elif dB == 0:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; Pt = p[extra]&nbsp; &nbsp; &nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; P0 += p[extra]&nbsp; &nbsp; &nbsp; A = [ [P0, P1], [Pt, 0] ]&nbsp; &nbsp; &nbsp; mat = conv2(mat, A)&nbsp; &nbsp; pr = mat[0][:]&nbsp; &nbsp; ind = len(mat)-1&nbsp; &nbsp; for n in range(ind):&nbsp; &nbsp; &nbsp; z = conv(mat[n+1][:-n-1], [1.0/(n+2)]*(n+2))&nbsp; &nbsp; &nbsp; for i in range(len(pr)):&nbsp; &nbsp; &nbsp; &nbsp; pr[i] += z[i]&nbsp; &nbsp; res.append([v*pR[r] for v in pr])&nbsp; return [sum(li) for li in zip(*res)]############################################################################################################################################def conv(x, y):&nbsp; &quot;&quot;&quot;&nbsp; 1D convolution.&nbsp; The resultant vector is of length len(x)+len(y)-1.&nbsp; &quot;&quot;&quot;&nbsp; P, Q = len(x), len(y)&nbsp; N = P + Q - 1&nbsp; z = []&nbsp; for k in range(N):&nbsp; &nbsp; t = 0&nbsp; &nbsp; lower = max(0, k-(Q-1))&nbsp; &nbsp; upper = min(P-1, k)&nbsp; &nbsp; for i in range(lower, upper+1):&nbsp; &nbsp; &nbsp; t = t + x[i]*y[k-i]&nbsp; &nbsp; z.append(t)&nbsp; return z############################################################################################################################################def conv2(A, B):&nbsp; &quot;&quot;&quot;&nbsp; 2D convolution.&nbsp; A and B are matrices stored as lists of lists.&nbsp; The&nbsp; resultant matrix has a number of rows of nrows(A)+nrows(B)-1, and&nbsp; number of columns of ncols(A)+ncols(B)-1.&nbsp; &quot;&quot;&quot;&nbsp; ar = len(A)&nbsp; ac = len(A[0])&nbsp; br = len(B)&nbsp; bc = len(B[0])&nbsp; cr = ar + br - 1&nbsp; cc = ac + bc - 1&nbsp; C = []&nbsp; for k in range(cr):&nbsp; &nbsp; C.append([])&nbsp; &nbsp; for j in range(cc):&nbsp; &nbsp; &nbsp; lrows = max(0, k-(br-1))&nbsp; &nbsp; &nbsp; urows = min(ar-1, k)&nbsp; &nbsp; &nbsp; lcols = max(0, j-(bc-1))&nbsp; &nbsp; &nbsp; ucols = min(ac-1, j)&nbsp; &nbsp; &nbsp; t = 0&nbsp; &nbsp; &nbsp; for kk in range(lrows, urows+1):&nbsp; &nbsp; &nbsp; &nbsp; for jj in range(lcols, ucols+1):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; t += A[kk][jj]*B[k-kk][j-jj]&nbsp; &nbsp; &nbsp; C[-1].append(t)&nbsp; return C####################################################################### Start.&nbsp; Pass arguments into the main function at the top.if __name__ == '__main__':&nbsp; import sys&nbsp; main(sys.argv[1:])[/code][/sblock]</blockquote>

[QUOTE="komi, post: 4392759, member: 60878"] 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 [URL="http://forums.gleemax.com/showpost.php?p=16398005&postcount=106"]Gleemax[/URL] 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: [code] ( 8, 'rolltwice'), ( 1, 'fair'), ( 0, 'fair'), ( 2, 'fair'), ( 3, 'fair'), ( 4, 'fair'),[/code] 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: [code] # | 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[/code] 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. [code] # | 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[/code] 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). [code] # | 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[/code] 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 [URL="http://forums.xkcd.com/viewtopic.php?f=17&t=24889&start=0&st=0&sk=t&sd=a"]xkcd thread[/URL] 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][code] #!/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:]) [/code][/sblock] [/QUOTE]

Verification