Aug 21 2010

## [Game Programming] Consider A Different Approach To Cards Shuffling

Very commonly, computer programs (usually games) that have the need to simulate a shuffling of a deck of cards (or drawing a tile from a bag, etc.) will go the obvious way of putting the items in an array, and then randomize the order of the elements of the array. A common algorithm for doing that is the Fisher–Yates shuffle (you can find a suitable implementation easily by googling).

The purpose of this post, however, is not to discuss “how” to shuffle arrays. Rather, I would like to bring up the question of “why” (do it) in the first place.

In the non-digital world, the shuffling of a deck of cards is mostly necessary given the circumstances – ie, for convenience. In a card game, you shuffle the deck of cards to randomize the order of the cards, and players draw from the top (or bottom) of the deck in sequence. Why do players draw from the top (or bottom) of the deck? For practical reasons, of course. Convenience.

Imagine a card game where the game designer decides that players must pick a card randomly from the deck each time they need to draw a card – the game will end up taking too long to play, drawing cards become tedious, and the game won’t be very popular.

In both methods of card drawing, the outcome is really the same – whether you (i) shuffle a deck of cards and then draw from the top of the deck sequentially, or (ii) leave a deck as it is and then randomly pick a card from the deck each time you need to draw a card, the probability of a particular card being drawn by a player is exactly the same. Let’s take a look at a deck of 52 cards. If you shuffle the deck rigorously, the chance of a card being positioned at the location it is shuffled into, and therefore being drawn at that particular position, is 1.92% (1/52).

Now, look at the other scenario. Leave the deck as it is without shuffling. When a player randomly picks a card from the deck, the probability of picking a particular card as the first card remains at 1.92% (1/52). What is the probability of a particular card to be drawn as the second card? A common misconception is that with less cards left, the probability for subsequent cards are now skewed. Not really. Let’s look at the calculations. First, for a card to be drawn as the second card, it must not be drawn as the first card – got that? The chance of that happening is 98.08% (51/52). Next, the chance of the card being drawn as the second card in the reduced deck of 51 cards is 1.96% (1/51). The composite probability is… 51/52 x 1/51 = 1/52, which is still 1.92%! You can go on to compute for the third card, which is 51/52 x 50/51 x 1/50 = 1/52, and so on.

Okay, we have established that the probability remains the same for both methods of card drawing. So what?

Well, when it comes to programming, I would debate that it is unnecessary to shuffle a deck of cards. Players no longer need the convenience here, so why not pick a card at random each time you need to draw a card? This approach has a couple of advantages:

(i) Preempt cheating by memory peeking. If you use a shuffled deck, you naturally store the sequence in memory, which means hackers can potentially look at the sequence. If you generate a random number on demand, picking a card at random each time a card is to be drawn, nobody can have fore-knowledge of what is to come.

(ii) Fast. You can jump right into a game session without expensive CPU overhead for shuffling arrays. If you have a large deck, shuffling can be inefficient no matter which algorithm you use. Instead of shuffling the deck, you just write the code to pick a card randomly from the remaining deck. Hassle in the non-digital world, fast in the digital version.

// ActionScript 3.0 function drawNext(deck:Array):* { var j:uint = deck.length; var r:uint = Math.random() * j; var c:* = deck[r]; deck.splice(r, 1); // removes item from array return c; } |

Therefore, when translating a non-digital game into a digital one, take a step back and ponder over whether it is really necessary to implement the rules literally. As long as the intended outcome (in this case the intended probability of each card being drawn at a certain position) is the same, it would probably be worthwhile exploring more efficient implementations.

on 21 Aug 2010 at 6:41 pmMakes sense, though I don’t think the overhead of the previous method is too great, but if it indeed makes things more efficient, then great.

on 22 Aug 2010 at 12:56 ama) the probability that a particular card is picked as the first card is 1/52, as second 1/51, as third 1/50 and so on, so that the probability of a particular hand is 1/52!

there are 52! permutations, not 52^52

b) you cannot rely on the Flash client if you want to avoid player cheating (Flash Media Server is a better choice for that purpose)

c) it takes less than 3/100000 of a second to shuffle an array of 52 numbers. is that slow?

on 22 Aug 2010 at 1:46 am@pantelis, did you skip the computations on the probabilities I pointed out above? you are having the same misconception as what i pointed out

not all games use decks of 52 cards, you could be using 10 decks, etc. and you could be implementing it for mobile devices.

with regards to cheating, you are missing the point about storing sequences in memory, isn’t it?

anyway, the point to my post is really to highlight that it is not always necessary to translate rules literally from the non-digital to the digital version. think about the why, then the how. think about the tiles in a scrabble game in a bag – do you not think the probabilities are the same if you were to (i) draw a tile from the bag (as per the rules) and (ii) shuffle the tiles and dispense them in sequence?

on 22 Aug 2010 at 2:52 am@sunny, if you have 2 objects there are 2 possible arrangements of them. If you have 3 there are 6 and if you have 52 there are 52! (1*2*3*…*52). So, the probability of a particular hand (consisting of 52 cards) is 1/52! According to your math the probability of a given sequence is (1/52)^52 which means that there are 52^52 possible arrangements. and that is simply wrong.

i do not know any card game that uses 10 decks, but to shuffle 520 numbers, it only takes ~24/100000 of a second. i do make card games for mobile devices, and always shuffle the array. there is no performance issue because of that.

on 22 Aug 2010 at 10:10 amPardon me for being slow… but how do you arrive at your conclusion on the number of possible outcomes for the “draw a card at random from remaining cards” method. To be very clear, there are two card drawing methods here – (i) shuffle the deck and draw from the top, and (ii) leave deck un-shuffled and draw a card at random from remaining cards (obviously, does not work in real life due to existence of visual cues and prior knowledge of deck composition).

By the way, my math showed that the probability stays the same for both methods (you probably missed the point about “remaining cards”).

on 22 Aug 2010 at 12:10 pmLovely article and funny comments:) Nothing against it, should work fine as long random is random

Now a little article about ‘reallife shuffling’:

What are the odds of shuffling a deck of cards into the right order?

It depends on how you shuffle them and the cards’ order when you start. If you truly randomise the deck, the chances of the cards ending up in perfect order – spades, then hearts, diamonds and clubs – are around 1 in 10 to the power 68 (or 1 followed by 68 zeros). That’s a huge number, roughly equal to the number of atoms in our galaxy. Yet card players report it happening. The reason is fresh packs of cards come in perfect order and if they’re not shuffled well, can end up back in order. For example, if a dealer riffle shuffles a fresh pack – splitting the deck in two and interleaving the cards together – the pack can end up back where it was after just eight shuffles. Thus, paradoxically, people who aren’t very good at shuffling can do a better job of jumbling a pack than those who are.

I think it’s time to make some tests, good luck:)

on 22 Aug 2010 at 12:18 pmSome mathematicians published a research some time ago that it will take on average 7 shuffles (by hand) to truly randomize the order of a 52 cards deck.

Ah yes, we are assuming random is random, if it is not, then both methods of card drawing still suffers from the same problem

on 22 Aug 2010 at 9:42 pm@sunny

your math is wrong. i already gave you a counter proof of that: 52 items can be arranged in 52! ways. this is a fact of life, ever since pascal, bernoulli, and poisson (and their gambling habits) have founded statistics. therefore, the probability of one particular hand (it doesn’t matter which) is 1/52! your math results in (1/52)^52. are these two numbers the same??? you don’t need a calculator to figure that out, they are light years apart. do you know of any statistics book or web page with the claim that the 52 cards can be arranged in 52^52 ways? because that’s what your math results in.

i’ll give you another proof that might help you decide where misconception is: we agree that the probability of a particular card be drawn first is 1/52. after the first card is drawn, there is no such thing as “for a card to be drawn as the second card, it must not be drawn as the first card – got that? The chance of that happening is 98.08% (51/52)”. pardon me, but, i haven’t got that. after the first card is drawn the probability of the second card not been drawn as the first card is 1 (because we are certain that the second card was not drawn first). probabilities have to do with events whose outcome is uncertain. the probability of a particular card to be drawn second is equal to 1/51, because there is only one favorable outcome (that particular card) and 51 possible outcomes, to be drawn third is 1/50 and so on. it follows then, that the probability of a particular hand of 52 cards is (1/52)*(1/51)*(1/50)*…*(1/2)*(1/1)=1/52! when 51 cards have been drawn we are certain that the 52nd card is the one that has not been drawn. no matter how you pick the cards, in statistics this is called drawing without replacement (unless you take the first card drawn and put it back in the deck, which obviously is not the case with card games). according to your logic the probability of a particular card been drawn first, second, or last is 1/52…

you still haven’t answered my question though: for the imaginary game that uses 10 decks, is ~24/100000 of a second slow?

on 23 Aug 2010 at 3:26 pm>> you still haven’t answered my question though: for the imaginary game that uses 10 decks, is ~24/100000 of a second slow?

I think his point was more theoretical in nature, that you should consider different solutions instead of just assuming 1 way is the only way.

As for your ~24/100000 estimate, it is an estimate. It is purely based on the hardware (supercomputer, desktop, laptop, smart phone, or crappy old phone/processor), OS, programming languages/compilers, etc. In the case of 52 cards you may be correct, but what about randomly choosing (and hence sorting) say, an entire phone book of 300 million people in the US to ‘win’ a prize (or be audited by the IRS)? many sorting algorithms are 0!n or worse and as the number of items increases the processing time can grow enormously (for instance, logarithmically).

Sure, in this case, 52 cards isn’t a big deal, but why ‘randomize’ say, 20k records when you can just leave them in your base data set and do a simple random selection of a record.

on 23 Aug 2010 at 9:40 pmI’ll preface this by saying that I do agree with you. However…

When shuffling a deck (or multiple decks) of cards in the “real” world (ok, so we don’t live in the Matrix), once the cards are shuffled they stay in that order until they’re dealt (or reshuffled). So randomly picking a card at deal-time does not actually maintain the “reality” of shuffling prior to dealing any cards, though it nets a similar result. Ultimately, I’d agree there’s no serious issue with this, but…it feels “righter” to me to go the pre-shuffle route.

And unless we’re talking huge arrays of data, I’d agree with the commenters that it’s not really a huge savings from a processing pov.

on 24 Aug 2010 at 2:30 am@pantelis, I am truly blown away by your circular and contradictory logic.

Consider the following scenarios:

(i) You take a fresh deck of 52 cards, shuffle it, draw 2 cards from the top of the deck and discard them. What is the chance of the next card drawn (ie 3rd card) from the top of the deck to be Ace of Spades?

(ii) You take a fresh deck of 52 cards, shuffle it, draw 1 card from the top of the deck and discard it. Shuffle the deck again, draw another card from the top of the deck and discard it. Shuffle the deck again. What is the chance of the next card drawn from the top of the deck to be Ace of Spades?

(iii) You take a fresh deck of 52 cards. Now, don’t shuffle it. Let’s ask Paul the Octopus, who is completely innocent and ignorant of the way a fresh deck of cards is prearranged, to truly randomly pick one card from the deck and discard it. Ask him/it to do it again a second time, also completely randomly without bias. What is the chance of the third card Paul picks, truly randomly without bias, from the deck of remaining cards to be Ace of Spades?

on 28 Aug 2010 at 8:08 amSeems like pantelis isn’t coming back to tell us more about statistics.

I finally got the time to draft a proper reply, which got a little too long (because short didn’t seem enough to convey the facts):

http://www.ghostwire.com/blog/archives/on-permutations-probabilities-and-psychology/

Thanks!

on 27 Sep 2010 at 7:35 pmThere is a subtlety to the argument and the probability logic – doesn’t the “prob of the second card not being drawn as the first card” depend on whether the first card has been identified? If it can be identified, the argument seems to be invalid. Either way this seems confusing. Are issues like this common in the kind of game programming you do?