2
$\begingroup$

Rules

Basics

52 well shuffled cards are dealt equally to both players. Player 1 starts the first hand. The game consists of a number of rounds, which are played as follows. On each round, players get alternate turns. The first person to run out of cards wins immediately (this could be at any turn in any round).

Starting a round

A person starts a round by playing any number of cards face down on the table and declare what rank they are. (If it is your last card/s you must be truthful to win.) For example, one could play three cards from his deck and say that they are sevens. Then it is the other person's turn.

On each turn

If it is your turn, you may

  • Pass - Turn goes back to the other player.
  • Play - Play any number of cards on top of the same deck. You are declaring them to be of the same rank as what the round was started with. You cannot declare falsely (bluff) if these is/are your last card(s).
  • Pick - Pick up the cards that the other person played on his last turn (if he did play any). If they are true (same as what was declared at the start of the round), you keep the cards and the other player starts a new round. Otherwise, if it is a bluff, you give the cards to the other player and start a new round.

If both players pass consecutively, the cards on the table are discarded and the person who played the last card starts a new round.

Question

Is there any way to determine the probability of an optimal player winning against another optimal player (where both players know that each other are optimal)?

Even if your answer is exactly 1/2, justify it.

$\endgroup$
  • 1
    $\begingroup$ Am i getting this right that both players start with a 26 card hand? And thus have perfect information over what cards the other has? $\endgroup$ – DrunkWolf Dec 15 '15 at 11:49
  • $\begingroup$ Also, this is a bit of an immovable object vs unstoppable force type situation, because obviously an optimal player can always tell if someone is bluffing, but at the same time, his bluffs are unreadable. Furthermore, the winning condition is unclear, do you win when the last cards on the table are discarded, or when they're played and not picked up? In the former case you could have draws as well. $\endgroup$ – DrunkWolf Dec 15 '15 at 11:54
  • 5
    $\begingroup$ You can't always tell when someone is bluffing. I can know you have two sevens. When you put down two cards and say they are sevens, I don't know if they are or not. $\endgroup$ – Kate Gregory Dec 15 '15 at 12:54
  • 1
    $\begingroup$ Define "optimal". Would an optimal player have a 100% win rate at "guess how many fingers I'm holding up behind my back"? $\endgroup$ – Kevin Dec 15 '15 at 16:01
  • 3
    $\begingroup$ On the first turn, player one declares they are playing twenty-six Kings. Their hand is empty and they immediately win. I assume this isn't the intended optimal strategy, can you clarify the rules to prevent this? $\endgroup$ – Ninety-Three Dec 15 '15 at 18:12
3
$\begingroup$

Edit: I had the rules wrong, below is a correct analysis with the correct rules.

To show how complicated this game is, let's try to solve a much simpler version. Suppose instead the deck has only 4 cards, namely, two kings and two queens, but all other rules are the same. Let's call the players Alice and Bob, with Alice going first.

If Alice is dealt either two queens or two kings, she immediately wins, so assume they are each dealt a queen and a king.

Alice has only two sensible options: she should play a single card, then either tell the truth (T) or lie (L) about its identity. Bob can then either doubt Alice's claim (D), play the card which Alice claimed to play (P), play the opposite card, or pass. If he passes, he immediately loses, and it turns out that if Bob can win dishonestly, then he can also win honestly, so we only consider the first two options.

TD: Bob is wrong, so Alice gets another turn, and wins.

LP: Alice just successfully lied. Bob plays a card, but then Alice plays her other card and wins.

TP: Alice plays one card, then Bob plays a card. Alice has no choice but to pass, as does Bob. Since Bob played last, he starts the next round and wins.

LD: Alice lied, but was called out, so she picks up her card, and Alice and Bob switch roles.

Let's say that the probability of Alice winning under optimal play is $p$. We can summarize the above information in a matrix, where each entry contains the probability of Alice winning in that situation: $$ \begin{array}{c|c|c|} &P&D\\\hline T & 0&1\\\hline L & 1 & 1-p\\\hline \end{array} $$ Notice the recursion above, because in the LD case, we have the same game with the roles reversed, so Alice now wins with probability $1-p$ instead of $p$.

The only solution is to use a mixed strategy. Suppose Alice tells the truth with probability $a$. Her best strategy is to choose $a$ so that Bob's payoff is equalized. If Bob chooses $P$, his expected payout is $1-a$, and if he chooses $D$, he gets $a\cdot 1+(1-a)(1-p)=1-p+pa$. Setting these equal, we get that $$a = \tfrac{p}{1+p}$$ By symmetry, Bob will Believe with probability $ \frac{p}{1+p}$ as well.

Calculating Alice's probability of winning by summing over the four possibilities in the above matrix, then setting this equal to $p$, we get $$ p = 2(\tfrac{p}{1+p})(\tfrac{1}{1+p})\cdot 1+(\tfrac{1}{1+p})^2(1-p) $$ Amazingly, when you solve this, you get that $p$ is equal to the inverse of the Golden Ratio, i.e. $$p=\frac{\sqrt{5}-1}2\approx 61.8\%$$ is Alice's probability of winning under optimal play. To achieve this, she tells the truth about $\frac{.618}{1+.618}=38\%$ percent of the time. Bob should believe her with the same probability. Of course, this was assuming Alice was dealt a queen and a king. Overall, her probability of winning is $\frac13\cdot 1+\frac23\cdot 0.618=74.5\%$

We can perhaps guess, based on these results, that the game favors the first player, and the best strategy is to slightly lean towards deceit and doubt, but still be honest and trusting a nontrivial amount of the time.

However, you can see that the full 52 card game would be ridiculously complicated. This small game had itself as an option: imagine there were many games which mutually had each other as options. There would be a complicated web of nonlinear equations instead of a single nice one.

$\endgroup$
  • $\begingroup$ As written, the rules of the game say "If both players pass consecutively, [...] the person who played the last card starts a new round." So Alice can win for sure by telling the truth. The strategy you describe appears to be for the game where after two passes, the player who didn't play the last card starts the next round. $\endgroup$ – Julian Rosen Dec 15 '15 at 19:59
  • $\begingroup$ @JulianRosen Alice cannot win for sure by telling the truth. The other player will not always pass since he has more cards to play. $\endgroup$ – ghosts_in_the_code Dec 16 '15 at 14:46
  • $\begingroup$ I meant in the simpler game with only four cards $\endgroup$ – Julian Rosen Dec 16 '15 at 14:47
  • $\begingroup$ I don't quite follow all of your claims, such as "Her best strategy is to choose $a$ so that Bob's payoff is equalized" and "By symmetry, Bob will Believe with probability $\frac{p}{0.5+p}$ as well". $\endgroup$ – Fimpellizieri Dec 16 '15 at 20:46
  • $\begingroup$ @Fimpellizieri We know that the optimal strategies for each player (i.e. Nash equilibrium) will be mixed, since no option is always better. But, if Alice choose a strategy which did not equalize Bob's payoffs, then his best response would be to alwyas choose the option which gives the better expected payoff, which is not a mixed strategy, a contradiction. This explains more. Hard to explain in 400 characters, game theory is complicated. $\endgroup$ – Mike Earnest Dec 16 '15 at 21:08

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.