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.

4 comments:

  1. Granny Weatherwax Principle: "Million-to-one shots crop up nine times out of ten." The fact is that my own very brief experience with card activation has indeed thrown up five-card sequences of one colour, and more than once. That's in maybe half a dozen games or so. I have frequently run across extremely low-probability events in war games. In my very first WW2 'Portable Wargame' game using this system I had to cheat to break the sequence, once it got past four.

    Many years ago, I played a WW1 game in which players rolled each turn for the initiative. In this particular rule set the initiative had a large impact upon the move as the player with it got to move first, and to shoot first with results having immediate effect. Imagine if You had ten guys and I had ten guys, everyone with a 50-50 chance of scoring a hit. I shoot first, and knock over 5 guys. You have just 5 with which to shoot back. Even were you to win the initiative you would already bebind the 8-ball.

    In that game I won the initiative (a straight competitive die roll top score takes the initiative) on three of the eleven game turns that were played. Which three? The first, the third and the eleventh. The enemy won the initiative at moves 2,4,5,6,7,8,9,10. Observe the 7-turn sequence - a 1-in-64 deal bearing in mind it Could have gone the other way, but probably higher odds as the 7-long string had to begin at move 5 at the latest. Note too that the main action often doesn't begin until two ot three turns have been played.

    In your 'first approximation', I believe that one ought to start counting from the SECOND card of the same colour. The reason is that the card your draw in the first instance is going to be red or black. That is certain. So the chance that the second card will be the same is 50%; the third, 1:4; the fourth, 1:8; the fifth 1:16. One in sixteen - 6.7% - isn't that uncommon. It is immaterial which colour we're looking at; rather it is the sequence that is significant.

    Reverting to the WW1 example, the number of times a colour is drawn is also significant. This is leaving aside the possibility of strings. Consider a game of 8 turns. The probability that both sides will win the initiative 4 times each is just 70/256 ~ 27%. That means there is close to 73% chance in such a game that one side - it doesn't matter which - will win the initiative at least twice more than the other (5 or more against 3 or fewer).

    The probability that one or other side will win the initiative on at least 6 of the 8 (i.e at least 3 times the other) turns is actually greater than the probability of the 4-4 split!

    All this is probably OK if the significance of the initiative is not decisive. In that WW1 rule set it was very significant. In other rule sets it is much less so. I've known games in which getting to move twice in a row is of greater benefit than moving first or second in a bound.

    ReplyDelete
    Replies
    1. I fully agree that card activation can be a bad mechanic, if it is used in a badly designed ruleset. A game that is decisive, depending on a lucky first roll as you describe, is not a good game.

      W.r.t. computer probabilities: I computed the probability that, given a first card, the 2nd card being of a different (or same) colour. That means that once you draw the first card in a run, there is a 50% chance the run will only have a length of 1. There is of course a 100% probability every run will last at least for one card.

      I also agree there are some other effects going on. I compute run lengths, not a correlation between successive run lengths (e.g. a long run of red increases the chances of a long run for black, as long as the deck isn't reset). I could adapt my program a little bit to see what comes by omitting the Joker and let every deck of 52 cards run out before reshuffling. And then I should also make the count seperately for red and black, but I see no reason why these counts would be significantly different ...

      Delete
    2. I am inclined to abandon the card activation in favour of dice activation with some modifications. The method works for pairs of phases within a turn, or in rule sets like the Portable war game pairs of turns.

      Take the PW game. Colour roll, RED/BLACK dice, high roll wins the initiative and plays. Say RED wins. Red then rolls 1D6 for activating units (1-2 = half units minus 1; 3-4 half units; 5-6 = half units plus one). Once moves and combats completed, BLACK rolls for activating units.

      Once that turn is complete, roll once again for initiative. If BLACK wins it, he gets 2 moves in a row. Of course, that means that the next side to get two moves in a row is RED.

      In the General d'Armee rule set, the initiative rolls are heavily biased in French favour against the Austrians. Handy though that is, it doesn't mean the Austrians can't do much. In two games I have has with the rule system - Austrians both times - when I finally did win the initiative, I held it for two more turns in a row. We managed to make quite a bit of progress in that time!

      On the matter of letting the deck run, I recall a board and figure game that was card driven. In this game units were activated by cards, drawn singly from a large deck. Each card had a unit or group of units that were permitted to act. As each card was drawn - without replacement - the appropriate unit(s) did their thing. The game ended with the last card if a decisive result were not achieved sooner.

      As it happens, during play we found that one army kept winning consistently against the other. The strings of one side proved decisive. I don't thing we ever did get to the final card this way. So we tried splitting the decks and drawing in turn. This time it was the OTHER army that consistently won! I don't think the dilemma was ever satisfactorily resolved.

      Delete
    3. Is the game you are referring to the old Games Workshop game Battlemasters?

      Delete