tag:blogger.com,1999:blog-6899095487697524238.post3297148594206729236..comments2014-04-14T18:17:25.382-07:00Comments on GTORangeBuilder Blog: GTO Brain Teaser #1: Exploitation and Counter-Exploitation in Rock Paper Scissorsasheivenoreply@blogger.comBlogger76125tag:blogger.com,1999:blog-6899095487697524238.post-52045447765270347182014-04-14T12:15:02.291-07:002014-04-14T12:15:02.291-07:00You are right that the nash equilibrium strategy h...You are right that the nash equilibrium strategy has him playing scissors as often as we play rock, but he can lose less than 1 quarter. If you tell me the exact strategy that you are proposing we play, I can tell you the counter strategy for him that loses less than 1/4th of the time.GTO RangeBuilderhttps://www.blogger.com/profile/01506290885754080155noreply@blogger.comtag:blogger.com,1999:blog-6899095487697524238.post-86542380533870087112014-04-14T12:09:12.266-07:002014-04-14T12:09:12.266-07:00then our strategy should be to play rock as often ...then our strategy should be to play rock as often as our opponent plays scissors and paper the rest of the time:<br />then <br />we win = r * (1 -s ) + s * s<br />tie = p * (1 - s) + r * s<br />we lose = s * (1 - s)<br /><br />because r >= 1/2 and s <= 1/2 my opponents strategy of playing scissors as often as our paper as much as possible would push him to play 1/2 scissors to counteract our strategy and losing 1/4 of the time is the best he can do.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6899095487697524238.post-55372088375867385892014-04-14T10:55:45.251-07:002014-04-14T10:55:45.251-07:00I'm not 100% sure I understand the strategy yo...I'm not 100% sure I understand the strategy you are proposing, but if you are saying we should play 50% rock, 50% paper, our opponent could always play paper when he is allowed to and effectively be playing 50% rock and 50% paper as well. We would then break even against him.GTO RangeBuilderhttps://www.blogger.com/profile/01506290885754080155noreply@blogger.comtag:blogger.com,1999:blog-6899095487697524238.post-92174179613592260252014-04-14T10:29:25.633-07:002014-04-14T10:29:25.633-07:00I don't buy any of this. Please explain where ...I don't buy any of this. Please explain where I'm wrong. <br /><br />Over time my opponent will know my strategy and I'll know his.<br /><br />My opponent would just match the scissors % to my paper %, insofar as he could. <br /><br />My paper % should always be >= 50% as that is where my advantage lies.<br /><br />Therefore my opponent can best counter that advantage by playing scissor 1/2 the time.<br /><br />My only gain then is when I play rock to counteract the scissor.<br /><br />That gives me<br />1/4 P v R = +1/4<br />1/4 P v S = -1/4<br />1/4 R v S = +1/4<br />1/4 R v R = 0<br /><br />That means I win 1/4 of the time.<br /><br />If I play 2/3 paper, I only win 1/6 of the time vs 1/2 R & 1/2 SAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-6899095487697524238.post-401700707307678632014-04-07T05:39:59.594-07:002014-04-07T05:39:59.594-07:00Repost of my first comment which failed to appear ...Repost of my first comment which failed to appear :<br /><br />Bonus :<br />The optimal strategy if my opponent is intelligent and can predict my moves as I can predict his would be for me to make a random choice (head or tails) betwwen paper and rock on the first round, and for him to do the same.<br />I would then gain 25$ on average which is what I would be willing to pay.<br />(By "on average" here I mean : a means of all possible results. I know there are only two rounds.)<br /><br />Explanation :<br />The only difficulty lies in the strategy for the first round. In the second round, my opponent will play rock if he hasn't play rock before, and a random choice of P/R/S if he has. I will play paper if he hasn't played rock before, and gain 50$, or play a random selection of P/R/S and gain 0$ on average if he has played rock before.<br /><br />There are only 9 possible games for the first round :<br />If I play R and he plays R, I will gain 0$ on average for the two rounds.<br />If I play R and he plays P, I will gain 0$ on average for the two rounds.<br />If I play R and he plays S, I will gain 1000$ for the two rounds.<br /><br />If I play P and he plays R, I will gain 50$ on average for the two rounds.<br />If I play P and he plays P, I will gain 50$ for the two rounds.<br />If I play P and he plays S, I will gain 0$ for the two rounds.<br /><br />If I play S and he plays R, I will lose 50$ on average for the two rounds.<br />If I play S and he plays P, I will gain 100$ on average for the two rounds.<br />If I play S and he plays S, I will gain 50$ on average for the two rounds.<br /><br />So if my opponent plays randomly in the first round, all options will give me the same gain on average.<br />But if I play randomly, the situation is very different for him, as he can minimize my gain to an average of zero by playing rock.<br />But of course I could predict that and play paper in the first round and gain 50$ if he has played rock.<br />Which he could then predict, and play scissors to beat me, which I could predict and play rock, which he could predict, which I could predict...<br />If I can predict his move I can counter him, and if he can predict mine he can counter me.<br />So my best choice is to be unrpedictable and that goes for him too, while I still keep in mind that playing rock first is the best strategy for him if I make a random choice between the three options.<br />So my best choice is to make a random choice between paper and rock, thus optimizing my results against rock while remaining upredictable.<br />If he can predict that, it will be best for him to avoid playing scissors, because against my rock or paper his scissors will gain me 50$ on average, instead of 25$ for his rock or paper against mine.<br /><br /><br />rickadinnoreply@blogger.comtag:blogger.com,1999:blog-6899095487697524238.post-81803129477599541512014-04-07T05:34:08.161-07:002014-04-07T05:34:08.161-07:00Follow-up to my earlier comment :
I got it wrong....Follow-up to my earlier comment : <br />I got it wrong. I can still improve my strategy and pay as much as 33.33$to play if I throw a die, and play paper if I get 1,2,3,4, and rock if I get 5 or 6. So a 2/3 chance to play paper, 1/3 chance which of course just matches the result of the first problem.<br />In that case, there is no optimal strategy for my opponent, he can play whatever he wants.<br />If I increase the odds that I play paper to more than 50%, thent it becomes interesting for him to play scissors which will give me a 0$ gain against my paper, but it is balanced by the risk he might lose 100$ if I still play rock. A 2/3 chance of paper vs 1/3 chance of rock is the equilibrium. Whatever he chooses to play then will make me gain 33.33$ on average, whether he plays scissors or not.<br />rickadinnoreply@blogger.comtag:blogger.com,1999:blog-6899095487697524238.post-64354084174164453762014-04-07T04:15:15.581-07:002014-04-07T04:15:15.581-07:00I can see that several other people have come up w...I can see that several other people have come up with this answer already but I will post my solution as well.<br /><br />The Expected Value (EV) of regular RPS is 0 for both players, using the strategy of 1/3 for each possibility. The constrained player is unable to play this strategy so EV(us) > 0.<br /><br />Because the constrained player must play rock at least 1/2 of the time, if we play scissors with P > 0, then we will lose at least 50% of the time. If the game is to have positive EV, then we should be able to do better.<br /><br />In any Nash equilibrium, neither player must be able to better by changing their strategies. After ruling out every pure strategy (which I will leave up to the reader), we can see that mixed strategies are required. In any continuous, mixed strategy equilibrium, players will be indifferent between the strategies that play that have non-zero probability (otherwise they could do better by adjusting the probabilities).<br /><br />We want to find probabilities that will make our opponent indifferent to playing paper or scissors. Therefore:<br />Payoff (opponent, scissors) = P(us, paper) - P(us, rock)<br />and Payoff (opponent, paper) = P(us, rock) - P(us, scissors)<br />are equal. But P(us, scissors) = 0, so this simplifies to:<br /><br />P(us, paper) - P(us rock) = P(us, rock) or<br />P(us, paper) = 2 * P(us rock)<br /><br />Since P(us, paper) + P(us, rock) + P(us, scissors) = 1, we get:<br />3 * P(us rock) = 1 or,<br />P(us, rock) = 1/3, and<br />P(us, paper) = 2/3.<br /><br />In an equilibrium, we must be indifferent between paper and rock. Using the same logic above, we get P(opponent, scissors) = 2/3 and P(opponent, paper) = 1/3, otherwise it would our payoff would be higher under rock or paper.<br /><br />From this we can calculate the EV of 100/6 = 16.66. Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6899095487697524238.post-58682403218540734002014-04-07T03:28:31.459-07:002014-04-07T03:28:31.459-07:00Bonus :
The optimal strategy if my opponent is int...Bonus :<br />The optimal strategy if my opponent is intelligent and can predict my moves as I can predict his would be for me to make a random choice (head or tails) betwwen paper and rock on the first round, and for him to do the same.<br />I would then gain 25$ on average which is what I would be willing to pay.<br />(By "on average" here I mean : a means of all possible results. I know there are only two rounds.)<br /><br />Explanation :<br />The only difficulty lies in the strategy for the first round. In the second round, my opponent will play rock if he hasn't play rock before, and a random choice of P/R/S if he has. I will play paper if he hasn't played rock before, and gain 50$, or play a random selection of P/R/S and gain 0$ on average if he has played rock before.<br /><br />There are only 9 possible games for the first round :<br />If I play R and he plays R, I will gain 0$ on average for the two rounds.<br />If I play R and he plays P, I will gain 0$ on average for the two rounds.<br />If I play R and he plays S, I will gain 1000$ for the two rounds.<br /><br />If I play P and he plays R, I will gain 50$ on average for the two rounds.<br />If I play P and he plays P, I will gain 50$ for the two rounds.<br />If I play P and he plays S, I will gain 0$ for the two rounds.<br /><br />If I play S and he plays R, I will lose 50$ on average for the two rounds.<br />If I play S and he plays P, I will gain 100$ on average for the two rounds.<br />If I play S and he plays S, I will gain 50$ on average for the two rounds.<br /><br />So if my opponent plays randomly in the first round, all options will give me the same gain on average.<br />But if I play randomly, the situation is very different for him, as he can minimize my gain to an average of zero by playing rock.<br />But of course I could predict that and play paper in the first round and gain 50$ if he has played rock.<br />Which he could then predict, and play scissors to beat me, which I could predict and play rock, which he could predict, which I could predict...<br />If I can predict his move I can counter him, and if he can predict mine he can counter me.<br />So my best choice is to be unrpedictable and that goes for him too, while I still keep in mind that playing rock first is the best strategy for him if I make a random choice between the three options.<br />So my best choice is to make a random choice between paper and rock, thus optimizing my results against rock while remaining upredictable.<br />If he can predict that, it will be best for him to avoid playing scissors, because against my rock or paper his scissors will gain me 50$ on average, instead of 25$ for his rock or paper against mine.<br /><br />rickadinnoreply@blogger.comtag:blogger.com,1999:blog-6899095487697524238.post-36207677438196920902014-04-06T22:14:39.488-07:002014-04-06T22:14:39.488-07:00This comment has been removed by the author.Scott Fujanhttps://www.blogger.com/profile/07814686307108533155noreply@blogger.comtag:blogger.com,1999:blog-6899095487697524238.post-71574173181673155592014-04-06T22:07:35.254-07:002014-04-06T22:07:35.254-07:00Spoiler.
The most you should be willing to pay is...Spoiler.<br /><br />The most you should be willing to pay is 100/6 = $16.66.<br /><br />I think that the equilibrium strategy is for the unconstrained player to play paper 2/3 of the time and rock 1/3 of the time. The constrained player plays scissors 2/3 and paper 1/3 of the time he gets to choose.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6899095487697524238.post-31705193214088416932014-04-06T18:26:14.110-07:002014-04-06T18:26:14.110-07:00That is entertaining, I like that a lot, thanks fo...That is entertaining, I like that a lot, thanks for sharing!GTO RangeBuilderhttps://www.blogger.com/profile/01506290885754080155noreply@blogger.comtag:blogger.com,1999:blog-6899095487697524238.post-54717199942256353892014-04-06T18:09:59.380-07:002014-04-06T18:09:59.380-07:00Your explanation was not wlog. Using your logic ch...Your explanation was not wlog. Using your logic choose paper 100%. Then wlog fix R at 100%. You win every game! Wow, Clever!<br /><br />Lets look at a better strategy against yours. Suppose your opponent chooses Scissors and Rock just as often. Then we have as the expected number of wins the following: .5(2/3 -1/6) + .5(-2/3 + 1/6) = 0 when using your strategy. You break even. If you never play scissors, this works out better. Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6899095487697524238.post-46549003166767144142014-04-06T17:40:18.368-07:002014-04-06T17:40:18.368-07:00"the probabilities of the other are 0.5+(s*0...."the probabilities of the other are 0.5+(s*0.5), 0.5*(1-r-s), 0.5*r"<br /><br />This statement is wrong, but it works out since s is 0. It should be:<br /><br />"the probabilities of the other are max[0.5, s], (1-max[0.5, s])/(1-s)*(1-r-s), (1-max[0.5, s])/(1-s)*r"Scott Fujanhttps://www.blogger.com/profile/07814686307108533155noreply@blogger.comtag:blogger.com,1999:blog-6899095487697524238.post-34528082495018590352014-04-06T15:16:20.075-07:002014-04-06T15:16:20.075-07:00Interesting problems. I suggest the following simi...Interesting problems. I suggest the following similar ones:<br />1. With 50% probability your opponent cannot throw rock. Does this give you an advantage? (No.)<br />2. In two rounds game your opponent is not allowed to throw rock in at least one of the rounds. Does this give you an advantage? (Yes) How much?<br /><br />Compare 1 and 2 and be amused.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6899095487697524238.post-79194350569567476122014-04-06T14:10:59.568-07:002014-04-06T14:10:59.568-07:00Initially, for the first few rounds I would play r...Initially, for the first few rounds I would play rock most of the time, to achieve a draw or a win over scissors which is the likely intuitive reaction to being forced to play rock. The opponent being of such intellegience, would recognise the pattern and choose paper as a strategy, at which time I would begin by using scissors. I don't know the math, but my instinct would be to go against the intuition of the opponent as much as I can to optimise my wins. At a certain point, this would begin to fail and I suspect I would start to lose two-three times in a row, at which point I would quit. Sorry, I don't have a genius IQ to offer much more.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6899095487697524238.post-10314237850161495112014-04-06T07:21:59.062-07:002014-04-06T07:21:59.062-07:00I've got the first part as far as strategy. Yo...I've got the first part as far as strategy. You should play paper 2/3 of the time and rock the rest. <br /><br />I started by ruling out cases. Since you cannot profit on S, you would never throw S. Hence, your opponent can never profit on R and will only throw it when forced to. Then it was simply a matter of finding the ratio I would throw that made opponent's choice irrelevant. <br /><br />If my math is right, you should be willing to pay up to $16.66. Unknownhttps://www.blogger.com/profile/14717865402284864435noreply@blogger.comtag:blogger.com,1999:blog-6899095487697524238.post-50806644334318498632014-04-06T07:10:42.881-07:002014-04-06T07:10:42.881-07:00Small typo in forth paragraph: "where R is an...Small typo in forth paragraph: "where R is an element of [1/2, 1] and p and s are elements of [0,1/2]"Nathan Braderhttps://www.blogger.com/profile/08981508182765366895noreply@blogger.comtag:blogger.com,1999:blog-6899095487697524238.post-91114917847392666772014-04-06T07:07:32.128-07:002014-04-06T07:07:32.128-07:00Let r, p and s be the probabilities we play rock, ...Let r, p and s be the probabilities we play rock, paper and scissors on a given game respectively. It follows that,<br /><br />r + p + s = 1<br />where r, p and s are elements of the interval [0,1]<br /><br />For our opponent we will use a similar notation, only with uppercase letters,<br /><br />R + P + S = 1<br />where R is an element of [1/2, 0] and p and s are elements of [1/2,1]<br /><br />Rearranging, we find that,<br /><br />s = 1 - r - p<br />S = 1 - R - P<br /><br />Now the expected gains, G, we get from any one game is given by,<br /><br />G = AW + 0D + (-A)L = A(W - L)<br />where A is the amount exchanged between players and W, D and L is the probability of winning, drawing and losing respectively.<br /><br />The probability of winning on single game, W, is given by the sum of the probabilities of each of the winning configurations occurring is<br /><br />W = rS + pR + sP<br /><br />Similarly the probability of losing on a game is<br /><br />L = Rs + Pr + Sp<br /><br />and so the expected gains is given by<br /><br />G = A( r - R + P - p + 3(pR - Pr) )<br /><br />Now note that our opponent must play rock at least half the time, so whenever we play scissors, at minimum we will lose half of the time and so it will never improve our gains. Therefore we should never play scissors. In the worst case scenario, our opponent is aware that we will never play scissors and that playing rock more than he has to will never improve his gains. This means<br /><br />R = 1/2<br />G = A( r + (p-1)/2 + P(1-3r) )<br /><br />Assuming the opponent is aware of this, he will do what he can to minimize G. This would mean that if (1-3r) is negative then he would maximize P (the only variable he controls). Similarly if (1-3r) is positive, he will minimize P. Finally if (1-3r) is 0, he cannot affect G.<br /><br />In all of these scenarios, if we set r = 1/3 (or at least as close as possible to it) we will maximize G. This means that we should play rock a third of the time and paper the rest of the time. Our expected gains per game is G = A/6 so if A = $100 we should only be willing to pay $16.66 or less if we wish to make any gains per game.Nathan Braderhttps://www.blogger.com/profile/08981508182765366895noreply@blogger.comtag:blogger.com,1999:blog-6899095487697524238.post-33839811962492630962014-04-06T06:56:20.700-07:002014-04-06T06:56:20.700-07:00Joel you're incorrect on this one. The problem...Joel you're incorrect on this one. The problem clearly states your opponent is a smart thinking player. If you never play scissors, you opponent will always play scissors when he has the choice and you will not profit. Therefore you *must* play scissors some percentage of the time.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6899095487697524238.post-67907985342524434972014-04-06T06:30:46.953-07:002014-04-06T06:30:46.953-07:00This is almost 100% correct, but your opponent doe...This is almost 100% correct, but your opponent does have a strategy where if you are playing 33% rock and 67% paper, you cannot increase your EV by shifting your weighting between rock and paper. To do this your opponent actually needs to play both paper and scissors a non-zero %.<br /><br />When you are playing 33% rock and 67% paper and your opponent is playing that optimal strategy your two strategies form a nash equilibrium: http://en.wikipedia.org/wiki/Nash_equilibriumGTO RangeBuilderhttps://www.blogger.com/profile/01506290885754080155noreply@blogger.comtag:blogger.com,1999:blog-6899095487697524238.post-60339179324597764232014-04-06T06:26:18.436-07:002014-04-06T06:26:18.436-07:00Good point, perhaps there is a better phrasing for...Good point, perhaps there is a better phrasing for that question. The way I stated it is somewhat standard in game theory but in every day life it raises all the concerns you mentioned.GTO RangeBuilderhttps://www.blogger.com/profile/01506290885754080155noreply@blogger.comtag:blogger.com,1999:blog-6899095487697524238.post-27855583612269139132014-04-06T06:25:21.029-07:002014-04-06T06:25:21.029-07:00Very cool!
The problem of programmatically findin...Very cool!<br /><br />The problem of programmatically finding nash equilibrium is actually a very interesting one and is something I spend a lot of my time on.<br /><br />One of the fastest and most powerful algorithms is http://en.wikipedia.org/wiki/Fictitious_play which is definitely worth reading about if you are curious.<br /><br />There are also techniques called CFRM (counter factual regret minimization) and linear programming (generally not useful in practical settings in big games.<br /><br />Glad you enjoyed the problem and thanks for posting your code, that's great!GTO RangeBuilderhttps://www.blogger.com/profile/01506290885754080155noreply@blogger.comtag:blogger.com,1999:blog-6899095487697524238.post-44447866389793512452014-04-06T04:34:09.083-07:002014-04-06T04:34:09.083-07:00I'd like to post a comment about the optimal p...I'd like to post a comment about the optimal price to pay, because it is a whole 'nother game theory question (or two or three). <br /><br />Consider: if the value of playing for $100 is $50, should you pay fifty? No, that would zero your winnings. So how many others are competing to play? if none, then you should bid a penny. If there others, then the question becomes more along the lines of, how long does a game take, and what is your time worth? What is your job satisfaction worth? Would you be willing to replace your career with RPS for the next twenty years for a ten percent raise?<br /><br />Michael Rudminhttps://www.blogger.com/profile/11447598297872228006noreply@blogger.comtag:blogger.com,1999:blog-6899095487697524238.post-76162762317093836252014-04-06T04:24:30.373-07:002014-04-06T04:24:30.373-07:00Cleaned up the code, sprinkled some comments, and ...Cleaned up the code, sprinkled some comments, and added it to a GitHub repos ( https://github.com/ttsiodras/RockPaperScissors-SlashdotPuzzle ). <br /><br />Thank you for posting this, I thoroughly enjoyed solving it! :-)ttsiodrashttp://users.softlab.ece.ntua.gr/~ttsiod/noreply@blogger.comtag:blogger.com,1999:blog-6899095487697524238.post-12752065734306083342014-04-06T03:43:27.100-07:002014-04-06T03:43:27.100-07:00I hacked a solution and a simulation of the soluti...I hacked a solution and a simulation of the solution in Python (run with Pypy for speed!) - what do you think?<br /><br />https://gist.github.com/anonymous/10004339ttsiodrashttp://users.softlab.ece.ntua.gr/~ttsiod/noreply@blogger.com