4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Wouldn't it be 3n in two pass case? 2n to get through the deck, then n to get through the leftover color? $\endgroup$ – DrunkWolf Dec 28 '15 at 7:37
  • $\begingroup$ Oops, yes, of course. I'm gonna edit it. (as a proof I wasn't too far away, in the code there's the right answer two_score = N*2+N :D) $\endgroup$ – damio Dec 28 '15 at 8:13
  • 1
    $\begingroup$ why do you need 3n guesses? On the first pass, I guess black always. This gets me all the black cards, and I now know that the other pile contains all red. Go ahead and shuffle all you want, they are all red. I now guess all red and I'm done. The guesses are 2R + B. $\endgroup$ – Kate Gregory Dec 28 '15 at 16:24
  • 1
    $\begingroup$ @KateGregory and R = B = N , so 3N $\endgroup$ – DrunkWolf Dec 28 '15 at 18:24
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The bad return was a typo, sorry :D. Also, to classify a strategy better than the other, I have the metric Given any deck, what's the probability of one being better than the other. I should have clarified that. But yeah, I'm gonna explore if the cases where two_pass is better is because of a coding problem or a real worst-case. EDIT: But thanks a lot for your answer :D $\endgroup$ – damio Dec 28 '15 at 8:18
  • 1
    $\begingroup$ My point is that for a alternative sequence, the algorithm is gonna guess half the cards in the case 101010.. and all the cards in the case 01010101....I fail to see a case where it can guess no cards. $\endgroup$ – damio Dec 28 '15 at 9:51
  • 1
    $\begingroup$ oh yeah, I forgot to clarify that there's the same number of 1 and 0 in the cards. $\endgroup$ – damio Dec 28 '15 at 9:55
  • 1
    $\begingroup$ @Frenchguy edited with proof that even if both are equal, there's worst-cases where guessing loses. $\endgroup$ – DrunkWolf Dec 28 '15 at 10:09
  • 1
    $\begingroup$ ah thanks, I accepted the answer. Thanks a lot for helping me explore this problem ! $\endgroup$ – damio Dec 28 '15 at 10:23
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ nice one, that was the beginning of my reflexion for the probability based function $\endgroup$ – damio Dec 30 '15 at 23:10
2
$\begingroup$

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
$\endgroup$
  • $\begingroup$ Makes me wonder if there's a better strategy between probability_guess and two_pass... $\endgroup$ – damio Jan 8 '16 at 0:42
  • $\begingroup$ @Frenchguy I do not have any proof, but my gut feeling is that it isn't possible. Reshuffling loses information about order of cards. Unless it can be guaranteed that there is only one colour of cards left after the first reshuffle, then we risk an additional reshuffle. I believe that as N grows large, the guarantee given by two_pass (never need more than one reshuffle) is more valuable than any attempt to guess more accurately. Hence, Arth's suggestion will slightly improve two_pass (it will require ~1 move less). But other from that, I doubt it is possible to improve it for large N. $\endgroup$ – Alderath Jan 12 '16 at 9:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.