I enjoy a game called “Commands and Colors: Ancients”, which I’ve blogged about here before. It’s a simulation of tactical ancient warfare that uses special dice to resolve battles. In any given battle you can consider each six-sided die to have faces labeled with the symbols Miss, Miss, Hit, Sword, Helmet, Flag. To improve my play, I decided to generate and study a table of the odds of getting a specified number of hits when a specified number of dice is rolled. I set out to write a Python program to do this.
There are special circumstances under which flags and helmets convert to hits, so the program actually needs to print out several tables and is not entirely trivial. Still, it is computing on a mathematically simple model with strictly bounded computational cost – except for war elephants. These units have the special ability that when they roll a sword, the sword is counted as a hit and then rerolled. (This may make more sense if you think of a sword roll as representing impact damage.) You keep rolling and marking hits as long as the die keeps coming up swords.
To calculate the non-elephant probabilities I enumerated eight entire state spaces for each of 1 to 8 dice (the most you can ever roll under the rules – takes Alexander the Great or Julius Caesar leading a Heavy unit with the the Clash of Shields +2 bonus active), then counted up instances of each distinct outcome (so many misses, hits, swords, flags, banners) to assign a probability mass to each.
(Statisticians often think in terms of probability mass or probability weight, which has to be conserved as a distribution changes. It’s analogous to thinking of electricity as a fluid.)
I then had to write code to mutate a copy of each distribution according to the elephants’ sword-reroll rule. To do this, each outcome containing a sword hit needs its probability mass divided by six and reallocated to itself and five other outcomes with one fewer sword apiece; you stop reallocating when the probability mass on a sword-containing outcome drops below a very low noise level.
That particular piece of code gave me more trouble than the rest of the program put together. At one point I grumbled to a friend who had been following the project “I’m having persistent bugs in my probability mass reallocator.”
He looked right back at me and said, with a perfectly straight face, “Have you considered reversing the polarity of the neutron flow?”
heh. i saw a comment once (possibly on usenet?) from someone who really did fix a problem (with some reactor experiment) by reversing the polarity of a neutron flow–the phase polarity.
My memory of Calc 2 is a bit rusty, but couldn’t you have treated the exploding die as an infinite series and taken the limit with L’Hopital’s rule?
Also, you’ll want to invert the neutrino flux, not reverse the polarity of the neutron flow.
Cool story. Is there a reason why you didn’t just calculate the probabilities directly?
P(n hits) = (1/6)^n
P(n hits + helmet) = (1/6)^(n+1)
P(n hits + flag) = (1/6)^(n+1)
P(n hits + miss) = (1/3) * (1/6)^n
For the non-Whovians in the crowd, that last line was coined for the third Doctor, Jon Pertwee, as an all-purpose piece of technobabble.
>Cool story. Is there a reason why you didn’t just calculate the probabilities directly?
Those formulas aren’t correct; the general closed form for the non-elephant case with no specials would involve binomial coefficients. Let B(n, m) is the binomial coefficient n over m, which is the number of ways to chose a subset of cardinality m fom a set of cardinality n. If we want to calculate the odds that (say) 3 hits might come up on 4 dice, it’s actually B(4, 3)/6 ** 4.
It gets trickier than that when specials are involved, and much trickier for elephants. I don’t know what the closed form is in the second case, and there may not be one at all for the third one because of the reroll rule. I originally tried tabulating the returns from Monte Carlo simulation, then realized the state spaces are small enough for direct enumeration to be faster.
Because when you have hydraulic torque leakthrough, every second can mean lost pranktens!
Have you considered using Markov chains to find the probabilities? Your description of the war elephant mechanic sounds like it would be well suited to being modeled with one. Then again, I’m not too familiar with the game, and I probably know just enough about probability to get myself in trouble.
Have you considered using Markov chains to find the probabilities? Your description of the war elephant mechanic sounds like it would be well suited to being modeled with one.
Sure I considered it; in fact, arguably, I implemented it. The probability mass reallocator could be viewed as an algorithm for walking a regular DAG generated by a Markov chain.
I have mentioned that I used to be a mathematician, I think :-)
>My memory of Calc 2 is a bit rusty, but couldn’t you have treated the exploding die as an infinite series and taken the limit with L’Hopital’s rule?
Yes. I wasn’t sure how to prove where the rest of the probability mass would go in that case, though. It seemed more prudent to enumerate than risk getting a subtly wrong answer because I’d botched the derivation of the closed form.
Mind you, if the state spaces had been even a bit larger I’d have gone that route anyway and hacked out some sort of proof; 6 ** 8 = 1679616 pushes the upper limit of what you can enumerate on a fast PC without annoying lag.
The other consideration was that once I’ve generated the state spaces, there are lots of different reports I could generate from them cheaply, and I wasn’t initially certain which ones I’d want. Thus, enumeration followed by filtering and counting seemed like a better deal than having to prove a different closed form for each report (and possibly getting it wrong).
“When in doubt, use brute force.”
Interesting. Any chance you’ll be posting that code soon? I know you’ve been a bit busy with legal matters and such…
>Interesting. Any chance you’ll be posting that code soon? I know you’ve been a bit busy with legal matters and such…
After the World Boardgaming Championships this August. At WBC I intend to be the only person on the CC:A tournament ladder with a copy of my table handy. Not a large edge, but I’ll take it.
>Those formulas aren’t correct;
The formulas are correct, but I may have explained them poorly. Read P(X) as P(a sword roll is converted to X). The formulas would let you do the probability mass reallocation in one step.
superb
tangent:
>Statisticians often think in terms of probability mass or probability weight, which has to be conserved as a distribution changes.
i’m aware this was only a by-blow attempted exemplar of what you were trying to do.
but, these words in isolation:
errm. what? other way round. only social humans would say that. homo sapiens would say the opposite. and if faced with this statement, would say something analagous to Charles Babbage’s classic summary of the top-flight hacker’s gut reaction to the average human:
On two occasions I have been asked [by members of Parliament], ‘Pray, Mr. Babbage, if you put into the machine wrong figures, will the right answers come out?’ I am not able rightly to apprehend the kind of confusion of ideas that could provoke such a question.
>It gets trickier than that when specials are involved, and much trickier for elephants
all is forgiven, for this moment of genius
that phrase will live with me for a long time to come. “it’s harder than it seems” “and much trickier for elephants”
shades of dwarf fortress
>Because when you have hydraulic torque leakthrough, every second can mean lost pranktens!
jeffwey wead wocks
When you’re done with your program, I suggest comparing physical dice rolls with your model’s predictions.
Hey Eric, have you seen the new Star Trek flick?
If so, what did you think?
I just got back, I give it a B+. I liked it, it was better than everything made yet except maybe Wrath of Khan.
This would be a good comment thread.
Live long and prosper.
What stabs from hell’s heart and subsumes most of category theory?
Khan extensions.
I think the Old Spock storyline brought the classic Enterprise crew together just a little too conveniently. Young Spock is kind of a dick, and Kirk comes across like Irresponsible Captain Tylor, blundering his way into the captain’s chair. Yet we are supposed to believe that these two become fast friends because Fate (as related by Old Spock) Would Have It So.
But the movie is fun to watch, effects like warp and transporters are brought thoroughly into modern times, and it is good to see Nimoy back again, this time as an older and wiser Spock. So I agree wholeheartedly with Darrencardinal’s B+ grade.
Daniel Franke: i’m a big fan of math puns, but i’m afraid you’ve stumped me. i’ve asked one of the better physicists i know, and he’s stumped too.
can you kill the joke by explaining the reference?
Saltation: http://en.wikipedia.org/wiki/Kan_extension
ah haaaaa!!!
vielen dank.
can’t offer in exchange that level of cleverness, but i wrote this about 15 years ago (extrapolating from a Fortune file quote), which a lot of maths people find rather droll:
On the Validity of Using 2 in Empirical Research: A Note
Saltation: heh.
If you just want the probabilities, a Monte Carlo simulation is trivial to make.