Pick A Card, Any Card

This was another Riddle, posed by Ollie. The question was:

From a shuffled deck of 100 cards that are numbered 1 to 100, you are dealt 10 cards face down. You turn the cards over one by one. After each card, you must decide whether to end the game. If you end the game on the highest card in the hand you were dealt, you win; otherwise, you lose.

What is the strategy that optimizes your chances of winning? How does the strategy change as the sizes of the deck and the hand are changed?

So up to ten times you pick up a card from the deck and decide to ACCEPT or PASS it. The criteria for selection was:

1. If it is the last card you must ACCEPT it
2. If you PASSED a card larger than your current card then you must pass this (unless this violates rule #1)
3. If there is a fifty percent chance or higher that all the consecutive cards are smaller then ACCEPT the current card (unless this violates rule #2)

The equation for determining if all the consecutive cards are smaller than the current card is:

where i is the index of the card you are evaluating (the first card would be 0, the second would be 1, etc.)

The result for the 10 card hand size, 100 card deck is that you can successfully determine the card 62.2% of the time. This changes with as follows:

varying hand size:

varying deck size (no apparent change):

#!/usr/bin/python
import random
import matplotlib.pyplot as plt
import numpy

deck_size = 100
threshold = 0.5

def make_hand(hand_size):
    got_hand = False
    while not got_hand or len(hand) != len(set(hand)):
        hand = []
        for i in range(0,hand_size):
            hand.append(random.randint(1,deck_size))
        got_hand = True
    return(hand)

def run_hand(hand_size):
    hand = make_hand(hand_size)
    for i in range(0,len(hand)):
        decision = False
        skip_evaluation = False
        max_skipped_card = 0
        percent_lowest = 1
        saved_card = 0.1

        #Skip immediately if you've skipped a larger card already
        if hand[i] < max_skipped_card:
            skip_evaluation = True

        #Skip if its the last card
        if i == len(hand)-1:
            saved_card = hand[i]
            skip_evaluation = True
            
        #Evaluate the % every consecutive card is lower
        if hand[i] > len(hand)-i and not skip_evaluation:
            max_skipped_card = max(max_skipped_card,hand[i])
            for w in range(1,len(hand)-i):
                percent_lowest = percent_lowest * ((hand[i]-w-i)/(deck_size-i-w))
            if percent_lowest > threshold:
                decision = True
                saved_card = hand[i]
                break

    return saved_card == max(hand)

def run_trial(hand_size,deck_size,iterations):
    successful_trials = 0
    for i in range(0,iterations):
        successful_trials = successful_trials + run_hand(hand_size)
    return [deck_size,(successful_trials / iterations)]

results = []
for i in range(2,20):
    results.append(run_trial(10,i*10,100000))
x, y = zip(*results)
plt.plot(x,y)
plt.plot(x,y,'ko')
plt.title('Pick A Card, Any Card! With Variable Deck Size\nThreshold: 0.5, Deck Size: 100')
plt.ylabel('Correct Selection (%)')
plt.xlabel('Deck Size')
plt.ylim((0,1))
plt.show()

Advertisements