|
Title: Best or Good ways to roll 6 sided dice using binary input. Post by: Dabs on October 02, 2014, 03:32:16 PM Quick Question:
How do I get a number from 1 to 6 inclusive (like a regular 6 sided dice) if all I have are bits or bytes, or hex digits, such as results from SHA or HMAC? Preferably with no bias. I have seen a few solutions: One is to get a bunch of hex digits, if the number is too high, get another bunch, then do a modulo division. Another is to make some random dice rolls (how did you do that in the first place), then have another method to re-arrange them using a fisher-yates shuffle. (I think I saw this on pocket dice.) Which isn't easy to do in your head, and to me seems inefficient. (The game looks fun, and the difference to humans may be negligible.) Ok, I'll post this now and see what you guys think. Title: Re: Best or Good ways to roll 6 sided dice using binary input. Post by: espringe on October 02, 2014, 04:30:55 PM There exists no such n that would allow you to use the
Code: 2^n % 6 == 0 The other obvious solution is to traverse through 3 bits at a time, discarding any result that is a 7-8. You'll probably want to put some logic in that if you exhaust your source of entropy (which you would happen 1 in ~42 billion times with a sha256), the result is either invalid or all-players-win or even just accept some bias. Title: Re: Best or Good ways to roll 6 sided dice using binary input. Post by: Dabs on October 02, 2014, 10:35:56 PM Yes, that's what I thought too. There is the discard method, and on 32 bits, that's 4 in 4 billion times I would go over the maximum non-biased number. Without discard, there would be a bias towards the first 4 numbers, one in a billion times.
*edit* The question is how negligible is negligible. Some of these guys ... well, 4 in 4 billion means 1 in a billion. Now they would go roll half a billion times to see if there was any bias, but at those numbers the variance might do more to the perceived biased than the actual bias. If I use 12 hex digits, that is 48 bits, and that's a number from 0 to 281,474,976,710,655. (I could use 16 for 64 bits, but my dumb spreadsheet rounds off; I'd like to use a number that a lot of people can easily verify.) That means, 4 / by that large number which is 0.0000000000000142109. You could roll a few billion times, and you wouldn't see the bias. Add a + 1 to the roll, and the bias is towards 2 to 5. Making 1 and 6 a negligibly rarer roll result, by an amount no human will ever notice. Is that something people might be willing to live with, if I use this kind of formula to create a roll for a 6 sided die? It will, of course, be provably fair. The thing is I'd like to avoid discarding any data (not that I'd need so many) but I only have 128 hex characters to work with for a 512 bit hash. I need at least 3 dice rolls from it. Title: Re: Best or Good ways to roll 6 sided dice using binary input. Post by: Dabs on October 03, 2014, 12:40:17 AM I did find another method. And that's to use 6 hashes. The lowest hash among the 6 is the result of the roll. (See how my lotto used to work.)
I'd have to accept a chance of collisions. If I use HMAC-SHA512, that's 2 in 2^512? (Or some other very large number.) / 6 (or some other calculation that involves 6 512-bit hashes.) *edit* I found this: Quote The usual answer goes thus: what is the probability that a rogue asteroid crashes on Earth within the next second, obliterating civilization-as-we-know-it, and killing off a few billion people ? It can be argued that any unlucky event with a probability lower than that is not actually very important. *edit2* I just found this term too: rejection sampling. This means the same thing as discarding numbers above the maximum (which, for 48 bits is higher than 281,474,976,710,651.) Title: Re: Best or Good ways to roll 6 sided dice using binary input. Post by: Bobblehead Pete on October 03, 2014, 03:43:10 AM Just a question, in a dice game, should a site allow multiple users?
Title: Re: Best or Good ways to roll 6 sided dice using binary input. Post by: Dabs on October 03, 2014, 03:46:26 AM Just a question, in a dice game, should a site allow multiple users? What do you mean? All dice sites have multiple players right now. Each one plays independently of each other though. Title: Re: Best or Good ways to roll 6 sided dice using binary input. Post by: rivoke on October 03, 2014, 07:32:00 AM Just a question, in a dice game, should a site allow multiple users? What do you mean? All dice sites have multiple players right now. Each one plays independently of each other though. I think he means multiple accounts ?? Title: Re: Best or Good ways to roll 6 sided dice using binary input. Post by: Dabs on October 04, 2014, 02:15:46 AM Just a question, in a dice game, should a site allow multiple users? What do you mean? All dice sites have multiple players right now. Each one plays independently of each other though. I think he means multiple accounts ?? What's the problem with that? The player can dice on multiple accounts if he wants to. He has multiple chances to win or lose his bets. Doesn't make a difference to other players, and doesn't make a difference to the site. Besides, there is no way to fully prevent that kind of activity. People will just use tor or other ip addresses or proxies or whatever. Title: Re: Best or Good ways to roll 6 sided dice using binary input. Post by: dooglus on October 04, 2014, 02:54:31 AM Quick Question: How do I get a number from 1 to 6 inclusive (like a regular 6 sided dice) if all I have are bits or bytes, or hex digits, such as results from SHA or HMAC? Preferably with no bias. Convert the hash to hexidecimal. Read through it character by character until you find a digit 1 through 6. Use that digit as your roll. It's incredibly unlikely that there's no such digit. (1 in 10^76 for sha256 and 1 in 10^153 for sha512). If there is no such digit, use (hash%6)+1. This way people who can't divide 512 bit numbers by 6 in their head can easily check the rolls themselves. Title: Re: Best or Good ways to roll 6 sided dice using binary input. Post by: Dabs on October 04, 2014, 04:01:04 AM This way people who can't divide 512 bit numbers by 6 in their head can easily check the rolls themselves. dooglus! That's condescending to those people who can't divide 512 bit numbers by 6, in their heads. What about my using 48 bits per roll, with discard? (or without, but with bias). Title: Re: Best or Good ways to roll 6 sided dice using binary input. Post by: dooglus on October 04, 2014, 04:44:24 AM This way people who can't divide 512 bit numbers by 6 in their head can easily check the rolls themselves. dooglus! That's condescending to those people who can't divide 512 bit numbers by 6, in their heads. I don't think so. I'm one of them. Quote What about my using 48 bits per roll, with discard? (or without, but with bias). I don't think any number of bits gives you a multiple of 6 different values, so it's never unbiased. The bias is insignificant in most cases however. Title: Re: Best or Good ways to roll 6 sided dice using binary input. Post by: Dabs on October 06, 2014, 01:06:21 PM This way people who can't divide 512 bit numbers by 6 in their head can easily check the rolls themselves. dooglus! That's condescending to those people who can't divide 512 bit numbers by 6, in their heads. I don't think so. I'm one of them. Eh, I'm one of them too. Of course I was joking. :) I can't divide 2 bit numbers by 6 in my head, so 512 is kinda out of my range. Quote Quote What about my using 48 bits per roll, with discard? (or without, but with bias). I don't think any number of bits gives you a multiple of 6 different values, so it's never unbiased. The bias is insignificant in most cases however. 48 bits looks nice then. I mean, 4 in 281,474,976,710,656. Someone would have to roll about half that number to barely see the bias (and of course the variance is probably bigger.) |