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! (B)