It is days like this that I realize just how much math education I have missed.
I am a roleplaying gamer who actually delves into roleplaying game design on a semi-regular basis. The reason it is semi-regular is that, in addition to occasionally designing a game system from scratch, I am also inclined to fiddle with, and tweak, the systems of the games others have written for my own purposes. When playing (or even merely reading) something like D&D, Pathfinder RPG, Mutants and Masterminds, Sengoku, GURPS, Nephilim, Shadowrun, or any of the dozens of other game systems I've used over the years, I tend to find things I want to improve or just change.
I make changes from everything as minor as adding a new Ki Focus technique to the Sengoku system to reinventing the entire dice system used in Pathfinder RPG to make it an open-ended system involving multiple dice numbered from zero to five instead of a closed system involving a single die numbered from one to twenty.
It is while working on some details of this latter, more ambitious change to an existing system that I started trying to automate the process of measuring the probabilities of achieving particular rolls. I wrote some code in Ruby to do so, and the code works -- as long as system resources hold up. The problem is that my code stores numbers in arrays and for any nontrivial example combination of dice the number of possible rolls quickly outstrips my computer's capacity to store all those numbers in arrays that rapidly expand to ridiculous sizes.
I started trying to optimize the code a little bit to minimize memory use, by calculating possible permutations of possible combinations of die rolls in a given roll of dice one at a time, recording each unique permutation of each unique combination before "forgetting" it. This would obviate any need to store the complete set of permutations of combinations in an array. I got as far as only calculating the permutations for each combination, one combination at a time, while still having all combinations stored in their own array. My plan was to optimize it a piece at a time, but ultimately I realized that optimizing my brute force approach is probably just a case of far too much work for too little return on investment.
What I really need is some elegant mathematical expression I can use to translate arbitrary numbers of dice, of arbitrary numerical ranges, into a number of possible rolls. After searching around on the Internet for a while and thinking about it, I realized that there are three problems:
Lots of people seem to be interested in a total number of combinations or total number of permutations possible, for various constraints on what constitutes an acceptable combination or permutation, but nobody seems to be interested in finding out how many permutations of combinations might add up to a given possible number. Thus, there are no examples that I have found so far that would tell me what number of possibilities in ten rolls of a ten-sided die would add up to the number 17.
Almost nobody seems to consider the problem of using algorithms (such as the built-in Ruby methods Array#combination and Array#permutation) that fill up memory far too quickly by generating complete sets.
My math background is insufficient to figure this all out without basically trying to independently rediscover solutions that have probably made people famous in ages past.
I had been using Ruby 1.8.7's already mentioned combination and permutation methods. I have also, just for the heck of it, toyed with Ruby 1.9.2's Array#repeated_permutation, with similarly depressing results. These things are designed to generate arrays, and not to generate statistics for what would be unreasonably resource-consuming operations with a brute force approach.
An example of the sort of input and output I would like my program to generate is as follows -- what the program I have written so far provides for a relatively small number of a relatively low value set of dice:
> ruby permute.rb 5 1 5
5 1 0.03%
6 5 0.16%
7 15 0.48%
8 35 1.12%
9 70 2.24%
10 121 3.87%
11 185 5.92%
12 255 8.16%
13 320 10.24%
14 365 11.68%
15 381 12.19%
16 365 11.68%
17 320 10.24%
18 255 8.16%
19 185 5.92%
20 121 3.87%
21 70 2.24%
22 35 1.12%
23 15 0.48%
24 5 0.16%
25 1 0.03%
total possible rolls = 3125
There is little point right now in showing the source for this. It is nothing more than generation of arrays and counting various things that can be gleaned from those arrays. It is a naive, brute force approach to the problem that any competent programmer should be able to accomplish in his or her sleep (and that I accomplished after agonizing over it for a little while before realizing Ruby had actually done all the hard work for me).
In case it is not obvious, however, this is what my naive, brute force implementation does:
It takes three arguments. The first is a hypothetical number of dice. The second and third are the low and high values shown on the faces of the die type used. Thus, if there were such a thing as a regular polygonal five-sided die, the above would show the number of possible permutations, and the percentage chance for each permutation of all combinations of rolls that would produce each possible sum of values for five of those dice. At the end of the list, then, it shows the total possible rolls -- the sum of all numbers from the second column. Because I was using a brute force approach to this, it took approximately two seconds to generate that list.
I did, as I said, add an optimization that reduced the amount of RAM usage, but it is a relatively trivial change to the basic brute force approach that did not buy me much. It is still effectively an unusable program for any remotely nontrivial die roll example.
Generating the total possible rolls is easy. I wrote a dead-simple method for it just to make the puts expression look prettier:
def total_rolls(dice,start,finish)
(finish - start + 1) ** dice
end
. . . but generating the number of rolls for each possible sum of die results is a touch more challenging for me.
I guess I will just have to struggle with this for a while, and see what pops out of my head first -- a way to brute-force the problem without eating up all available RAM and swap space (dragging my laptop to a halt in the process), or figuring out an arithmetic expression I can translate to code to produce the needed numbers without actually calculating and storing craptons of permutations. I just need to be able to do something like this without hanging the process until it fills all available memory.
> ruby permute.rb 100 1 100
Once I have the per-sum number of possibilities, generating the percentages is definitely the easy part.