The Grinder - September 2012

The most recent of my collection of miscellaneous articles, which were found in my refrigerator on return from vacation.

--- --- --- The Grinder --- September 21, 2012 --- --- ---

A little bit of Battletech history from a Mechwarrior Online interview with Jordan Weisman (source 1, 2):

MWO: What was your inspiration to create BattleTech?
Jordan Weisman: I had seen images and model kits from the Japanese shows Macross, Southern Cross, and Crusher Joe. I loved the visuals but wanted to create a story for them in which the Mechs where only machines, but machines that their pilots imbued with personality like we do with our warplanes, tanks, and even cars. I wanted to adapt these wonderful machines to setting that was born from Western tradition, in this case a retelling the Roman Successor States. And most of all, I wanted to create a game which merged the reality of tank warfare with the sci-fi/fantasy of giant suits of armor.

Emphasis added: I never knew about the historical reference to the fall of Rome. Parts of the Battletech universe story line makes more sense to me now (not much more sense, but hey, it's Battletech).

image: From The Warp

Painting Pink - From the Warp -- A nice little tutorial on an often misunderstood color. -->

(Some of you may recall my own misadventure with this lovely hue.)

Node-Based Scenario Design -

 The Alexandrian 

From WIRED: An interview with Jon Peterson, author of Playing at the World.  I want.

Web site for the book, and the Amazon page.






From Technology Review:

Mathematics of Sudoku Leads To "Richter Scale" of Puzzle Hardness

There might be some studying in my future, if I want figure this one out.


And now it's time to go clean out the 'Fridge, and maybe shave.
~

Conditional Dice Rolls with Partial information

Last time I wrote about Conditional Dice Rolls, or using conditional probability to correct the results of an earlier roll that was made incorrectly. The rest of this will make more sense if you read that first.
To do this you need to know 2 things --- You need to know what the probability of success for your first roll, and what that probability should have been. But wait, there is one more thing, an important assumption I rather glossed over last time --- You need to have completely forgotten everything about the first roll except that you succeeded or failed.

And that's harder than you might think. ---> More after the fold --->

Conditional Dice Rolls

It happened to me again at the Wednesday Battletech game, one of those honest mistakes that can happen in a complicated situation. My Griffin fired two medium lasers at a Jenner needing 7's or better, and both hit. A short time later I realized my mistake, I had miscounted and the roll should have been 8 or better. I could not remember what the original rolls had been.
There is a way to fix this, to repair my mistake, to determine if my shots really should have missed, and that is fair to both players. It's a good trick, and you don't even have to do any math to use it.

But you might have to roll a lot of dice.  ---> More after the fold --->

Taking a RISK - the distribution of armies lost

I came across the following question at boardgames.stackexchange.com:

How can I estimate my chances to win a Risk battle?

Elliot Avedon Virtual Museum of Games, Courtesy Canadian Museum of Civilization.

Now there is already plenty of material on the web about probability in the popular boardgame RISK*, but maybe I can add just a little bit more.

Most people already know that, given the choice, the Attacker should always 3 dice and the Defender should always roll 2, since this always gives the best results (a Nash equilibrium). Since it's always the Attackers choice to roll an attack or not, the relevant question seem to be "How many armies [X] will the Attacker lose if they make [N] attack rolls?"

Elliot Avedon Virtual Museum of Games, Courtesy Canadian Museum of Civilization.

Using some probabilities from a RISK FAQ for the probabilities of losses, I calculated the average attacker losses (about 0.921 per roll) and standard deviation (~0.81). It's not possible to lose 0.9 armies in RISK! as the attacker losses vary between 0, 1, and 2 per roll. However, as the results of many attack rolls are added up, the losses will begin to resemble the normal distribution. We can plug the average and standard deviation into a normal approximation formula, and get back a probability for losses in a fairly simple calculation. For a given number of attack rolls "A" and number of attacking armies lost "K",

Z = (K - 0.921*A) / (0.811*sqrt(K))

where Z is a standard normal variable (mean 0, standard deviation 1), and the probability of K-or-fewer losses in A attack rolls can be evaluated with the standard normal probability CDF function, otherwise known as the NORMSDIST(Z) function in Excel. That's pretty much it, except maybe for some graphs to show off the results.

Cumulative probability of K attacking armies lost in 25 attack rolls

The blue line shows the cumulative probability of K losses in A attack rolls (vertical red line). The yellow triangles show an approximate 50% confidence interval, meaning that your actual losses should be within this range 50% of the time. The red diamonds show a 90% interval for the same. These intervals are actually slightly wider than the stated 50%/90%; because I rounded outwards to the nearest whole number of armies, and there is no other good way to do it.

Cumulative probability of K attacking armies lost in 35 attack rolls

Recall this is an approximation, and it depends on there being lots of independent random events (dice rolls!) for the approximation to work well. It should start to work very well somewhere between 20-30 attack rolls, and depending on how fussy you are may give usefully accurate results for as few as 10-15 rolls. For smaller battles, or deciding whether or not you should attack just one more time, you might consider more accurate methods (look here, for starters).

Cumulative probability of K attacking armies lost in 70 attack rolls

You can think of this in terms of Defender losses too. Two armies are lost with every attack (between the attacker and defender), so if there are A attack rolls and K attacking armies are lost, that means the defender will be losing 2*A - K armies. For instance, in 25 attack rolls a total of 50 armies are lost; the probability of the attacker losing 20 armies the same as the probability of the defender losing 30.

Cumulative probability of K attacking armies lost in 50 attack rolls

Nostalgic Tangent: Calculating the probabilities of losses for the attacker and defender was one of my first mathematical efforts to figure out a game. I didn't know how to do the calculation, but I wrote a program on my Apple II+ to roll lots of electronic dice for me, and calculated the probabilities that way. Later I learned that this technique is called Monte Carlo simulation, and statisticians do this regularly to examine the properties of new statistical methods.

*** There WILL BE a link to the spreadsheet for these calculations, but it's getting late, so I'll have to add that in tomorrow. ***


Having written this, I realized that I haven't quite answered the question. I've given the probability for a given number of attacks/losses, but the question is "How many armies will it cost me to win?"

There is another approximation to answer that, but it's much less well known. I guess I'll have to write a part 2. Stay tuned!

---------------------------------------------------------------------------------

* RISK is a registered trademark of HASBRO, Inc., of course.

Footnote: The RISK! game images used in this post are from Elliott Avedon's Virtual Game Museum, and are used with permission of the Canadian Museum of Civilization. The Virtual Game Museum has much more interesting game related information, and I may be posting about it again.

Dice Distributions Revisited

Recent thoughts about calculating the distribution of the maximum sum of several dice (ex: roll 3, sum the highest 2) made me realize I needed a better tool for calculating the distribution of sums of dice in the first place. I first wrote about this some time ago in Dice Distributions, so I knew how to do it better, I just hadn't gotten around to doing it.

Tangent: While researching this I can across a great set of mathematical Dice Problems from Doctormatt (Web Page, Blog).

And now back to our story -

I first set up a spreadsheet to give me Pascal's Triangle, which looks like this:

This gets used in lookup functions to calculate (in a second worksheet) what I'm calling the "Dice Triangle", The number of dice [N] rolled is indicated in the column headers, and the sum of N D-sided dice [X] rolled in indicated in the first column. The number of ways to roll that sum is indicated in the table. The number of sides on the die [D] can be changed by entering a different value into the green shaded cell.

The first D rows of the table come directly from Pascal's Triangle. Subsequent rows are calculated from previous rows of this table. A few more details of how this is done in my earlier post (Dice Distributions), otherwise you can ask me, or dig into the spreadsheet for yourself (sorry, in a hurry today).

Here is the spreadsheet: Dice Distribution Calculator
I have not made this public, so you cannot change it directly online. You can download a copy for yourself (under the File dropdown) and play with it to your hearts content.

Maximums and Minimums of Dice Rolls

A week month a while back I received questions from Christian and a read post from Saxywolf on essentially the same question: What is the probability of rolling a given value on an D-sided die, if you roll N dice and take the highest (or the lowest).

Here's the trick:
The probability of rolling a 1 on 1 d6 is 1/6. (regular 6-sided dice)

For 2d6 the probability of rolling a 1 as the maximum is 1/6 times 1/6, or 1/(6*6) = 1/36.

For Nd6 the probability of rolling a 1 as the maximum is 1/6 times itself N times, or (1/6)^N.

For D-sided dice just substitute D for 6 above, so that the probability of rolling a 1 as the maximum of N D-sided dice is 1/D times itself N times, or (1/D)^N.

Now consider the problem of rolling 2-or less as the maximum. The probability of rolling 2-or-less is 2/D, and the probability of rolling a  2-or-less as the maximum is 2/D times itself N times, or (2/D)^N.
That's 2-or-less, but we really just want the probability of rolling 2, not 1 or 2.  BUT we already know the probability of rolling a 1 as the maximum on the same dice, so we can subtract that to get what we want:

The probability of rolling a 2 as the maximum is 2/D times itself N times, minus the probability of rolling 1 as the maximum, or (2/D)^N - (1/D)^N.

And that's it. Using the same math you can work the complete distribution of the maximum for any number of dice with any number of (equally likely) faces. Just start at 1 and work up. For minimums, just turn the problem around and find the probability of X-or-less.

Still too much math? Fear not for there is a spreadsheet to do the calculations for you:
 Link to Google Docs Spreadsheet

See the blue numbers in the green-shaded cells? Change those to the number of side on your dice and the number you want to roll, and it will calculate the distribution for you. It might even work inside the blog?Nope, but it was worth a try. The spreadsheet is now public and can be edited at the link above (also downloaded). Changes made there WILL show up here when the page is reloaded, which means you are looking at whatever was most recently entered.



And a chart to display the results:

This is a bit of an experiment, both linking to a shared spreadsheet, and adding the HTML code to it directly inside my blog post. One upshot of this is that when one person changes the spreadsheet, it will change it for everyone. Play nice! Let me know if it works too. [Fixed!]

More Dice, More Information, but not as much as you think

I may have created some confusion in my previous posts on the information in dice (1,2). That's understandable, because the concept of information is complex and has multiple interpretations, most of which I would not claim to really understand either. Let's see if I can sort this out without making an even bigger mess.

Shannon Information measures the information content of a random distribution of discrete events. A coin flip (heads/tail), a To-Hit roll (hit/miss), and a Hit-Location roll (arm, leg, torso, etc.) are all examples of this. What really matter here is not the number of dice rolled or coins flipped, but the number of possible outcomes and the probability of each. So you might use 4d6 to determine the result of a to-hit roll, but there are still only two outcomes - hit or miss. In game terms, you can think this as the information you don't know yet, just before you roll the dice, or the variability of outcomes of that roll.
Shannon information is measured on a logarithmic scale (base 2), so each additional bit represents a doubling of information. In absolute terms, the difference between 10 and 11 bits of information is MUCH more than the difference between 2 and 3 bits. Be careful with this sort of comparison though, because it's a bit like comparing apples and oranges (or comparing to-hit and hit location rolls). Such comparisons may not be meaningful.

There is an extension of Shannon Information to continuous outcomes, but this also requires changing the definition somewhat. I won't go too far into this, but there is one key point I'd like to make. When dealing with the sum of multiple dice, the distribution of the sum tend to become more like a normal distribution as the number of dice increases. Calculating the entropy of the sum of 10D6 is a bit of work, but the entropy of a normal distribution is easy to calculate. Long story short, I can get a good guess at the entropy for the sum of a large number of dice by using the normal distribution as an approximation.

I had speculated about calculating the information in an entire game. This was rather silly of me, because this would mean framing the outcome of an entire game as a single probability distribution. I can't do that, but now I know how to make an educated guess. If I only considered the win/lose aspect of a game this would be easy, because that is just a complicated sort of discrete "coin-flip" outcome. The more interest way to look at this is to consider ALL the ways a game might play out, and to treat this as a sort of continuous outcome. The law of averages comes into play, some ways the game will play out are more likely than others. For instance, if at some point in the game you make multiple attacks to achieve an objective, perhaps to destroy an enemy tank, then in the final outcome of the battle it might not matter which attack was successful, so long as one of them was - they all lead to the same outcome. This might be stretching the concept too far, but I should be able to use the entropy of the normal distribution to approximate the amount of information of a very complicated random distribution - like that of an entire game.

Now I can make an educated guess about the information in a game. I'll use a Battletech example, but there is surprisingly little dependence on the game. The most common random event in Battletech is weapons fire, which includes the to-hit and hit-location rolls, which each have about about 3 bits each (as calculated here). In a two player game where each player has 4 battlemechs, and each mech makes about 5 weapons attacks per turn, there will be about 10 random events per turn for the first 5 turns or so, about 200 random events, then a decreasing number of attack for the next 5 turns, call it 150 random events. That's 350 random events in one game, but I left out anything else that might require a die roll, so I'll round it up to 400. The basic random event in Battletech is about 3 bits, and 400 repeat random events adds about log2(400) or 8.6 bits, for a total of 11.6 bits.

Sooooo ... now that I've gone through all that, it seems that the information in a game is just log2 of the number of random events, plus a few bits of overhead. Does this mean anything all? I need to think on that.

Here is a partial answer: A game doesn't need any randomness at all, it could be completely strategic, like Chess. Add just a little bit of randomness, the whole game may depend on just a few rolls of the dice. As randomness increases the law of averages will come into play - Games like Risk and Battletech have many dice rolls - so many that the average effect of many rolls is almost always more important than single roll. Too much randomness, and players lose the ability to affect the outcome. The trick is getting is the right balance of randomness, and I don't think there is a formula for that.

PS: My friend Ashely also recently noted that it might be a good idea to eliminate any rolling of the dice that doesn't significantly add to the game. Wisdom!

More:
Dice and Information
Dice and Information, So What?

Granular Skill Checks, and Interpolation

I just read a discussion in the CBT forums (Thanks PiP!) about the "granularity" of skill rolls in Battletech. The basic problem is that skill level changes in the boardgame make a BIG difference in play, but if you are running A Time Of War (Battletech roleplaying) then you want may small changes so that characters can improve gradually in many small steps - as opposed to 3-steps to a Superman.

I'll keep this discussion about the Battletech RPG, but these comments should apply to any game where characters have skill levels that seem too granular. I originally posted this whole thing in the CBT forums, then UN-posted it because what I had was broken. Now it is fixed, but much longer, so I hope nobody minds that I'm linking back to myself.

One way of doing this would be to use a different random distribution for skill checks. The second editions of the Battletech roleplaying game (Mechwarrior) uses 2d6 rolls just like the boardgame, and all skill were very granular. The 3rd edition of the game made a switch to 2d10 "exploding" dice, which greatly reduced the granularity problem, but suffered because it was difficult to make meaningful improvement in character skills.

There are also various "house rules" for doing the same sort of thing, but these generally require changing other aspects of the game to balance out the change in probability distribution. For instance you might switch to a 2d10 or 4d6 to-hit roll. There is less granularity now, which is good for your RPG, but the game has changed! On this new scale a +1 or -2 modifier will have relatively less effect or results, potentially "breaking" the usual balance of the game. You might fix this by adjusting all these modifier, but you won't ever get the original balance back this way.

I have an alternate suggestion: Add a decimal point to the skill levels, and an extra 1d10 roll when rolling for a skill check. Differences between Battletech skill level are BIG changes, so the idea is to add steps in-between. For example, instead of Gunnery 5 and 4, some possible skill levels are 5.0, then 4,9, 4.8, 4.7, 4.6, 4.5, 4.4, 4.3, 4.2, 4.1 and finally 4.0. Likewise any skill level, just adding a fractional skill level to it. There is a word for this - "Interpolation". We can interpolate between whole number skill levels, filling in with smaller changes in probability.

To use this, calculate the target number (TN) normally adding the skill level and any modifiers, and round the final number down. Make the usual 2d6 roll;
if this is less than the TN, you fail;
if this is more than the TN, you succeed;
if you roll exactly the target number, then you must also roll the 1d10, read it as 0-9, and this must be equal or greater than the decimal in your skill to succeed (if the decimal is "0" then this always succeeds, no need to roll).

Example: Suppose the base gunnery skill is 3.6, and after various modifiers the target number to-hit is 8.6, which rounds to 8. You roll 2d6 and ...
On a 9 or better you hit,
On a 7 or less you miss,
On exactly 8, you roll 1d10 (0-9), and if this is a 6,7,8, or 9 then you hit, otherwise you miss.

With TN=9 probability of success would be 0.278, and TN=8 it would be 0.417. The effect of the decimal in the skill level and the 1d10 die roll is to interpolate, or smooth out, between those two probabilities. The final probability of success for a TN of 8.6 is 0.333.

This gives 10 steps of skill improvement to every 1 in the regular rules, which ought to be fine-grained enough to satisfy the pickiest Game Master. In fact it may be too fine, and you might want to restrict it to just 5 steps (.0, .2, .4, .6, .8) or even 2 (.0, .5). Further, you will need to adjust the experience needed for fractional skill improvements accordingly. If it cost 100 experience points to improve Gunnery skill from 5 to 4, then it should cost about 10 to improve from 5.0 to 4.9. Most GM's love to tinker with this sort of thing anyway, so I'll leave the application in your capable hands (or fangs, tentacles, whatever).

Now the really good news - interpolating skills does not "break" any other parts of the game by changing the probability distribution the game is designed on, it just smooths it out, so a +1 or -2 modifier still has the same effect it always did. There is nothing special about using 2d6 with this either, so you might easily apply this to any RPG with granular skills.

Here is a chart with the probabilities of success on a 2d6 skill check. The way I have set this up makes it look a bit like a wavy staircase:

Probability of success on 2d6 with standard skills

You could walk up those steps! And the granularity is obvious. This chart has target number up to 13 because I need to show the probability go all the way down to zero for the next chart. Now a chart showing the same for interpolated "Skills with a decimal":

Probability of success with interpolated skills

Nice and smooth. If you look really hard you might notice this is actually 11 straight line segments joined together. This method of interpolation really just connects the dots between probabilities for whole number skill levels.

Now we have wiped out the granularity problem, but at the cost of some extra dice rolls. If you don't want to roll so many extra dice, you could make a single 1d10 interpolation roll (after fire declaration) and apply it to all skill checks results for that turn. This will be weirdly granular, because it is like changing your skill level randomly from turn to turn, but it will average out to the same effect over the course of many rolls.

Number Needed to Hit

In the comments on my previous post on Dice and Information, I mentioned a statistic called Number Needed to Treat (NNT). This is used in epidemiology and medical science as a way to compare the benefit and cost of two treatment. For example, this might be two different drugs that might be used to treat an illness. Here "benefit" means any beneficial effect, maybe something major like preventing fatal heart disease, or something minor like prevention of allergy symptoms. For this discussion I will assume it is a BIG benefit, like saving a life.

Benefit: Suppose that in a clinical trial running one year, 80% of patients on drug A benefit from the drug, and 82% of patients on drug B benefit equally. Now drug B is better by 2%, but what does that mean? If we treat 100 patient on each drug for one year, we expect 80 "benefactors" from Drug A and 82 benefactor from drug B, a difference of two patients saved every year for every 100 treated, or one saved for every 50 patients treated (for one year).

A shorter way to calculate this is NNT = 1/(0.82-0.80) 1/(0.02) = 50 patients "needed to treat" for one to benefit. Make sure to subtract the smaller probability from the larger, or you up with a negative number.

Cost: Now suppose that drug B costs $10,000 per year, compared to $1000 per year for drug A; Is drug B worth ten times the expense? NNT helps answer that question. Consider that treating 50 patients for one year (the NNT) would cost $250,000 on drug B and and $50,000 on drug A - a difference of $200,000 for one life saved each year. Now is drug B worth the cost? If the benefit is strong, like not dying, then it may be worthwhile. It certainly is if you are the 1-in-50 patient, but you can't know that is advance. Also, resources are limited. It is not good practice to make patients pay large expenses, or tie-up hospital resources, for treatments with very little benefit.

If anyone is wondering, this is not Obama-Care Death-Panel stuff, this is a serious sort of decision that determines what doctors call "Best Practice".

Well so far this has been pretty boring, but now we can take the idea behind NNT and turn it into a statistic for games. 

If we replace the probability a treatment will be effective with the probability of a successful "to-hit" roll, we get a measure of Number or rolls Needed to Hit (NNH). This is now the number of to-hit attempts you will need to make, with some higher probability of success, in order to hit one more target on average. In the sniper rifle example from the previous comments, the difference between 80% and 82% means one more hit out of every 50 shots fired. This 2% gain could be useful from the perspective of a first-person-shooter game, or even critical to ensure taking out an important target, but on a larger scale other things could matter more. For instance, if the more accurate rifle weighs more, or costs more, and this is reflected in game usage and costs, then 2% gain in accuracy might not be worthwhile.

Dice and Information ... So What?

After I finished my previous post on Dice and Information I had the thought, "These are some pretty neat numbers, but So What? What's it good for?"

One way to look at information is as a measure of uncertainty in the game, or at least the uncertainty in the outcome of a single move that is part of a larger game (The information in an entire game, start to finish, is a matter for another day.). Consider the game of Chess, which has nothing random about it. There is no information at all in a chess move, your just make your move, perhaps taking another piece, and it always works. Suppose now we change Chess so that it requires an attack roll if you want to take another piece, with a 50% chance of success (put the piece back where it started if the attack fails). Now there is uncertainty with each move (1 bit of entropy) and the outcome of any move is far from certain. We might change this to 90% success, which works out to about 0.08 bits* (oops. Thanks Bradley!) about 0.47 bits* of entropy per attack. This means that any attack is nearly certain quite likely to succeed. If the chance of success is 10%, then the entropy is again 0.08 0.47 bits*, and the attack is nearly certain likely to fail.

So entropy is measuring uncertainty in the sense of the predictability of results, but NOT the predictably of  a preferred result, such as a successful attack roll.

* It might help to think of 10% or 90% success as the flip of an unbalanced coin. Information is maximized, and the result is most uncertain, when the coin is fair (50% success).


This post hasn't gone the direction I thought it would - I was thinking (incorrectly) I could describe Entropy as a measure of the uncertainty in the outcome, but this is rather different. Consider a player making three to-hit rolls in a game, at 90%, 50%, and 10% success. The first (90%) has just a little entropy (0.47 bits) and the outcome is quite likely. The player has a high degree of control, because the decision to attack is very likely to succeed. At 50% the entropy of this roll is maximized at 1 bit, and the player will be most uncertain of the result either way. At 10% entropy is again 0.47 bits, but the player is very likely NOT to succeed. Now the player has very little control, or very little influence on the outcome of the game (with this single roll).

Back to the drawing board? The paragraph above hits a few rough spots, because Entropy and player control out outcomes in a game are maybe two different things. This gives me something new to think about.

...

And before I can finish hammering the bugs out of this post, Ashley has her response up over at Paint-it-Pink. At risk of quoting Ashley out-of-context ...

Ashley: Now when one applies modifiers to a 2D6 roll, if one knows that it only encodes 3.27 bits, then a modifier of one is equivalent to one bit. If I'm correct then a modifier of three is equal to three bits of information, which has the effect of reducing surprise in the diced for result? Such modification of the base 2D6 roll is therefore highly significant, which seems to me to support my proposition about the modifiers for targeting computers and pulse lasers in the Battletech game being too coarse.

Not quite right, but Ashley's intuition is basically correct. We need to sort this out a bit. First, the modifiers she mentions are for a Battletech "To-Hit" roll with Hit-or-Miss outcomes, and this is the same situation as flipping an unbalance coin. As in my "battle chess" example above, modifying this roll doesn't necessarily decrease the information. Second, the 3.27 bits a for a 2d6 hit-location roll** is separate from the To-Hit roll. However, we might combine the To-Hit and Hit-Location rolls by considering a "miss" to be a no-location result and grouping it with actual location results.

** Irrelevant quibble: this is actually about 3.0, because there are multiple ways to roll "Arm" hits.

Here is a new table, similar to my earlier table where I calculated the Entropy of a 2d6 result, but now the possibility of a miss of a 2d6 roll of 7 or less.

Now suppose the To-Hit roll is more difficult. Ashley's intuition says the entropy ought to decrease. Here's another table with a "12" needed to-hit.

Sure enough, the entropy has decreased. Unlike the battle Chess example, here the Entropy of hit-location (including no-location) will usually decrease with more difficult to-hit rolls (it hits maximum entropy with a to-hit roll of 3+).

Lesson learned: When thinking about entropy, it is important to include all possible outcomes of the random result.

Somehow I think this topic is not done yet, but that is all I have time for today.

A small update (12/12/2010, 4 PM): I just made the following comment on Ashley's blog, and I'm copying it here so I might remember to come back to the idea later.

Now here is a brain bender - Suppose you could roll one set of dice to resolve a whole turn of Battletech play, or a whole game - How much information would be in that? I don't know myself, but I'll think on it. My intuition is a simpler game should have less total information than a complex one, but I'm not sure yet what it would mean to compare them.

More:
Dice and Information
More Dice, More Information ...

Dice and Information

There is a concept is statistics and the information sciences of information. Several concepts actually, as there are different types of information, but I want to focus specifically on Shannon information or Entropy. Entropy is a way of measuring the amount of variability or uncertainty in a probability distribution, and a simple way to illustrate this is with the example of a coin flip.

But first, a comment of notation, since the Blogger editor is not too equation friendly. Calculating entropy requires a logarithm function, usually denoted ln(x) or loge(x) for base-e or natural-log, and Shannon Information specifically uses a base-2 logarithm, which I denote here as log2(x). If  my equations are not clear, any mention of the log function (outside this paragraph) always means the base-2 logarithm. If you are following along with a calculator, you probably have a natrual-log button ln(x), but can calculate the base-2 log as log2(x) = ln(x)/ln(2).

Image source, and quite interesting in itself.

Assuming a fair coin with a 0.50 probability of heads or tails, then the first step is to calculate a quantity called the Self-information or "surprisal" of all events. This is a measure of how surprising a given event is relative to the other possible events in the distribution. This less likely the event, the higher the value of its surprisal.

Surprisal is equal to -log2(p), where p is the probability of a given outcome. Calculating ...

log2(.5) = -1, 

-(-1) = 1

... and the NOT so surprising result here is that heads and tails are equally surprising, with a value of 1 each.

Shannon Information is measured in "bits", the basic unit of information used in calculation by computers. To relate this to games it might help to think of one bit of information being equal to the amount of variability in the flip of a coin. Now that we have the surprisal, we can calculate the Entropy as the average or expected value of the surprisal over the entire distribution. This is p times the surprisal -log2(p) of each event, summed over all events. For this example the calculation is trivial; 0.5 times the surprisal of 1 (for heads) plus another 0.5 times a surprisal of 1 (for tails), is just 1, so a fair coin flip has 1 bit of entropy.

Here I have a table representing the information in discrete uniform distributions from 1 to N. In gaming terms this is the information in single N-sided dice, with each face of the die being equally likely as all others. I included all the values representing true polyhedral dice, and some additional values for comparison (most of these are powers of 2 or 10).
The second column p(x) gives the probability of each "face", the third the surprisal, and the forth the entropy.
Here we can see that a 2-sided die (a coin!) again has 1 bit of entropy, a 4-sided die (d4) has 2 bits, a d8 has 3 bits, and a hypothetical d16 has 4 bits, following powers of 2 as you might expect. I put in some extreme values just for fun - the final row, a one million-sided die, would have nearly 20 bits (or 20 coin-flips) of entropy.

As in the example of the fair coin, when all outcomes are equally likely, the surprisal and entropy are equal. This also maximizes the value of the entropy - meaning that if any result was more or less likely than another, the result can only become more predictable, and the value of the entropy must be less, as will be seen in the next example.

For the second example I'm calculating the entropy of the sum of two six-sided dice. This table shows the possible results from 2 to 12, the probability of each result (twice) as the odds-in-36 and a probability. Next (4th column) is the surprisal of each result, and unlike the uniform distributions this values varies with the probability of the outcome. A roll of 7 has a surprisal of 2.58 bits, and a roll of 12 (or 2) 5.17 bits; a 12 is the more surprising result, relatively speaking.
The final column is the surprisal multiplied by the probability, and these are summed to determine the Entropy at the bottom, which is 3.27.

In terms of information, a 2d6 roll is in-between the d9 and d10 rolls from the first table. This doesn't mean they are the same, but that they have a similar amount of variability.

For the third table I have calculated the entropy for some commonly used dice-rolls in games and listed them in order of increasing entropy. The 2d10- designates the difference of two ten-sided dice, as used for penetration damage in Squadron Strike.

Note the entropy of 4d6 is less than twice than of 2d6, and likewise 2d6 is not twice that 1d6. As numbers from single dice are summed, the distribution becomes less uniform, more like the bell curve of the normal distribution, is more predictable, and therefore has less entropy. If we were using two separate d6 rolls to generate a uniform random number between 1 and 36, we should expect the d36 entropy to be twice than of a d6, and it is; log2(1/36) = 5.17. We also see this with the entropy of d100 being twice that of d10.

What strikes me from this is rolls of 1d6, 3d6, and everything in-between, vary by only about 1 coin-flip of entropy, so maybe the many variations of dice used in games really don't make so much difference in terms of the variability of play.

A final note: Just because there might be more information in some combinations of dice does not mean the game takes full advantage of that variability. For instance if you are making a to-hit roll with some probability of success (hit or miss), then there is at most 1 bit of information in that result no matter what kind of dice you roll it with. There are only a full 6.64 bit of information in a d100 roll if there are 100 unique outcomes.

More:
Dice and Information, So What?
More Dice, More Information ...

Blue versus Gray, or maybe Federation versus Rebels?

"Mr. Business" left me a good question on my last post about Gratuitous Space Battles, and it deserves a good answer.

N.B. writes: As an alternative, what about special anti-fighter weapons? Perhaps a frigate type ship that can act as picket against fighter waves. Specialized weapons can overcome numbers in many cases.

And

Like American Civil War. 100 Grays with rifles vs 3 Blues with a Gatling gun. On the open fields of a typical A.C.W. battlefield, your 3 Blues are going to win.

To the first part about specialized weapons, GSB lets you do just that. There are anti-fighter missiles and tractor beams to help shoot down those pesky little space-piranhas. Of course, big ships can carry heavy armor that is nearly impenetrable to fighter weapons, so it helps to have a few big ships with big guns to soften up those hard targets. Real battles are complicated, with many factors influencing the outcome. Lanchester's Laws are a simplification down to the bare basics of the number of men and how effective the are at killing the other guys. This demonstrates a principle of warfare; the advantage of superior numbers and why it exists, but it doesn't begin to cover all the possibilities that real situations allow.

The second part though - the Civil War example - is something that can be described nicely by Lanchester's Law (squared law). I'll change the number just a bit for my convenience though.

Suppose we start off with equal sides: 100 Blue and 100 Gray soldiers, each side equivalently armed with Rifle Muskets, and each able to shoot freely at any soldier on the other side. These sides should be approximately equal, with 100 soldiers on one side going to receive about as many casualties as they deal out to the other.
A game-like example will be useful: If we set this up as a game played in rounds, and give each soldier a 2% change of killing one of the other soldiers each round (completely arbitrary, just bear with me), then each side will lose about 2 soldiers each round (at the start) and the winner is probably just a matter of chance.

Now lets change it up - lets give the Blues Gattling guns (or maybe Uzi's?), and lets say that these BIG guns inflict casualties on the other sider 25 times faster that the old muskets of the Gray's. Now the Blue team is 25 time more effective, and therefore 100 Blues should now be equal to 25 times 100 equals 2500 Gray soldiers. Right?

Nope, 'fraid not, at least not according to Lanchester. The Squared law tells us that the advantage of greater number is proportional to the square of the ratio of the number of soldiers on each side. The Gray's can balance the Blue advantage with just 500 soldiers, not 2500, because a 500-to-100 is a ratio of 5, and 5 squared is 25. The reason behind this is that ever time Blue suffers a single casualty, they lose a greater portion of their total firepower.

Back to my game-like example: If each Blue soldier now has a 50% chance of killing a Gray soldier each round, and the Grays are still at 2% but there are now 500 of them, then there should be about 50 Gray and 10 Blue casualties in the first round. Now the ratio is 450 to 90, still 5-to-1, and the sides are still balanced. Under the differential equations of Lanchester's Laws, these to forces will grind each other down always at this 5-to-1 ratio until both sides are dead.

Now if this game has any bit of randomness, or as in reality things are not always equal, that ratio will not stay at 5-to-1 for very long. Before many rounds of fire are exchanged one side will gain a slight advantage, and that advantage will expand in to a victory without killing all the soldiers on both sides. If Gray bring 600 soldiers instead of 500 they should win this game every time, and this still isn't half way to 2500.

We could play this game differently too. Instead of giving Gray more soliers we can take away some of the Blues. With their BIG guns, just 4 Blues should be equal to 100 Grays. Now the difference in the casualty ratio really shows, because after just one round Blue will have 2 soldiers left, and Gray will still have 98. 20 Blue to 100 Gray should be about even (but don't hold me to that, because I make mistake when I'm tired and do math in my head).

That said, I haven't really done justice to N.B.'s Civil war example. There probably were Civil War examples of 100 Confederates charging a Union Gattling gun and getting torn to peices. As I said before, it's complicated! I'm no student of Civil war history, but I know it was a time of changing technology and tactics. A few decades earllier and 200 musket-wielding Grays charging straight at 100 similarly armed Blues was probably a winning tactic, but 200 Grays charging 100 Blues - who by-the-way have a few of Mr. Gattling's latest inventions - I think that might not work out so well for the Grays.

Gratuitous Space Battles

This is actually part 3 of my series on Lanchester's Laws, sort of. Since writing parts 1 and 2 have been reconsidering the whole topic, and I seem to have a number of ideas that branch off of this topic but one doesn't necessarily follow another. Therefore I've decided to worry a little less about how this all fits together, and just write something and get it posted. The figuring out can come later.
That said, it time for something I've been putting off for far too long ...

... which is a game called Gratuitous Space Battles. GSB is my first computer game purchase in several years, and I consider it money well spent. Let's start with a video of the action!



This operates a little differently from most space battle games; this is a Tower Defense game. If a game is a series of interesting decisions, then all the decisions in this game come at the beginning. First you design ships, choose your fleet, give then orders, and click on START. Then you sit back and WATCH the battle unfold. If you lose the battle, you go back and try a different set-up. if you WIN the battle, you can go back and try to win with few resources. The replay value of this game is very high.

Gratuitous Space Battles has been called "massively single player", because you can submit and download scenario challenges from other players in the online GSB community. I haven't done much of this yet, but my experience so far has been very positive, with other players happily responding to my challenges, politely pounding me to newbie-snot, and offering tips on how I might do better. This offers the sort of difficulty level you can only get from human players, even though you aren't playing online, or even simultaneously.

GSB has a downloadable Demo that I would like you to try. This isn't just because I think it is a cool game; which it is, but I have something specific in mind. GSB is a perfect way to demonstrate Lanchester's Square Law in action. If you want to give this a try, download the demo and play a few rounds to get the idea how it works. Once you have that under you belt, try the following setup:

Create a fleet with as many fighters as you can manage, and tune it until it wins consistently. Next, start removing fighters a few at time until your fleet no longer wins easily. Lanchester's Square Law predicts that the casualties you will inflict are proportional to the square of the ratio of friendly/enemy units. With a bit of experimentation you should be able to find the balance point - the point where your fleet doesn't always win, but the addition or subtraction of just a few fighters changes the balance drastically. Try to find the point where adding 2-3 fighter practically guarantees a win, but subtracting 2-3 fighters is a sure loss. In GSB, fighters are as close to single soldiers as you can get, and it is interesting to find that balance point where "just a few men" can completely turn the tide of the battle.

Some hints if you want them, in white text in case you prefer to figure things out for yourself. Select the text below to view:
[hidden text]
Choose a few cruisers with 2-3 Plasma Launchers, and a few shorter range weapons.
One cruiser should have a Fighter Support Bay, and order your fighters to be "Cautious" so they will will return to the bay for repairs.
Faster, lightly-armed fighters attacking at minimum range (inside cruiser shields) are much more effective than slow, heavily armed fighters.
Give your fighters orders for "Cooperative", "Vulture", and "Stick Together". You should also order them to "Escort" one of your cruisers (at range 600) so they do not wander too far from the rest of your fleet.
[/hidden text]

OK, now for just a tiny bit of mathematical consideration. Suppose we take the source code for GSB and simplify it - stripping out everything that makes it look like a game, removing all options except for how many ship there are and the firepower of each ship, removing movement (assuming every ship can fire at any other), leaving just the input of forces at the beginning and a report of the battle outcome. What we have left is a basic attrition model; a simple program that conducts a simulated "battle", even though we don't get to watch the progress of that battle any more. With all the simplifications it is barely resemble a game, but it become a very effective tool for studying the effect small changes in force selection (or force orders) can have on the outcome of a battle. Consider putting this tool inside of a computer program and run through hundred, thousands, or even millions of scenarios, each with slightly different starting conditions, then look at which starting conditions lead to success or failure.

Just like my suggested example above, tinkering with the number of fighters to find a balance point, you might tinker with the behavior of forces. You can examine things like the effect of the priority in which enemy units are attacked, maybe add ammunition considerations, command and control, whatever you like. The point is, there can be value in studying very basic considerations in a model that has been stripped of all but the most basic structure. It's true that the effect of something complex (like command and control) probably depends on any number of other factors, but if you don't understand how something works in a simple model, then it is unlikely you can understand how it works in a more complex model.

I'm a big fan of simplifying thing down to base elements, and trying to understand them from the bottom up. Gratuitous Space Battles, even in demo form, is a good tools for studying Lanchester's Laws. It's not an ideal tool for such - that would require your own program - but it is very accessible to anyone with an interest in the topics, and it's a heap of fun too.  I give GSB a four-robot rating :-)


Over at the developer's blog, you can read about The Fighter Spam Issue he is having with the GSB campaign game. Essentially, by taking advantage of Lanchester's Squared Law, it becomes fairly simple to construct a fighter-heavy fleet that is nearly unbeatable. Balancing the game requires in this situation require putting some limits on the usefulness or availability of fighters.

Credits: Some of the images here are taken from the GSB developer's site, or the GSB Facebook page, and the rest are screenshot I created.

A question in the comments below inspired this response and example, and this related post.

Lanchester's Laws and Attrition Modeling, Part II

In Part One I introduced the basic concept behind Lanchester's Laws, and now I want to write more about how this applies to games. This time I'll start off with Ernest Adams' excellent 2004 Gamasutra article, and follow up with my take on actually applying this to a game.

Kicking Butt By the Numbers: Lanchester's Laws

[Alternate Link to Ernest Adams article, in case the Gamasutra link flakes out again.]

Adams makes a particular good point about Lanchester's Laws and "victory".

Now, Lanchester's Laws are far from perfect. For one thing, they only apply to battles of attrition, in which the object is to wipe out the other side. If "winning" a battle is defined in some other way -- and modern Western militaries don't normally consider slaughtering every last opponent to be a legitimate objective -- then Lanchester's Law has nothing to say about who wins. Napoleon "won" every battle he fought in his march into Russia, but he still lost 98 percent of his men and was forced to retreat without achieving his objective.

On the other hand, some wargames are often fought to the last man standing, so if you are trying to understand game balance it is well worth considering. Some early comments tell me that rest of this post may be a confusing slog through a lot of math - I'm afraid that is the nature of the beast. All I can do is ask the reader to bear with me for now, and stay tuned for Part III where there will be some more accessible examples. I will start of again by stating my assumptions, fixing some errors I made last time.

This is a very simplified model of combat; Each side has identical soldiers; Each side has a fixed strength which governs the proportion of enemy soldiers killed. Range, terrain, movement, and all other factors that might influence the fight are either abstracted to the proportion killed or ignored entirely. In the derivation from differential equations casualties are inflicted continuously over time, but it also works to think of casualties inflicted in rounds or turns, which will be a more familiar setting to most gamers.

My first error last time was stating this in terms of the probability of killing an enemy soldier instead of a proportion or kill-rate. The differential equation derivation of Lanchester's Laws is a deterministic relationship that does not involve probabilities at all. I'm a statistician and tend to think in terms of probabilities rather than fixed proportions, and I'm also working my way up to demonstrating a probabilistic derivation of the same thing, so forgive me if I got a bit ahead of myself. A definition involving probabilities should be even more useful because it will demonstrate the degree of uncertainty involved in a balanced game.

My second error was in describing the total casualties for the winning side in my example. Side 2 loses all 2000 soldiers, and side 1 suffers casualties equal to 4/9ths (44%) of 2000 soldiers, for a total of 889. I had incorrectly stated that side 1 would lose 4/9ths of its total force (which would be 1400 soldiers), and the previous post has been corrected.

Notes on some abbreviations I may use (some changes since part one):

• Pk = "Proportion killed" or combat effectiveness, with subscript k1 or k2 if it matters. This is usually a small proportion. 
• R = Pk1/Pk2 , the ratio of combat effectiveness. (1/R = Pk2/Pk1)
• N1, N2 = The initial force sizes (before combat) of each side.
• n1, n2 = The remaining force sizes at the end of combat.
• C1, C2 = The total casualties suffered by each side at the end of combat (C1 = N1 - n1).
• a = Exponent on the force size. For the Linear Law a=1, and for the Squared Law a=2.
• "~=" is used to represent "approximately equal to".
• Be aware that the !@#@!#%&*#!!! Blogger editor is subverting every effort to use smaller fonts as subscripts in the text. Hopefully the subscripts will be clear from context.

Here is a an expanded version of the formula from part one. That formula only worked in a special case; this is more general:

[Edit: The k1 and k2 subscripts are reversed, dangit.]

This is a more general form that accounts for both the Linear and Square Laws, adds the relative combat effectiveness Pk's, and allows for situation in between with 1<a<2. This assumes the condition of combat and acquiring targets are the same for both sides, and so the value of a is the same for both. (Yes it can be different, but that really complicates things). I should also clarify that in a battle to the last man standing, where either C1 = N1 or C2 = N2, or equivalently n1 = 0 or n2 = 0 (one side is completely destroyed).

If a game is perfectly balanced then both sides should be destroyed at the same time, which results in both n1 = 0 and n2 = 0. Plugging these in and a bit of algebra gives:

Some important points:

1. THE important point of Lanchester's Laws, is that the exponent representing the advantage of a higher rate of target acquisition applies to the size of the force (N), but not to the fighting effectiveness of the force (Pk). Under the Squared Law, any advantage that army 1 might have in combat effectiveness is usually quickly overcome if army 2 has the larger force. 
2. Lanchester's Laws are not a governing rule of combat, they are a description of an ideal principle. In actual combat/play this ideal is unlikely to hold. If one player has a range advantage (tending towards a=2), other other will make use of terrain to counter this (tending towards a=1). Battles tend to occur in sets of smaller skirmishes, each with it's own circumstances, and the final result may represent some average of these skirmishes. 
3. There is a third variation on Lanchester's Laws, known as the logarithmic law, which has relevance to interpreting historical data, but that will have to be a topic for another day.

So how is this used to balance a game? Let's suppose we have a hypothetical game where combat can potentially operate under the Squared law, but due to range and movement limitations effectively operates somewhere between Linear and Squared. I'll use a=1.5 to represent the actual state of this game, and work out examples under three cases:

Example 1 (Balance relative effectiveness):

1. For the Linear Law a=1.0, N1 = 3000, N2 = 2000, Pk1 = 0.01, and solving for Pk2 gives Pk2 = 0.015 and R = 0.67 (or 1/R = 1.5).
2. For the Squared Law a=2.0, N1 = 3000, N2 = 2000, Pk1 = 0.01, and solving for Pk2 gives Pk2 = 0.0225 and R = 0.444  (or 1/R = 4/9 = 2.25).
3. For my in-between value of a=1.5, and again N1 = 3000, N2 = 2000, Pk1 = 0.01, and solving for Pk2 gives Pk2 = 0.018371 and R ~= 0.554 (or 1/R ~= 1.84).

If I want to balance a scenario with these forces (or any 3:2 force ratio) side 2's forces will need to be between about 1.84 times as effective as side 1's in order for this to be a fair fight. What actually happens in the game will still depend on chance and the ability of players to take advantage of opportunities during play, but that's the hypothetical balance point.

Example 2 (Balance force sizes):

1. For the Linear Law a=0.01, N1 = 3000, Pk1 = 0.01, Pk2 = 0.015 and solving for N2 gives N2 = 2000.
2. For the Square Law a=2.0, N1 = 3000, Pk1 = 0.01, Pk2 = 0.015 and solving for N2 gives N2 ~= 2450.
3. For the in-between a=1.5, N1 = 3000, Pk1 = 0.01, Pk2 = 0.015 and solving N2 for gives N2 ~= 2289.

If I want a balanced scenario where the sides have this relative effectiveness (2:3 ratio, R = 0.67) side 2 will need an initial force size of about 2450 2289 to balance with side 1 in a fair fight. The outcome still depends on what happens in the game, but that's the hypothetical balance point.

Note that I arbitrarily chose a=1.5 for this example, pretending that I have a game where this is true. In practice I don't think it is possible to design a game to a particular value of a. What you can do is assume a value for a and design a game around it, assigning values and balancing scenarios with different types of units in this manner. This is difficult though, because in a game with many different types of units there is potentially a different balance point for every pair of units that might face each other, and there isn't any simple formula that can solve it for for us. This process gets VERY complicated.

At this point I have probably created more questions than I have answered. That is a problem, but I need to stop somewhere. The next part will hopefully include some more accessible examples, and some toy spreadsheets you can download to play with.
In my research I found two recent papers by Perry that were very helpful (especially 6 below) and greatly improved my own understanding of the topic. The MacKay paper (4) is maybe a simpler article to read first. You don't necessarily need to understand differential equations to read these, but it helps.

Part III of this series is here.

Bonus Link!

Lanchester Systems and the Lanchester Laws of Combat
by "The Custodian" at everything2.com

This is another basic introduction to Lanchester's Laws. The author (semi-anonymous) spends more time on the differential equations and some practical aspects that I glossed over completely, so it might be worth your time.

References and Reading (updated since part one)

1. Ernest Adams, "Kicking Butt By the Numbers: Lanchester's Laws", a Designer's Notebook, Gamasutra webzine, August 4, 2004.
2. Bruce Fowler, De Physica Belli: An Introduction to Lanchestrial Attrition Mechanics Part One, Defense Modeling Simulation and Tactical Technology Information Analysis Center, Huntsville, AL, 1995.  [Early versions of this series can be found online at DTIC: 1,2,3.]
3. Michael J. Artelli and Richard F. Deckro, Modeling the Lanchester Laws with System Dynamics, The Journal of Defense Modeling and Simulation: Applications, Methodology, Technology 2008 5: 1-20
4. Niall MacKay, Lanchester combat models, arXiv:math/0606300v1 [math.HO] (2006)
5. Wikipedia contributors. "Lanchester's laws." Wikipedia, The Free Encyclopedia. Wikipedia, The Free Encyclopedia, 3 May. 2010. Web. 23 Jun. 2010.
6. Perry, Nigel. Defence Science and Technology Organisation (Australia). Joint Operations Division 2009 Fractal effects in Lanchester Models of Combat [electronic resource] / Nigel Perry Defence Science and Technology Organisation, Canberra.
7. Perry, Nigel. Defence Science and Technology Organisation (Australia). Defence Science and Technology Organisation (Australia). Defence Systems Analysis Division. 2006 Verification and validation of the fractal attrition equation [electronic resource] / Nigel Perry DSTO, Edinburgh, S. Aust.