Hi Robin, thanks for looking in and commenting. My shuffling method is addressed here https://bridgecommaoutahead.substack.com/p/how-random-is-it-exactly. Folks who use something other than Javascript have solved this by using a random number generator that can generate an integer large enough to encompass the number of possible deals; they then convert that integer into a deal. You can see that since I only use Javascript, I rely on the window.crypto function that is available to all browsers--but that its degree of entropy is not guaranteed to be high enough for any given purpose. Not wanting to rely on just one call to that function, I call it 52 times and assign the resulting pseudo-random number to each card, then sort the deck on that number. A mathematician might look at that and tell me that using 52 pseudo random numbers does not improve on the potentially low degree of entropy from a single pseudo random number, but as a non-mathematician I did what felt like an improvement on using a single number. Each implementation of window.crypto obtains its seed from some source or other; therefore it varies by browser and possibly by operating system, and I don't control that--I just call window.crypto.getrandomvalues. I would like to know the actual degree of randomness of my method, but of course it's going to vary by platform and implementation of the window.crypto functions.
Can you tell me about how you do the shuffle? Do you use the "modified Fisher-Yates" algorithm (also known as Knuth's Algorithm P)? How do you choose the seed?
Hi Robin, thanks for looking in and commenting. My shuffling method is addressed here https://bridgecommaoutahead.substack.com/p/how-random-is-it-exactly. Folks who use something other than Javascript have solved this by using a random number generator that can generate an integer large enough to encompass the number of possible deals; they then convert that integer into a deal. You can see that since I only use Javascript, I rely on the window.crypto function that is available to all browsers--but that its degree of entropy is not guaranteed to be high enough for any given purpose. Not wanting to rely on just one call to that function, I call it 52 times and assign the resulting pseudo-random number to each card, then sort the deck on that number. A mathematician might look at that and tell me that using 52 pseudo random numbers does not improve on the potentially low degree of entropy from a single pseudo random number, but as a non-mathematician I did what felt like an improvement on using a single number. Each implementation of window.crypto obtains its seed from some source or other; therefore it varies by browser and possibly by operating system, and I don't control that--I just call window.crypto.getrandomvalues. I would like to know the actual degree of randomness of my method, but of course it's going to vary by platform and implementation of the window.crypto functions.
Uh Oh. I just read your article. You MUST not ditch Fisher-Yates. It is the correct way to shuffle. All you need to worry about is getting sufficient entropy (which I think you're doing because you are calling the crypto method which is not a PNRG, or so I believe). Anyway, if you do it as I describe, you will be guaranteed to get it right--provided that you have coded (or in your case, copied) correct Fisher-Yates code. It's easy to get wrong.
Hi Robin. My possibly naive method was inspired by thinking that the real action is in the generation of random numbers, or as close as you can get to random; if that were the case (I thought), then I really just need to get 52 as nearly random numbers as I can, assign each one to a card, and sort on the nearly-random numbers. I see now from https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle that this is basically the original pencil-and-paper method of Fisher & Yates, using the crypto generator in lieu of a paper "table" of random numbers. In the Wikipedia article, I also see this way down after long discussion of the algorithm:
"An alternative method assigns a random number to each element of the set to be shuffled and then sorts the set according to the assigned numbers. The sorting method has the same asymptotic time complexity as Fisher–Yates: although general sorting is O(n log n), numbers are efficiently sorted using Radix sort in O(n) time. Like the Fisher–Yates shuffle, the sorting method produces unbiased results."
As a layman, that seems to go full circle back to the pencil-and-paper method, and I truly don't understand why I need an algorithm other than sorting on my fairly random numbers.
I appreciate your attempt to explain it.
Fortunately, provable randomness is not actually a goal of my program. In fact, random deals might be the least interesting thing it provides, since you abandon randomness as soon as you make a recipe.
Also, to further shock you: if any placeholders are used in the Cards panel, the deck is shuffled twice. One shuffle up front, then cards are cherry picked to replace placeholders per the recipe, then another shuffle of the unallocated cards before dealing them out to whatever slots are left around the table. This solves a problem where too many cards in a suit were landing on hands that had several placeholders for that suit.
So you see, this is all geared toward creation of instructional deals, very likely non-random. Not suited for live competition with points or money on the line.
Good points. This is my special area of expertise (I teach this stuff at Northeastern University). You're right that the two methods are equivalent. The reason to use Fisher-Yates is time complexity (linear vs. linearithmic). Of course, with only 52 elements, both operations will complete in milliseconds or less so no big deal. Using a radix sort is linear but, because of the coefficient of n required, it typically doesn't become more efficient in practice until you start sorting much bigger datasets. Keep up the good work :)
Thanks for your response. I was playing bridge (without any hand shuffling) for five days. You might simplify your life slightly by making one call to crypto.RandomBytes(52) and then using each byte to provide one value for each iteration of the Fisher-Yates (Knuth) shuffle. Assuming that the 52 bytes are truly random (and they should be unless you just rebooted), you'll have 416 bits of entropy (of which you will in practice only use 312) but that's more than enough to make all possible deals equally likely (you need just 226 bits of entropy for a completely random deal). But your method looks OK--because you are not using a pseudo-random number generator--you're getting your entropy from the system.
Hi Robin, thanks for looking in and commenting. My shuffling method is addressed here https://bridgecommaoutahead.substack.com/p/how-random-is-it-exactly. Folks who use something other than Javascript have solved this by using a random number generator that can generate an integer large enough to encompass the number of possible deals; they then convert that integer into a deal. You can see that since I only use Javascript, I rely on the window.crypto function that is available to all browsers--but that its degree of entropy is not guaranteed to be high enough for any given purpose. Not wanting to rely on just one call to that function, I call it 52 times and assign the resulting pseudo-random number to each card, then sort the deck on that number. A mathematician might look at that and tell me that using 52 pseudo random numbers does not improve on the potentially low degree of entropy from a single pseudo random number, but as a non-mathematician I did what felt like an improvement on using a single number. Each implementation of window.crypto obtains its seed from some source or other; therefore it varies by browser and possibly by operating system, and I don't control that--I just call window.crypto.getrandomvalues. I would like to know the actual degree of randomness of my method, but of course it's going to vary by platform and implementation of the window.crypto functions.
Can you tell me about how you do the shuffle? Do you use the "modified Fisher-Yates" algorithm (also known as Knuth's Algorithm P)? How do you choose the seed?
Oops, replied to my post, not to you:
Hi Robin, thanks for looking in and commenting. My shuffling method is addressed here https://bridgecommaoutahead.substack.com/p/how-random-is-it-exactly. Folks who use something other than Javascript have solved this by using a random number generator that can generate an integer large enough to encompass the number of possible deals; they then convert that integer into a deal. You can see that since I only use Javascript, I rely on the window.crypto function that is available to all browsers--but that its degree of entropy is not guaranteed to be high enough for any given purpose. Not wanting to rely on just one call to that function, I call it 52 times and assign the resulting pseudo-random number to each card, then sort the deck on that number. A mathematician might look at that and tell me that using 52 pseudo random numbers does not improve on the potentially low degree of entropy from a single pseudo random number, but as a non-mathematician I did what felt like an improvement on using a single number. Each implementation of window.crypto obtains its seed from some source or other; therefore it varies by browser and possibly by operating system, and I don't control that--I just call window.crypto.getrandomvalues. I would like to know the actual degree of randomness of my method, but of course it's going to vary by platform and implementation of the window.crypto functions.
Uh Oh. I just read your article. You MUST not ditch Fisher-Yates. It is the correct way to shuffle. All you need to worry about is getting sufficient entropy (which I think you're doing because you are calling the crypto method which is not a PNRG, or so I believe). Anyway, if you do it as I describe, you will be guaranteed to get it right--provided that you have coded (or in your case, copied) correct Fisher-Yates code. It's easy to get wrong.
Hi Robin. My possibly naive method was inspired by thinking that the real action is in the generation of random numbers, or as close as you can get to random; if that were the case (I thought), then I really just need to get 52 as nearly random numbers as I can, assign each one to a card, and sort on the nearly-random numbers. I see now from https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle that this is basically the original pencil-and-paper method of Fisher & Yates, using the crypto generator in lieu of a paper "table" of random numbers. In the Wikipedia article, I also see this way down after long discussion of the algorithm:
"An alternative method assigns a random number to each element of the set to be shuffled and then sorts the set according to the assigned numbers. The sorting method has the same asymptotic time complexity as Fisher–Yates: although general sorting is O(n log n), numbers are efficiently sorted using Radix sort in O(n) time. Like the Fisher–Yates shuffle, the sorting method produces unbiased results."
As a layman, that seems to go full circle back to the pencil-and-paper method, and I truly don't understand why I need an algorithm other than sorting on my fairly random numbers.
I appreciate your attempt to explain it.
Fortunately, provable randomness is not actually a goal of my program. In fact, random deals might be the least interesting thing it provides, since you abandon randomness as soon as you make a recipe.
Also, to further shock you: if any placeholders are used in the Cards panel, the deck is shuffled twice. One shuffle up front, then cards are cherry picked to replace placeholders per the recipe, then another shuffle of the unallocated cards before dealing them out to whatever slots are left around the table. This solves a problem where too many cards in a suit were landing on hands that had several placeholders for that suit.
So you see, this is all geared toward creation of instructional deals, very likely non-random. Not suited for live competition with points or money on the line.
Good points. This is my special area of expertise (I teach this stuff at Northeastern University). You're right that the two methods are equivalent. The reason to use Fisher-Yates is time complexity (linear vs. linearithmic). Of course, with only 52 elements, both operations will complete in milliseconds or less so no big deal. Using a radix sort is linear but, because of the coefficient of n required, it typically doesn't become more efficient in practice until you start sorting much bigger datasets. Keep up the good work :)
Thanks for your response. I was playing bridge (without any hand shuffling) for five days. You might simplify your life slightly by making one call to crypto.RandomBytes(52) and then using each byte to provide one value for each iteration of the Fisher-Yates (Knuth) shuffle. Assuming that the 52 bytes are truly random (and they should be unless you just rebooted), you'll have 416 bits of entropy (of which you will in practice only use 312) but that's more than enough to make all possible deals equally likely (you need just 226 bits of entropy for a completely random deal). But your method looks OK--because you are not using a pseudo-random number generator--you're getting your entropy from the system.