Crunching the numbers: Mixed strategies
|
|
The Pokémon series is no stranger to Rock-Paper-Scissors. The Rocket Trio will sometimes solve their disputes with a quick match, and in Accumula Town, a girl will challenge the player to a Pokémon-themed version of the game with Fire, Water, and Grass.
A few TCG cards also feature Rock-Paper-Scissors: Misty's Duel, Team Galactic's Wager, and Fast Ticket. With Team Galactic’s Wager, it was ruled that people couldn’t flip a coin (which really means roll a die at a tournament) in order to simulate the effects of the game. This forces both players to try and quickly outwit their opponent. So what’s the best way of going about this?
Before I ever learned about game theory, the process in my head went something like, “I think someone told me that 50% of people start out with rock, so I should go with paper. But if my opponent is thinking one step ahead of me, than s/he will go with scissors, so should I go one step ahead of that by going with rock?” I’d go on and on and on much like the Sicilian from The Princess Bride. The thought of ever finding a solution to the game was, to say the least, inconceivable.
The way to approach this problem is by setting up a payoff table. The victories in Rock-Paper-Scissors are equal. Winning with scissors doesn’t reward us more than if we win with paper, so we’ll assign one victory point whenever a player wins.
Unlike before, there aren’t any dominant strategies. This means that the best strategy involves playing rock, paper, or scissors randomly for a fixed percentage of the time. Ever see A Beautiful Mind? John Nash proved this, and that’s why he’s such a big deal (among other things). Seeing how nicely symmetrical this game is, intuition may tell us to play each hand an equal number of times; i.e. play rock, paper, and scissors 33% each.
Looking at it algebraically, we assume our opponent will play rock with some sort of probability which we will call p1. Similarly, we can assume our opponent will play paper or scissors with some probability, p2 or p3 respectively. These are the only choices our opponent has, so this implies
Next, we look at our expected payoff (in this case, my chance to win) for each hand we can play. For example, if I go with rock, my expected payoff will be
Which simplifies to
We do the same thing with paper and scissors.
And we get the equations
Next, we set the expect values equal to each other. The logic behind that is this: if the expected values are not equal to each other, that would imply that at least one of the hands I play would have a higher payoff than the others. That would give me no incentive to play the lesser hands if I’m able to spot the weakness in my opponent’s strategy. Thus, my opponent wouldn’t want to give me the opportunity, and should opt out to minimize my maximum winnings.
The result becomes this
We plug this result in
So, the math is saying that my opponent should play each hand randomly 33% of the time if he or she wants to minimize my chances of winning. Also, this makes the expected value of my chance to win 33%. This should make sense because the other 67% would be ties and losses.
Mixed strategies show up all the time in Pokémon games. Deciding on switching your active to something better on your bench? Bam! Use mixed strategies. Thinking about what the best Pokémon are to make a good team? Bam! More mixed strategies. Figuring out what deck to bring to a tournament? Bam! Even more mixed strategies. Trying to kick it up a notch? Bam! Ask Emeril.
Let’s look at a real life Pokémon example. Your friend and you once again are arguing about what movie to watch. Your friend is fairly tired of getting beaten with the videogame all the time, so he or she has given up achieving victory digitally (at least for now), and has moved on to the TCG. Both of you have been up to date with the metagame and even have decks based on CMT (Celebi Prime, Mewtwo-EX, and Tornadus), ZekEels (Zekrom and Eelektrik), and Terrakion (the only Pokémon in this deck are four Terrakion cards) archetypes.
These three decks follow a Rock-Paper-Scissors type set up. Terrakion demolishes ZekEels. ZekEels has the advantage over CMT. CMT laughs in the face of Terrakion. Unlike Rock-Paper-Scissors, each deck only has a chance to win over the other. On top of that, there are no ties. Also, one Terrakion deck could be very different from another, so one deck could have an advantage in the mirror match.
Between the two of you, the win percentages between your decks are like so:
- Note: I pulled these numbers out of thin air. Please don’t take them seriously.
Giving this a quick glance, there are no pure strategies. Ergo, there must be a mixed strategy. We want to minimize our opponent’s chances of winning, so we’ll assign a probability that we’ll play Terrakion, ZekEeels, and CMT (p1, p2, p3) and look at our opponent’s expected values.
Once again, we’ll set all of the expected values equal to each other. Let’s call our opponent’s expected value y.
Ah, yes. My long time rival: a system of equations. Ironically, even though I’m a math major, arithmetic is my worst nightmare. Well, vocabulary is my worst nightmare, but I’ve lost many points on tests within my lifetime because of a tendency to make minus signs into plus signs.
Anyway, it wasn’t until college that I learned about how efficient matrices are. Hopefully, this example can save a few high school algebra students from hours of frustration.
Let’s attempt Gaussian Elimination the good ol’ fashioned way (with variables) and with matrices.
First, let’s turn our system of equations into a matrix. We need to set all the functions equal to a constant and arrange the variables in each equation to be in the same order.
Next, we find all coefficients of each variable in each equation.
What we’re trying to do here is organize our variables and their coefficients. The table below is for clarification:
Finally, we’ll place the coefficients of our variables in our matrix with the constants to the far right.
This type of matrix is called an augmented matrix, and our goal is to make the part to the left of the vertical bar the identity matrix. The identity matrix is an n x n matrix (meaning there are the same number of rows as there are columns) where everything is zero except for the numbers along the diagonal line, which should all be one. A picture is worth a thousand words, so here’s roughly what it should look like:
Essentially, this is just a pretty way of representing our system of equations. Each column represents one of our variables. In this case, from left to right, we have y, p1, p2, and p3. When we reduce the matrix to the left of the bar to the identity matrix, the value of each variable will correspond to the constant (the numbers to the right of the bar) in the same row.
So how do we do this? We can add or subtract multiples of matrix rows to one another, just like how we can add or subtract multiples of equations to one another in a system of equations. The way Gaussian Elimination works is by looking at a row. We take the first non-zero coefficient in that row and divide the row by that coefficient. This should make the first non-zero coefficient a one. Then, we subtract multiples of that row from the equations above and below the row we're looking at. Thus, out of all the rows in our matrix, only the row we're looking at has a non-zero coefficient for its first non-zero entry. I realize that's a bit of a mouthful, so let's apply it to our case.
With our example, it looks like this:
Subtract row 1 from row 2 and row 3 (R2:=R2-R1, R3:=R3-R1)
Divide 10 from row 2 (R2:=R2/10)
R1:=R1+40R2
R3:=R3+40R2
R4:=R4-R2
R3:=R3/160
R1:=R1-40R3
R2:=R2-3R3
R4:=R4+2R3
R4:=16R4/50
Finally! R1:=R1+305R4/2
R2:=R2+11R4/16
R3:=R3+23R4/16
Here’s the breakdown of our numbers: if we play Terrakion 22% of the time, ZekEels 46% of the time, and CMT 32% of the time, we’ll force our opponent to have a 48.8% chance to win. That’s good for us because that means we have a 51.2% chance to win.
While mixed strategies are powerful, it should be noted that both humans and computers are notoriously bad at being perfectly random (hence why the random number generators for computers are called psuedorandom number generators). That’s why the best Rock-Paper-Scissors algorithms are random at first, but then analyze the past choices of the opponent to spot patterns and exploit them.
Personally, if I think I’ll be running into a game of Rock-Paper-Scissors at a Pokémon tournament, I roll a die a few times and memorize the sequence of numbers. I’ve met quite a few clever players over the years, and whenever I get cocky or greedy and think I can beat the odds by outsmarting my opponent, it almost always ends in disaster.
| Crunching the Numbers |
|---|
| By Danielle Detering |
| Crunching the numbers • Graph theory • Game theory Game trees • Mixed strategies |
