# \[SUMMARY\] Paper Rock Scissors (#16)

**URL:** <https://rubytalk.org/t/summary-paper-rock-scissors-16/16073>\
**Category:** ruby-talk\
**Created:** [27 January 2005 13:59 UTC](https://rubytalk.org/t/summary-paper-rock-scissors-16/16073 "2005-01-27T13:59:21Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![James\_Edward\_Gray\_II](https://avatars.discourse-cdn.com/v4/letter/j/ea5d25/32.png) [@James\_Edward\_Gray\_II](https://rubytalk.org/u/James_Edward_Gray_II)\
**Post date:** [27 January 2005 13:59 UTC](https://rubytalk.org/t/summary-paper-rock-scissors-16/16073/1 "2005-01-27T13:59:21Z")

</div>

This week's quiz is a classic computer science problem in disguise. It's  
generally done with the Prisoner's Dilemma:

&nbsp;&nbsp;[http://plato.stanford.edu/entries/prisoner-dilemma/](http://plato.stanford.edu/entries/prisoner-dilemma/)

The game chosen doesn't much matter, but the idea is that there really shouldn't  
be much strategy involved. In the Prisoner's Dilemma, it's generally agreed  
that it's hard to beat a player that confesses every time. For the game of  
Paper Rock Scissors, the winning strategy is to be purely random, as Benedikt  
Huber explained on Ruby Talk:

&nbsp;&nbsp;You can't give any predictions on the next move of a random player.  
&nbsp;&nbsp;Therefore you have a 1/3 prop. to choose a winning, losing  
&nbsp;&nbsp;or drawing move.

To be fair, Paper Rock Scissors does have quite a bit of strategy theory these  
days, but the conditions of that theory (mostly body language) are unavailable  
to computer players. Entire books have been written on the subject, believe it  
or not:

&nbsp;&nbsp;[http://www.worldrps.com/](http://www.worldrps.com/)

So random is the best we can do? Is that hard to build? Uh, no. Here's a  
sample by Avi Bryant:

&nbsp;&nbsp;class AJBRandomPlayer \< Player  
&nbsp;&nbsp;&nbsp;&nbsp;def choose  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;[:paper, :scissors, :rock][rand(3)]  
&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;end

If we test that, we get the expected 50/50 results:

&nbsp;&nbsp;AJBRandomPlayer vs. JEGPaperPlayer  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;AJBRandomPlayer: 511.0  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;JEGPaperPlayer: 489.0  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;AJBRandomPlayer Wins  
&nbsp;&nbsp;AJBRandomPlayer vs. JEGQueuePlayer  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;AJBRandomPlayer: 499.5  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;JEGQueuePlayer: 500.5  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;JEGQueuePlayer Wins

Of course, that's so uninteresting, we're probably beginning to wonder if  
James's quiz selecting skills are on the fritz. Possibly, but interesting  
solutions make me look good none-the-less. This week, Christian Neukirchen sent  
in more than one of those:

&nbsp;&nbsp;CNBiasInverter: Choose so that your bias will be the inverted  
&nbsp;&nbsp;&nbsp;&nbsp;opponent's bias.  
&nbsp;&nbsp;  
&nbsp;&nbsp;CNIrrflug: Pick a random choice. If you win, use it again; else,  
&nbsp;&nbsp;&nbsp;&nbsp;use a random choice.  
&nbsp;&nbsp;  
&nbsp;&nbsp;CNStepAhead: Try to think a step ahead. If you win, use the choice  
&nbsp;&nbsp;&nbsp;&nbsp;where you'd have lost. If you lose, you the choice where you'd  
&nbsp;&nbsp;&nbsp;&nbsp;have won. Use the same on draw.  
&nbsp;&nbsp;  
&nbsp;&nbsp;CNBiasFlipper: Always use the choice that hits what the opponent  
&nbsp;&nbsp;&nbsp;&nbsp;said most or second-to-most often (if the most often choice is not  
&nbsp;&nbsp;&nbsp;&nbsp;absolutely prefered).  
&nbsp;&nbsp;  
&nbsp;&nbsp;CNBiasBreaker: Always use the choice that hits what the opponent  
&nbsp;&nbsp;&nbsp;&nbsp;said most often.  
&nbsp;&nbsp;  
&nbsp;&nbsp;CNMeanPlayer: Pick a random choice. If you win, use it again; else,  
&nbsp;&nbsp;&nbsp;&nbsp;use the opponent's choice.

I really should show all of those here, but that would make for a ridiculously  
large summary. Let's go with Christian's favorite:

&nbsp;&nbsp;class CNBiasInverter \< Player  
&nbsp;&nbsp;&nbsp;&nbsp;def initialize(opponent)  
&nbsp;&nbsp;&nbsp;&nbsp;super  
&nbsp;&nbsp;&nbsp;&nbsp;@biases = {:rock =\> 0, :scissors =\> 0, :paper =\> 0}  
&nbsp;&nbsp;&nbsp;&nbsp;@hit = {:rock =\> :paper, :paper =\> :scissors, :scissors =\> :rock}  
&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;  
&nbsp;&nbsp;&nbsp;&nbsp;def choose  
&nbsp;&nbsp;&nbsp;&nbsp;n = ::Kernel.rand(@biases[:rock] + @biases[:scissors] +  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@biases[:paper]).to\_i  
&nbsp;&nbsp;&nbsp;&nbsp;case n  
&nbsp;&nbsp;&nbsp;&nbsp;when 0..@biases[:rock]  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;:paper  
&nbsp;&nbsp;&nbsp;&nbsp;when @biases[:rock]..@biases[:rock]+@biases[:scissors]  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;:rock  
&nbsp;&nbsp;&nbsp;&nbsp;when @biases[:rock]+@biases[:scissors]..@biases[:rock]+  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@biases[:scissors]+@biases[:paper]  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;:scissors  
&nbsp;&nbsp;&nbsp;&nbsp;else  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;p @biases[:rock]+@biases[:scissors]..@biases[:paper]  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;abort n.to\_s  
&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;  
&nbsp;&nbsp;&nbsp;&nbsp;def result( you, them, win\_lose\_or\_draw )  
&nbsp;&nbsp;&nbsp;&nbsp;@biases[them] += 1  
&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;end

initialize() sets up the a Hash for tracking the biases. (I don't believe @hit  
is needed.) result() is the compliment to that. It adjusts the proper bias  
count each time the opponent makes a selection.

choose() does all the interesting work. A random number is chosen between 0 and  
the total of all the bias counts. That number is then associated with the  
indicated bias by some clever use of ranges and the opposite of that bias is  
returned as CNBiasInverter's choice.

In other words, as the opponent chooses more and more of a particular item, the  
bias count for that item climbs. This will cause the semi-random choice to  
drift towards the opposite of that favored move.

Let's compare with our baseline:

&nbsp;&nbsp;CNBiasInverter vs. JEGPaperPlayer  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;CNBiasInverter: 995.0  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;JEGPaperPlayer: 5.0  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;CNBiasInverter Wins  
&nbsp;&nbsp;CNBiasInverter vs. JEGQueuePlayer  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;CNBiasInverter: 653.5  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;JEGQueuePlayer: 346.5  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;CNBiasInverter Wins

The results are getting better. But, of course, random is still trump:

&nbsp;&nbsp;AJBRandomPlayer vs. CNBiasInverter  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;AJBRandomPlayer: 509.5  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;CNBiasInverter: 490.5  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;AJBRandomPlayer Wins

There were many, many interesting strategies, like the one above. But random  
remained the great equalizer. Which leads us to the critical question: What  
exactly is the point of this exercise?

Cheating, of course!

With the Prisoner's Dilemma and this quiz, it's common the engineer the  
environment to be ripe for cheating. Since there's no winning strategy  
available, we'll need to bend the rules a little bit. That's because  
programmers have enormous egos and can't stand to lose at anything!

(Note: Technically, no one even cheated. The definition of cheat that applies  
here is, "to violate rules dishonestly." Go back and reread the quiz, if you  
need to...)

What's the ultimate cheat? Well, here's the first by Bill Atkins:

&nbsp;&nbsp;class BACheater \< Player  
&nbsp;&nbsp;&nbsp;&nbsp;def initialize opponent  
&nbsp;&nbsp;&nbsp;&nbsp;Object.const\_get(opponent).send :define\_method, :choose do  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;:paper  
&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;  
&nbsp;&nbsp;&nbsp;&nbsp;def choose  
&nbsp;&nbsp;&nbsp;&nbsp;:scissors  
&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;end

It doesn't get much simpler than that! Bill's initialize() method uses the  
passed in name of the opponent to locate the correct Class object and redefine  
the choose() method of that Class to something super easy to deal with. The  
opponent is modified to always throw :paper and BACheater always throws  
:scissors.

That's 100% successful against anything we've seen thus far. Worse, you're  
player is permanently modified when it goes up against BACheater, leaving you  
vulnerable to clever strategies like CNBiasInverter above:

&nbsp;&nbsp;AJBRandomPlayer vs. BACheater  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;AJBRandomPlayer: 0  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;BACheater: 1000  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;BACheater Wins  
&nbsp;&nbsp;AJBRandomPlayer vs. CNBiasInverter  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;AJBRandomPlayer: 4.5  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;CNBiasInverter: 995.5  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;CNBiasInverter Wins  
&nbsp;&nbsp;BACheater vs. CNBiasInverter  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;BACheater: 1000  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;CNBiasInverter: 0  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;BACheater Wins

Ouch!

Another cheat used by more than one player was to try and predict an opponent's  
move, then respond with a counter. Here is Benedikt Huber's version:

&nbsp;&nbsp;KILLER = { :rock =\> :paper,  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;:paper =\> :scissors,  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;:scissors =\> :rock }  
&nbsp;&nbsp;  
&nbsp;&nbsp;class BHCheatPlayer \< Player  
&nbsp;&nbsp;  
&nbsp;&nbsp;&nbsp;&nbsp;def initialize( opponent )  
&nbsp;&nbsp;&nbsp;&nbsp;super  
&nbsp;&nbsp;&nbsp;&nbsp;@opp = Object.const\_get(opponent).new(self)  
&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;  
&nbsp;&nbsp;&nbsp;&nbsp;def choose  
&nbsp;&nbsp;&nbsp;&nbsp;KILLER[@opp.choose]  
&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;  
&nbsp;&nbsp;&nbsp;&nbsp;def result(you,them,result)  
&nbsp;&nbsp;&nbsp;&nbsp;@opp.result(them,you,result)  
&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;  
&nbsp;&nbsp;end

Again initialize() retrieves the Class object, but instead of modifying the  
Class, it simply creates an internal copy of the opponent. result() forwards  
each pick to the copied opponent, to keep it synchronized with the real  
opponent. From there, choose() is obvious: See what the opponent is about to  
do and counter.

It was pointed out on Ruby Talk that this doesn't demolish random players;  
however, against any random strategy, this becomes a random player. Countering  
a random choice is a still a random move, even if the choice isn't what the  
opponent is about to do.

There were other great cheats. Jannis Harder's self-repairing program and  
FGSpyPlayer (well commented) are both worth studying. Some cheating approaches  
were also overlooked. For example, no one tried to modify the score, but it can  
be done. There were also a lot of excellent non-cheating solutions. Which  
leaves me with no choice but to say the lame but utterly true, "All the  
submissions are worth a look!"

My thanks to all my fellow cheaters and the rule abiding players that tolerate  
our antics.

Tomorrow's quiz was an actual job project of mine, years ago...

---

<div class="post-metadata">

**Author:** ![Christian\_Neukirche1](https://avatars.discourse-cdn.com/v4/letter/c/ee7513/32.png) [@Christian\_Neukirche1](https://rubytalk.org/u/Christian_Neukirche1)\
**Post date:** [27 January 2005 15:29 UTC](https://rubytalk.org/t/summary-paper-rock-scissors-16/16073/2 "2005-01-27T15:29:12Z")

</div>

Ruby Quiz \<james@grayproductions.net\> writes:

> I really should show all of those here, but that would make for a ridiculously  
> large summary. Let's go with Christian's favorite:
> 
> &nbsp;&nbsp;class CNBiasInverter \< Player  
> &nbsp;&nbsp;&nbsp;&nbsp;def initialize(opponent)  
> &nbsp;&nbsp;&nbsp;&nbsp;super  
> &nbsp;&nbsp;&nbsp;&nbsp;@biases = {:rock =\> 0, :scissors =\> 0, :paper =\> 0}  
> &nbsp;&nbsp;&nbsp;&nbsp;@hit = {:rock =\> :paper, :paper =\> :scissors, :scissors =\> :rock}  
> &nbsp;&nbsp;&nbsp;&nbsp;end  
> &nbsp;&nbsp;&nbsp;&nbsp;  
> &nbsp;&nbsp;&nbsp;&nbsp;def choose  
> &nbsp;&nbsp;&nbsp;&nbsp;n = ::Kernel.rand(@biases[:rock] + @biases[:scissors] +  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@biases[:paper]).to\_i  
> &nbsp;&nbsp;&nbsp;&nbsp;case n  
> &nbsp;&nbsp;&nbsp;&nbsp;when 0..@biases[:rock]  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;:paper  
> &nbsp;&nbsp;&nbsp;&nbsp;when @biases[:rock]..@biases[:rock]+@biases[:scissors]  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;:rock  
> &nbsp;&nbsp;&nbsp;&nbsp;when @biases[:rock]+@biases[:scissors]..@biases[:rock]+  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@biases[:scissors]+@biases[:paper]  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;:scissors  
> &nbsp;&nbsp;&nbsp;&nbsp;else  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;p @biases[:rock]+@biases[:scissors]..@biases[:paper]  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;abort n.to\_s  
> &nbsp;&nbsp;&nbsp;&nbsp;end  
> &nbsp;&nbsp;&nbsp;&nbsp;end  
> &nbsp;&nbsp;&nbsp;&nbsp;  
> &nbsp;&nbsp;&nbsp;&nbsp;def result( you, them, win\_lose\_or\_draw )  
> &nbsp;&nbsp;&nbsp;&nbsp;@biases[them] += 1  
> &nbsp;&nbsp;&nbsp;&nbsp;end  
> &nbsp;&nbsp;end
> 
> initialize() sets up the a Hash for tracking the biases. (I don't believe @hit  
> is needed.) result() is the compliment to that. It adjusts the proper bias  
> count each time the opponent makes a selection.

Yeah, that @hit was a left-over of a half-way done refactoring. 🙂

> choose() does all the interesting work. A random number is chosen between 0 and  
> the total of all the bias counts. That number is then associated with the  
> indicated bias by some clever use of ranges and the opposite of that bias is  
> returned as CNBiasInverter's choice.

BTW, I'd be interested if anyone found a nicer looking solution to  
do a weighted rand.

> There were many, many interesting strategies, like the one above. But random  
> remained the great equalizer. Which leads us to the critical question: What  
> exactly is the point of this exercise?
> 
> Cheating, of course!

ROFL.

> There were other great cheats. Jannis Harder's self-repairing program and  
> FGSpyPlayer (well commented) are both worth studying. Some cheating approaches  
> were also overlooked. For example, no one tried to modify the score, but it can  
> be done. There were also a lot of excellent non-cheating solutions. Which  
> leaves me with no choice but to say the lame but utterly true, "All the  
> submissions are worth a look!"
> 
> My thanks to all my fellow cheaters and the rule abiding players that tolerate  
> our antics.

Someone proposed printing the result by oneselves and then  
exiting. 🙂

> **···**
>
> --  
> Christian Neukirchen \<chneukirchen@gmail.com\> [http://chneukirchen.org](http://chneukirchen.org)

---

<div class="post-metadata">

**Author:** ![Martin\_Ankerl](https://avatars.discourse-cdn.com/v4/letter/m/f04885/32.png) [@Martin\_Ankerl](https://rubytalk.org/u/Martin_Ankerl)\
**Post date:** [27 January 2005 16:40 UTC](https://rubytalk.org/t/summary-paper-rock-scissors-16/16073/3 "2005-01-27T16:40:59Z")

</div>

> BTW, I'd be interested if anyone found a nicer looking solution to  
> do a weighted rand.

What you are doing is called Roulett wheel selection, which is often  
used as a selection algorithm when using genetic algorithms. I think  
this is a bit nicer:

def choose  
# sum up all values  
sum = @biases.values.inject(0) {|sum, val| sum + val }  
# choose something  
search\_sum = rand(sum)  
# count up until found  
current\_sum = 0  
found = @biases.detect do |key, value|  
current\_sum += value  
current\_sum \> search\_sum  
&nbsp;&nbsp;end  
&nbsp;&nbsp;found[0]  
end

martinus