brianbec's WebLog

This Blog

Home
About

Syndication

Search

Navigation

General Goodies

Math and Physics

Programming

Oh, the Brutality!

I found a well regarded battery of statistical tests for random-number generators. The battery is called "DIEHARD" (nyuk nyuk), and encapsulates the accumulated experience and wisdom of George Marsaglia, a recognized expert. Follow this link for his web page http://stat.fsu.edu/~geo/diehard.html.

This is a crushing, brutal series of tests that looks for patterns in dozens of ways. Anything passing these tests will look pretty random for a wide variety of applications. Marsaglia provides some "certified" random bits at http://stat.fsu.edu/pub/diehard/cdrom/. I ran DIEHARD on several of these "certified" files, and they pass. Here are the results. The basic idea is that none of the p-values should be too close to 1.000000 or 0.000000. Capisce?

Ok, so I applied it to the C# Random class output and to the Park-Miller minimum multiplicative PRN that I vetted on theoretical grounds in the last few blogs: Oh, oh, oh, the brutality! p-values of 1.000000 All Over The Place. Pain Here and Suffering There.

For some reasons I could not diagnose, DIEHARD refused to run its last handful of tests on MY data sets, encountering some kind of end-of-file error, even though my files were of the same format (so far as I could tell) as Marsaglia's. Probably some ^Z issue. I may not bother looking into it: the evidence is IN:

C#'s Random is probably multiplicative congruential: I know mine is. But neither one is anywhere near adequate for anything that requires DIEHARD-strength randoms.

Published Wednesday, August 18, 2004 4:18 PM by brianbec

Comments

# re: Oh, the Brutality!@ Wednesday, August 18, 2004 11:54 PM

I'm involved in an online gaming community where the sufficiency of randomness has been hotly debated.

Many participants INSIST that the game shuffler is skewed against them, in part because the draws they experience online don't reflect the draws they experience when playing with physical cards.

Most of us "logical" folk have tried to convince them that (in all likelyhood) they probably don't shuffle sufficiently with physical cards, and therefore THOSE draws are the games that are less truly random.

Unfortunately, without access to the source code, its hard to generate a true sample set to determine if there is a real problem.

So my (probably unanswerable) question is: for this type of application (shuffling card decks--not just of exactly 52 cards, but decks that could be anywhere between 40 and 985 cards), how random is good enough?

I'm interested in your reaction to this quote by the game developers:
-----------------
The core random number generator used is "Algorithm A", from Knuth's "Art of Computer Programming", sec 3.2.2. This is a fast, easy to implement random number generator. Knuth states that it has "consistently produced reliable results, in extensive tests since its
invention in 1958."

I first implemented this generator in 6502 assembly code in 1981 or so, and it has never failed me.

The implementation of this generator used in our libraries uses the standard constants (24,55). Because this is somewhat fewer than the number of bits required to produce all possible hands, it was augmented with another generator using the constants (33,68). This yields a total state size of 3936 bits. Both generators were combined so that the random number calls used in our library could still return the same sequence of numbers when initiated by our old programs.

In MTGO, random numbers are initialized by the game servers. When a new game is started, the random number state is seeded via /dev/random, which uses hardware delays for a source of true random data. In addition, whenever a packet is received from a user by the game server, the lower order bits of the system CPU's clock cycle counter are added into the random state.

Shuffling is performed by swapping every card in the deck with a random other card in the deck. This is algorithm "P" for shuffling from Knuth. The book contains a formal analysis of its randomness. The 32 bit random values returned by the basic random number function are mapped into the appropriate range by fixed point multiplication.
-----------
They sound fairly confident in their implementation. Based on your recent work, do you see any red flags here?

Brad Corbin

# re: Oh, the Brutality!@ Thursday, August 19, 2004 12:59 AM

First thing: years ago (many :), I played duplicate contract bridge. I played big, national ACBL tournaments and I played local club bridge at a reasonably high level every night. Tournament hands were computer-generated; club hands were hand shuffled. There was no question that the computer-generated hands had many more "long" suits -- runs of six or more cards of a single suit in a 13-card hand. I even saw 8-card and 9-card runs in computer-generated hands much more frequently than in hand-shuffled hands. It was rather alarming, actually. This effect was widely discussed, was noticeable to experts and tyros alike, and there was no one who said it wasn't so. The speculation was that hand-shuffled hands were "smoother," or "squarer," that is, less random. I would be surprised if someone did NOT do a formal study of this, but I do not know of such a study offhand.

On the other topic, of Algorithm A, why not have them dump out a file and run it into DIEHARD?

brianbec

# Coding randomness@ Thursday, August 19, 2004 4:47 AM

"Brianbec" shares his thoughts on statistical tests for random-number generators. He appears to have found some very interesting results that he explains at lenghth on his Weblog....

TrackBack

# re: Oh, the Brutality!@ Thursday, August 19, 2004 9:24 AM

I believe there has been some detailed analysis of 52-card deck randomization (how many riffle-shuffles on average it takes to randomize a deck, etc.)

In a tournament environment with a deck size minimum of 60 cards (and that is the optimum, most of the time) and no maximum deck size, up to the limits of the software (985, if I remember right), most of the 52-card studies are inadequate.

The frequency of streaks and runs is precicely the area that has been discussed the most in this environment as well. "6 turns without drawing a land? OUTRAGEOUS! The shuffler is out to beat me."

I will have to propose they analyze the shuffler against DIEHARD. That, or I guess I could implement Knuth Algorithm A the way they have and run it myself!