January 27, 2007
RPS Battle of Wits
For a little programming fun, try playing the Online Rock-Paper-Scissors Battle of Wits.
Back in 1999 and 2000, Darse Billings introduced the world to computer-RPS in the First and Second International RoShamBo Programming Competition. You might imagine that rock-
How to Win at Rock-
True, it is impossible to build an algorithm that dominates the simple random player, but it is also impossible for the random player to dominate any other algorithm. In any tournament that includes nonrandom players, you can win by detecting the nonrandom strategies and beating them.
For example, if your opponents are the random player and good ole' rock, you can win the tournament by just playing "always paper." When you go up against random, you will be evenly matched. But you will dominate rock - that is better than random can do, and so you win overall.
Of course "always paper" and "always rock" are defeated by my daughter Piper's favorite RPS strategy, which is to make the move that beats her opponent's previous throw. Here is her algorithm, written in python:
import rps, random last = random.randrange(3) for turn in xrange(rps.turns): last = rps.play(rps.beat(last))
In this code rock is 0, paper is 1, and scissors is 2; rps.beat(last) returns the move that beats "last"; and rps.play(n) plays our move and returns our opponent's.
Piper's "beat last" algorithm is ruthlessly aggressive. On the other hand, it is also very predictable, so it will lose to a player who knows how to provoke it....
Below is Daddy's counter to Piper's algorithm - I call it the "provoker." It actually knows how to recognize and dominate a whole class of basic algorithms including "echo" and "good ole' rock":
import rps their_response, my_last_move = [0, 0, 0], 0 for turn in xrange(rps.turns): my_move = rps.beat(their_response[my_last_move])) their_response[my_last_move] = rps.play(my_move) my_last_move = my_move
As you can imagine, with enough deviousness you can do far better than this. And yet any program that tries to trip other algorithms will be predictable to some extent and therefore vulnerable to defeat itself!
MMORPS: Massively Mutiplayer Online RPS?
The online Rock-Paper-Scissors arena is now open for RPS battles. You program your bot as a CGI script on your own web server, and then you pit your bot against the others by entering its URL in the arena. Or you can just visit to pit other programmers' bots against each other.
Can you devise a bot that beats the "provoker"? Can you beat the other bots in the arena?
A list of bots in the arena is here. I have written the example bots in python, but you can write yours in whatever language you like; the http-based protocol is simple. (If you do make a bot with PHP or perl or ruby, please do let me know, because I would love to post some example code.)
For keeping score, the arena keeps a record of outcomes and ranks players by their average point scores. I have used Ed Pegg's suggestion to score games in a non-zero-sum way - there is a penalty for ties so that purely random play is at a disadvantage.
Full instructions for building your own RPS bot are posted here. There is a small python rps module that you can use, and code for some example bots is here. Of course the fun is devising your own bot. Simple submissions are helpful and welcome; both super-genius bots and easy-to-defeat bots are interesting.
Winning at rock-
If you can beat quickstudy you are doing well.
Have fun storming the castle!
Posted by David at January 27, 2007 12:45 AM
|Copyright 2007 © David Bau. All Rights Reserved.|