From: avi.bryant@... (Avi Bryant)
Date: 2005-01-23T23:25:53+09:00
Subject: Re: [QUIZ] Paper Rock Scissors (#16)

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/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 :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