- One game of ETDRPS consists of two simultaneous Rock Paper Scissors games. One game is played between Alice's right hand and Bob's left hand. The other game is played between Alice's left hand and Bob's right hand. These two games are won/lost/tied separately.
- Bob wins ETDRPS only if he wins more Rock Paper Scissors games than Alice does. If each player wins one game, or if both games tie, then Alice wins ETDRPS.
- Alice may not use paper.
This puzzle was "borrowed" from the Caltech Harvey Mudd Competition, which is supposed to be high school level. If you ask me, most of them are exceedingly difficult, but this one isn't too bad.
See the solution
18 comments:
High school level! Finally, one I can attempt.
Right, so Bob needs to win both games. He needs a foolproof strategy. Since Alice can't use paper, he can use rock and never get defeated. However, if a draw counts as a defeat, Alice will predict this, and use rock, to draw with him. So, in anticipation, he can use paper. Anticipating that he will anticipate this, she could use scissors. Then he, knowing that's the sensible thing for her to do, would use rock. Then she can't use paper, so she just has to stick to rock, to draw with him. And now we're back where we were, where she's using rock in anticipation of him using rock, so he can use paper...
In short, I really suck at this.
Interesting. Intuitively, I thought that Alice would have an advantage since she only loses if she loses both games. This is certainly the case where each is free to choose whichever of the 3 options - Bob will only win 1/3 of the time (since he also loses if it's a tie).
The restriction changes things. Since Alice can't use paper, Bob is effectively prevented from using scissors. Superficially, Bob's best strategy is to play two rocks since he'll win if Alice plays any scissors (75% of the time if Alice plays randomly). However, Alice will know this (or at least learn it after playing a couple of games) and can just also play two rocks to win. But...
Alice can't play this every game as Bob just needs to play one paper to win.
If Alice plays 1 rock and 1 scissors, she will always win if Bob plays paper to her scissors and lose if he plays rock. What Bob plays to her rock is irrelevant.
Ultimately, it all balances out. If Alice plays two scissors (say) 90% of the time (since that will win 75% of the time against a random Bob), Bob just plays two rocks 90% of the time. Alice could then counteract this by also playing two rocks 90% of the time but, since any change by Alice from mostly scissors to mostly rocks, will have the effect of slowly increasing the percentage of rocks played by her from the initial 10% (or whatever), with Bob's rocks percentage similarly decreasing, they will both end up around 50%.
So each should choose randomly and will have an equal chance of winning.
What says a simulation on computer with both playing randomly?
When you say "play randomly", what probability is assigned to each move?
Even probabilities, 1/9 for Bob's 9 possibilities, 1/4 for Alice's 4 possibilities.
That couldn't be the winning strategy, because Bob could improve his chances by always playing rock rock.
Alice randomly plays RR half the time and SS half the time;
Bob plays RR half the time and PP half the time.
Both players break even in the long run, even if the other changes his or her strategy.
Thanks to Secret Squïrrel for noting that Bob can't effectively use scissors.
Alternatively, I think they could also play RS/SR (Alice) and RP/PR (Bob) 50%/50% for the same result.
Alternatively, I think they could also play RS/SR (Alice) and RP/PR (Bob) 50%/50% for the same result.
Sorry, the alternative doesn't work.
Barefoot Bum, your solution is correct! Congratulations!
<bows>
Half the work was making sure the payoff matrix was correct.
Well, I've thought about what everyone has written and I disagree.
If Alice plays RR and SS 50/50, what's to stop Bob occasionally playing PR or RP? He will always win when Alice plays RR and always lose when she plays SS, so his overall return will still be a win half of the time.
If Alice decides to try and capitalise on this by playing SS more often, Bob responds by playing RR more often, which would then encourage Alice to play more RR (and less SS).
In the long run we might expect that an equilibrium will be reached. However, to presume that (in this case) Bob's best strategy is to pick some rigid percentage probability for each of his choices and then stick with that for ever, is to ignore the fact that he can improve his chances by being "ahead of the game" (or, at least ahead of Alice).
In other words, he throws some PR/RP out there and, as soon as he detects Alice favouring SS, he increases the frequency of RR. When Alice starts to favour RR he bumps the occurrence of PP/PR/RP, and so on.
Now, all of the above applies equally well to Alice:
she can decide to play the occasional RS or SR and her overall chance of winning will remain 50%, even if Bob is similarly using PR/RP.
Each player can try to outfox the other by "being ahead of the game", and detecting and responding to the other's change of strategy earlier than they do.
So, assuming that Alice and Bob are equal to each other, we would expect that they will each win 50% of the time, but I don't see that they are necessarily forced to only choose from plays where both hands are the same.
I'm happy for someone to show me if there is an error in my thinking.
Your scenario is:
Definition: Optimal play consists of Alice playing RR/SS and Bob playing RR/PP. Any other probability distribution of plays is by definition suboptimal.
Lemma: From the payoff matrix, we can conclude that for all suboptimal strategies, if one player adopts a consistent suboptimal strategy, the other can adoption a consistent suboptimal strategy that will result in an improved outcome.
1. Bob plays suboptimal strategy A to tempt Alice to play suboptimal strategy B, which would improve Alice's outcome.
2. When Bob detects that Alice is playing suboptimal strategy B, Bob adopts suboptimal strategy C which would improve his own outcome vs. B.
The problem is that Bob can confidently switch to C only after he has actually fallen behind by playing A. If Alice is sufficiently dynamic to adopt B in response to A, then she is sufficiently dynamic to adopt D in response to C. Therefore, the best that Bob can do is use C to recoup his losses from playing A.
To a certain extent, your assertion is correct: there are more complicated strategies that achieve the same outcome as the boring A:RR/SS B:RR/PP strategy. But you can't do better than the optimum.
All more complicated strategies entail at least an initial loss. If the game has a finite number of rounds, even if the number of rounds is unknown, all more complicated strategies have a worse outcome: Bob could use suboptimal play to tempt Alice to the countering suboptimal play, and the game could end before he could recoup his losses.
If the game has a finite number of rounds, even if the number of rounds is unknown, all more complicated strategies have a worse outcome over the distribution of games with different numbers of rounds.
Uh, yeah, what Barefoot Bum said.
I'm using a particular definition of "optimal strategy". The optimal strategy of player A is that which maximizes A's chance of winning given that player B knows A's strategy, and plays the best strategy to counter it.
Really, you could make the same argument for many simple games. Let's say that we play tic-tac-toe, and it soon becomes clear that I will only let you win a game if you leave a winning move open for me first. Then shouldn't you respond by leaving me a winning move every game?
Thanks to both of you - think I've got it now that I understand that the players each have full knowledge of the other's strategy, before they play.
To paraphrase - if Bob were intending to slip the occasional PR/RP in, then Alice will simply play SS a little more often. Of course, since Bob knows this beforehand, they could go back and forth, counteracting each other until one realises that by simply sticking with plays where both hands are the same, they will have an unassailable strategy.
Post a Comment