How Random Is It, Exactly?

Spoiler alert: I don't know, but better than it was before today's upgrade

In the Computation Corner office

The standard Computation Corner warning applies: this post is about computer programming.

I am neither a mathematician nor a statistician, so when it comes to the topic of randomness I throw myself upon the mercy of Google and hope to turn up some PRNG (Programs Right for Non-maths Guy).

Early on, I was so grateful to find working code samples based on the Fisher-Yates randomization algorithm—and for the opportunity to pretend that I knew what that was before finding the samples—that I just blindly made that the basis for my deck-shuffling function. And by “basis” I mean I cut and paste that code right in there.

Deal generation continued apace and things were fine for over a year until I accidentally read some articles about how computers are deterministic, and true randomness is unlikely, and some foolish people—true scientists pity them—actually rely on (*sniff*) Fisher-Yates and math.random() and oh Lawdy what seed are they using and puh-leeze don’t tell me they are relying on 32-bit integers anywhere in there.

I wish I had stopped reading, but my eyes were locked on in horror and I couldn’t stop. When I reached the end of the article, I knew that my shuffling method was inadequate and that my users could experience the agony of duplicate deals, possibly within as few as 30 years of non-stop deal generation on every computer on the planet. Though you know, to show you how divorced from academia I am, it seems to me that if the duplicate deal is possible, wouldn’t it be just as likely to happen in, say, five minutes as in 30 years? That’s a rhetorical assertion, not even really a question, and does not require an answer; if I don’t know why it’s nonsensical now, no amount of fancy figuring and diagrams will help me so please don’t try. I know where the math section of the ACBL Encyclopedia of Bridge is, and how to flip past its diagram-filled pages.

So. My shuffle was inadequate and there was nothing for it but to search harder on Google for something that would make me feel better. Would it be more nearly random? I hoped so, but making me feel better was Job #1.

The first thing I did was ditch Fisher-Yates. My reading about obtaining non-deterministic seeds for my randomization code convinced me that Javascript’s math.random was not quite the thing. Again, for cloudy reasons which I could not explain to save my life.

I then happened upon window.crypto.GetRandomValues() as a way to obtain pseudo-random numbers possibly based on a more cryptographically secure seed. I say “possibly” because of this nugget from the Mozilla developer docs (emphasis added):

“There is no minimum degree of entropy mandated by the Web Cryptography specification. User agents are instead urged to provide the best entropy they can when generating random numbers, using a well-defined, efficient pseudorandom number generator built into the user agent itself, but seeded with values taken from an external source of pseudorandom numbers, such as a platform-specific random number function, the Unix /dev/urandom device, or other source of random or pseudorandom data.”

So, no minimum entropy mandate; user agents urged to do the best they can to make it good and entropyish; and one or more possibly pretty good, all right sources of pseudorandom data. Compliance is optional and not monitored but did I mention that they urge folks to do right, and some browser developers just might do as they are urged? That, my friends, is probably—possibly—better than my 32-bit Fisher-Yates thing. Maybe.

So, I had my function to get better (I hoped) random values based on a possibly more nearly random seed. Now I had to deal with the 32-bit issue. What would it profit me to use a better PRNG to get my FARNs (Fake *ss Random Numbers) if I then restricted them to a container (an unsigned 32-bit integer) too small to hold them? It seems obvious that I should have just switched to unsigned 64-bit integers, and that’s what I did. Then, though, those 64-bit variables didn’t play nice with the little bit of code that referenced them; it seems that some built-in Javascript functions that operate on integers can’t deal with the big boys.

I set that aside for a very long time because I had other fish to fry. But today I finally sat down and figured out the really quite simple solution to my problem, and the generator now happily uses the better random number function, and it uses 64-bit unsigned integers.

Is it better than before? I think so. Do I therefore feel better? You betcha!

Here, for coders and math folk, is the actual shuffling function:

 shuffleDeck () {
    // Shuffle the deck.
    // Assign a super-duper cryptographically random integer to
    // each card in the deck, and put each integer/card pair
    // into an array. Then sort the array in ascending order
    // on the random integer.
    // window.crypto.getRandomValues() is a browser function,
    // won't run in a node.js server application.
    const array = new BigUint64Array(52);
    window.crypto.getRandomValues(array);
    var randomCards = [];

    for (var i = 0; i < this.theCards.length; i++) {
      randomCards.push([array[i], this.theCards[i]]);
    }

    randomCards.sort((a, b) => {
      if (a[0] < b[0]) { return -1; }
      if (a[0] > b[0]) { return 1; }
      return 0;
    });

    for (var i = 0; i < this.theCards.length; i++) {
      this.theCards[i] = randomCards[i][1];
    }
  }

That’s just the deck-shuffler. I have more to write about randomness, not of the whole deck but as it relates to deal shapers and recipes. That will be another post with less pseudo-science and more bridge.

Happy dealing!