6 ms·

a little off topic but is it possible to truly randomize the 80,658,175,170,943,878,571,660,636,856,403,766,975,289,505,440,883,277,824,000,000,000,000 shuffle

a little off topic but is it possible to truly randomize the 80,658,175,170,943,878,571,660,636,856,403,766,975,289,505,440,883,277,824,000,000,000,000 shuffle combinations? edit: also, when i play solitaire via an ipad app there is always a 'top score' by someone for the hand i was dealt. i dont understand how this is probabilistically possible

teh 11y ago
Shuffling can be done in linear time, e.g. with https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle so yes.
- gamegoblin 11y ago
  I believe user thomasthomas was referring to this problem: https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#Pseudorandom_generators:_problems_involving_state_space.2C_seeding.2C_and_usage https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#P... That is, is there enough entropy in your typical PRNG to actually generate all of those shuffles with equal probability.
  - sltkr 11y ago
    You can easily seed your PRNG with a cryptographic entropy source which can certainly provide enough entropy. But in reality you don't care. You could seed the PRNG with the current system time in nanoseconds or something, and every game you'll ever play is different. Even if the PRNG has limited state, you'll never notice it as a human player.
    - dietrichepp 11y ago
      I'd like to elaborate. The cryptographic PRNG has lots of entropy, and it probably happens to be enough entropy. You need ~226 bits, and most cryptographic PRNGs will be more than that—but not all! Information-theoretic entropy is actually a stronger requirement, and it's why we use /dev/urandom (which is secure and fast) instead of /dev/random (which is information-theoretic secure, but slow). So it might be possible that your secure PRNG still cannot generate all permutations.
      - schoen 11y ago
        Paging tptacek to quarrel with the account of RNG entropy presented here (?)
        dietrichepp 11y ago
        Quarrel? Here, let me clarify. A PRNG has state with a certain amount of potential entropy, call this X. Uniformly shuffling a deck of cards requires a certain amount of entropy, Y. If X > Y then theoretically you can generate all possible shufflings with your PRNG, assuming it's seeded properly. If X < Y, then you can't. The key difference is that your PRNG could be cryptographically secure even though X < Y. It turns out that Y ≈ 226 bits, and so it's plausible that your cryptographically secure RNG would have X = 128 bits, for example, even though I'd typically expect a larger number. People often conflate entropy with security. A random number source could have high amounts of entropy and be insecure, while a random number source with less entropy could be very secure. Or let me put it this way: entropy is necessary but not sufficient for security.
        schoen 11y ago
        I agree with your argument on a pigeonhole-principle level (if you only observe fewer than 128 bits of state and then shuffle cards in a deterministic way based on a summary of your observations, you can't get all possible shuffles out), and I think that's a nice observation. 52! is surprisingly huge, and determinism is deterministic. :-) The issue is just about what /dev/urandom and /dev/random do.
        dietrichepp 11y ago
        There's a lot of misinformation and cargo cult crypto programming, but the basic summary is that /dev/random information-theoretic security is unnecessary for most applications, but necessary for being able to know that you can produce every possible permutation of a deck of cards. http://www.2uo.de/myths-about-urandom/ http://www.2uo.de/myths-about-urandom/
    - xigency 11y ago
      Well, beyond what a human player would notice, to be able to be dealt any possible hand in solitaire, a random or pseudo-random number generator would need log 2 (52!) bits of state or > 226 bits, which is the point I think the commenter was making, compared to the 32- or 64-bits of information a built-in function would take. Something like a properly seeded 256 bit xorshift might satisfy this as a random number generator. But even that setup may not be sufficent.
  - cobaltblue 11y ago
    You can always use https://www.fourmilab.ch/hotbits/ https://www.fourmilab.ch/hotbits/ as well.
m_eiman 11y ago
Top score: if all players have them same seed for the RNG, they'll be playing the same sequence of games - unless you've played more games than any other player there'll be a high score. Need to keep track of RNG state between sessions, of course.
kyle_u 11y ago
In practice, for my game, I use a single positive signed int as the initial seed for the Scala/Scala.js PRNG (Amazingly, they implement the same algorithm), meaning only two billion or so possible games. If I re-seeded the PRNG each time I moved a card ordering, then the full [52!] shuffles could be generated. I only use initial seed, so that a given seed will always generate the same shuffle/deal order.
- dietrichepp 11y ago
  Here's the critical issue: how do you re-seed? This is actually far, far more difficult than it sounds.
openasocket 11y ago
The Mersenne twister algorithm (https://en.wikipedia.org/wiki/Mersenne_Twister https://en.wikipedia.org/wiki/Mersenne_Twister) has a period of 2^19937 - 1, way more than 52!~2^256 possible shuffles, and is fairly widely used. I know for a fact it is used by the python standard library.
- greiskul 11y ago
  It's not a matter of the size of the period, but of the size of the seed. To be able to generate all shuffles, you need to seed with at least 226 bits.

teh 11y ago

Shuffling can be done in linear time, e.g. with https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle so yes.

gamegoblin 11y ago
I believe user thomasthomas was referring to this problem: https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#Pseudorandom_generators:_problems_involving_state_space.2C_seeding.2C_and_usage https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#P... That is, is there enough entropy in your typical PRNG to actually generate all of those shuffles with equal probability.
- sltkr 11y ago
  You can easily seed your PRNG with a cryptographic entropy source which can certainly provide enough entropy. But in reality you don't care. You could seed the PRNG with the current system time in nanoseconds or something, and every game you'll ever play is different. Even if the PRNG has limited state, you'll never notice it as a human player.
  - dietrichepp 11y ago
    I'd like to elaborate. The cryptographic PRNG has lots of entropy, and it probably happens to be enough entropy. You need ~226 bits, and most cryptographic PRNGs will be more than that—but not all! Information-theoretic entropy is actually a stronger requirement, and it's why we use /dev/urandom (which is secure and fast) instead of /dev/random (which is information-theoretic secure, but slow). So it might be possible that your secure PRNG still cannot generate all permutations.
    - schoen 11y ago
      Paging tptacek to quarrel with the account of RNG entropy presented here (?)
      - dietrichepp 11y ago
        Quarrel? Here, let me clarify. A PRNG has state with a certain amount of potential entropy, call this X. Uniformly shuffling a deck of cards requires a certain amount of entropy, Y. If X > Y then theoretically you can generate all possible shufflings with your PRNG, assuming it's seeded properly. If X < Y, then you can't. The key difference is that your PRNG could be cryptographically secure even though X < Y. It turns out that Y ≈ 226 bits, and so it's plausible that your cryptographically secure RNG would have X = 128 bits, for example, even though I'd typically expect a larger number. People often conflate entropy with security. A random number source could have high amounts of entropy and be insecure, while a random number source with less entropy could be very secure. Or let me put it this way: entropy is necessary but not sufficient for security.
        schoen 11y ago
        I agree with your argument on a pigeonhole-principle level (if you only observe fewer than 128 bits of state and then shuffle cards in a deterministic way based on a summary of your observations, you can't get all possible shuffles out), and I think that's a nice observation. 52! is surprisingly huge, and determinism is deterministic. :-) The issue is just about what /dev/urandom and /dev/random do.
        dietrichepp 11y ago
        There's a lot of misinformation and cargo cult crypto programming, but the basic summary is that /dev/random information-theoretic security is unnecessary for most applications, but necessary for being able to know that you can produce every possible permutation of a deck of cards. http://www.2uo.de/myths-about-urandom/ http://www.2uo.de/myths-about-urandom/
  - xigency 11y ago
    Well, beyond what a human player would notice, to be able to be dealt any possible hand in solitaire, a random or pseudo-random number generator would need log 2 (52!) bits of state or > 226 bits, which is the point I think the commenter was making, compared to the 32- or 64-bits of information a built-in function would take. Something like a properly seeded 256 bit xorshift might satisfy this as a random number generator. But even that setup may not be sufficent.
- cobaltblue 11y ago
  You can always use https://www.fourmilab.ch/hotbits/ https://www.fourmilab.ch/hotbits/ as well.

m_eiman 11y ago

Top score: if all players have them same seed for the RNG, they'll be playing the same sequence of games - unless you've played more games than any other player there'll be a high score. Need to keep track of RNG state between sessions, of course.

kyle_u 11y ago

In practice, for my game, I use a single positive signed int as the initial seed for the Scala/Scala.js PRNG (Amazingly, they implement the same algorithm), meaning only two billion or so possible games. If I re-seeded the PRNG each time I moved a card ordering, then the full [52!] shuffles could be generated. I only use initial seed, so that a given seed will always generate the same shuffle/deal order.

dietrichepp 11y ago
Here's the critical issue: how do you re-seed? This is actually far, far more difficult than it sounds.

openasocket 11y ago

The Mersenne twister algorithm (https://en.wikipedia.org/wiki/Mersenne_Twister https://en.wikipedia.org/wiki/Mersenne_Twister) has a period of 2^19937 - 1, way more than 52!~2^256 possible shuffles, and is fairly widely used. I know for a fact it is used by the python standard library.

greiskul 11y ago
It's not a matter of the size of the period, but of the size of the seed. To be able to generate all shuffles, you need to seed with at least 226 bits.