CMS by Drupal
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.
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.
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.