Shuffling and Dealing
“The generation of random numbers is too important to be left to chance.”
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
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 been concentrated on mixing a deck of cards. For testing, I deal
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 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:
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 'the data 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 'get randoms ' FOR J=1 TO 51 'bubble sort FOR K=J+1 TO 52 IF X(J)>X(K) THEN SWAP X(J),X(K): SWAP A(J),A(K) NEXT K NEXT J
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 sorting
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 credit.
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 D=52 FOR J=1 TO 52 R=RND(1,D) 'random integer, 1 to size X(J)=A(R) 'assign the value A(R)=A(D) 'fill the hole DECR D 'reduce the range of choices NEXT J
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
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.
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().
DIM Deck%(51) 'starts as an ordered pack DIM Deal%(3,12) '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 R=RND(0,51-CD) 'available choices decremented each loop Deal(hand,card)=Deck(R) 'assign card to hand Deck(R)=Deck(51-CD) 'move "last" card in range to selected cell NEXT CD
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:
SUB DealHand DIM Deck(51) AS INTEGER 'deck of cards DIM N% '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 N=51 FOR C=0 TO 12 FOR H=0 TO 3 'north=0, east=1, south=2, west=3 R=RND(0,N) D=Deck(R) MOD 13 'ace=0, king=1, ..deuce=12 S=Deck(R)\13 'spades=0, hearts=1, diamonds=2, clubs=3 BIT SET Deal(H,S),D 'deal card (hand,suit) Deck(R)=Deck(N) 'move last card to current cell DECR N NEXT H NEXT C END SUB '(DealHand)
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.