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?

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 ...