Dice rolls seem very off in Catan

[bitguru]

The game developer once posted the relevant code fragment. It was
die1 = bga_rand(1,6)
die2 = bga_rand(1,6)

If you read BGA FAQ you will learn that bga_rand calls the cryptographically safe PHP function random_int(). This RNG function is of the highest mathematical standard and is public domain. If you find a problem in this PHP function you will get worldwide media attention.

My assumption is that BGA's RNG is implemented correctly. I was not expecting to find and flaws in the code, I was just curious about the implementation, and if it "wastes" random bits or if it finds a clever way to re-use them.

(And curiosity aside, nobody cares if pseudorandom bits are "wasted" anyway. Maybe worrying about it might make sense for something like a radioactive decay-based RNGs. I know those can generate only so many random bits per time period.)

But you saying "die1 = bga_rand(1,6)" wouldn't give me any confidence if I did suspect there was a flaw. I'd need to see the implementation of bga_rand().
(BTW, this page says that PHP's random_int() uses CryptGenRandom() under Windows and the getrandom(2) system call under Linux. I guess I'd have to look at both of them if I really wanted to see about "wasted" bits. I'm curious, but probably not curious enough.)

[bitguru]

I don't know this game, but typically a game will just ask for a random integer between 1 and 6, and then another one, and that's it. Not a lot of room for mistakes.

I'm belaboring the point, and perhaps that's a dumb thing to do, but think what it means to "just ask for a random integer between 1 and 6". How many random bits would you need to achieve a precisely flat distribution?

You might think you'd need only three random bits to do it, but sometimes that's not enough. At least the naive way.

Here's the naive way. Match your three random bits to this table:
000 -> 1
001 -> 2
010 -> 3
011 -> 4
100 -> 5
101 -> 6
110 -> start over
111 -> start over
(the rows could be in any order; scramble the right-side values any way you want)

25% of the time your table tells you to start over. Which means get a three fresh random bits and do it again. It could go on forever, but in practice it won't. Just like a baseball game can go forever, with the score tied at the end of every extra inning, but in practice they all end. (Sorry to use an americas+japan analogy.)

But wait, when you hit a "start over" row, you could save a bit. The two "start over" rows are equally likely to have hit, so designate one of the rows 0 and one of the rows 1 for a "free" random bit. Now you only need two more fresh ones. It could still go on forever now, but you "waste" fewer bits when you hit a "start over" row.

I said this was the naive way. I'm pretty sure there is a more sophisticated algorithm that "wastes" fewer bits. Probably one that (unlike the naive algorithm) has an upper bound of how many random bits are needed to determine a single die roll.

That's what I was curious to see. It had nothing to do with suspecting that whatever algorithm is actually in use might be flawed.

[Jellby]

No, you completely misunderstand me. [...] I'm not sure how I gave you the wrong impression.

I confess I started writing the reply before I finished reading your post. That's why I added the the "disclaimer" at the beginning of my reply afterwards. I know that was not what you meant, but similar statements are often seen in complaints about dice.

I said this was the naive way. I'm pretty sure there is a more sophisticated algorithm that "wastes" fewer bits. Probably one that (unlike the naive algorithm) has an upper bound of how many random bits are needed to determine a single die roll.

It seems you're more concerned about efficiency than fairness. Even if underlying code does the naive (and maybe "wrong") thing: generate a random uniformly-distributed real number in the range [0,1), get an integer as floor(6*x)+1 (that could be wrong because 2^n is not divisible by 6, so some intervals would be ever so slightly more likely than others). Even if that's the case, the practical effect would be completely negligible.

[Gulchen]

...

I said this was the naive way. I'm pretty sure there is a more sophisticated algorithm that "wastes" fewer bits. Probably one that (unlike the naive algorithm) has an upper bound of how many random bits are needed to determine a single die roll.

That's what I was curious to see. It had nothing to do with suspecting that whatever algorithm is actually in use might be flawed.

2 is prime, and 6 is not a power of 2, so by unique factorization into primes, no finite power of 2 is a multiple of 6.
Thus there is no upper bound on how many are needed for perfectly-uniform sampling.

More tightly, the remainders of ​ 2^1 , 2^2 , 2^3 , 2^4 , 2^5 , 2^6 , 2^7 , 2^8 , ... ​ for division by 6 are 2,4,2,4,2,4,...
(since each power is 2 times the previous power), so for perfect uniformity conditioned on getting an output,
there must be at least ​ 2,4,2,4,2,4,... sequences of 1,2,3,4,5,6,7,8,... respectively ​ random bits that don't give an output.


What you described achieves this lower bound, though I prefer thinking of it as

Use the first bit to choose one of {0,3}, and then add the result of
00 -> 1 ​ ​ ​ ​ ​ , ​ ​ ​ ​ ​ 01 -> 2 ​ ​ ​ ​ ​ , ​ ​ ​ ​ ​ 10 -> 3 ​ ​ ​ ​ ​ , ​ ​ ​ ​ ​ 11 ​ -> ​ start over
(or any scrambling of the right-side values), where ​ "start over"
is just for the choice from {1,2,3}, not for the choice from {0,3}.

.


There is probably some scrambling that makes these two ways give exactly the same
output or lack thereof ​ for each sequence of bits, though I have not tried checking this.

[Mathew5000]

I'm pretty sure there is a more sophisticated algorithm that "wastes" fewer bits. Probably one that (unlike the naive algorithm) has an upper bound of how many random bits are needed to determine a single die roll.

Apparently not, because of a theorem by Knuth and Yao stating that a random integer generator cannot be both unbiased and constant-time. Reference: https://stackoverflow.com/a/62920514 You may also be interested in one of the links referenced there, https://web.archive.org/web/20111209063 ... 65653.html

[bitguru]

It seems you're more concerned about efficiency than fairness.

I'm not concerned about fairness at all. At least not yet.

In the last 10 games I've played, combined number of 1,1 rolls and 6,6 rolls have been higher than the 1-out-of-18 one would expect. And the number of 8s has been more than the number of 6s. If this kept up for another 100 games, I might begin to be concerned.

I once lost at blackjack for 22 consecutive hands at a real table. (Or rather, didn't win in 22 consecutive hands. There were some pushes in there.) This is easy to do on purpose but not easy to do when playing near-perfect strategy. Weird things happen in life. It would have been more fun to win 22 consecutive hands.

I was simply curious what algorithm BGA decided on for their millions of die rolls.

Even if underlying code does the naive (and maybe "wrong") thing:

The naive algorithm I described is not wrong. It results in a fair die roll.

It simply uses more bits than it needs to. (Or possibly my naive algorithm is optimal, but I wouldn't think so.) And, as I tried to say before, who cares if some psuedo-random bits get "wasted"? Psuedo-random bits are very cheap.

generate a random uniformly-distributed real number in the range [0,1), get an integer as floor(6*x)+1 (that could be wrong because 2^n is not divisible by 6, so some intervals would be ever so slightly more likely than others). Even if that's the case, the practical effect would be completely negligible.

I remember, back in the 80s, that 1+floor(6x), where x ∈ [0,1), was common. Because IIRC that's the only randomness the Basic language provided.

However I doubt that Basic's RND was precisely uniform. I think to generate a truly uniformly distributed floating point value would be tricky, but I've never tried it. In common floating point formats, there are more bit combinations denoting values in [0.0,0.5) than there are for [0.5,1.0).

I think it's better to stay in the integer realm.

If you do 1+(n%6), where n is a 32-bit unsigned integer. Then (unless I messed up the math) you get:
1: 715,827,883 bit combinations
2: 715,827,883 bit combinations
3: 715,827,883 bit combinations
4: 715,827,883 bit combinations
5: 715,827,882 bit combinations
6: 715,827,882 bit combinations

Rolling a 1 (or 2, or 3, or 4) would be 1.0000000014 times more likely to occur than a 5 (or 6), not a fair roll.

Is this "completely negligible"? Maybe, but I'd be disappointed if BGA did their rolls this way, or even if they did the same thing with a 64-bit integer.

The naive algorithm is better. And the naive algorithm usually (but not always) uses way fewer than 32 bits.

[bitguru]

I'm pretty sure there is a more sophisticated algorithm that "wastes" fewer bits. Probably one that (unlike the naive algorithm) has an upper bound of how many random bits are needed to determine a single die roll.

Apparently not, because of a theorem by Knuth and Yao stating that a random integer generator cannot be both unbiased and constant-time. Reference: https://stackoverflow.com/a/62920514 You may also be interested in one of the links referenced there, https://web.archive.org/web/20111209063 ... 65653.html

Cool, I'll have to track down that Knuth&Yao paper. I used to be a theoretical computer scientist, and I would read papers like this for fun.

It's interesting that you can fair-roll an eight-sided die with exactly three random bits. But you can't fair-roll a six-sided die with three random bits. You can sometimes, but sometimes you need more.

But I would guess (with low confidence) that it takes fewer bits on average to roll a 6-sider than an 8-sider.

Say you want a million 8-sider rolls. You need 3,000,000 random bits for that.

Now say you want a million 6-sider rolls. Could you do it with fewer than 300,000,000 expected bits? (Not guaranteed less than three million bits but on average less than three million bits.) My intuition says yes, but that's not worth much.

Here's how one of your links summarized Knuth&Yao:

Knuth and Yao showed that any optimal binary tree algorithm for generating integers in [0, n) uniformly, will need at least log2(n) and at most log2(n) + 2 bits on average.

Mabye (?) it's possible to roll a million 6-siders with only 2,584,963 expected random bits!

(Because log2(6) is slightly less than 2.584963.)

This Knuth&Yao result says that it shouldn't take more than 4,584,963 expected random bits.

[bitguru]

Use the first bit to choose one of {0,3}, and then add the result of
00 -> 1 ​ ​ ​ ​ ​ , ​ ​ ​ ​ ​ 01 -> 2 ​ ​ ​ ​ ​ , ​ ​ ​ ​ ​ 10 -> 3 ​ ​ ​ ​ ​ , ​ ​ ​ ​ ​ 11 ​ -> ​ start over
(or any scrambling of the right-side values), where ​ "start over"
is just for the choice from {1,2,3}, not for the choice from {0,3}.
.

There is probably some scrambling that makes these two ways give exactly the same
output or lack thereof ​ for each sequence of bits, though I have not tried checking this.

It works out the same as this order, where the leftmost bit is your first bit.

000 -> 1
001 -> 2
010 -> 3
011 -> start over (keep the leftmost bit, but get fresh two rightmost bits)
100 -> 4
101 -> 5
110 -> 6
111 -> start over (keep the leftmost bit, but get fresh two rightmost bits)

But the way you describe it makes it more obvious why only two more bits are needed to "start over". Nice.

[Jellby]

Rolling a 1 (or 2, or 3, or 4) would be 1.0000000014 times more likely to occur than a 5 (or 6), not a fair roll.

Is this "completely negligible"?

For the purposes of "professional" gambling in a casino, maybe not. For the purposes of playing a board game at BGA, with real opponents of various skills and with other random elements (board, cards, etc.) I think it is. But one could test that "theory" and always prefer lower numbers in Catan.

And I'm not saying that's how the code works, just that if that were the case, I wouldn't care.

[Palmieri5]

When players move the Robber, the Robbed number comes out at higher percentage and players are using this to gain an advantage.