Dealing

Card dealing is a task commonly addressed online; it's a good beginner-level programming assignment, not to mention the cornerstone of all card games.

There are many approaches to card dealing. The one used in One Chip Video Poker is not a very elegant one - I chose it because it's suitable for use where code and data space are at an extreme premium, and because video poker has a couple of properties that accomodate it.

Card Representation

Cards are easily represented in a single byte each – the intuitive way to do it is just use the numbers from 0 to 51. Intuitive for assembly or C programmers, anyway, who like to think of numbering things starting at zero.

One very happy property of cards is that there are four suits, and four is one of those useful powers of two.

If you shift the suit bits off, you're effectively dividing by four. From 0..51, dividing by four – and ignoring any decimal remainder – gets you a number from 0 to 12. Handily enough, those correspond to the thirteen ranks.

Ranks:

Suits:

Not quite arbitrarily chosen – as it happens, if you add 3 to the suit values, you get the character codes for the heart, diamond, club, and spade on the PC console. That's how I get the nifty printouts like the one in the table at the bottom of the page.

Examples:

Hand Representation

Again, simplicity is the guiding light. At the beginning of a game, the PIC uses the current LCRNG seed (hopefully well stirred) and starts from there to generate the first ten cards out of the deck.

Why ten cards? Five of them form the initial (pat) hand, and the other five are the cards that can potentially be drawn.

A great deal more variety could conceivably be introduced to the game by dealing only five cards, then stirring the LCRNG while the player chose cards to hold, then dealing the drawn cards from the newly stirred seed. I may modify the game to work that way – but it's simpler to keep the dealing all in one place, and 4 billion hands is enough variety to be getting along with. Also, it would be very difficult to exhaustively test that kind of arrangement with a PC simulation.

The Dealing Algorithm

With all that in mind, here is the actual dealing algorithm.

Start with an empty hand, i.e. no cards dealt. Then, for each of n cards you want to deal:

1. Generate a random number with the LCRNG.

2. Grab the 6 most significant bits (since the higher-order bits tend to be more random than the lower-order ones).

3. Now you have a random number from 0..63. There are only 52 cards possible, 0..51; so, if your number is greater than 51, go back to step 1.

4. If any cards have already been dealt, check the new card against them to make sure it isn't already in the hand. If it is, go back to step 1.

5. The card is legit! Add it to the hand.

The astute reader will have osberved that this algorithm has the potential to run forever. In theory, the random number generator could be called trillions of times before a number from 0..51 could be gleaned from the top 6 bits, or it may spend years choosing cards it's already chosen.

As it turns out, that isn't a problem, and we owe it all to the fact that the “random” number generator is so predictable. As shown on the previous page, the LCRNG can only be in 2³² states, and the deal-10-cards strategy means there are only 2³² possible pat-plus-draw hands. 2³², or about four billion, isn't too bad a number of things to simulate exhaustively on a modern PC, assuming that each instance only needs a teeny thing done. I wrote a little PC C++ program that, for every possible seed, dealt the corresponding 10-card hand the same way the One Chip Poker program would do it. While it did that it kept track of how many times it had to call the LCRNG in order to generate the hand, and how many times it generated cards that were already present and therefore had to be redone.

It concluded this:
Highest # calls to LCRNG for any hand: 39
Highest # collisions: 15

39 calls to the LCRNG to generate 10 cards seems pretty bad, but this is all still blink-of-an-eye performance. Good enough!

Dealing cards this way turns out to need only around 45 machine instructions and around 16 bytes of variables including the 10 bytes for the hand, but not including the LCRNG's code & variables. (The LCRNG sits on 73 machine instructions and 8 bytes of RAM).

Verifying PIC implementation

The unit test for dealing is a little test program to deal out 10-card hands and show them on the LCD. Then, a corresponding PC program does the LCRNG / hand generation the same way and prints out expected results.

Here's an example of the simulation:

	On a 20x4 character display, the 10-card hands will just fit, one per line. The test starts with a hardcoded seed, generates 4 hands, and displays them – the first 5 cards on a row are the pat hand, and the last 5 are the draw pool. Then it awaits a button press from the user and does it all again. Repeat forever.
	The PC equivalent has a cleaner display, though there is no single-character “10” like the circuit has. I used a zero instead. Comparing this and the above picture, you can see that they're getting the same hands by doing the same calls.