Asp Forum - [QUIZ] Paper Rock Scissors (#16

James Gray

1/21/2005 2:19:00 PM

The three rules of Ruby Quiz:

1. Please do not post any solutions or spoiler discussion for this quiz until
48 hours have passed from the time on this message.

2. Support Ruby Quiz by submitting ideas as often as you can:

http://www.grayproductions.net/...

3. Enjoy!

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

Alright generals, break out you copies of "The Art of War" and let's get a
little competition going!

Your task is to build a strategy for playing the game of Paper Rock Scissors
against all manner of opponents. The question here is if you can adapt to an
opponent's strategy and seize the advantage, while he is doing the same to you
of course.

If you're not familiar with this childhood game, it's very simple. Both players
choose one of three items at the same time: Paper, a Rock, or Scissors. A
"winner" is chosen by the following rules:

Paper covers a Rock. (Paper beats a Rock.)
Scissors cut Paper. (Scissors beat Paper.)
A Rock smashes Scissors. (A Rock beats Scissors.)
Anything else is a "draw".

Defining a player for straight forward. I'm providing a class you can just
inherit from:

class YourPlayer < Player
def initialize( opponent )
# optional
#
# called at the start of a match verses opponent
# opponent = String of opponent's class name
#
# Player's constructor sets @opponent
end

def choose
# required
#
# return your choice of :paper, :rock or :scissors
end

def result( you, them, win_lose_or_draw )
# optional
#
# called after each choice you make to give feedback
# you = your choice
# them = opponent's choice
# win_lose_or_draw = :win, :lose or :draw, your result
end
end

We'll need some rules for defining players, to make it easy for all our
strategies to play against each other:

* send in one file for each strategy
* a file should contain exactly one subclass of Player
* start the name of your subclass with your initials
* start the name of your files with your initials
* start any data files you write to disk with your initials

Those rules should help with testing how different algorithms perform against
each other.

Here are two dumb Players to practice with:

class JEGPaperPlayer < Player
def choose
:paper
end
end

class JEGQueuePlayer < Player
QUEUE = [ :rock,
:scissors,
:scissors ]

def initialize( opponent )
super

@index = 0
end

def choose
choice = QUEUE[@index]

@index += 1
@index = 0 if @index == QUEUE.size

choice
end
end

Here's how those two do against each other in a 1,000 game match:

JEGPaperPlayer vs. JEGQueuePlayer
JEGPaperPlayer: 334
JEGQueuePlayer: 666
JEGQueuePlayer Wins

Finally, here's the game engine that supports the players:

#!/usr/bin/env ruby

class Player
@@players = [ ]

def self.inherited( player )
@@players << player
end

def self.each_pair
(0...(@@players.size - 1)).each do |i|
((i + 1)...@@players.size).each do |j|
yield @@players[i], @@players[j]
end
end
end

def initialize( opponent )
@opponent = opponent
end

def choose
raise NoMethodError, "Player subclasses must override choose()."
end

def result( you, them, win_lose_or_draw )
# do nothing--sublcasses can override as needed
end
end

class Game
def initialize( player1, player2 )
@player1 = player1.new(player2.to_s)
@player2 = player2.new(player1.to_s)
@score1 = 0
@score2 = 0
end

def play( match )
match.times do
hand1 = @player1.choose
hand2 = @player2.choose
case hand1
when :paper
case hand2
when :paper
draw hand1, hand2
when :rock
win @player1, hand1, hand2
when :scissors
win @player2, hand1, hand2
else
raise "Invalid choice by #{@player2.class}."
end
when :rock
case hand2
when :paper
win @player2, hand1, hand2
when :rock
draw hand1, hand2
when :scissors
win @player1, hand1, hand2
else
raise "Invalid choice by #{@player2.class}."
end
when :scissors
case hand2
when :paper
win @player1, hand1, hand2
when :rock
win @player2, hand1, hand2
when :scissors
draw hand1, hand2
else
raise "Invalid choice by #{@player2.class}."
end
else
raise "Invalid choice by #{@player1.class}."
end
end
end

def results
match = "#{@player1.class} vs. #{@player2.class}\n" +
"\t#{@player1.class}: #{@score1}\n" +
"\t#{@player2.class}: #{@score2}\n"
if @score1 == @score2
match + "\tDraw\n"
elsif @score1 > @score2
match + "\t#{@player1.class} Wins\n"
else
match + "\t#{@player2.class} Wins\n"
end
end

private

def draw( hand1, hand2 )
@score1 += 0.5
@score2 += 0.5
@player1.result(hand1, hand2, :draw)
@player2.result(hand2, hand1, :draw)
end

def win( winner, hand1, hand2 )
if winner == @player1
@score1 += 1
@player1.result(hand1, hand2, :win)
@player2.result(hand2, hand1, :lose)
else
@score2 += 1
@player1.result(hand1, hand2, :lose)
@player2.result(hand2, hand1, :win)
end
end
end

match_game_count = 1000
if ARGV.size > 2 and ARGV[0] == "-m" and ARGV[1] =~ /^[1-9]\d*$/
ARGV.shift
match_game_count = ARGV.shift.to_i
end

ARGV.each do |p|
if test(?d, p)
Dir.foreach(p) do |file|
next if file =~ /^\./
next unless file =~ /\.rb$/
require File.join(p, file)
end
else
require p
end
end

Player.each_pair do |one, two|
game = Game.new one, two
game.play match_game_count
puts game.results
end

To use:

paper_rock_scissors.rb jeg_paper_player.rb jeg_queue_player.rb

Or you can point it at a directory and it will treat all the ".rb" files in
there as Players:

paper_rock_scissors.rb players/

You can also change the match game count:

paper_rock_scissors.rb -m 10000 players/

62 Answers

Avi Bryant

1/22/2005 2:07:00 PM

> * a file should contain exactly one subclass of Player
> * start the name of your subclass with your initials

Why use prefixes on the class names, rather than a module? Wouldn't it
be better for my subclass to be AJB::MyPlayer than AJBMyPlayer?

Avi

James Gray

1/22/2005 3:00:00 PM

On Jan 22, 2005, at 8:10 AM, Avi Bryant wrote:

>> * a file should contain exactly one subclass of Player
>> * start the name of your subclass with your initials
>
> Why use prefixes on the class names, rather than a module? Wouldn't it
> be better for my subclass to be AJB::MyPlayer than AJBMyPlayer?

It's a fair style issue you raise and you're probably right. But, I
didn't think of it at the time and I do have reasons for you NOT to do
it that way. (Score print out, for one.) So, just consider it coding
to a specification. ;)

James Edward Gray II

Benedikt Huber

1/23/2005 11:38:00 AM

> Here's how those two do against each other in a 1,000 game match:
>
> JEGPaperPlayer vs. JEGQueuePlayer
> JEGPaperPlayer: 334
> JEGQueuePlayer: 666
> JEGQueuePlayer Wins

I would suggest that you need at least 55% to win. (45%-55% is draw)
Otherwise, a strategy simply selecting a random choice will always have a
50% chance of winning - The results of a single run will be highly
unpredictable and change from time to time.

Avi Bryant

1/23/2005 11:52:00 AM

Well, how is this competition going to be scored? A strategy trying to
win the most number of matches will be somewhat different from one
trying to win by the largest margin.

Christian Neukirchen

1/23/2005 12:18:00 PM

"Avi Bryant" <avi.bryant@gmail.com> writes:

> Well, how is this competition going to be scored? A strategy trying to
> win the most number of matches will be somewhat different from one
> trying to win by the largest margin.

I think the latter is more preferable, because else it's just
a matter of luck if you play against/use random numbers.

I'd propose to sum all wins per player and compare those.

--
Christian Neukirchen <chneukirchen@gmail.com> http://chneuk...

Christian Neukirchen

1/23/2005 1:32:00 PM

Ruby Quiz <james@grayproductions.net> writes:

> Your task is to build a strategy for playing the game of Paper Rock Scissors
> against all manner of opponents. The question here is if you can adapt to an
> opponent's strategy and seize the advantage, while he is doing the same to you
> of course.

First, congratulations to this great quiz. It was a great fun for me
and other people on #ruby-lang.

I tested my players in this arena:

players/cn_bias_breaker.rb players/cn_mean_player.rb
players/cn_bias_flipper.rb players/cn_step_ahead.rb
players/cn_bias_inverter.rb players/jegpaperplayer.rb
players/cn_irrflug.rb players/jegqueueplayer.rb

Here's a description of all my bots and how often they usually win in
above arena. They are ordered in my preference, so if you chose (for
reasons whatsoever) not to run all of them, please pick the first ones
first.

# CNBiasInverter: Choose so that your bias will be the inverted
# opponent's bias.
(4-6 wins)

# CNIrrflug: Pick a random choice. If you win, use it again; else,
# use a random choice.
(4-6 wins)

# CNStepAhead: Try to think a step ahead. If you win, use the choice
# where you'd have lost. If you lose, you the choice where you'd
# have won. Use the same on draw.
(3-5 wins)

# CNBiasFlipper: Always use the choice that hits what the opponent
# said most or second-to-most often (if the most often choice is not
# absolutely prefered).
(4 wins)

# CNBiasBreaker: Always use the choice that hits what the opponent
# said most often.
(3-5 wins)

# CNMeanPlayer: Pick a random choice. If you win, use it again; else,
# use the opponent's choice.
(1-4 wins)

---

# This is a shell archive. Save it in a file, remove anything before
# this line, and then unpack it by entering "sh file". Note, it may
# create directories; files and directories will be owned by you and
# have default permissions.
#
# This archive contains:
#
# cn_bias_breaker.rb
# cn_bias_flipper.rb
# cn_bias_inverter.rb
# cn_irrflug.rb
# cn_mean_player.rb
# cn_step_ahead.rb
#
echo x - cn_bias_breaker.rb
sed 's/^X//' >cn_bias_breaker.rb << 'END-of-cn_bias_breaker.rb'
X# CNBiasBreaker: Always use the choice that hits what the opponent
X# said most often.
X
Xclass CNBiasBreaker < Player
X def initialize(opponent)
X super
X @biases = {:rock => 0, :scissors => 0, :paper => 0}
X @hit = {:rock => :paper, :paper => :scissors, :scissors => :rock}
X end
X
X def choose
X @hit[@biases.max {|a, b| a[1] <=> b[1]}.first]
X end
X
X def result( you, them, win_lose_or_draw )
X @biases[them] += 1
X end
Xend
END-of-cn_bias_breaker.rb
echo x - cn_bias_flipper.rb
sed 's/^X//' >cn_bias_flipper.rb << 'END-of-cn_bias_flipper.rb'
X# CNBiasFlipper: Always use the choice that hits what the opponent
X# said most or second-to-most often (if the most often choice is not
X# absolutely prefered).
X
Xclass CNBiasFlipper < Player
X def initialize(opponent)
X super
X @biases = {:rock => 0, :scissors => 0, :paper => 0}
X @hit = {:rock => :paper, :paper => :scissors, :scissors => :rock}
X end
X
X def choose
X b = @biases.sort_by {|k, v| -v}
X if b[0][1] > b[1][1]*1.5
X @hit[b[0].first]
X else
X @hit[b[1].first]
X end
X end
X
X def result( you, them, win_lose_or_draw )
X @biases[them] += 1
X end
Xend
END-of-cn_bias_flipper.rb
echo x - cn_bias_inverter.rb
sed 's/^X//' >cn_bias_inverter.rb << 'END-of-cn_bias_inverter.rb'
X# CNBiasInverter: Choose so that your bias will be the inverted
X# opponent's bias.
X
Xclass CNBiasInverter < Player
X def initialize(opponent)
X super
X @biases = {:rock => 0, :scissors => 0, :paper => 0}
X @hit = {:rock => :paper, :paper => :scissors, :scissors => :rock}
X end
X
X def choose
X n = ::Kernel.rand(@biases[:rock] + @biases[:scissors] + @biases[:paper]).to_i
X case n
X when 0..@biases[:rock]
X :paper
X when @biases[:rock]..@biases[:rock]+@biases[:scissors]
X :rock
X when @biases[:rock]+@biases[:scissors]..@biases[:rock]+@biases[:scissors]+@biases[:paper]
X :scissors
X else
X p @biases[:rock]+@biases[:scissors]..@biases[:paper]
X abort n.to_s
X end
X end
X
X def result( you, them, win_lose_or_draw )
X @biases[them] += 1
X end
Xend
END-of-cn_bias_inverter.rb
echo x - cn_irrflug.rb
sed 's/^X//' >cn_irrflug.rb << 'END-of-cn_irrflug.rb'
X# CNIrrflug: Pick a random choice. If you win, use it again; else,
X# use a random choice.
X
Xclass CNIrrflug < Player
X def initialize(opponent)
X super
X @last_choice = [:rock, :scissors, :paper][rand(3)]
X end
X
X def choose
X @last_choice
X end
X
X def result(you, them, win_lose_or_draw)
X if win_lose_or_draw == :win
X @last_choice = you
X else
X @last_choice = [:rock, :scissors, :paper][rand(3)]
X end
X end
Xend
END-of-cn_irrflug.rb
echo x - cn_mean_player.rb
sed 's/^X//' >cn_mean_player.rb << 'END-of-cn_mean_player.rb'
X# CNMeanPlayer: Pick a random choice. If you win, use it again; else,
X# use the opponent's choice.
X
Xclass CNMeanPlayer < Player
X def initialize(opponent)
X super
X @last_choice = [:rock, :scissors, :paper][rand(3)]
X end
X
X def choose
X @last_choice
X end
X
X def result(you, them, win_lose_or_draw)
X if win_lose_or_draw == :win
X @last_choice = you
X else
X @last_choice = them
X end
X end
Xend
END-of-cn_mean_player.rb
echo x - cn_step_ahead.rb
sed 's/^X//' >cn_step_ahead.rb << 'END-of-cn_step_ahead.rb'
X# CNStepAhead: Try to think a step ahead. If you win, use the choice
X# where you'd have lost. If you lose, you the choice where you'd
X# have won. Use the same on draw.
X
Xclass CNStepAhead < Player
X def initialize(opponent)
X super
X @choice = [:rock, :scissors, :paper][rand(3)]
X end
X
X def choose
X @choice
X end
X
X def result(you, them, win_lose_or_draw)
X case win_lose_or_draw
X when :win
X @choice = {:rock => :paper, :paper => :scissors, :scissors => :paper}[them]
X when :lose
X @choice = {:rock => :scissors, :scissors => :paper, :paper => :rock}[you]
X end
X end
Xend
END-of-cn_step_ahead.rb
exit

--
Christian Neukirchen <chneukirchen@gmail.com> http://chneuk...

avi.bryant

1/23/2005 2:22:00 PM

Here's my submission. I take no credit for the basic idea, which is
shamelessly ripped from Dan Egnor's famous "Iocaine Powder" program;
mostly what I was trying to do was provide a clean Ruby implementation
of Dan's insights.

For reasons that will become clear later on, this submission actually
contains several subclasses of Player in the same file - if this is a
problem when running the competition, let me know, it's easy to work
around. However, the "real" player being submitted here is
AJBMetaPlayer.

The basic idea behind AJBMetaPlayer is this: it keeps an array of
other instances of Player subclasses. When it gets handed the
result(), it passes the information along to each of these players;
when it needs to choose(), it picks just one of the players and
returns its choice. It also keeps a running tally on each move of
which of the player instances would have won or lost if it had been
the one chosen for that move, and then uses that when picking a player
for next time. It will always pick the player that would have had the
best record so far, had it been chosen every time.

The interesting twist is that AJBMetaPlayer also makes use of two
PlayerDecorators, which present a Player interface but are wrapped
around existing players. One of these is the Inverter, which reverses
the results that are provided to it: a Player instance wrapped in an
Inverter will see the world as your opponent sees it. The other is
the Defeater, which shifts the choices made in choose() so that they
defeat the original choice (ie, :rock becomes :paper and so on). By
using all of the possible combinations of these, a single Player class
can show up 6 times in the AJBMetaPlayer's players array: normally,
defeated, defeated twice (so :rock becomes :scissors), inverted,
inverted + defeated, inverted + defeated + defeated. This allows it
to model all of the potential second- and triple-guessing an opponent
might be doing. The generic algorithm for picking the best player
instance will automatically detect and exploit this if it's there.

Absent any randomness, if you have a player instance identical to your
opponent in the players array, wrapped with an Inverter (so it gets
the same results your opponent does) and then a Defeater, you will
beat it every time. Indeed, if it were considered legal, a very
effective approach would be to search for all active Player subclasses
and construct an instance of each, wrapped in all the possible
variations. Since this seems a little too much like cheating,
AJBMetaPlayer by default uses only two base strategies that are
hopefully representative of the deterministic players it will
encounter. One of these, AJBFrequencyPlayer, just counters whatever
move its opponent has played most often in the past. The other,
AJBHistoryPlayer, builds a tree of its opponents previous runs of
moves (of lengths 1..20), and assumes that if it finds the same run
again, the player might continue it in the same way. The meta player
should do quite well against players that are either susceptible to
such analysis, *or are using a sufficiently similar analysis
themselves*. For safety, there's also AJBRandomPlayer thrown in by
default, as a fallback if nothing else seems to work.

Here's the code:
# AJBMetaPlayer.rb
# (c) Avi Bryant 2005
# heavily inspired by Dan Egnor's "Iocaine Powder":
# http://dan.egnor.name/io...

class Hash
def max_key
max{|a,b| a[1]<=>b[1]}[0] unless empty?
end
end

class Symbol
def defeat
case self
when :paper
:scissors
when :scissors
:rock
when :rock
:paper
end
end
end

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

class AJBFrequencyPlayer < AJBRandomPlayer
def initialize(op)
super
@frequencies = Hash.new(0)
end

def choose
(@frequencies.max_key || super).defeat
end

def result(y, t, win)
@frequencies[t] += 1
end
end

class AJBHistoryPlayer < AJBRandomPlayer

class Node
def initialize
@children = {}
@scores = Hash.new(0)
end

def add_child(key)
@scores[key] += 1
@children[key] ||= Node.new
end

def add_scores_to(totals)
@scores.each{|k,v| totals[k] += v}
end
end

MaxNodes = 20

def initialize(op)
super
@nodes = []
@root = Node.new
end

def choose
scores = Hash.new(0)
@nodes.each{|n| n.add_scores_to(scores)}
(scores.max_key || super).defeat
end

def result(y, t, win)
(@nodes << @root).collect!{|n| n.add_child(t)}
@nodes.shift until @nodes.size <= MaxNodes
end
end

class AJBMetaPlayer < Player
class PlayerDecorator
def initialize(player)
@player = player
end
end

class Defeater < PlayerDecorator
def choose
@player.choose.defeat
end

def result(y, t, win)
end
end

class Inverter < PlayerDecorator
def choose
@player.choose
end

def result(y, t, win)
@player.result(t, y, !win)
end
end

def initialize(op)
super
@players = [AJBRandomPlayer.new(op)] +
variations(AJBHistoryPlayer) +
variations(AJBFrequencyPlayer)
@scores = {}
@players.each{|p| @scores[p] = 0}
end

def result(y, t, win)
@players.each{|p| score(p, t)}
@players.each{|p| p.result(y, t, win)}
end

def choose
@scores.max_key.choose
end

:private

def variations(klass)
straight = klass.new(@opponent)
inverted = Inverter.new(klass.new(@opponent))
[straight,
inverted,
Defeater.new(straight),
Defeater.new(inverted),
Defeater.new(Defeater.new(straight)),
Defeater.new(Defeater.new(inverted))]
end

def score(player, move)
@scores[player] += ScoreTable[[player.choose, move]]
end

ScoreTable =
{[:scissors, :rock] => -1,
[:scissors, :scissors] => 0,
[:scissors, :paper] => 1,
[:paper, :rock] => 1,
[:paper, :scissors] => -1,
[:paper, :paper] => 0,
[:rock, :rock] => 0,
[:rock, :scissors] => 1,
[:rock, :paper] => -1}
end

Jannis Harder

1/23/2005 2:47:00 PM

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

This is my first player (Markov chain based)
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.6 (Darwin)
Comment: Using GnuPG with Thunderbird - http://enigmail....

iD8DBQFB87jh5YRWfc27RzQRAoqpAJ4uEzEGtiKqZpgl7wRJopUofihhywCcDK+k
eG/3jZfl12/u8KFhfHqxuwE=
=RXxb
-----END PGP SIGNATURE-----

class JIXPlayerM < Player
WIN = {:paper => :scissors, :rock => :paper , :scissors => :rock}
def initialize( opponent )
@mk=Hash.new
@last=[nil]*3 # try other values
end
def choose
if !@last[0].nil?
nodekey = @last.map do |i|
i[0].to_s+"-"+i[1].to_s
end.join(",")
@mk[nodekey]= MKNode.new if !@mk[nodekey]
@mk[nodekey].choose
else
[:paper,:rock,:scissors][rand(3)]
end
end

def result( you, them, win_lose_or_draw )

if !@last[0].nil?
nodekey = @last.map do |i|
i[0].to_s+"-"+i[1].to_s
end.join(",")
@mk[nodekey]= MKNode.new if !@mk[nodekey]
@mk[nodekey]<< WIN[them]
end
@last[0,1]=[]
@last<< [you,them]

end
private
class MKNode
def initialize(paper=0,rock=0,scissors=0)
@paper=paper
@rock=rock
@scissors=scissors
end
def choose
if @paper+@rock+@scissors == 0
[:paper,:rock,:scissors][rand(3)]
else
rnd = rand(@paper+@rock+@scissors)
if rnd < @paper
:paper
elsif rnd < @paper+@rock
:rock
else
:scissors
end
end
end
def <<(x)
case x
when :paper
@paper+=1
when :rock
@rock+=1
when :scissors
@scissors+=1
end
end
def inspect
max = @paper+@rock+@scissors.to_f
if max == 0
"#<JIXPlayerM::MKNode --- >"
else
"#<JIXPlayerM::MKNode p{#{@paper/max}} r{#{@rock/max}} s{#{@scissors/max}} >"
end
end
end
end

Bill Atkins

1/23/2005 3:42:00 PM

My 12-line solution has so far won 100% of the time against every
player I've been able to come up with, even players whose moves are
completely random. Here it is:

class Cheater < Player
def initialize opponent
Object.const_get(opponent).send :define_method, :choose do
:paper
end
end

def choose
:scissors
end
end

# :D

--
$stdout.sync = true
"Just another Ruby hacker.".each_byte do |b|
('a'..'z').step do|c|print c+"\b";sleep 0.007 end;print b.chr
end; print "\n"

Jannis Harder

1/23/2005 4:43:00 PM

Bill Atkins schrieb:

> My 12-line solution has so far won 100% of the time against every
> player I've been able to come up with, even players whose moves are
> completely random.

# Start
class HyperCheater < Player
def initialize(opponent)
@opponent=opponent
Object.const_get(opponent).send :define_method, :choose do
:scissors
end
end
def choose
:rock
end
def result( you, them, win_lose_or_draw )
Object.const_get(@opponent).send :define_method, :choose do
:scissors
end
Object.const_get(self.class.to_s).send :define_method, :choose
do # SelfRepair
:rock
end
end
end
END
# :P

comp.lang.ruby

[QUIZ] Paper Rock Scissors (#16

James Gray

Avi Bryant

James Gray

Benedikt Huber

Avi Bryant

Christian Neukirchen

Christian Neukirchen

avi.bryant

Jannis Harder

Bill Atkins

Jannis Harder

x Login to ForumsZone