Thursday, November 13, 2014

Are the Shuffles Random?

In a word: yes, they are (effectively) random.

Solitaire Till Dawn is now available for purchase in the Mac App Store!

Every so often, we get accused of rigging the shuffles in Solitaire Till Dawn. In the old releases that had a free trial, people would ask if they would win more games if they bought the app. (The answer was "no", you were no more likely to win or lose regardless of whether you'd purchased.)

The other day, I got a message from a user who was unhappy because he wasn't winning games in the new version at the same rate that he did in the older versions. He seemed certain that the new version was somehow making the games harder to win. (It isn't.)

(We have been trying to send email to that user, on this issue and in reply to other messages he has sent in the past few weeks. Our replies keep getting returned marked as "undeliverable". If you are that person: we don't know why we can't get through to you, but seriously we've been trying! We aren't ignoring you.)

What the heck is a PRNG?
Of course, the shuffles aren't truly random. It's hard to get a computer to do something completely at random. They aren't supposed to; you don't want them making random changes to your documents or your accounting data, after all. But you do want some deliberate randomness, or a good imitation of it, for games. You get that by using a piece of software called a pseudo-random number generator, or "PRNG" for sort.

A PRNG keeps a number called a seed. Every time you ask the PRNG to give you a new random number, it performs some deliberately-weird calculations on the seed. Then it gives you the result of the calculations, and also keeps them to use as the seed for the next time you ask.

So the sequence of "random" numbers you get from a PRNG aren't really random at all! They're just the results you get from applying a calculation to a number, and then again to that result, and then again with that result, and so on. If you start over with the same seed value, you will get the same sequence of results, every time.

The reason this is useful is that those calculations provide results that closely resemble a truly random sequence. You won't be able to predict the next number unless you know the seed and do the math yourself; and you get a distribution of results that looks a lot like a random distribution.

When you first start up a PRNG, you have to choose a seed. Like most apps that use PRNGs, Solitaire Till Dawn uses the current time and date (expressed as a single number, the number of seconds since Jan 1, 1970). So every time you start Solitaire Till Dawn, you get a different seed, and your "random" number sequence won't repeat what you got the last time.

Now, there's more than one PRNG algorithm out there. Some are better than others; some give results that don't look as random as we would like. Solitaire Till Dawn has always used the same algorithm, an industry standard that gives good results. For those who care, it is the Park and Miller "Minimal Standard" as reported in the Communications of the ACM, Vol.31, No. 10, 1988.

Okay, but...
So why might it seem as if the games are too hard, or not fair, or aren't properly shuffled? We think there are several possible reasons.

You're playing the wrong game. There are, for example, three close variations on Klondike in Solitaire Till Dawn. Some are harder to win, some easier. If you mistakenly play the wrong one, it's not surprising at all if you find it harder (or easier) to win than you remember. (For the record: Klondike Easy is the easiest to win, and Klondike Strict is the hardest. Klondike Familiar is in the middle; it's the one most people know, and it's the one that Solitaire Till Dawn opens by default the very first time you start it up.)

You see patterns that aren't really there. There are only four suits, only 13 ranks. Two shuffles can be genuinely different, yet might produce layouts that look similar. Play four games in a row that have a King as the first card in the tableaus, and you're going to notice that "pattern". If there are any other similarities in the layouts, that will reinforce the feeling that "the cards weren't really shuffled." But they really were, and I promise you that those layouts differ in other ways. (Human beings are really good at spotting patterns, and we tend to see them even when they aren't really there.)

You got lucky (or unlucky). If you flip a coin 100 times, you expect to get about 50 heads and about 50 tails, and you also probably expect not to see the same result for more than three or four flips in a row. If you get ten heads in a row, you might start to wonder whether you're flipping an honest coin.

But it's not that unusual to get ten heads or tails in a row. The chance of that happening when you flip only ten times is about one in five hundred. If you flip 100 times, it becomes much more likely. And if you have 1000 people flip a coin ten times each, it's not surprising at all for one or more of them to get ten heads or ten tails.

A run of bad luck may seem excessively unlikely, and therefore not random, to the person who experiences it. But there are literally thousands of people playing Solitaire Till Dawn. It is massively unlikely that you will win the state lottery, but the people who run the lottery know that somebody will eventually win it, and probably within the next few weeks. As the author of Solitaire Till Dawn, I am not surprised to get the occasional email from someone who got a run of bad luck and wants to know why. The answer is usually "you won the lottery". (Sorry that, in this case, it's a bad thing!)

Selective memory. I hate to bring this up, because you don't win friends (or make sales) by blaming the customer. But the truth is that failures and setbacks make a bigger impression on our memories than successes and wins. In over 20 years of selling Solitaire Till Dawn, I have never gotten an email saying "Are your shuffles really random? I'm winning too many games!"

When we win, we smile and go on to the next game. When we lose, we're frustrated, and if we continue to lose, the frustration builds up and may not be relieved by the occasional win. It makes the losses loom large in our memory.

Tough games. It's worth pointing out the obvious again: some games are harder to win than others, and some are very hard to win indeed. It takes a particular type of mind to enjoy these extreme challenges, and many people don't like to find a game in which it's nearly impossible to have a good win rate. My only advice here is to read the rules for each game: they'll tell you whether wins are easy or common. Stay away from the tough ones unless you enjoy the challenge.

In summation...
This has been a long post. Congratulations for reading it all the way through!

The upshot is this: Solitaire Till Dawn does its best to provide you with shuffles that you can't distinguish from random (and its "best" really is pretty good). Solitaire Till Dawn does not ever stack the deck, either to let you win or to make you fail—unless you ask it to.

That exception is the File > Play Game Number menu command. This lets you enter a "game number" to re-create a shuffle you've seen before. The game number is actually just the seed for the PRNG; as explained above, starting with the same seed gives reproducible results and allows a shuffle to be reproduced at your command. The previous seed is saved aside while your game number is used instead. Once you've finished replaying that game, the previous seed is reinstated, and your shuffles from that point on are once again (pseudo) random.

2 comments:

  1. I win Klondike Familiar about 65-70% of the time. The longest winning streak I have is 25 games. When I get stuck, I go back and start over and try different combinations of cards till I win or determine there is no way possible to win a game. This has been over 6000 games in the last three years

    ReplyDelete