Wednesday, December 14, 2016

Old Maid

Old Maid is a card game that consists of pairs of matching cards and one unmatched card called the “old maid”.  Although specialized Old Maid decks of cards can be used, a standard deck of playing cards can work just as well by using cards with the same type and color for the matching cards (for example, the ace of spades would match with the ace of clubs, the king of hearts would match with the king of diamonds, etc.), but discarding one card, traditionally the queen of clubs, to leave the queen of spades for the old maid.


The game begins with the dealer dealing out all the cards to each player.  Each player looks at his or her hand and discards any matches that were dealt to them.  Then starting with the player to the left of the dealer and going in a clockwise direction, the player picks a card from the hand of the player to the right of him or her.  If that card makes a match with one of the cards in the player’s hand, that match can be discarded, otherwise that card is added to the player’s hand.  Then the next player takes a turn by picking a card and either discarding the match or adding the card to his or her hand.  Gameplay continues in this fashion until all the matches our discarded, leaving the old maid.  Whoever has the old maid at the end of the game is the loser.

This game is popular among children because it is so simple.  All you have to do is pick a random card and make matches.  There’s no strategy involved, which means the outcome of every game is based solely on chance.  But a game based solely on chance can be analyzed with the laws of probabilities, which means we should be able to predict which player has an advantage of winning, whether it be the dealer or the non-dealer, and whether it be the player who starts with the old maid or the player who doesn’t start with the old maid.

Old Maid: 2 Players, 1 Card

Before answering these questions, we should first analyze the simplest version of Old Maid and work our way through versions of increasing complexity, and hope to find some general rules and patterns.  The simplest version of Old Maid is to play with 2 players and 1 card.  It’s actually not much of a game at all, but at least gives us a good starting point.  The dealer deals out the one and only card to the other player, and the other player is “left” with the old maid and automatically loses.  In this version, the dealer wins 100% of the time, and the non-dealer wins 0% of the time.  Note also that the player who starts out with the Old Maid wins 0% of the time.

Old Maid: 2 Players, 3 Cards

The next simplest version of Old Maid is with 2 players and 3 cards, where one card is the old maid and the other two cards are a match.  Let us define the old maid as the queen of spades (Q), and the match as the king of hearts (K) and the king of diamonds (K).  Now when the dealer deals out the cards, the non-dealer will receive two cards and the dealer will receive one card.  Since the dealer receives only one card, and there are three cards to choose from (Q, K, K), there are only three scenarios to consider:

1) {Q | K, K} – The dealer receives the old maid (Q), and the non-dealer receives the other two matching cards (K, K).  In this case, the non-dealer discards his or her matching pair, and the dealer is left with the old maid (Q).  The dealer wins 0% of the time, and the non-dealer wins 100% of the time.  The player who starts with the old maid (the dealer) wins 0% of the time.
                                                                                                                       
2) {K | Q, K} – The dealer receives one card of the matching pair (K), and the non-dealer receives the old maid and the other match (Q, K).  In this case, no one starts with the matching pair, so the non-dealer takes his turn picking the dealer’s card (K), makes a match (K, K), and is left with the old maid (Q).  The dealer wins 100% of the time, and the non-dealer wins 0% of the time.  The player who starts with the old maid (the non-dealer) wins 0% of the time.

3) {K | Q, K} – The dealer receives the other card of the matching pair (K), and the non-dealer receives the old maid and the other match (Q, K).  In this case, no one starts with the matching pair, so the non-dealer takes his turn picking the dealer’s card (K), makes a match (K, K), and is left with the old maid (Q).  The dealer wins 100% of the time, and the non-dealer wins 0% of the time.  The player who starts with the old maid (the non-dealer) wins 0% of the time.

In this version of Old Maid, the dealer wins 0% of the time in 1/3 of the scenarios (when he or she is dealt the old maid), but wins 100% of the time in 2/3 of the scenarios (when he or she is not dealt the old maid), and therefore overall wins 0(1/3) + 1(2/3) = 2/3 = 67% of the time, which means that the non-dealer wins 100 – 67 = 33% of the time.  The player who starts out with the old maid wins 0% of the time in all three scenarios.

Old Maid: 2 Players, 5 Cards

Things start getting a little more interesting when Old Maid is played with 2 players and 5 cards, because now the outcome is not solely based upon the hand that is dealt to the players but also upon the selections the players make during gameplay.  Let us once again define the old maid as the queen of spades (Q), but one match as the king of hearts (K) and the king of diamonds (K) and another match as the ace of hearts (A) and the ace of diamonds (A).  Here are the possible hands that can be dealt:

#
Hand
Discard Matches
Leftover
1
{K, K | Q, A, A}
{K, K | Q, A, A}
1 card
2
{A, A | Q, K, K}
{A, A | Q, K, K}
1 card
3
{Q, K | K, A, A}
{Q, K | K, A, A}
3 cards
4
{Q, K | K, A, A}
{Q, K | K, A, A}
3 cards
5
{Q, A | K, K, A}
{Q, A | K, K, A}
3 cards
6
{Q, A | K, K, A}
{Q, A | K, K, A}
3 cards
7
{K, A | Q, K, A}
{K, A | Q, K, A}
5 cards
8
{K, A | Q, K, A}
{K, A | Q, K, A}
5 cards
9
{K, A | Q, K, A}
{K, A | Q, K, A}
5 cards
10
{K, A | Q, K, A}
{K, A | Q, K, A}
5 cards

Because the non-dealer receives 3 cards out of the 5 possible, we can use mathematical combinations to and observe that there are 5C3 = 10 total hands.  To have 1 card leftover, the non-dealer must receive 1 match out of the 2 possible, which happens 2C1 = 2 times.  To have 3 cards leftover, the non-dealer must receive 1 match out of the 2 matches possible, and then either of the 2 parts of the 1 match out of the 1 leftover matches possible, which happens 2C11C1∙21 = 4 times.  To have 5 cards leftover, the non-dealer must receive either 2 parts of the 2 matches out of the 2 matches possible, which happens 2C2∙22 = 4 times.

When there is only one card leftover after the matches have been discarded, which happens 2/10 = 1/5 of the time, the probabilities are the same as the 2 player 1 card game: the dealer wins 100% of the time, the non-dealer wins 0% of the time, and whoever starts with the Old Maid wins 0% of the time.

When there are only three cards leftover after the matches have been discarded, which happens 4/10 = 2/5 of the time, the non-dealer starts out by discarding one match and then selects one of two cards from the dealer.  To analyze this situation better, let us pick one of its specific hands and follow the resulting gameplay.  Let’s say that the dealer was dealt the queen of spades (Q) and the king of hearts (K), and the non-dealer was dealt the king of diamonds (K), the ace of hearts (A), and the ace of diamonds (A) (hand {Q, K | K, A, A}).  The non-dealer starts out by discarding the matching aces (A, A) leaving the king of diamonds (K) leftover.  Now the non-dealer must select one of the two cards from the dealer (Q, K).  If the non-dealer picks the king of hearts (K), which is a ½ probability, he or she will have a match of kings (K, K) and the dealer is left with the queen of spades (Q) and loses.  However, if the non-dealer picks the queen of spades (Q), which is also a ½ probability, he or she will have the queen of spades and the king of diamonds (Q, K).  Now the dealer would have a turn, and would also have a ½ probability of picking the king of diamonds (K), making a match and winning, or a ½ probability of picking the queen of spades (Q), not making a match and continuing the game.  The game would continue on forever until one player finally does not pick the queen of spades (Q) and wins the game.

Perhaps it would be easier to represent the probability of this Old Maid scenario with a simple coin game.  In this game, you and your friend take turns flipping a coin, and whoever flips a head first wins.  (Flipping a tail would be the equivalent of choosing the queen of spades (Q) in the Old Maid equivalent.)  The first player has a ½ probability of winning on the first turn by flipping a head.  However, if the first player flips a tail, then the second player takes a turn and now has a ½ probability of winning by flipping a head, for an overall ½ ∙ ½ = ¼ probability of winning.  If the second player flips a tail, then the first player takes another turn and now has a ½ probability of winning by flipping a head, for an overall ½ ∙ ½ ∙ ½ = probability of winning.  From the first player’s perspective, the overall probability of winning is ½, then , then 1/32, and so on, which is an infinite sum where t1 = ½ and r = ¼, making the overall probability of winning S = t1/1 – r = ½/1 – ¼ = 2/3.  From the second player’s perspective, the overall probability of winning is ¼, then 1/16, then 1/64, and so on, which is an infinite sum where t1 = ¼ and r = ¼, making the overall probability of winning S = t1/1 – r = ¼/1 – ¼ = 1/3.


These are the same probabilities in the 3-card-leftover scenario of the 2 player 5 card Old Maid game: the dealer (who starts with the old maid) wins 33% of the time, and the non-dealer (who doesn’t start with the old maid) wins 67% of the time.

When no matches can be discarded, leaving all five cards leftover, which happens 4/10 = 2/5 of the time, the non-dealer starts out by selecting one of two cards from the dealer and discarding a match.  To analyze this situation better, let us once again pick one of its specific hands and follow the resulting gameplay.  Let’s say that the dealer was dealt the king of hearts (K) and the ace of diamonds (A), and the non-dealer was dealt the queen of spades (Q), the king of diamonds (K), and the ace of hearts (A) (hand {K, A | Q, K, A}), and begins by selecting the king of hearts (K) from the dealer and discarding the matching kings (K, K), leaving the dealer with the ace of diamonds (A) and the non-dealer with the queen of spades and the ace of hearts (Q, A).  Now the probabilities are the same as the 3-card-leftover scenario of the 2 player 5 card Old Maid game, except now the dealer has the advantage: the dealer (who doesn’t start  with the old maid) wins 67% of the time, and the non-dealer (who does start with the old maid) wins 33% of the time.

In this 5 card version of Old Maid, the dealer wins 100% of the time in 1/5 of the scenarios (when only one card is leftover), 33% of the time in 2/5 of the scenarios (when three cards are leftover), and 67% of the time in 2/5 of the scenarios (when all five cards are leftover), and therefore overall wins 1(1/5) + 1/3(2/5) + 2/3(2/5) = 3/5 = 60% of the time, which means the non-dealer wins 100 – 60 = 40% of the time.  The player who starts out with the Old Maid wins 0% of the time in 1/5 of the scenarios (when only one card is leftover), 33% of the time in 2/5 of the scenarios (when three cards are leftover), and 33% of the time in 2/5 of the scenarios (when all five cards are leftover), and therefore overall wins 0(1/5) + 1/3(2/5) + 1/3(2/5) = 4/15 = 27% of the time.

Old Maid: 2 Players, More Cards

The more cards there are, the more complex the probabilities get.  For the 7 card version of Old Maid, the dealer wins 0(3/35) + 1(12/35) + 1/4(12/35) + 3/4(8/35) = 3/5 = 60% of the time, and the player who starts with the Old Maid wins 0(3/35) + 0(12/35) + 1/4(12/35) + 1/4(8/35) = 1/7 = 14% of the time.  For the 9 card version of Old Maid, the dealer wins 1(6/126) + 1/3(24/126) + 2/3(48/126) + 2/5(32/126) + 3/5(16/126) = 19/35 = 54% of the time, and the player who starts with the Old Maid wins 0(6/126) + 1/3(24/126) + 1/3(48/126) + 2/5(32/126) + 2                                                                                  /5(16/126) = 12/35 = 34% of the time.  Following the pattern, we can create a piecewise function with sum notation to generalize these probabilities.  If p is the number of pairs in the deck, the probability of the dealer winning is:






and the probability of the player winning who starts with the Old Maid is:

Computer Simulation

Another way to test these conjectures and equations is to create a computer program that simulates millions of Old Maid games and keeps track of all the desired data.  The following program, written in Python, simulates a 2 Player Old Maid game for a defined number of games with a defined number of cards, and keeps track of the average amount of times the dealer wins, the average amount of times the player who starts with the old maid wins, and the average amount of times the old maid is picked per game:

01
# Old Maid Simulator
02
# Python 2.7.3
03
# After running, input the number cards in the deck and the number of games
04
#  you want to simulate.
05

06
# import python libraries
07
import random
08
import math
09

10
# the combination function
11
def nCr(n,r):
12
    f = math.factorial
13
    return f(n) / f(r) / f(n-r)
14

15
# function that calculates the expected probability of the dealer winning
16
#   using the equation
17
def DealerWinProbability(p):
18
    probdealerwin = 0
19
    if p % 2 == 0:
20
        for k in range(p / 2 + 1):
21
            probdealerwin = probdealerwin + 1.0 * (k + 1) / (2 * k + 1) * nCr(
22
                p, p / 2 - k) * nCr(p / 2 + k, 2 * k) * 2 ** (2 * k) / nCr(
23
                2 * p + 1, p + 1)
24
        for k in range(p / 2):
25
            probdealerwin = probdealerwin + 1.0 * (k + 1) / (2 * k + 3) * nCr(
26
                p, p / 2 - k) * nCr(p / 2 + k, 2 * k + 1) * 2 ** (
27
                2 * k + 1) / nCr(2 * p + 1, p + 1)
28
    else:
29
        for k in range((p - 1) / 2 + 1):
30
            probdealerwin = probdealerwin + 1.0 * k / (2 * k + 2) * nCr(p, (
31
                p - 1) / 2 - k + 1) * nCr((p - 1) / 2 + k, 2 * k) * 2 ** (
32
                2 * k) / nCr(2 * p + 1, p + 1)
33
        for k in range((p - 1) / 2 + 1):
34
            probdealerwin = probdealerwin + 1.0 * (k + 2) / (2 * k + 2) * nCr(
35
                p, (p - 1) / 2 - k) * nCr((p - 1) / 2 + k + 1, 2 * k + 1) * (
36
                2 ** (2 * k + 1)) / nCr(2 * p + 1, p + 1)
37
    return probdealerwin
38

39
# function that calculates the expected probability of a the player who
40
#   starts with the old maid winning using the equation
41
def OldMaidWinProbability(p):
42
    proboldmaidwin = 0
43
    if p % 2 == 0:
44
        for k in range(p / 2 + 1):
45
            proboldmaidwin = proboldmaidwin + 1.0 * k / (2 * k + 1) * nCr(
46
                p, p / 2 - k) * nCr(p / 2 + k, 2 * k) * 2 ** (2 * k) / nCr(
47
                2 * p + 1, p + 1)
48
        for k in range(p / 2):
49
            proboldmaidwin = proboldmaidwin + 1.0 * (k + 1) / (2 * k + 3) * (
50
                nCr(p, p / 2 - k)) * nCr(p / 2 + k, 2 * k + 1) * 2 ** (
51
                2 * k + 1) / nCr(2 * p + 1, p + 1)
52
    else:
53
        for k in range((p - 1) / 2 + 1):
54
            proboldmaidwin = proboldmaidwin + 1.0 * k / (2 * k + 2) * nCr(p, (
55
                p - 1) / 2 - k + 1) * nCr((p - 1) / 2 + k, 2 * k) * 2 ** (
56
                2 * k) / nCr(2 * p + 1, p + 1)
57
        for k in range((p - 1) / 2 + 1):
58
            proboldmaidwin = proboldmaidwin + 1.0 * k / (2 * k + 2) * nCr(p, (
59
                p - 1) / 2 - k) * nCr((p - 1) / 2 + k + 1, 2 * k + 1) * 2 ** (
60
                2 * k + 1) / nCr(2 * p + 1, p + 1)
61
    return proboldmaidwin
62

63
# function that simulates Old Maid games
64
def OldMaidSimulator(cards, games):
65
    # assign variables
66
    players = 2
67
    pairs = (cards - 1) / 2
68

69
    # create a virtual deck, where each card is labeled with a whole number
70
    # the old maid is 0, and a match is two cards that add up to the
71
    #   total number of cards
72
    deck = []
73
    for i in range(cards):
74
        deck.append(i)
75

76
    # counting variables for stats
77
    count_dealerwin = 0
78
    count_dealerstartoldmaid = 0
79
    count_dealerwinstartoldmaid = 0
80
    count_otherplayerwinstartoldmaid = 0
81
    count_oldmaidpicked = 0
82

83
    # loop through by the defined number of games
84
    for i in range(games):
85
        # new hand
86
        hand = []
87
        for j in range(players):
88
            hand.append([])
89

90
        # shuffle deck
91
        random.shuffle(deck)
92

93
        # deal cards
94
        for j in range(cards):
95
            hand[j % players].append(deck[j])
96

97
        # match pairs and remove them
98
        for j in range(players):
99
            # find matches
100
            removecard = []
101
            for k in range(len(hand[j])):
102
                if (cards - hand[j][k]) in hand[j]:
103
                    removecard.append(hand[j][k])
104

105
            # remove matches
106
            for k in range(len(removecard)):
107
                hand[j].remove(removecard[k])
108

109
        # set up variables
110
        playerpicker = 0
111
        currentcount_oldmaidpicked = count_oldmaidpicked
112
        currentcount_dealerstartoldmaid = count_dealerstartoldmaid
113
        if 0 in hand[1]:
114
            count_dealerstartoldmaid += 1
115

116
        # loop game play until only the old maid is left
117
        while len(hand[0]) + len(hand[1]) > 1:
118
            # define whose turn it is
119
            playerpicked = (playerpicker + 1) % players
120

121
            # pick a random card
122
            pickedcard = random.choice(hand[playerpicked])
123
            hand[playerpicked].remove(pickedcard)
124

125
            # if the card is the old maid (0), then keep it
126
            if pickedcard == 0:
127
                count_oldmaidpicked += 1
128
                hand[playerpicker].append(pickedcard)
129

130
            # if the card is not the maid (0), then discard it and its match
131
            else:
132
                hand[playerpicker].remove(cards - pickedcard)
133

134
            # switch players
135
            playerpicker = (playerpicker + 1) % players
136

137
        # update stats
138
        if len(hand[1]) == 0:
139
            count_dealerwin += 1
140
            if currentcount_dealerstartoldmaid != count_dealerstartoldmaid:
141
                count_dealerwinstartoldmaid += 1
142
        else:
143
            if currentcount_dealerstartoldmaid == count_dealerstartoldmaid:
144
                count_otherplayerwinstartoldmaid += 1
145

146
    # get expected probabilities based on the equation
147
    probdealerwin = DealerWinProbability(pairs)
148
    proboldmaidwin = OldMaidWinProbability(pairs)
149

150
    # print final stats
151
    print "For a 2 Player, " + str(
152
        cards) + " card game of Old Maid, simulated " + str(games) + " times:"
153
    print "  The dealer won " + str(round(
154
        100.0 * count_dealerwin / games, 1)) + "% of the games played. " + str(
155
        "(Exp: ") + str(round(100.0 * probdealerwin, 1)) + "%)"
156
    print "  The player who started with the old maid won " + str(round(
157
        count_otherplayerwinstartoldmaid)) / (games), 1)) + (
158
        "% of the time. (Exp: ") + str(round(100.0 * proboldmaidwin, 1)) + "%)"
159
    print "  The old maid was picked an average of " + str(round(
160
        1.0 * count_oldmaidpicked / games, 2)) + " times per game."
161

162
# Get user input values of the number of cards in the deck and the number of
163
while True:
164
    # get the user input value of the number of cards in the deck
165
    while True:
166
        try:
167
            cards = int(input("Please enter the number of cards in the " + (
168
                "deck (must be an odd number): ")))
169
        except NameError:
170
            print "You must enter an odd number."
171
            continue
172
        except SyntaxError:
173
            print "You must enter an odd number."
174
            continue
175
        else:
176
            if cards % 2 == 1:
177
                break
178
            else:
179
                print "You must enter an odd number."
180

181
    # get the user input value of the number of games to simulate
182
    while True:
183
        try:
184
            games = int(input("Please enter the number of games " + (
185
                "to simulate: ")))
186
        except NameError:
187
            print "You must enter a number."
188
            continue
189
        except SyntaxError:
190
            print "You must enter a number."
191
            continue
192
        else:
193
            break
194

195
    # run the simulation
196
    print ""
197
    OldMaidSimulator(cards, games)
198
    print ""
199
    print ""

For example, simulating a 5 card game 1,000,000 times results in the following:

>> 
Please enter the number of cards in the deck (must be an odd number): 5
Please enter the number of games to simulate: 1000000

For a 2 Player, 5 card game of Old Maid, simulated 1000000 times:
  The dealer won 60.0% of the games played. (Exp: 60.0%)
  The player who started with the old maid won 26.8% of the time. (Exp: 26.7%)
  The old maid was picked an average of 0.8 times per game.

The higher the number of games that are simulated, the closer the simulated probabilities are to the expected probabilities, which shows that the complex probability equations are indeed accurate.

Summary

The following is a summary of the expected probabilities for the dealer winning (and for the player who starts with the old maid winning) a 2 Player Old Maid game for a deck of 1 card to a deck of 51 cards (which is the number of cards for Old Maid on a standard deck of playing cards):

cards
pairs
dealer
wins
old maid wins

cards
pairs
dealer
wins
old maid wins
1
0
100.0%
0.0%

3
1
66.7%
0.0%
5
2
60.0%
26.7%

7
3
60.0%
14.3%
9
4
54.3%
34.3%

11
5
55.8%
23.2%
13
6
52.4%
38.1%

15
7
53.7%
28.8%
17
8
51.5%
40.4%

19
9
52.5%
32.5%
21
10
51.0%
42.0%

23
11
51.8%
35.1%
25
12
50.8%
43.1%

27
13
51.3%
37.1%
29
14
50.6%
43.9%

31
15
51.0%
38.5%
33
16
50.5%
44.6%

35
17
50.8%
39.7%
37
18
50.4%
45.1%

39
19
50.7%
40.7%
41
20
50.3%
45.5%

43
21
50.6%
41.5%
45
22
50.3%
45.9%

47
23
50.5%
42.1%
49
24
50.2%
46.2%

51
25
50.4%
42.7%

Analyzing the table we can see several patterns.  First of all, the dealer is always more likely to win than the non-dealer.  Secondly, the player who starts with the old maid is always more likely to lose than the player who does not start with the old maid.  Third, as the number of cards increases, the likelihood of the dealer winning (mostly) decreases, and the likelihood of the player who starts with the old maid winning (mostly) increases, and both percentages approach a limit of 50%. 

The most unexpected part of all this is that these probabilities are only continuous if the data is split between even and odd matching pairs (as presented in the table).  If you consider a deck with 4, 5, and 6 matching pairs (9, 11, and 13 cards), we might expect the dealer percentages to continually decrease, but in fact they do not, as the respective percentages are 54.3%, 55.8%, and 52.4%.  The probabilities only continuous decrease if you separate the data between even and odd matching pairs, for example a deck with 4, 6, and 8 matching pairs (9, 13, and 17 cards) do have decreasing percentages 54.3%, 52.4%, and 51.5%.  This means that the dealer has a slight advantage if there is an odd number of matching pairs as opposed to an even number.

So if you’re playing Old Maid with a friend and you want to stack the probabilities in your favor, make sure you’re the dealer, play with as little the number of cards as you dare, and try to make sure you have an odd number of matching pairs.  But most importantly, don’t forget to have fun – it is a game, after all.


No comments:

Post a Comment