TopRock/Paper/Scissors-er

26Sep07

There is apparently a rock-paper-scissors contest, where you program a strategy in C++, to be hosted at UW in the first weeks of November. Registration goes until October 12. The exact rules are not yet announced, but here is a link to the announcement.

Advertisements


4 Responses to “TopRock/Paper/Scissors-er”

  1. 1 bugzpodder

    Woot, I actually won this (for head-to-head segment, and fastest time among top 25%)! And it’s all because of Nash equilibrium! 😀

    There was a score given for time taken on the round. I optimized for time and if my deterministic strategy was doing bad (which is nothing more than a frequency checker), I switched to the random strategy. So I essentially won using a random strategy and by beating other entries in time! 😀 (It’s not actually as simple as that, as you have to be in the top 25% to advance to the 2nd round)

    In quarter-finals I was against one entries based on one of Cormack’s spam algorithms (there were 2in the top 8 lol). we were doing similar in time but i did a little bit better in results (that algorithm was actually very good, it beat the most number of AIs in the first round and was just a tad bit slower). I was very lucky to make it pass that. Semi-finals somehow my strategy flawed and I was down by 500 points (I have no idea why this happened), but luckily the other algorithm was pretty slow and I managed to escape by a hair by being very fast. In the finals the other guy didn’t stand a chance — its algorithm was almost 10000x slower than me. heh. hat’s probably the last thing anyone expects — a random strategy winning that wins, lol.

  2. 2 bugzpodder

    Since you pointed to my comment from your blog I thought I’d explain my AI in more detail.

    My deterministic strategy was based on frequency analysis of previous moves. In the simplest example, suppose your opponent somehow likes rock over papers or scissors. A frequency analysis should therefore reveal that it is more likely that she plays rock. In order to take advantage of this fact, our strategy can always play paper to increase the its expected score. Of course, we can extend the analysis to look at longer sequences. For example, if my opponent just played Rock, Paper, Rock. Then we can find the most common move following these three moves that occurred before and assume the opponent will use that move. This actually works surprisingly well even when using lengths of up to 7 (in the contest I achieved about 10% more wins than the expected 33.3% to about 43%). There is also this meta-strategy concept. It is slightly difficult to explain, but we assume the opponent *knows* what my strategy is. To counter that, we can use a meta-strategy to second-guess the opponent. Instead of playing rock, one might play papers or scissors for example. Also, instead of analysing just the opponent’s moves, we can also analyze my own moves (this assumes that the opponent uses *my* strategy against myself). So there are these multiple strategies, which one did I actually use? Well the answer is to that is: pick the best one! We run these strategies in parallel and pick the one with the highest cumulative score! This of course assumes that the opponent stays true to a single strategy (unfortunately the assumption is false — as mentioned in the previous post I lost 5% more than the expected 33% in the semi-finals). More information on meta-strategies can be found by looking up “Iocaine Powder explained”. These strategies enabled me to place in 4th or 5th in the round-robin portion of the contest. (Official results will be released in a few days on the contest webpage)

    If none of these strategies gave a high score, I simply used random. As I mentioned in my original post, this is a very crucial fallback strategy. Coupled with a fast implementation was the key to winning the head-to-head portion, especially because run time was part of the score. As I mentioned above, the mistake I made was that I did not keep track of my total score. What I should also do is if my score gets too low, switch to random. This would definitely cut my expected losses in the semi-finals from 5% to about 0.5% which is *very* significant.

  3. 3 bugzpodder

    Also, in the top 8 out of about 30 which qualified the head-to-head challenge, 5 of them were based on the infamous Iocaine Powder (unfortunately none of them except me realized that the runtime + random is the key to winning the head-to-head portion, not better prediction — that would only win you round-robin).
    There were two more that was based on Prof Gordon Cormack which he apparently discussed in CS241/CS497 lectures. There was also this one ad-hoc strategy based on trees which won the most original entry category.


  1. 1 Coding Games « Dave a.g.p.’s Blog

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: