Shuffling and Dealing
“The generation of random numbers
is too important to be left to chance.”
— Robert R. Coveyou
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 concentrated on mixing a deck of cards.
For testing, 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:
Before continuing, a disclaimer is in order. The PowerBASIC Random Number
Generator has only 232 different states, which limits the programmer to
about four billion unique series of random numbers. To access all
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
Meanwhile, being determined to write our own code, we will concentrate on a pair of methods that are both valid and easy to implement in PowerBASIC.
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.
DIM A(1 TO 52) AS LONG
DIM X(1 TO 52) AS DOUBLE
'for the random values
DIM J%, K%
FOR J=1 TO 52: A(J)=J: NEXT
'initialize the pack
FOR J=1 TO 52: X(J)=RND: NEXT
FOR J=1 TO 51
FOR K=J+1 TO 52
IF X(J)>X(K) THEN SWAP X(J),X(K): SWAP A(J),A(K)
Array A() now contains a shuffled series of numbers
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
FOR J=1 TO 52: A(J)=J: X(J)=RND: NEXT
'seed deck, get randoms
ARRAY SORT X(), TAGARRAY A()
'A() is shuffled
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 number 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 random values. 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
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.
DIM A%(1 TO 52), X%(1 TO 52)
DIM D%, J%, R%
FOR J=1 TO 52: A(J)=J: NEXT
'seed the deck
FOR J=1 TO 52
'random integer, 1 to size
'assign the value
'fill the hole
'reduce the range of choices
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
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
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
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.
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().
'starts as an ordered pack
'stores the players' cards
DIM Hand%, Card%, CD%, R%
'OUT: Deal(h,c) = hands:#0-3, cards:#0-12
FOR CD=0 TO 51: Deck(CD)=CD: NEXT
'initialize the pack
FOR CD=0 TO 51
Hand=CD MOD 4
Card=CD MOD 13
'available choices decremented each loop
'assign card to hand
'move "last" card in range to selected cell
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:
DIM Deck(51) AS INTEGER
'deck of cards
'range of random choices
DIM C%, H%, S%, D%, R%
'Card, Hand, Suit, Denomination, Random
FOR C=0 TO 51: Deck(C)=C: NEXT
'initialize pack: 0=spade ace .. 51=club deuce
FOR C=0 TO 12
FOR H=0 TO 3
'north=0, east=1, south=2, west=3
D=Deck(R) MOD 13
'ace=0, king=1, ..deuce=12
'spades=0, hearts=1, diamonds=2, clubs=3
BIT SET Deal(H,S),D
'deal card (hand,suit)
'move last card to current cell
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:
bit(0)=1 =ace; bit(1)=2 =king; bit(2)=4 =queen; ... bit(12)=4096 =deuce
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.