Sunday, February 04, 2018

Drawing cards from a deck

Drawing cards from a deck is a popular mechanic for unit activation in wargames. In its most simple form, a standard card deck is used. Whenever a red card is drawn, a "red" unit can be activated, and if a black card is drawn, a "black" unit is activated. Variations on this procedure are straightforward: keeping a number of cards in hand and selecting one; cards that can activate groups of units; cards that stipulate specific actions (firing, movement); etc.

When such a mechanic is discussed, invariably the argument is used that it is possible "... to draw 5 red cards in a row, while the opponent cannot do a single thing! Thus, this mechanic is flawed! I hate card activations!"

But is this really so? Let's look in some detail at the probabilities involved in drawing cards and try to find out what is the typical length of a run of cards all of the same colour?


A first approximation ...

First, some basic assumptions:
  • We use a single deck of standard playing cards: 26 red cards, 26 black cards.
  • We will simply look at the colour of the cards being drawn (red or black), and not the suit (diamonds, hearts, clubs, spades).
  • We use a discard deck, i.e. drawn cards do not go immediately back into the pool. 
  • We call a sequence of drawn cards, all of the same colour, a run of cards.
Let's simplify our problem, and assume we have a 50% probability of drawing a red card, and 50% probability of drawing a black card whenever we draw a card from the deck. I know this is not correct, because the more red cards we draw, the less red cards remain in the deck, but as I said, we will keep it simple ...

The first card we draw is either red or black. Let us assume the colour is red. But what is the probability the 2nd card is also red? It's rather obvious that in 50% cases the card will be red, and in 50% of the cases, the card will be black.
Thus, we have 2 situations:
  • 1st card is red, 2nd card is black: 50% probability
  • 1st card is red, 2nd card is also red: 50% probability 
The first case stops the run of red cards. So, we can already conclude that there is a 50% probability that a run of cards of the same colour only lasts for 1 card. In 50% of the cases, we will have at least 2 cards of the same colour, but maybe there are more?
By using the same reasoning, we can extend the 2nd case:
  • 1st card is red, 2nd card is black: 50% probability
  • 1st card is red, 2nd card is also red: 50% probability 
    • ... and the third card is black: again 50%, so a cumulative probability of 25%
    • ... and the third card is red: again 50%, so a cumulative probability of 25%
And we can extend this even further:
  • 1st card is red, 2nd card is black: 50% probability
  • 1st card is red, 2nd card is also red:
    • ... and the third card is black: 25%
    • ... and the third card is red:
      • ... and the fourth card is black:  12.5%
      • ... and the fourth card is red: 12.5%
        • ...
So, we see a pattern here. The probability of drawing N red cards in a row, followed by a black card, equals 1/2 to the power of N. Thus:
  • drawing 1 red card, followed by a black one: 0.5^1 = 0.5 = 50%
  • drawing 2 red cards, followed by a black one: 0.5^2 = 0.25 = 25%
  • drawing 3 red cards, followed by a black one: 0.5^3 = 0.125 = 12.5%
  • drawing 4 red cards, followed by a black one: 0.5^4 = 0.0625 = 6.3%
  • drawing 5 red cards, followed by a black one: 0.5^5 = 0.03125 = 3.1%
  • drawing 6 red cards, followed by a black one: 0.5^6 = 0.015625 = 1.6%
  • ...
Note that the probability is exactly halved for adding an additional card to the run.

For the expected length of a run of cards, we add all the various lengths, weighted by their respective probabilities:

1*0.5 + 2*0.25 + 3*0.125 + 4*0.0625 + 5*0.03125 + 6*0.015625= 1.875.

However, we should also add the terms for even longer runs. This comes down to the sum of all terms N/(2^N), for N ranging from 1 to 26. Mathematics learns us that this sum eventually reaches the value 2 when N goes to infinity, which is a reasonable approximation in our case, since the terms for larger values of N are very, very small. Hence, we can say the expected length of a run of cards of the same colour equals 2.

But, we approximated the probabilities for drawing a red or black card. So let's look at the same problem in a more accurate manner.

A second approximation ...

Above we assumed the probability of drawing either a red of black card was always 50%. However, this is an upper bound for drawing red cards, since there are fewer red cards left in the deck. On the other hand, the probability for drawing black cards will increase slightly, because there will be relatively more black cards remaining after first drawing one or more red cards. In principle, we also would have to take into account how many red and black cards have been drawn so far (in all previous runs), but let's assume we start with a fresh deck, consisting of 26 red and 26 black cards.

When our first card is a red card, we have a deck left of 51 cards, with 26 black and 25 red cards. Thus, there is a 26/51 probability of drawing a black card as the next card, and a 25/51 probability of drawing a red card. Next, we have 50 cards still in the deck, and again, we can express the probabilities of drawing a red or black card by comparing the red or black cards left in the deck to the total cards remaining. By calculating cumulative probabilities for drawing red or black cards from the remaining deck after having drawn a red card first, we have the following series of outcomes:
  • drawing 1 red card, followed by a black one: 26/51 = 0.5098 = 50.98%
  • drawing 2 red cards, followed by a black one: 25/51 * 26/50 = 0.2549 = 25.49%
  • drawing 3 red cards, followed by a black one: 25/51 * 24/50 * 26/49 = 0.1248 = 12.48%
  • drawing 4 red cards, followed by a black one: 25/51 * 24/50 * 23/49 * 26/48 = 0.0598 = 5.98%
  • drawing 5 red cards, followed by a black one: 25/51 * 24/50 * 23/49 * 22/48 * 26/47 = 0.0280 = 2.80%
  • drawing 6 red cards, followed by a black one: 25/51 * 24/50 * 23/49 * 22/48 * 21/47 * 26/46 = 0.0127 = 1.27%
  • ...
So you see that the results are not that far off from the first approximation - extending the run by one card roughly halves the probability. The difference becomes more noticeable when calculating the probabilities for longer card runs, but those probabilities are so small anyway they are of little or no concern when actually playing a game.

We could also compute the expected length of a run using these adjusted probabilities for the first 6 terms:

1*0.5098 + 2*0.2549 + 3*0.1248 + 4*0.0598 + 5*0.0280 + 6*0.0127 = 1.8494

So, our average card run is a little bit less compared to the earlier calculation, but not by that much.

In practice ...

In practice, drawing a black card after a run of red cards means the start of a new run for the other player. Also, the deck has a "memory", which we did not take into account so far. A long run of red cards increases the probability of a long run of black cards, as long as we do not reset the deck. So, there are some correlated effects taking place. Could we calculate such probabilities? This becomes a much more difficult exercise, but we could simulate it.

Let's try a little experiment. I took a card deck, shuffled the cards thoroughly, and went through the entire deck 12 times, writing down the length of card runs for both colours. Below you see my tallied results, along with the relative frequencies.


Length of run
Counted runs
Relative frequencies
1
113
48%
2
53
23%
3
29
12%
4
15
6%
5
9
4%
6
5
2%
7
6
3%
8
2
1%
9
2
1%
10
0
0%

I counted a total of 234 runs, with an average length of 2.21. You can see that the relative frequencies pretty much follow the previously computed pattern - roughly halving the probability for each additional card in the run. Of course, with such a low number of runs, you always see discrepancies, especially in the lower frequencies. And there's also another problem. I counted the last run in the deck by itself, not continuing the run over a reshuffled deck. This should favour shorter runs just a little bit more.

Let's simulate some more ...

Many rulesets that use a card drawing mechanism often have a "Joker" card. Whenever this card is drawn, the entire deck is reshuffled. This has the effect that the deck is reset, and so we start again with a no-memory deck of 26 cards for each colour, closely approximating the probabilities derived before. Moreover, it handles the ending of one deck and starting a new one rather elegantly.


I didn't try to compute probabilities for including a Joker card, but I wrote a little computer program in Python that simulates exactly this. The program simulated the drawing of cards, including a Joker, and counted how long each run was. I counted runs that extended over the Joker - thus 2 red cards that showed up before the Joker, together with 2 cards after the reshuffling -  as a run of 4 cards.

It took me a short while to write such a program, and I let the simulation run till I reached a total of 100 million runs. After all, the deck never runs out of cards, since the Joker will turn up eventually. Below you see the results.



Length of run
Counted runs
Relative frequencies
1
50035520
50%
2
25490112
25%
3
12728374
13%
4
6220250
6%
5
2978897
3%
6
1398615
1.4%
7
640678
0.6%
8
287923
0.3%
9
126047
0.1%
10
54784
0.05%
11
22918
0.02%
12
9483
0.01%
13
3823
0%
14
1585
0%
15
621
0%
16
220
0%
17
90
0%
18
38
0%
19
10
0%
20
7
0%
21
1
0%
22
3
0%


As you see, the overall trend is again noticeable: runs with a length of 1 occur roughly 50% of the time, and adding a card to the run length means halving the probability. The average run length is 1.96, again very close to 2.

Since so many runs were simulated, it is no surprise that extremely-low-probability run lengths such as 21 or 22 also occurred a few times.

How to use in wargaming?

As I have said various times before on this blog, a specific rule mechanic doesn't mean much if you do not embed it in a wider ruleset.

Personally, I do like card-based activation mechanisms instead of a more classic IGO-UGO turn sequence. I think it adds some unpredictability, and keeps players involved. Also, it forces you to think a bit more about what the most important action is you want to do right now. On the other hand, I realize it's a more difficult to coordinate actions between different units.

But at least the statistics above show that on average, we can expect card runs that have a length of 2, and that 50% of the runs only consist of 1 card. So, if you do not like card-based activation, never again use the argument that card-based activation is a bad mechanic because runs of 10 cards show up all the time. Find some other argument instead! :-)

Addendum (August 2018)

I ran some more simulations, using smaller decks of cards. The results above use a deck of 52 cards. That means that the "memory" of the deck, once a few cards are drawn, is not that significant. But if you use a smaller deck, drawing a red card can significantly alter the probabilities of drawing either a red or black cards as the next card.

In the table below, you see simulation results using decks of respectively 2, 5, 13, 26, 52 and 100 cards for each colour, along with a single joker card. The simulation ran until 100 million runs were counted for each situation. Only the relative frequencies are given.


Run Length
2R 2B 1J
5R 5B 1J
13R 13B 1J
26R 26B 1J
100R 100B 1J
1
54.169254
50.8453
50.14161
50.03552
50.01213
2
31.074643
27.62782
25.98496
25.49011
25.12289
3
10.308592
13.20506
12.91458
12.72837
12.56171
4
3.276445
5.446757
6.144677
6.22025
6.24422
5
0.839346
1.924615
2.787807
2.978897
3.08893
6
0.241495
0.627716
1.207153
1.398615
1.521995
7
0.065005
0.219173
0.50101
0.640678
0.744987
8
0.018477
0.07116
0.197757
0.287923
0.363415
9
0.004876
0.022266
0.075606
0.126047
0.17653
10
0.001347
0.006872
0.028315
0.054784
0.085345
11
0.000373
0.002212
0.010366
0.022918
0.040829
12
0.000112
0.000707
0.003833
0.009483
0.01964
13
2.30E-05
0.000226
0.001446
0.003823
0.009206
14
6.00E-06
6.90E-05
0.000548
0.001585
0.004322
15
4.00E-06
3.10E-05
0.000209
0.000621
0.002023
16
1.00E-06
1.40E-05
7.90E-05
0.00022
0.000929
17

3.00E-06
2.90E-05
9.00E-05
0.000445
18


1.20E-05
3.80E-05
0.000237
19


4.00E-06
1.00E-05
0.000107
20


1.00E-06
7.00E-06
5.60E-05
21


1.00E-06
1.00E-06
2.60E-05
22



3.00E-06
1.50E-05
23




3.00E-06
24




3.00E-06
25




3.00E-06
26




1.00E-06






Average run length
1.66661907
1.83302574
1.928604
1.962917
1.989873


As you can see, the pattern follows very closely our findings above. You notice that very small decks (2 cards, 5 cards), shorter runs are relatively more common, but again, this is to be expected. Even for very small card decks (2 cards for each colour), the expected length of a run is still 1.66, and this goes gradually up to 2 when you use larger sets of cards.