4 ms·

In terms of actually playing games with cards, the effective number of permutations can be much smaller (though still large enough to be going on with). In man

In terms of actually playing games with cards, the effective number of permutations can be much smaller (though still large enough to be going on with). In many card games, the suits are distinct but functionally identical; you could swap spades rank-for-rank with hearts and get a functionally equivalent deck. In Klondike solitaire, the tableau is concerned with red cards and black cards, not all four suits. I imagine somebody has done research on this: for a given card game, how many functionally distinct shuffles there are.

wduquette 2y ago
I remember looking at some early Draw Poker machines in Las Vegas back in the late 80's/early 90's, and thinking about pseudo-random number generation (as it existed at that time). If it was using a standard linear-congruential RNG with a 16 bit value, there would be only 65536 possible seeds, and hence only that many distinct sequences of random numbers, and hence only that many possible shuffles. Even a 64-bit RNG would have only 1.844674407370955e+19 possible shuffles, far lower than 52!.
- zaik 2y ago
  ln(52!)/ln(2)≈226 bits. You don't have to depend on a single random 64-bit number: https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
  - Straw 2y ago
    If the RNG has < 226 bits of state, such as most non cryptographic PRNGs, you cannot reach all shuffles even if you use multiple numbers.
    - IanCal 2y ago
      I'm not totally sure that's true. I get where you are coming from, an 8 bit rng can only output 256 distinct values at most. 256 would be the longest cycle. However if you combine the outputs of two, but don't step them at the same time, you can have more outputs. Imagine you had one that outputs just 0 and 1 and then loops. You could have two of these updating at a different frequency and have four distinct outputs. I think that makes sense.
      - wduquette 2y ago
        Oh, yeah, there are ways to finesse it. I’m just wondering whether anyone involved in those early poker machines had made the effort.
        cardiffspaceman 2y ago
        In Nevada one was required to “prove the randomness” of random outcomes in video poker machines as well as other electronic gambling machines. So effort was made.
    - kcnj 2y ago
      Hey, sorry to contact you via this method. I meant to reply to your comment under the thread on SCALE but it's locked. I'm expecting an offer from that company and would like to ask you about your experience there. If you don't mind, could you accept my connection request on LinkedIn and we could chat there? Thank you :)
- DerekL 2y ago
  When playing draw poker, you only need to select 10 cards from the deck, because the other cards will never be played. So that's 52⋅51⋅…⋅43 = 57,407,703,889,536,000, which needs 56 bits.
sophacles 2y ago
You're right. There are also game rules that can act as multipliers (e.g. who has the blind affects the game state in poker - so that means that there are actually multiple "games" for each given shuffle). Something you may find interesting is formal methods - what we're talking about here are "equivalence classes". In formal methods you want to analyze the totality of a system and understand every outcome based on every possible state within the rules of the system. Clearly this is a combinatoric nightmare in anything interesting (even a simple system like a card game and 52 cards, as we can see). Equivalence classes are a way of knowing distinct, but not actually different, states, and grouping them together so that they can all be considered just once.
montefischer 2y ago
Those interested can read Mark Conger's thesis to learn about the mathematics of repeated cards: https://websites.umich.edu/~mconger/thesis.pdf https://websites.umich.edu/~mconger/thesis.pdf
ozyschmozy 2y ago
Pretty easy to calculate how many distinct shuffles considering only the numbers: 52!/(4!^13)=~9.2e49. Still monstrously big

wduquette 2y ago

I remember looking at some early Draw Poker machines in Las Vegas back in the late 80's/early 90's, and thinking about pseudo-random number generation (as it existed at that time). If it was using a standard linear-congruential RNG with a 16 bit value, there would be only 65536 possible seeds, and hence only that many distinct sequences of random numbers, and hence only that many possible shuffles. Even a 64-bit RNG would have only 1.844674407370955e+19 possible shuffles, far lower than 52!.

zaik 2y ago
ln(52!)/ln(2)≈226 bits. You don't have to depend on a single random 64-bit number: https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
- Straw 2y ago
  If the RNG has < 226 bits of state, such as most non cryptographic PRNGs, you cannot reach all shuffles even if you use multiple numbers.
  - IanCal 2y ago
    I'm not totally sure that's true. I get where you are coming from, an 8 bit rng can only output 256 distinct values at most. 256 would be the longest cycle. However if you combine the outputs of two, but don't step them at the same time, you can have more outputs. Imagine you had one that outputs just 0 and 1 and then loops. You could have two of these updating at a different frequency and have four distinct outputs. I think that makes sense.
    - wduquette 2y ago
      Oh, yeah, there are ways to finesse it. I’m just wondering whether anyone involved in those early poker machines had made the effort.
      - cardiffspaceman 2y ago
        In Nevada one was required to “prove the randomness” of random outcomes in video poker machines as well as other electronic gambling machines. So effort was made.
  - kcnj 2y ago
    Hey, sorry to contact you via this method. I meant to reply to your comment under the thread on SCALE but it's locked. I'm expecting an offer from that company and would like to ask you about your experience there. If you don't mind, could you accept my connection request on LinkedIn and we could chat there? Thank you :)
DerekL 2y ago
When playing draw poker, you only need to select 10 cards from the deck, because the other cards will never be played. So that's 52⋅51⋅…⋅43 = 57,407,703,889,536,000, which needs 56 bits.

sophacles 2y ago

You're right. There are also game rules that can act as multipliers (e.g. who has the blind affects the game state in poker - so that means that there are actually multiple "games" for each given shuffle). Something you may find interesting is formal methods - what we're talking about here are "equivalence classes". In formal methods you want to analyze the totality of a system and understand every outcome based on every possible state within the rules of the system. Clearly this is a combinatoric nightmare in anything interesting (even a simple system like a card game and 52 cards, as we can see). Equivalence classes are a way of knowing distinct, but not actually different, states, and grouping them together so that they can all be considered just once.

montefischer 2y ago

Those interested can read Mark Conger's thesis to learn about the mathematics of repeated cards: https://websites.umich.edu/~mconger/thesis.pdf https://websites.umich.edu/~mconger/thesis.pdf

ozyschmozy 2y ago

Pretty easy to calculate how many distinct shuffles considering only the numbers: 52!/(4!^13)=~9.2e49. Still monstrously big