Monday, October 19, 2015

How to properly shuffle virtual cards in software.

Last night, during one of many bouts with insomnia, I was attempting to bring on sleep by playing a mindless game,  Solitaire.   I say mindless since it requires only the tiniest bit of skill to play.  All you have to do is not miss a play.  The game will be won if it is winnable,  it depends on the order the cards come out of the deck.

This particular version of the game,  installed from the Chrome web store,  looked beautiful,  had wonderful card animation, nice sound, and terrible card shuffling!  After 30 lost games in a row,  I was quite annoyed, and further from sleep than when I began.

How do I know it was bad shuffling?   Well it was obvious by the regular discovery of two or three of the same number of card in succession.  Three Aces in a row,  or fives, etc.  This poor shuffle, at least in Solitaire,  leads to unwinnable games far more often than winnable games.

A poor shuffle might be advantageous in Poker,  to one player at least, but still a bad thing in the bigger picture.

I see this often.  Poor shuffling in a card game program.    I always remember my high school days and a certain programming contest a few friends and I had.

It was 1983.  My high school had several Apple ][+ computers in the library, as well as a couple in the vocational electronics class I was taking.   This was the early days of personal computers and almost nobody had one at home.   

Myself and a few friends, classic nerds of the day, were very much in love with these little machines.  We often fought over who would get time on them after class.  Our parents had become accustom to us staying after school until the janitor kicked us out and we trudged home to a cold dinner.   We amused ourselves with programming contests we’d come up with.  Each hoping to achieve the position of alpha male in our geeky clique.

The contest of one particular week grew out of a problem one of our group was having with trying to write a good blackjack game.    You see, we were programming in BASIC at the time, and it was not a very fast language.   The Apple ][+ had a CPU running at around 1Mhz.  BASIC, being an interpreted language was slow,  very slow,  unbelievably slow by today's standards.   Akin to comparing a formula one car to a cart drawn by a donkey.

Doug,  the kid working on the blackjack game, was rather cocky.  He was similar to Dr. Sheldon Cooper on The Big Bang Theory.  Very smart, yes, but so incredibly full of himself that we tolerated him only.   His problem was that it took well over two minutes for his card shuffle to complete at the beginning of the game.   He proposed a contest to come up with a better sorting routine.

By the end of the week, when we gathered to present our results, I was the clear winner and not by a narrow margin!    There were four of us, not counting Doug.   Doug had managed to get his shuffle down to one minute and thirty two seconds while sacrificing a bit of randomness.  Faster, but the shuffle was poor with many cards adjacent to their brothers.

The other three guys varied with one being a bit slower, and the other two beating Doug by just a couple of seconds.   All three also had somewhat poor shuffles.

My shuffle took all of four seconds.    Four,  yes,  only four seconds, in BASIC, on an Apple ][+.   Additionally, my shuffled deck was thoroughly shuffled with hardly a single instance of card pairs left. For awhile thereafter, Doug wasn't so cocky.

No,  I didn’t cheat, or use machine language.  It was a method that I came up with that I wish all programmers would use in modern card games.   Not for the speed, that hardly matters on today's incredibly fast machines.  No,  I wish programmers would use my method for the thorough randomness of the shuffled deck.

Here’s how it works.   Now,  I can’t present this in C, or Python,  .NET, or any modern language.   I’m not going to bore you with BASIC since it’s basically a dead language now.   I’m going to attempt to convey the idea,  it’s simple enough.

So first you need the deck to be shuffled.   In BASIC I simply loaded an array with numbers to represent the cards,  one through fifty two. I guess you'd use a table or something today.

Now, to shuffle them  you need a simple loop.   The loop with run fifty two times with a counter that’s incremented during each pass.   This counter will point to the position in the deck we’re working with.

For each pass of the loop,  you take the current card and exchange it with a random position in the deck.   So for pass one,  we’re working with the first card in the deck.  Pick a random number between one and fifty two and swap those two ‘cards’.

After only one pass through the loop, you’ll already have a deck that is shuffled better than what most modern card games end up with.   And it will happen incredibly fast.   Now, run the loop two or three times and you have a properly and thoroughly shuffled deck of cards.

Easy.   Simple.   So please,  programmers,  do this and properly shuffle your cards.  It will make for a much more realistic flow of the card game.

Thanks.

1 comment: