Change the fair dice algorithm to be more principled.#493

Right now the balanced dice algorithm is ad hoc. According to what I saw on the Colonist blog, you create a “dice deck”, which you shuffle prematurely to avoid card counting.

I think we can make this more principled. First, some definitions. Let p_i = P(i is rolled under true distribution), So, p_2 = 1/36, p_3 = 2/36, and so on. Likewise, let q_i = P(i is rolled under balanced distribution). Our goal is to optimize q_i so that the dice feel fair to the players, while still being somewhat random.

I think one good way to do this is the following:

1. First, we calculate the discrepencies between the current count N_i of rolls for number i, and the expected (under the true distribution) number of rolls, p_i N, where N = ∑_i N_i. Define A_i = N_i - p_i N.

2. Then, we optimize the following objective:

   minimize KL(q || p) - β 𝔼_{i ~ q}[A_i].

   That is, we want to match the true distribution p well, while choosing numbers which are under-rolled so far. The parameter β is like a spring constant: It determines how strongly we care about rolling under-performers. (In statistical mechanics, β is the inverse temperature.)

   This optimization has a nice closed form. Simply choose

   p_i ∝ q_i exp(-β A_i).

   For simplicity, I would choose β = 1.

This is a more principled way to create balanced dice, while still being very unpredictable. Even a small choice of β makes the game much fairer: After 60 turns, the KL divergence from the ordinary dice’s statistics to the true probabilities tends to be about 0.11 bits, but this median is achieved in only 21 rolls when using the balanced dice. Simultaneously, the distribution stays close to random: at β = 1, the KL divergence form the true distribution to the balanced distribution within about 15 turns approaches its steady-state distribution with a median of about 0.32 bits and a 90th percentile of about 0.54 bits. This is very close to true randomness; it’s usually just one or two numbers which have been under-rolled which are weighted higher than ordinary. (The reason the KL distribution approaches a bounded steady-state is because the balanced dice are self-balancing, so the discrepencies get pulled back towards zero, where the balanced dice match the true dice.) Finally, as one would hope, this balancing scheme also satisfies the property that the first-turn probabilities are simply the true probabilities.

Here’s a chart of the KL divergence from statistics to the true probabilities:

And here’s a chart of the KL divergence over time from the true probabilities to the balanced probabilities:

Both charts are constructed by running 10,000 simulations, with the dark line being the median, and the shaded area an 80% confidence interval (so, 10th percentile to 90th)

Here’s a simulation (generated by AI), written in Javascript + HTML: