Forum: Ruby GOPS (#116)

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
James G. (Guest)
on 2007-03-02 15:35
(Received via mailing list)
The three rules of Ruby Q.:

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 Q. by submitting ideas as often as you can:

http://www.rubyquiz.com/

3.  Enjoy!

Suggestion:  A [QUIZ] in the subject of emails about the problem helps
everyone
on Ruby T. follow the discussion.  Please reply to the original quiz
message,
if you can.

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

by Christoffer Lerno

GOPS, the Game of Pure Strategy (a.k.a Goofspiel), is a very simple
cardgame.

In GOPS, one suit is singled out as "competition suit" and each of the
remaining
suits becomes the hand for a player (with one suit discarded if there
are only
two players). The competition suit is shuffled and placed face down.

Game starts by turning up the top card in the competition stack. The
players
then make a hidden bid on the card, using one of their own cards. Once
all
players have made a bid, the cards are revealed and the player with the
highest
card collects the competition card. In case of a tie, the competition
card is
discarded.

The game then proceeds in the same manner until the competition stack is
empty.

The winner is the player with the highest number of points calculated
from the
competition cards won, where Ace is the lowest--worth 1 point--and King
is the
highest--worth 13 points.

The task for this quiz is to write a bot to play 2-player GOPS against
other
bots.

A bot needs to be able to read gameplay on STDIN and write its moves to
STDOUT
using the following protocol:

  1. The engine sends the first competition card as the string
"Competition
     card: CARD", where CARD is the value of the card, from 1 (Ace) to
13
     (King).

     Example: The server would write "Competition card: 12" if the
competition
     card for this round was Queen of the competition suit.

  2. The engine then expects a response within 30 seconds. The response
should
     be the value of the card you wish to play as a string.  You may
only play
     each card in your suit once, of course.

     Example: The bot could print the line "10" to STDOUT (and flush
output)
     to bid with a ten.

  3. The engine will respond by sending the card the opponent just
played as
     the string "Opponent's bid:  CARD" where CARD is the value of the
bid
     (1-13).

     Example, the engine would print "Opponent's bid:  3" if the
opponent bid
     a 3 in the last round.  This tells you that your 10 beat the
opponent's
     3 and you won the Queen.

  4. Return to 1 with the next card in the competition stack, until all
13
     cards have been played.

Here is a very simple random bot implementing the protocol:

  (1..13).sort_by { rand }.each do |card|
    $stdin.gets # competition card--ignored
    $stdout.puts card
    $stdout.flush
    $stdin.gets # opponent's play--ignored
  end

A GOPS engine and some trivial bots are available for you to use in
testing your
strategies:

  http://rubyquiz.com/gops.zip
Robert D. (Guest)
on 2007-03-02 17:19
(Received via mailing list)
On 3/2/07, Ruby Q. <removed_email_address@domain.invalid> wrote:
> The three rules of Ruby Q.:
>
>
Maybe I missed something, but I needed to
add

$:.unshift( File.join( "..", "lib" ))
on top of test/ts_all.rb

Robert

In fact, in some ways, we are more confused than ever.
But we feel we are confused on a higher level and about more important
things.
-Anonymous
James G. (Guest)
on 2007-03-02 17:25
(Received via mailing list)
On Mar 2, 2007, at 9:19 AM, Robert D. wrote:

> On 3/2/07, Ruby Q. <removed_email_address@domain.invalid> wrote:
>> The three rules of Ruby Q.:
>>
>>
> Maybe I missed something, but I needed to
> add
>
> $:.unshift( File.join( "..", "lib" ))
> on top of test/ts_all.rb

Sure, you can do that.

You can do that when you invoke a test too:

   $ ruby -I lib:test test/...

I just use the provided Rakefile:

   $ rake

James Edward G. II
Robert D. (Guest)
on 2007-03-02 17:29
(Received via mailing list)
On 3/2/07, James Edward G. II <removed_email_address@domain.invalid> wrote:
> > on top of test/ts_all.rb
>
> James Edward G. II
>
Ok sorry no rake on my machine I am ashamed :(
Raj S. (Guest)
on 2007-03-02 22:38
(Received via mailing list)
Do we construct the bot to play against one opponent or two?
If we add an option that allows for a 3 player game, in what order do we
recieve the opponents played cards?

Raj
James G. (Guest)
on 2007-03-02 23:06
(Received via mailing list)
On Mar 2, 2007, at 2:37 PM, Raj S. wrote:

> Do we construct the bot to play against one opponent or two?

This quiz focuses on just two players...

> If we add an option that allows for a 3 player game, in what order
> do we recieve the opponents played cards?

Mainly for this reason.  Let's keep things simple.

Feel free to add a bin/tournement script though that runs a series of
games among more than two players...

James Edward G. II
Robert D. (Guest)
on 2007-03-03 00:18
(Received via mailing list)
On 3/2/07, James Edward G. II <removed_email_address@domain.invalid> wrote:
>
> Feel free to add a bin/tournement script though that runs a series of
> games among more than two players...
>
> James Edward G. II
>
>
I just wondered if it might not be a good idea to shorten the Spoiler
Period this time; if I have more BOTs to play against maybe I could
improve mine, but I am aware that looking at the code of the other
BOTs is spoiling the fun too, hmmm, I do not know, maybe everyone
could decide for oneself?

What you think James?

Robert
James G. (Guest)
on 2007-03-03 00:27
(Received via mailing list)
On Mar 2, 2007, at 4:18 PM, Robert D. wrote:

> I just wondered if it might not be a good idea to shorten the Spoiler
> Period this time; if I have more BOTs to play against maybe I could
> improve mine, but I am aware that looking at the code of the other
> BOTs is spoiling the fun too, hmmm, I do not know, maybe everyone
> could decide for oneself?
>
> What you think James?

I think we should keep the spoiler period.  Give people some time to
build some tough bots.  We will still have a few days after it.

Feel free to swap bots with a buddy off-list though, if you want to
start working against someone else sooner.

James Edward G. II
Christoffer Lernö (Guest)
on 2007-03-03 00:28
(Received via mailing list)
On Mar 2, 2007, at 23:18 , Robert D. wrote:

> I just wondered if it might not be a good idea to shorten the Spoiler
> Period this time; if I have more BOTs to play against maybe I could
> improve mine, but I am aware that looking at the code of the other
> BOTs is spoiling the fun too, hmmm, I do not know, maybe everyone
> could decide for oneself?

Well the tricky part with this quiz is that if you want to make sure
you have a strong bot you have to invent strong bots for it to
compete with. Just making a bot that beat all other bots is no
problem if you know how they play...

/C
James G. (Guest)
on 2007-03-03 00:31
(Received via mailing list)
On Mar 2, 2007, at 4:27 PM, Christoffer Lernö wrote:

> compete with. Just making a bot that beat all other bots is no
> problem if you know how they play...

That might be a good case for solving this one using an evolution
algorithm to grow smarter players.  Anyone trying that?

James Edward G. II
Raj S. (Guest)
on 2007-03-03 00:35
(Received via mailing list)
>
> Well the tricky part with this quiz is that if you want to make sure
> you have a strong bot you have to invent strong bots for it to compete
> with. Just making a bot that beat all other bots is no problem if you
> know how they play...
Well then, once you've played your bot against the other weaker bots out
there, start playing the bot against itself.
Robert D. (Guest)
on 2007-03-03 01:11
(Received via mailing list)
On 3/2/07, Raj S. <removed_email_address@domain.invalid> wrote:
>
> >
> > Well the tricky part with this quiz is that if you want to make sure
> > you have a strong bot you have to invent strong bots for it to compete
> > with. Just making a bot that beat all other bots is no problem if you
> > know how they play...
> Well then, once you've played your bot against the other weaker bots out
> there, start playing the bot against itself.
>
>
Well that only works for self learning or evolutionary bots, I am
afraid that is out of my scope:(
I plan to write a little less stupid bot, and than another one to beat
the first one and so on.
But I see your points, hopefully I can get some time in the office to
work on it :-P

Robert
Christoffer Lernö (Guest)
on 2007-03-04 23:55
(Received via mailing list)
Here is an example of what can be done with a static strategy.

This bot has a fixed strategy, always playing the same card in
response to a challenge card. This can be surprisingly effective,
brutally beating some of my attempts at bots that instead would try
to evaluate the best play using knowledge of the opponent's cards.

I can't take credit for the idea though, it was thought up by a co-
worked of mine.

Since I did not want to try static solutions by hand, I decided to
try to evolve the best possible solution.

This bot was created by randomly creating bots and keeping the best.
A bot would only be accepted if it could beat all the previous
"master" bots. This particular bot was the best I had after a few
hours of random bot births.


/C
Christoffer Lernö (Guest)
on 2007-03-05 00:13
(Received via mailing list)
I found it very helpful to write my own quick and dirty
implementation of GOPS for testing bots.

def fight(ai1_class, ai2_class)
   ai1 = ai1_class.new
   ai2 = ai2_class.new
   deck = (1..13).sort_by{ rand }.to_a
   deck1 = (1..13).to_a
   deck2 = (1..13).to_a
   points1 = 0
   points2 = 0
   while card = deck.shift
     round = 13 - deck.size
     card1 = ai1.get_card(round, card, deck1, deck2)
     card2 = ai2.get_card(round, card, deck2, deck1)
     deck1.delete card1
     deck2.delete card2
     raise "#{ai1} play corrupt (last play: #{card1})" unless
deck1.size == deck.size
     raise "#{ai2} play corrupt (last play: #{card2})" unless
deck2.size == deck.size
     if card1 > card2
       points1 += card
     elsif card2 > card1
       points2 += card
     end
   end
   [points1, points2]
end

def best_of_100(ai1, ai2)
   win1 = 0
   win2 = 0
   100.times do
     result = fight(ai1, ai2)
     case result[0] <=> result[1]
     when 1
       win1 += 1
     when -1
       win2 += 1
     end
   end
   [win1, win2]
end


class SimpleAi
   def get_card(round, card, deck, opponent_deck)
    card
   end
end
James G. (Guest)
on 2007-03-05 02:49
(Received via mailing list)
On Mar 4, 2007, at 3:55 PM, Christoffer Lernö wrote:

> Here is an example of what can be done with a static strategy.

Which means I just had to make a static player slayer.  ;)

This guy will crash if he plays a non-static bot or even if he plays
against multiple static bots without clearing his memory, but the
result is still fairly entertaining:

Final Score
-----------
Muppet:  41
Observant:  40
=> Muppet won the game.

Final Score
-----------
Muppet:  11
Observant:  80
=> Observant won the game.

Final Score
-----------
Muppet:  11
Observant:  80
=> Observant won the game.

Final Score
-----------
Muppet:  11
Observant:  80
=> Observant won the game.

Final Score
-----------
Muppet:  11
Observant:  80
=> Observant won the game.

My initial plan was to make him smarter, but I found not being passed
a bot name a pretty big barrier to that.

Here's the code:

#!/usr/bin/env ruby -w

class Player
   CARDS = (1..13).to_a

   def initialize
     @cards_left = CARDS.dup
     @wins       = Array.new
   end

   def play_card(card)
     @cards_left.delete(card)
   end

   def win_card(bid_card)
     @wins << bid_card
   end

   def score
     @wins.inject { |sum, card| sum + card } || 0
   end
end


class Observant < Player
   BRAIN = "memory.dump"

   def initialize
     super

     @bids_left = CARDS.dup
     @opponent  = Player.new

     @memory    = File.open(BRAIN) { |file| Marshal.load(file) }
rescue Array.new
     @this_game = Array.new
   end

   def bid_on_card(card)
     @bidding_for = card
     @last_play   = choose_a_card
   end

   def record_result(opponents_card)
     if @last_play > opponents_card
       win_card(@bidding_for)
     elsif opponents_card > @last_play
       @opponent.win_card(@bidding_for)
     end

     @bids_left.delete(@bidding_for)
     play_card(@last_play)
     @opponent.play_card(opponents_card)

     @this_game[@bidding_for] = opponents_card
   end

   def memorize_game
     File.open(BRAIN, "w") { |file| Marshal.dump(@this_game, file) }
   end

   private

   def choose_a_card
     if @memory.empty?
       @bidding_for
     else
       expected = @memory[@bidding_for]
       expected == 13 ? 1 : expected + 1
     end
   end
end

if __FILE__ == $PROGRAM_NAME
   observant = Observant.new
   13.times do
     $stdout.puts observant.bid_on_card($stdin.gets[/\d+/].to_i)
     $stdout.flush
     observant.record_result($stdin.gets[/\d+/].to_i)
   end
   observant.memorize_game
end

__END__

James Edward G. II
Christoffer Lernö (Guest)
on 2007-03-05 09:49
(Received via mailing list)
Observer is such a cheater... ;)

# Mutated muppet: The two-faced static bot
strategy =  [4, 2, 5, 6, 1, 7, 11, 8, 12, 3, 13, 9, 10]
shift = rand(4) - 3
13.times do
   $stdout.puts strategy[($stdin.gets[/\d+/].to_i + shift) % 13]
   $stdout.flush
   $stdin.gets
end
Ola Leifler (Guest)
on 2007-03-05 16:40
(Received via mailing list)
Hi!

Here's my first attempt at a Ruby Q.. It may be slight overkill,
but I thought that Direct Ruby P.ming (http://
drp.rubyforge.org/), a kind of evolutionary programming technique,
could be useful when implementing a learning agent. It can train
against others, using the supplied GOPS::Game engine.

/Ola Leifler

Example of a learning session:

irb(main):240:0> drpbot=DRPBot.new
#<DRPBot:0x12e3b18 ...>

irb(main):241:0> drpbot.learn
D, [2007-03-05T15:38:18.194945 #21885] DEBUG -- : Best draw card
function after training:
Proc.new do
    card=    @cards.detect {|card| card > (if not (@played_cards).empty?
   then
    (@played_cards).min
   else
    (if not ((1..13).to_a-@competition_cards).empty?
   then
    ((1..13).to_a-@competition_cards).first
   else
    12
end)
end)} || @cards.min
    @played_cards << card
    @cards-=[card]
    card
end.call
James G. (Guest)
on 2007-03-06 17:32
(Received via mailing list)
On Mar 4, 2007, at 3:55 PM, Christoffer Lernö wrote:

> Here is an example of what can be done with a static strategy.

Here's my favorite strategy I've been able to come up with.

The idea is to toss little cards until we notice sure wins.  For
example, after the opponent has played his King, ours is a sure win.
At that point we find the highest bid card remaining and set the King
aside for winning that.  Then we start watching for the Queen...

It's pretty dependent on the bid card order, so muppet still does
pretty well against it and even random gets the better of it from
time to time.

Here's the code:

#!/usr/bin/env ruby -w

class Player
   CARDS = (1..13).to_a

   def initialize
     @cards_left = CARDS.dup
     @wins       = Array.new
   end

   attr_reader :cards_left
   protected   :cards_left

   def play_card(card)
     @cards_left.delete(card)
   end

   def win_card(bid_card)
     @wins << bid_card
   end
end


class Planner < Player
   def initialize
     super

     @bids_left = CARDS.dup
     @opponent  = Player.new

     @sure_wins = Hash.new
   end

   def bid_on_card(card)
     @bidding_for = card
     @last_play   = choose_a_card
   end

   def record_result(opponents_card)
     if @last_play > opponents_card
       win_card(@bidding_for)
     elsif opponents_card > @last_play
       @opponent.win_card(@bidding_for)
     end

     @bids_left.delete(@bidding_for)
     play_card(@last_play)
     @opponent.play_card(opponents_card)
   end

   private

   def choose_a_card
     find_sure_wins

     @sure_wins[@bidding_for] || @cards_left.min
   end

   def find_sure_wins
     ((@opponent.cards_left.last + 1)..13).to_a.reverse_each do |card|
       next unless @cards_left.include?       card
       next if     @sure_wins.values.include? card
       next unless targets = @bids_left - @sure_wins.keys

       @sure_wins[targets.max] = card
     end
   end
end

if __FILE__ == $PROGRAM_NAME
   planner = Planner.new
   13.times do
     $stdout.puts planner.bid_on_card($stdin.gets[/\d+/].to_i)
     $stdout.flush
     planner.record_result($stdin.gets[/\d+/].to_i)
   end
end

__END__

James Edward G. II
This topic is locked and can not be replied to.