March 12, 2009

Rock-Paper-Scissors for Winners

The simple game of rock-paper-scissors has a long history as a way of settling disputes, whether in the playground or at the conference table.

In the playground version of rock-paper-scissors, each of two players makes a fist. On a count of three, each player simultaneously puts down a fist, which means rock, a flat hand, which means paper, or two fingers in a "V," which means scissors. The following non-transitive rules decide the winner: Rock beats scissors, scissors cut paper, and paper wraps rock. If both players make the same gesture, the bout ends in a tie.

Is there a winning strategy for this game? It doesn't make sense to show the same configuration each time. An alert opponent would quickly learn to anticipate your move, make the appropriate response, and always win. A similar danger lies in following any other sort of pattern. Thus, unless you can find a flaw in your opponent's play, your best bet is to mix the three choices randomly.

But without the help of a randomizer of some sort, people aren't very good at making random choices on their own. In the article "Winning at Rock-Paper-Scissors" in the March 2009 College Mathematics Journal, Derek Eyler, Zachary Shalla, Andrew Doumaux, and Tim McDevitt present strategies for defeating people who are poor generators of random sequences.

Suppose, for example, that a player tends to choose one option (symbol) more often than the others. According to McDevitt and his coauthors, winning play generalizes to the following strategy:

* Never choose the symbol that loses to the most likely symbol.
* Choose the most likely symbol if the symbol that it beats has probability greater than 1/3.
* Otherwise, choose the symbol that beats the most likely symbol.

To see what happens in practice, McDevitt and his associates collected data from 119 people who played 50 games of rock-paper-scissors against a computer using this optimal strategy. Their subjects had a strong preference for rock: 55.5% started with rock, 32.8% with paper, and 11.8% with scissors.

"Symbol choices beyond the first seem to depend on previous choices," the authors note. "Players seem to have a distinct preference for repeating plays."

For example, a player who chose paper on one trial had a .421 probability of repeating this play on the next trial, well above 1/3.

So, when playing against such a player, your best bet is a strategy of always playing the symbol that defeats the symbol that your opponent previously played. But that only works in the short term. In the long run, you would end up choosing the same symbol every time, and your opponent might catch on.

"A more sophisticated approach analyzes an opponent's previous two choices," McDevitt and his colleagues write. Experimental results suggest that people have a tendency to repeat symbols or to cycle through the symbols.

The researchers developed a computer program that bases its choice of symbol adaptively on its human opponent's previous two choices, updating the probabilities of different pairs of choices every time its human opponent chooses a symbol.

In one test that involved 241 participants each playing 100 games against the computer, the computer won 42.1%, lost 27.7%, and tied 30.2% of individual games. That's significantly better than playing randomly would achieve.

"In closing, we note that deviating from the optimal strategy is always dangerous because a superior strategy always exists," the researchers warn.

In the test, for example, two players defeated the program 100 times out of 100. "Conversations with those two players revealed that one of them stopped and started the match repeatedly until he found the perfect strategy through trial and error," McDevitt and his colleagues note, "and the second accessed and analyzed the program to determine the computer's strategy."

You can try beating a computer implementation of the strategy described above at McDevitt's "Rock-Paper-Scissors" Web page.

References:

Beasley, J. 1990. The Mathematics of Games. Oxford University Press.

Eyler, D., Z. Shalla, A. Doumaux, and T. McDevitt. 2009. Winning at rock-paper-scissors. College Mathematics Journal 40(March):125-128.

Peterson, I. 2002. Mating games and lizards. In Mathematical Treks: From Surreal Numbers to Magic Circles. Mathematical Association of America.

No comments: