PowerBASIC Shuffling and Dealing

“The generation of random numbers is too important to be left to chance.”   –Robert R. Coveyou

Shuffling About

Sometime in the 1980's, when computer bridge scoring was just getting started and BASIC programming was becoming quite popular, the American Contract Bridge League (ACBL)  published a shuffle-deal routine in BASIC code.  It is unfortunate, however, that no one — including, apparently, the programmer — had bothered to do any testing; for the routine was hideously flawed.  The programmer, by randomly selecting partially filled hands rather than random undealt cards, created a scenario in which the purportedly random choices did not carry equal weight; and such a contingency is unacceptable in the world of probabilities.

As with sort routines, there has been an exhaustive amount of research on shuffling.  Gaming casinos and online poker sites alike are keenly interested in maximizing the randomness of their shuffles; otherwise, the results could be predicted and their games could be mathematically beaten.  Despite all the study, debates still rage over the efficacy of certain algorithms.

Being addicted to the game of contract bridge as well as to computer programming, my research has extensively focused on mixing a deck of cards.  For testing an algorithm, I deal four 13-card hands using various shuffles, then compare the results with known mathematical expectations.  Everything meaningful is counted — hand patterns, suit lengths, runs, individual card placements, and more.

Said testing merely corroborates the countless existing analyses of shuffling algorithms, however.  Much online commentary is available explaining why certain popular and seemingly workable methods are inherently flawed.  Here are some good places to start reading:

http://en.wikipedia.org/wiki/Knuth_shuffle

http://www.codinghorror.com/blog/2007/12/the-danger-of-naivete.html

Before continuing, a disclaimer is in order.  The PowerBASIC Random Number Generator has only 2³² different states, which limits the programmer to about four billion unique series of random numbers.  To access all permutations of 52 cards would require an RNG with a period of at least 226 instead of just 32.  For that reason, an online casino or the like would want to utilize a more robust RNG.  Many such algorithms exist, and source code is readily available.  For that matter, if one would prefer that someone else do the programming, true random numbers themselves are freely available at:

http://www.random.org

Meanwhile, being determined to write our own code, we will concentrate on a pair of methods that are both valid and easy to implement.

Any computerized dealing routine must begin with the pack arrayed in some ordered fashion; otherwise, there would be no way of tracking the cards' locations.  One popular choice is to arrange them spades first, ace to deuce, then the hearts, diamonds, and clubs.  The first card, therefore, would be the ace of spades, and the deuce of clubs would come last.  That sounds like a good plan.

RANDOM  SORT  SHUFFLE

This routine generates a series of random numbers, then sorts them.  As the randoms in array X() are organized, the data in A() are moved about in parallel fashion.  This example utilizes a simple Bubble Sort for the process.

Array A() now contains a shuffled series of numbers 1-52.  A different sorting routine would produce a different shuffled sequence, but that doesn't matter.  How the resultant values translate to actual cards is the programmer's choice.  I realize that this method seems absurdly simple, because it is.  PowerBASIC makes the procedure even more concise with a built-in sorting facility.  Here is a tiny yet perfectly valid card-shuffler:

Sorting randoms in this fashion is the method used by the ACBL for its preparation of tournament hands.  They also do some tricky stuff with random seeds and whatnot in an attempt to ensure that all 53 billion billion billion possible deals actually can be accessed.

There is a potential implementation problem, though.  Any duplication in the data series will not be handled randomly by sort routines, which tend to collect equal values sequentially.  It would be incumbent upon the programmer to ensure that there be no duplication of such values, if that could matter.  In any case, one can do better, at least in terms of speed — not that one would necessarily need it:

THE  FISHER–YATES–KNUTH–DURSTENFELD  SHUFFLE

Although I conceived this algorithm independently some decades ago (it isn't all that complicated), Ronald Fisher and Frank Yates did it first, so they get the credit.  The better-known guru Donald Knuth later published the same method in his classic, The Art of Computer Programming, then acknowledged Fisher and Yates in a subsequent printing.

Being a linear O(n) algorithm, it is more or less as fast as possible.  From the sort list A(), a random unit is selected and collected sequentially in X().  Then the last data element is placed in the slot vacated by the selected unit, and the scope of the random search is decremented.  The process repeats until all data elements have been assigned.  Array X() then contains a shuffled list.

Refilling the position of each selected element serves to collect the unallocated data into an increasingly smaller contiguous list; array elements greater than the current value of D become irrelevant.  An alternative method would be to zero-out allocated cells, then skip over them if subsequently selected.  That flawed approach was later eliminated by Mr. Richard Durstenfeld, so he gets some credit as well.

Yes, one might be able to speed up the process somewhat by using pointers or assembly code.  As it is, however, my PC generates a quarter-million deals per second using this method; so I am content.

A  WORD  ABOUT  HUMAN  SHUFFLES

Using a deck of Kem cards of average wear and average grime, I made 100 normal shuffles, noting the sizes of both the cuts and the resultant 'packets'.  The cuts varied from 24-28 cards, and the packets ranged between one and seven cards.  Starting with an ordered deck, a shuffling routine then simulated my human shuffles by making weighted random choices of cut and packets, based upon their empirically determined frequencies of occurrence.

Results of testing proved reasonable, albeit unacceptable by computer standards.  Six shuffles yielded much better statistics than three, and ten shuffles were even better yet.  Perhaps that disparity would be lessened by starting with a more randomly organized deck, such as from a live game; meanwhile, ten shuffles seems like a good choice.

Note: other studies have concluded that seven shuffles are mathematically sufficient to randomize the deck, but their formulas do not take into account the 'packeting factor' of used, sticky cards.

What's the Deal?

Shuffling is only part of the job; the cards must be dealt as well.  The two processes can be combined effortlessly using the FYKD Shuffle.  Although it makes no difference whether the cards are distributed one at a time or thirteen at a time, the following routine simulates a standard human-style deal of one card at a time around the table, collecting the random selections to the 4×13 array, Deal().

Comprehensive valid methods don't necessarily require a lot of code!

It is the responsibility of the programmer, or course, to begin each deal at a unique position in the Random Number Generator cycle, to avoid duplicating a hand.  There also are various options for storing the cards, of course.  Instead of using my example 4×13 matrix, one might choose to array the dealt cards together as Cards(0-51) or Cards(1-52), and assign to each card a number representing a designated hand.  I can tell you from experience, though, that that is not the best way to go.  For the serious programmer, I offer this highly versatile setup which has served my card-oriented programs quite well:

Having been stored in binary fashion in a 4×4 array of suits, the cards in each suit are effectively sorted as well!  Stepping through the bits sequentially accesses the cards in ranking order:

Somewhere along the line I found it useful to double those values; I have forgotten why, but it had something to do with not using zero as a parameter.