4 ms·

If you converted the rules to be powers of 2, each coin representing a binary digit, it shouldn't be too bad 24d10 becomes 0-240, so change it to 0-256 and you

by setr 9y ago

If you converted the rules to be powers of 2, each coin representing a binary digit, it shouldn't be too bad 24d10 becomes 0-240, so change it to 0-256 and you've got 8 flips (8d2?) Distribution won't be correct but hey, 8 flips

LolWolf 9y ago
Well, you can re-flip on >240, with an expected number of flips to receive a number in the range being around 1/(1-15/256) ~ 1.062, so pretty close to just one 8-coin-flip (with some low probability of having to re-flip, which vanishes exponentially as the number of re-flips). This has the guaranteed correct distribution ('correct' being 'uniform'), too! EDIT: I guess, to be more clear about the algorithm: flip 8 coins and convert this result to binary. If the result is greater than 240, flip the eight coins again. The number of total 8-coin-flips that need to be done on average is something like 1.062, and the likelihood that you need to perform n 8-coin-flips to receive a result ≤ 240 vanishes exponentially as (15/256)^(-n).
- yoklov 9y ago
  24d10 has a normal-ish distribution. The scheme you suggest will produce a uniform distribution.
  - LolWolf 9y ago
    Oh, interesting, did not know that! I guess I only now just realized that 24d10 is 10 dice with 24 values (I just read the GGP and thought, oh 240 uniform is easy to make)... there's probably some nice way to emulate that with 1-bit RNGs in expected finite (ideally small!) time. EDIT: I screwed up again, 24d10 is 24 dice with 10 values. Oops. Point is still roughly the same!
ajross 9y ago
Four flips can get you 16 outcomes of course, rerolling values out of bounds means you need 4*16/10 = 6.4 amortized flips to generate a d10, or ~154 total to get 24d10. For large dice counts like that, it's probably better to just use a manual table for a bell curve based on ~8-10 flips. No human player is going to care about result fidelity beyond a thousand possible results anyway.
- ajross 9y ago
  Actually I'm realizing a much more efficient (but still simple enough to be practical) way to generate d10 results is to do them in pairs. Do seven flips to generate a binary number to be interpreted as a "percentile" result in the range 00-99, rerolling on 100-127, then treat the two digits independently. That gets you to 4.48 amortized flips per d10.
  - zaroth 9y ago
    Now if you just had a bit more time on your hands to work on this problem...
  - nybble41 9y ago
    Why stop there? If you switch to triples (10 flips, reroll on 1000-1023) then you can get an amortized cost of about 3.4 flips per d10. That's very close to the ideal outcome of log2(10) ~= 3.32 flips. Above 3d10 the rate of re-rolls increases; 20 flips for 6d10 gives a worse amortized cost than two sets of three.
kzrdude 9y ago
I didn't know the central limit theorem when I played D&D, but it's interesting how massively different those two distributions are -- 24d10 versus a uniform 24-240 distribution. 24d10 is 24 independently rolled d10's, that means we convolute the uniform distribution with itself 24 times and the result will be nearly indistinguishable from a scaled bell curve. Edit: Click the “Graph” button here to visualize: http://anydice.com/program/4ddf http://anydice.com/program/4ddf
- Y_Y 9y ago
  I'd like to just add a shoutout for the word "convolve" as the verb referring to this particular action of convolution.
  - kzrdude 9y ago
    Ah that's nice. I took the relevant course in Swedish, where we use the German loan word "Faltung" (turns to faltning in Swedish) for this operation.
tzs 9y ago
At most 8 flips. In many cases you'll be able to use less if you flip the most significant bits of your 8 bit number first. E.g., if you have 45 HP and the first flip is 1, you can probably stop flipping at that point.

by setr 9y ago

LolWolf 9y ago

Well, you can re-flip on >240, with an expected number of flips to receive a number in the range being around 1/(1-15/256) ~ 1.062, so pretty close to just one 8-coin-flip (with some low probability of having to re-flip, which vanishes exponentially as the number of re-flips). This has the guaranteed correct distribution ('correct' being 'uniform'), too! EDIT: I guess, to be more clear about the algorithm: flip 8 coins and convert this result to binary. If the result is greater than 240, flip the eight coins again. The number of total 8-coin-flips that need to be done on average is something like 1.062, and the likelihood that you need to perform n 8-coin-flips to receive a result ≤ 240 vanishes exponentially as (15/256)^(-n).

yoklov 9y ago
24d10 has a normal-ish distribution. The scheme you suggest will produce a uniform distribution.
- LolWolf 9y ago
  Oh, interesting, did not know that! I guess I only now just realized that 24d10 is 10 dice with 24 values (I just read the GGP and thought, oh 240 uniform is easy to make)... there's probably some nice way to emulate that with 1-bit RNGs in expected finite (ideally small!) time. EDIT: I screwed up again, 24d10 is 24 dice with 10 values. Oops. Point is still roughly the same!

ajross 9y ago

Four flips can get you 16 outcomes of course, rerolling values out of bounds means you need 4*16/10 = 6.4 amortized flips to generate a d10, or ~154 total to get 24d10. For large dice counts like that, it's probably better to just use a manual table for a bell curve based on ~8-10 flips. No human player is going to care about result fidelity beyond a thousand possible results anyway.

ajross 9y ago
Actually I'm realizing a much more efficient (but still simple enough to be practical) way to generate d10 results is to do them in pairs. Do seven flips to generate a binary number to be interpreted as a "percentile" result in the range 00-99, rerolling on 100-127, then treat the two digits independently. That gets you to 4.48 amortized flips per d10.
- zaroth 9y ago
  Now if you just had a bit more time on your hands to work on this problem...
- nybble41 9y ago
  Why stop there? If you switch to triples (10 flips, reroll on 1000-1023) then you can get an amortized cost of about 3.4 flips per d10. That's very close to the ideal outcome of log2(10) ~= 3.32 flips. Above 3d10 the rate of re-rolls increases; 20 flips for 6d10 gives a worse amortized cost than two sets of three.

kzrdude 9y ago

I didn't know the central limit theorem when I played D&D, but it's interesting how massively different those two distributions are -- 24d10 versus a uniform 24-240 distribution. 24d10 is 24 independently rolled d10's, that means we convolute the uniform distribution with itself 24 times and the result will be nearly indistinguishable from a scaled bell curve. Edit: Click the “Graph” button here to visualize: http://anydice.com/program/4ddf http://anydice.com/program/4ddf

Y_Y 9y ago
I'd like to just add a shoutout for the word "convolve" as the verb referring to this particular action of convolution.
- kzrdude 9y ago
  Ah that's nice. I took the relevant course in Swedish, where we use the German loan word "Faltung" (turns to faltning in Swedish) for this operation.

tzs 9y ago

At most 8 flips. In many cases you'll be able to use less if you flip the most significant bits of your 8 bit number first. E.g., if you have 45 HP and the first flip is 1, you can probably stop flipping at that point.