A Rock Paper Scissors Brainteaser

New submitter arsheive (609065) writes with a link to this interesting RPS brainteaser: "How do you play against an opponent who _must_ throw Rock 50% of the time, and how much would you be willing to pay to play against them?"

Comments

put a spin on it

[ihtoit]

Rock, paper, scissors, lizard, Spock!

Scissors cut paper
Paper covers rock
Rock crushes lizard
Lizard poisons Spock
Spock smashes scissors
Scissors decapitate lizard
Lizard eats paper
Paper disproves Spock
Spock vaporizes rock
Rock crushes scissors

Programming Course Topic

[NeuroBoy]

I've been having students in my introductory programming courses work on this class of problem for a few years.. They all seem to really enjoy it. I code up bots to play RPS with certain biases just like the OP and they have to program a single player that identifies the bias in an opponent and adjusts its play to give it an advantage. They all routinely can generate solutions that perform far better than random against predictable, dumb bots, but things get very interesting when I throw the students' bots against each other in a throwdown tournament. :)

Re:100% paper

[BlackPignouf]

From TFA: "At the start of each round an independent judge flips a fair coin and tells your opponent the result but does not tell you. If the coin came up heads your opponent must play rock."
The opponent isn't forced to get at least 50% rock after any number of plays.

Re:Simple.... Odds are even

[narcc]

Actually now that I think about it more

... you realize that you're doing the submitter's homework?

Two Games

[inhuman_4]

You should play paper 4/6 of the time, rock 1/6, and scissors 1/6 of the time.

The key (if you RFTA) is that whether or not your opponent plays rock is determined by a coin toss. So really you are playing a compound game. You are playing a coin toss and rock paper scissors (RPS). Since the coin toss determines your opponents move, you can think of it as playing 50% coin toss and 50% RPS. The RPS is a subgame of the coin toss.

Since the coin toss is the dominate game, you play with win that first. But instead of heads/tails, it is paper/other. The answer to the coin toss is a 50/50 guess of heads/tails, so the answer to the paper/other is 50% paper, 50% other.

The "other" is the RPS game. And since the answer to the RPS game is 1/3 rock, 1/3 paper, 1/3 scissors, we know what the solution to the other 50% of the game is.

So the equations are:choice = (Coin Toss) + (RPS) so: paper = 1/2 + 1/3, rock = 0 + 1/3, scissors = 0 + 1/3. Or paper = 4/6, rock = 1/6, scissors = 1/6.

No actual advantage?

[MtHuurne]

First, make sure you read TFA, since it explains what the summary doesn't: how the 50% is determined and how the opponent can play in the non-forced turns.

If you play using a deterministic algorithm, for example always play paper, the opponent can figure it out and beat you on all the non-forced turns. At best you'll get an even result.

If you play using a random algorithm, the opponent can figure out the frequencies you're using and compensate for that. For example, if you decide to play paper 50% of the time and rock and scissors 25% of the time, you'd win against an opponent playing rock 50% of the time and paper and scissors 25% of the time. However, if the opponent decides to play rock 50% of the time and scissors the other 50%, the result is even again. If the opponent would be forced to play rock more than 50% of the time, there is no room to compensate and you would win consistently with 100% paper. I think that with 50% rock, there is enough room to respond to any frequency distribution you can come up with, although I have no proof for that.

You could change your algorithms during play, but if there isn't any algorithm that results in an advantage when playing it consistently, gaining an advantage from changing your algorithm would depend on how well your opponent responds to your changes. In other words, you're playing mind games. I don't think the 50% rock restriction is going to be of any help here.

Re:Simple.... Odds are even

[Tom]

...but...but... but it's interesting homework! :-)

Re:Simple.... Odds are even

[ShanghaiBill]

The Nash Equilibrium is for you to play paper 2/3rds of the time, and rock 1/3rd. His best counter strategy is to play rock 50% (he cannot go lower) and scissors 50%. He cannot do better. If you deviate from 2/3 paper and 1/3 rock, he can adjust his strategy to do better. With the optimal strategy, you will win 1/2, lose 1/3, and tie 1/6.

Here is my search for the Nash Equilibrium:

#include

struct rps {
    double rock;
    double paper;
    double scissors;
};

static double
eval(struct rps *a, struct rps *b)
{
    return
        (a->rock * (b->scissors - b->paper)) +
        (a->paper * (b->rock - b->scissors)) +
        (a->scissors * (b->paper - b->rock));
}

int
main(void)
{
    struct rps you;
    struct rps him;

    him.rock = 0.5;
    double worst_best_eval_for_him = 1.0;
    double best_rock_for_you = 0;
    double best_paper_for_you = 0;
    double worst_best_paper_for_him = 0;
    double dx = 0.001;
    for (you.rock = 0; you.rock best_eval_for_him) {
                    best_eval_for_him = p;
                    best_paper_for_him = him.paper;
                }
            }
            if (worst_best_eval_for_him > best_eval_for_him) {
                worst_best_eval_for_him = best_eval_for_him;
                best_rock_for_you = you.rock;
                best_paper_for_you = you.paper;
                worst_best_paper_for_him = best_paper_for_him;
            }
        }
    }
    printf("worst_best_eval_for_him = %f\n", worst_best_eval_for_him);
    printf("best_rock_for_you = %f\n", best_rock_for_you);
    printf("best_paper_for_you = %f\n", best_paper_for_you);
    printf("worst_best_paper_for_him = %f\n", worst_best_paper_for_him);
    return 0;
}

Re:Simple.... Odds are even

[ShanghaiBill]

Sorry, but Slashdot mangled that code badly because of the angle brackets.

Let me try again:

#include <stdio.h>

struct rps {
    double rock;
    double paper;
    double scissors;
};

static double
eval(struct rps *a, struct rps *b)
{
    return
        (a->rock * (b->scissors - b->paper)) +
        (a->paper * (b->rock - b->scissors)) +
        (a->scissors * (b->paper - b->rock));
}

int
main(void)
{
    struct rps you;
    struct rps him;

    him.rock = 0.5;
    double worst_best_eval_for_him = 1.0;
    double best_rock_for_you = 0;
    double best_paper_for_you = 0;
    double worst_best_paper_for_him = 0;
    double dx = 0.001;
    for (you.rock = 0; you.rock < 1.0; you.rock += dx) {
        for (you.paper= 0; (you.paper + you.rock) < 1.0; you.paper+= dx) {
            you.scissors = 1.0 - you.rock - you.paper;
            double best_paper_for_him = 0.0;
            double best_eval_for_him = -1.0;
            for (him.paper = 0; him.paper < 0.5; him.paper += dx) {
                him.scissors = 1.0 - him.rock - him.paper;
                double p = eval(&him, &you);
                if (p > best_eval_for_him) {
                    best_eval_for_him = p;
                    best_paper_for_him = him.paper;
                }
            }
            if (worst_best_eval_for_him > best_eval_for_him) {
                worst_best_eval_for_him = best_eval_for_him;
                best_rock_for_you = you.rock;
                best_paper_for_you = you.paper;
                worst_best_paper_for_him = best_paper_for_him;
            }
        }
    }
    printf("worst_best_eval_for_him = %f\n", worst_best_eval_for_him);
    printf("best_rock_for_you = %f\n", best_rock_for_you);
    printf("best_paper_for_you = %f\n", best_paper_for_you);
    printf("worst_best_paper_for_him = %f\n", worst_best_paper_for_him);
    return 0;
}

Re:Always do rock.

[ArcadeMan]

Of course. You use the rock to smash him in the head while he tries to stab you with the scissors. Your friend then uses the paper to write a letter to your parents about how you died in a stupid fight about statistics.