4 ms·
I wonder if there are any good, simple procedures that could be applied during a game to mitigate against biased dice (without giving up on physical dice)? For
by tzs 9y ago
I wonder if there are any good, simple procedures that could be applied during a game to mitigate against biased dice (without giving up on physical dice)?
For games that only use one die, perhaps something like generating a random number in 1 <= r <= 6n[1], using some procedure that all the players have input to so they can all agree to trust the number, and then shifting all die roll results by that number? So if the number were 3 and the die came up 2, it would count as 5.
That would not remove the bias from the die, but it would move it to a different number. For games where some numbers are consistently good for you and some are consistently bad for you that would be enough to make it so that biasing the die does not work in the long run--some games it would end up in your favor and some it would end up against you.
For games with two dice, that might not work as well. If a single random number were picked and used to shift both die results, it would shift the bias just like with the single die game.
However, the dice will still be biased to come up matching, and in some games matching numbers on the two is significant.
One might try to address this by generating two random numbers at the start of the game, one for each die, for the shifts. That would have bias against getting a match on the two dice, so would provide an advantage in games where a match is bad.
[1] Generalizing to n-sided dice is left as an exercise for the reader.
- dkarl 9y agoPresumably the person who supplies the dice knows how they're loaded. With a shift, they might still be able to use that information to their advantage. Instead, you could use the agreed-upon randomness at the beginning of the game to apply numeric labels to the faces of the dice. As long as the labels themselves aren't loaded... and the person who supplied the dice would still have information about the distribution.
- maksimum 9y agoI think you raise a very interesting question, and I like your initial solution. I feel like a game is fair if all players know that a die is biased, but no player has an advantage in predicting the outcome. To achieve that: for each die, for each roll have the players agree on a random permutation of the observed faces to actual faces for that roll. As a result even if all players know that 6 will land with probability 1 in the original throw, after permuting each side has probability 1/6. The agreement algorithm: have the parties each propose a permutation, and compose the permutations together in order to get a final "unbiased" permutation. I think if there is at least one honest party, this will work. Another approach is to let everyone sample the dies before playing until they are satisfied, and let everyone adjust their strategy accordingly.
- jknz 9y agoUnbiasing a coin is easy (the Von Neuman technique): toss it twice, if the results are different then output the first toss. If the results are the same, forget both and start again. You can use this technique to unbias a 4-die or 8-die by throwing a coin multiple times (apply the above technique for each digit in base 2). To produce a fair 6-die from a biased coin, the following should work. - Using the Von-Neumann technique, creates 3 independent unbiased coin X, Y, Z. Then X= 1 + X + 2Y + 2Z is uniform in {1,...,8}, we basically randomize each digit in base 2. - Finally, throw the unbiased 8-die until you obtain a number different than 7,8. The result is unbiased in {1,...6}. import numpy as np def biased_coin(): return np.random.choice([0,1], p=[0.1,0.9]) def unbiased_coin(): a = biased_coin() b = biased_coin() if a != b: return a else: return unbiased_coin() def unbiased_eight(): return 1 + unbiased_coin() + 2*unbiased_coin() +4*unbiased_coin() def unbiased_six(): d = unbiased_eight() if d < 7: return d else: return unbiased_six() np.bincount([unbiased_six() for i in range(6000)]) Edit: there was a mistake in the previous version of the comment because the digits in base 2 were not be independent. The last version is correct, I believe :)
- deleted 9y ago[deleted]
- elihu 9y agoOne (cumbersome) solution is for all players to provide their own dice. Whenever a die roll occurs, all players roll one die at the same time, and the totals are summed and the remainder is taken after dividing by the number of players. So, as long as at least one player's die is fair the outcome will be fair. If you're playing Catan by email, this approach can be extended with bit commitment. Each player rolls a die and sends a message to the other players with the number they rolled signed with their own digital signature but also encrypted with a key randomly chosen for that round of die rolls. None of the other players can know what the other players rolled without the key. Once everyone has sent all the other players their rolls (i.e. they've "committed" to a particular die roll but the other players don't know what it is yet), they exchange keys to reveal the numbers they rolled.
- Simon_says 9y ago> the remainder is taken after dividing by the number of players. Minor nitpick: you should take the remainder after dividing by the number of sides on a die, with the understanding that zero == max possible roll.
- elihu 9y agoYeah, that's right I think.
- jamessb 9y agoGiven a dice with an unknown bias, you can generate a stream of unbiased random bits [1]. The method is an extension of von Neumann's trick for un-biasing a biased coin in which you flip it multiple times and take advantage of symmetry (specifically flip it twice and return heads if you got heads then tails, return tails if you got tails then heads, or repeat the procedure if you obtained two heads or two tails). You can then go from this bit-stream to a number in {1,...,6} using the trick jknz mentions below (take 3 successive bits, and interpret them as a binary number between 0 and 7, add one to get a number between 1 and 8, and start again if the result is 7 or 8). [The method in the paper is apparently asymptopically optimal (as the number of faces on the dice goes to infinity). However, for small numbers of faces I think it is slightly worse than the method jknz described. Consider the 4-faced dice: the Peres method converts a pair of dice rolls into 1 or zero bits, but jknz's method would sometimes produces two bits (the rolls 1,4/2,3/3,2/4,0 are binary 00,11/01,10/10,01/11,00 resulting in sampled bits 0,0/0,1/1,0/11). Working out all the cases shows this makes the method slighly more efficient.] [1]: http://dx.doi.org/10.1109/TIT.2014.2381223 http://dx.doi.org/10.1109/TIT.2014.2381223