Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Ruby > [QUIZ] Paper Rock Scissors (#16)

Reply
Thread Tools

[QUIZ] Paper Rock Scissors (#16)

 
 
Ruby Quiz
Guest
Posts: n/a
 
      01-21-2005
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/ruby_quiz/

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 aper, :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
aper
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 aper
case hand2
when aper
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 aper
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 aper
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/


 
Reply With Quote
 
 
 
 
Avi Bryant
Guest
Posts: n/a
 
      01-22-2005
> * 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

 
Reply With Quote
 
 
 
 
James Edward Gray II
Guest
Posts: n/a
 
      01-22-2005
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



 
Reply With Quote
 
Benedikt Huber
Guest
Posts: n/a
 
      01-23-2005
> 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.





 
Reply With Quote
 
Avi Bryant
Guest
Posts: n/a
 
      01-23-2005
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.

 
Reply With Quote
 
Avi Bryant
Guest
Posts: n/a
 
      01-23-2005
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 aper 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/iocaine.html

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

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

class AJBRandomPlayer < Player
def choose
[aper, :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

rivate

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, aper] => 1,
[aper, :rock] => 1,
[aper, :scissors] => -1,
[aper, aper] => 0,
[:rock, :rock] => 0,
[:rock, :scissors] => 1,
[:rock, aper] => -1}
end
 
Reply With Quote
 
Jannis Harder
Guest
Posts: n/a
 
      01-23-2005
--------------000402080705020908050800
Content-Type: text/plain; charset=ISO-8859-15; format=flowed
Content-Transfer-Encoding: 7bit

-----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.mozdev.org

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


--------------000402080705020908050800
Content-Type: text/plain; x-mac-type="2A2A2A2A"; x-mac-creator="48647261";
name="jix_player_m.rb"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline;
filename="jix_player_m.rb"

class JIXPlayerM < Player
WIN = {aper => :scissors, :rock => aper , :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
[aper,: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
[aper,:rock,:scissors][rand(3)]
else
rnd = rand(@paper+@rock+@scissors)
if rnd < @paper
aper
elsif rnd < @paper+@rock
:rock
else
:scissors
end
end
end
def <<(x)
case x
when aper
@paper+=1
when :rock
@rock+=1
when :scissors
@scissors+=1
end
end
def inspect
max = @paper+@(E-Mail Removed)_f
if max == 0
"#<JIXPlayerM::MKNode --- >"
else
"#<JIXPlayerM::MKNode p{#{@paper/max}} r{#{@rock/max}} s{#{@scissors/max}} >"
end
end
end
end
--------------000402080705020908050800--


 
Reply With Quote
 
Bill Atkins
Guest
Posts: n/a
 
      01-23-2005
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
aper
end
end

def choose
:scissors
end
end


#

--
$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"


 
Reply With Quote
 
Jannis Harder
Guest
Posts: n/a
 
      01-23-2005
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
#



 
Reply With Quote
 
James Edward Gray II
Guest
Posts: n/a
 
      01-23-2005
On Jan 23, 2005, at 5:40 AM, Benedikt Huber wrote:

> Otherwise, a strategy simply selecting a random choice will always
> have a
> 50% chance of winning


Looks like we are seeing some strategies that do better than 50%
against a random player.

James Edward Gray II



 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Paper scissors stone angelojoseph803@googlemail.com Ruby 2 11-01-2007 05:39 PM
Rock paper scissors population algorithm, need help!!! hAmmeRoL@gmail.com C++ 2 08-09-2007 12:59 PM
[SUMMARY] Paper Rock Scissors (#16) Ruby Quiz Ruby 1 01-27-2005 04:39 PM
Building Paper, Rock, Scissors TooNaive C Programming 7 06-14-2004 09:28 AM
OT: Paper PC for Paper MCSE LnkWizard MCSE 1 04-02-2004 06:50 PM



Advertisments