Rock-Paper-Scissors and Sicilian Reasoning

I got "the official" rock-paper-scissors (RPS) book for Christmas, and I have to say that while it was a nice gesture I'm not too impressed with it. The book is intended to be satirical, although it's so dry and borderline-boring that it took me a bit of reading to be sure.

Sadly, the first page of the book I opened to gets one of the most fundamental ideas of RPS, "Sicilian reasoning", wrong. The fundamental idea of Sicilian reasoning (a name taken from a wonderful scene in the movie The Princess Bride) is to try to reason out a move in a game based on an analysis of the opponent's reasoning—difficult, since the opponent is also presumably using Sicilian reasoning. In this context, Dan Egnor's groundbreaking work on Iocaine Powder in the First International Computer RPS Competition deserves to be more widely known…

The problem with Sicilian reasoning is that it seems endless; no matter how far ahead you reason, you imagine your opponent reasoning one step farther, and thus require one more step yourself. Egnor's fundamental observation is that in RPS there are ultimately only three ways to win: cover rock with paper, dull scissors with rock, cut paper with scissors.

  1. Imagine that I predict that your next move is paper. So I will naïvely play scissors.
  2. But, I reason, you might know I'm predicting you'll play paper, in which case you'll play rock to dull my scissors. So I'll play paper.
  3. But you might know I'm predicting you'll play paper and using Sicilian reasoning, in which case you'll play scissors to cut my paper. So I'll play rock.
  4. But you might know I'm predicting you'll play paper and using two levels of Sicilian reasoning, in which case you will play paper to cover my rock. So I'll play scissors.

Now the funny thing is that option 4 (three levels of Sicilian reasoning) leads me to make exactly the same move I would have made naïvely! In fact, since there are only three moves in RPS, there can be only three ways I can modify my move based on my prediction about your move.

Egnor points out that there are three more basic strategies to consider, though. Suppose that I believe your move will be made based not on Sicilian reasoning about my prediction of your move, but on your prediction of my move! Then I have three more responses.

  1. Imagine that I predict that you think that my next move will be paper. This would lead you to play scissors. So I will naïvely play rock.
  2. But, I reason, you might be using Sicilian reasoning, and will play paper to counter my prediction-based move of rock. So I'll play scissors.
  3. But you might be using two levels of Sicilian reasoning, and will play rock to counter my move of scissors. So I'll play paper.

Again, the reasoning becomes circular after the three possibilities.

Egnor's key insight in Iocaine Powder was to run various naïve predictors of his own and opponent's moves, and to keep track of what each of the three resulting modes of Sicilian reasoning would choose as moves based on the predictors. A meta-predictor kept track of which Sicilian reasoning mode and predictor were performing the best, and the program's next move was selected on this basis. This worked really well.

The moral of the story? Never go up against Dan Egnor when death is on the line.


Update 2013-10-03: This post got some nice comments on the Harry Potter and the Methods of Rationality Sub-Reddit. Thanks to Keshav Kini for the link! Friend of Bart

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

I Think the Real Key

is to make sure that your prediction method beats pseudo-random. I can glance at my watch before each round, divide the second hand's position by 3 and take the remainder.

This is easier than it sounds - say my second hand is on 42 seconds. I can add the two digits, 4 + 2 = 6. Then 6 / 3 has a 0 remainder, and I choose "rock".

If my second hand reads 55, I can again add the digits, 5 + 5 = 10. 10 / 3 has remainder 1, so I choose scissors.

For a second hand that reads 17, I get 1 + 7 = 8 / 3 gives a remainder of 2. I choose paper.

This methods always works, so the mental math is not difficult, it can be done in about 2 seconds.

If your strategy can't beat random, then it's all down to pure chance. I don't see how any strategy can consistently beat random. Random can't consistently win, either. It's all down to chance.

A very good game for adults to play with children. For a minute or two. Not a very good game for two adults or two children.

No, no, no

Read the First International Computer Competition link. Random placed at about the middle of the pack of contestants.

But how can that be? Well, because of the tournament format, which actually makes RPS a multi-player event. You see, you have to exploit the weaknesses of players like "Always Rock" and of weak real submissions to do well in the final tournament scoring. But to exploit a weakness in your opponent's play, you need to make non-random moves—which makes you vulnerable.

The top entries all had a random fallback strategy, so that they could never lose too badly. But even in the "best-of-the-best" tournament random didn't do so well.

Darse Billings, who organized the computer tournament, also has an interesting related article about the need to take risks in tournament play. (The article focuses on chess.) Highly recommended. Friend of Bart

Tournament

There's no doubt that anyone whose strategy is worse than pseudo-random is hopeless.

I'd expect pseudo-random to finish right in the middle of a tournament - it's going to beat some complicated strategies and lose to some horrible strategies. That's what "pseudo-random" means. But what you're talking about now is something very different. It's not the strategy of the game, it's the strategy for a round-robin tournament of the game. A simple hand-to-hand match is almost completely based on luck. Five year olds can beat me at least 3 out of 10 rounds.

The strategy for a round-robin tournament is to take some risks while being sure you beat all the "dumb" strategies. Even then, it's hard to imagine that you'd get the same winner if you ran an identical tournament field twice.

Or to put it more colorfully...

This webpage explains why you are wrong. See my links page for how to build your own URL for this. Smiling

They consistently got the same winners...

The two computer tournaments identified consistent winners out of a huge field, regardless of what subsets were included, etc.

One key to consistency is that you really have to run way, way more than 10 rounds. 100 would be good, 1000 better. This sounds silly, but backgammon tournaments have essentially the same property (not that this makes it any less silly, just less unique).

A good player (i.e. someone good at predicting and reasoning) should be able to consistently beat a 5 year old RPS player over a reasonably long run of games.

Hmmm...

There is a lot reasoning -- but what happens when you're playing a young toddler and the plays are totally random? All reasoning is out the window unless there is analysis and observed pattern in the history of the choices made.

The times I've played, it appears its based on the players personality, psychology (even like the basketball games), and the pattern classifications they decide they want to use at the moment. Overall it appears to me there might need to be more than goes into the reasoning than this Sicilian or Meta approach to have better prediction accuracy.

It's an augmented predictor

The Sicilian reasoning is just used to augment some existing predictor. Certainly you need a decent predictor to start with. The thing is that if I know what predictor you're using, I'll win every game against you using Sicilian reasoning regardless of how "good" it is.

Children, BTW, are horrible at randomizing just like everyone else. One of my Reed classmates taught pigeons to peck at lights "randomly"; it took them a long time to learn.