In a Guess The Color game, what's the optimal strategy?

Question

Here's a one-player card game:

1. We begin with a shuffled card deck
2. The player try to guess the color of the card at the top (black or red)
3. If the player guess right, he can keep the card. Else the card is put in another stack
4. When the stack finish, the player shuffle the non-guessed cards and go back to 2.
5. The game finish when there's no card left.

A first strategy to win would be to first ask one color until the first stack ends and then ask another color. With N, number of cards of one color. The is always gonna be 3N guesses before the end of the game.

Let's call it the two_pass strategy.

def two_pass():
    return BLACK if times_shuffled == 0 else RED

But here's another strategy:

• You can use the cards you guessed right and the cards you have seen during the game to guess the probability of how many cards of one color are left in the stack

Then you can have something like this:

def probability_guess():
    blacks_left = N - blacks_seen_but_not_taken - blacks_taken
    prob_of_getting_black = blacks_left / cards_left
    if prob_of_getting_black < 0.50:
        return RED
    else:
        return BLACK #EDITED, was 'WHITE' before

And here's the trick question: Is probability_guess better than two_pass? (will it always need less guesses than the other strategy)

EDIT: Here's some python code with a simulation of the game and the strategies: https://gist.github.com/mdamien/bb3848310965dfe91419

Answer 1

The answer is:

Two pass is better (at least in worst-case)

Because

First of all, your probability guess as stated in the question never returns Black, so it never finishes. #had an unedited version of the question open

Assuming this is a mistake probability guess still has a worst case where it never finishes. More specifically there's a $1/2^N$ chance that it finishes a single pass without 'learning' anything. It could literally guess every card wrong every single time. However, in case you have equal amounts of reds/blacks that not the case.

If the amount of red/blacks are equal

Then the best guess algorithm becomes a lot better. However it's easy to show that the worst-case is still worse.

Suppose that your algorithm guesses 0 if it has no clear indication either way, or 1 if it's seen more 0's so far.

if our code is 1001, it will guess wrong, right, wrong, right. leaving you with 10 for the next time. If this is ordered right for you (01) you will get it in 6, but if it's wrong, you will need another pass, and get it in 7. This can always happen if a pass leaves an equal amount of both red and black.

Answer 2

You could of course improve the two_pass strategy with:

if (times_shuffled || blacks_taken == N) return RED;
return BLACK;

It still has the maximum number of guesses as 3N, but will reduce the guesses in the case where a string of REDs ends the first pass.

Answer 3

Regarding worst case:

Example to demonstrate worst case:

If with N = 5, we have deck: 1010001011

We will use 10 moves making the guesses: 0000011111

After this, we have two 1:s and two 0:s left, which might shuffle into: 1010

And we use 4 moves to guess: 0000

After this, we still have two 1:s left. So we will need two more moves, totalling 16 (which is worse than 3N = 15).

The reason why probability_guess algorithm may become worse than the two_pass algorithm is becuase it might requires more than one reshuffle. The two_pass algorithm is guaranteed to never need more than one reshuffle. Already at N=3 and N=4, probability_guess algorithm may require an additional reshuffle, but in these cases, it will still not become worse than two_pass. When N=5, though, the impact of the additional required reshuffle may cause the worst case performance to become worse than two_pass, as shown above.

Regarding average case:

Interesting things happen around N = 26. For N = 26, two_pass and probability_guess have approximately equal performance in the average case. When N > 26, probability_guess algorithm will degrade in performance, becoming worse than two_pass algorithm, even in the average case.

Speculative reasoning around average case performance:

Lets compare benefits and drawbacks of probability_guess for two cases. Benefit of probability_guess is that you use available information from past observations which improves your probability to guess subsequent guesses correctly. Drawback of probability_guess is that there is a risk that you may need more than one reshuffle.

For the simplistic case N = 1: We have 50% to guess the first card correctly. For the second card, we have a 100% chance to guess it correctly. In this case, the probability_guess algorithm increased our chance to guess correctly (from 50% to 100%) for that second card (which is half of the total number of cards). Ie. the benefit is quite big.

Consider case when we let N tend towards infinity. Take N=10^9 as an example of a big N. When picking the second card, our probability to guess the second card correctly is 500,000,000 / 999,999,999 which is approximately 50%. Ie. probability_guess didn't help much in improving the probability to get it correct. The same reasoning applies for the majority of the guesses for the initial shuffle. Only when you are near the end of the deck will the probability_guess give a significant improvement to the probability to guess correctly. But "near the end of the deck" is a very small portion of the entire deck. The drawback, however, has become larger. Now we do not only risk having to reshuffle twice. We might have to reshuffle several times. The benefit does not outweigh the drawback.

As a specific example, I did one million solution attempts for N=500. Out of these, 94.7% were slower than the two-pass alogrithm. And in the worst case, 7 reshuffles were necessary.

Summary:

N < 5       : probability_guess better than two_pass in average case, and equal in worst case
5 <= N < 26 : probability_guess better than two_pass in average case, but worse in worst case
N == 26     : probability_guess roughly equal to two_pass in average case, but worse in worst case
N > 26      : probability_guess worse than two_pass in average case