Mar 28, 2014

Hi! My name is Alan Comer, and I am here today to talk about randomness .  I have worked on many TCGs over the last 10+ years — Magic Online, Kaijudo, and Pokémon are the biggest. Every time, randomness becomes a hot topic of discussion.  It happens inside the companies, as well as on the forums. I have been called on many times to explain what really happens, and why. I would like to start with the basics so that everybody is on the same footing.

First off, what is randomness?

For true randomness, each event is independent of all others and is impossible to predict.  Each possible outcome has a specific chance that it will occur.

How do we use randomness?

We don’t.  We use something called pseudo-random (as does every other game ever made).  We try to get as close to true random as possible because getting 100% of the way there is extremely painful.  Like many things in computer science, you must weigh tradeoffs.  The more random you get, the longer it takes to generate results.

Okay, so how are pseudo-random numbers generated?

There are many ways.

C/C++ has a function called rand().  It is generally considered terrible.  To improve on this, people have come up with better and better algorithms— ComplimentaryMultiply with Carry, Mersenne Twister, on up to cryptographically secure algorithms.  These are called PseudoRandom Number Generators, or PRNG for short.

Which is best?

Well, the cryptographically secure ones are best, but quite time consuming.  After that, things break down into various camps arguing their side is better.  As a general rule, they are good enough for our purposes, as long as they are used correctly. Virtually all games use PRNGs

What is a seed?

The original input into the PRNG. From this number, the PRNG creates random numbers

What do we need to look for in our algorithm?

ResearcherAdeptWEBFirst order results:  Does every number show up approximately the same number of times as every other over a given sample size?

Second order results:  Given the previous number, is the likelihood of the next number still flat?  Failure to be flat here would cause things like “Card A shows up after Card B too often”

Periodicity:  Simply put, how long does it take before it repeats? How long after you give it a seed does it take before it works reasonably? If this is too low, you could learn the sequence and be able to predict results later in the game based on earlier ones. Periodicity in PRNGs are orders of magnitude larger than the length of the game, and anything longer than the length of the game is enough.

How can the PRNG be proven it is random?

It can’t.  The nature of statistics states that statistics itself can’t be proven.  That is why it is called “The Theory of Statistics”.  Anybody who is telling you that they can prove something with statistics is wrong.  In addition, no matter what test is run, there is always a chance of a false positive or negative.

How should one test for a failure of randomness?

The proper test is to first, state your theory as to what is the problem is.  Next, you need to decide a sample size, and make sure it is large enough.  After that, you calculate what the expected result is, and what is a reasonable variance from that result (Z Score).  Finally, you run through all the steps and compare the result.  After this, it is likely that you have the correct answer.  Yes, this is ugly and annoying and time consumingBut, we do it because we must verify that our game is fair. 

What can go wrong with tests?

Human error:  This is a big one.  When you are looking at thousands of events, missing something uninteresting can be common and skew the results.

Looking at the past:  You must start with an idea of the problem, then test. Sooner or later, even very unlikely things are bound to happen.  If you get a funny opening hand 5 times in a row, many people think that the odds of that happening were very low.  However, the odds that it happen is 100% because it already happened.  It is now a known event.   Just think about the lottery. The odds of winning are very low.  However, most weeks, there is a winner and people ask “what were the odds?”  The randomizer wasn’t broken; in whole, everything worked like it should.  However, from that 1 person’s perspective…  The same thing happens with strange opening hands.  One person gets the event, and often posts in the forums just like one person eventually wins the lottery.

Too small a sample size:  On one project, the customer complained that Event A happened too frequently based on their sample size of 1,000 events.  I disagreed.  Eventually, they hired somebody independent to test it.  They came back after testing 1,000 events.  Yes, it was definitely wrong.  The event happened too infrequently.  I ran a test of 1,000,000 events.  It was fine.  Sample size is very important.

What have we done to test our algorithm in HEX?

CrazedRummagingWEBI have run 1,000,000 numbers and looked at the 1st and 2nd order results.  They look fine.

Periodicity tends not to be a problem for TCGs, as each game gets a new seed, and the periodicity is much larger than the length of the game.

Also, whenever anybody new joins the project, they are encouraged to look at the RNG and how it is used.  It is important that everybody on the project believes that we are random, and the best way to do that is for them to check it out themselves.

What are some problems I have seen over the years on TCGs?

Invalid shuffling algorithm:  Even though the PRNG is correct, I have seen a bad algorithm for shuffling a deck, which caused bias in the hands that were given.  I only saw this in old code, as the problem had been caught before I even arrived on the project.  HEX does not have this problem.

Not waiting long enough after the seed to use the PRNG.

I was working on one project, running 10000 games overnight Ai vs AI to test AI strengths.  I noticed that the AI always won an even number of games.  The seeds I was using were consecutive and the algorithm was not generating different enough numbers for it to affect consecutive games!  Again, this was not HEX.

Misusing the results of the PRNG.

A card that had a chance to kill each troop based on its toughness.  The code was comparing the result of the RNG wrong, which resulted in an extra 10% chance for each troop to die.  Yes, this was found in HEX, and has been fixed.

Using an RNG that doesn’t perform well directly after seeding, and reseeding it too often.

Yep, I have seen code that generates a new seed for each random number it needs.  When I saw this and tested it, I found that some numbers were twice as likely to be generated than others. This is a known effect of the PRNG that was being used for this.  This I also found in HEX, back when I did a complete audit of the PRNG.  However, it was in the pack opening code, something that as of this writing, has yet to be released to the public.

Finally, what is my opinion of the state of randomness in the game?

I feel really good about it.  It is a hard thing to get right, but a lot of experienced engineers have looked it over.  The last few audits have found no problems. There are quite a few posts about it on the forums, but I would be worried if there wasn’t.  In fact, while working on Magic Online, I came up with the following rule:

“There is a correct amount of people complaining on the forums for a game to be properly random”.   In short, if nobody is seeing strange looking events, the game isn’t random.  Conversely, if too many people are having problems, it also isn’t random.  Much like Game Theory saying there is an answer, but not what the answer is,  I don’t know what the correct level of comments is, just that there is one.

-Alan Comer

Discuss this article in our forums!