RoShamBo and Data Compression

• Home Page
• Biography
• PGP Public Key
• Research
• Writings
  • Grad School Advice
  • RoShamBo and Compression
  • The Two Envelope Problem
  • Two Envelope Variant
  • Statistical Learning Theory
  • The Coin Game Paradox
  • Quantum Mechanics
  • Analysis Of Multi-tasking
  • Note on Psuedorandomness
  • Note on Bit Commitment
• Source Code
• Pictures

In the summer of 2000, I entered the Second International RoShamBo Programming Competition. Clearly there is no general winning strategy for RoShamBo (also known as Rock, Paper, Scissors). So the contest organizer created some robot players which followed predictable strategies. Contest entrants were supposed to design algorithms to take advantage of the predictability of these robots while trying to be unpredictable to their opponents.

I entered an algorithm based on the Lempel-Ziv data compression algorithm. As discussed in the paper Gambling Using a Finite State Machine by Meir Feder (published in the IEEE Transactions On Information Theory, September 1991), there exists a duality between data compression and gambling. The basic idea is that if you have a sequence of data which you can compress well then the data must be predictable in some sense.

My RoShamBo algorithm tries to compress the current game history guessing that your next move will be rock and then compresses the game history guessing your next move will be paper, etc. If the best compression occurs when the algorithm guesses your next move to be paper then it seems reasonable to predict that your next move will indeed be paper. Using this idea you can make a simple modification to the Lempel-Ziv data compression algorithm to obtain a universal prediction algorithm.

A demonstration version of my RoShamBo algorithm is included below for your pleasure and amusement. Try some simple patterns (e.g. paper, rock, paper, rock, etc.) and see how long it takes the algorithm to catch on and start beating you. If you have more time, try to play "randomly" and see how long you can play before the computer figures out what pattern you are using. The paper by Feder shows that if you use only finite memory patterns, then the algorithm will eventually figure out your strategy and start winning.