[quiz] gops (#116)

ruby-talk
1

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.rubyquiz.com/

3. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem helps everyone
on Ruby Talk 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

2

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

···

On 3/2/07, Ruby Quiz <james@grayproductions.net> wrote:

The three rules of Ruby Quiz:

3

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

4

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

muppet.rb (461 Bytes)

5

Hi!

Here's my first attempt at a Ruby Quiz. It may be slight overkill, but I thought that Direct Ruby Programming (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

drp_bot.rb (4.57 KB)

PGP.sig (186 Bytes)

6

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 Gray II

···

On Mar 2, 2007, at 9:19 AM, Robert Dober wrote:

On 3/2/07, Ruby Quiz <james@grayproductions.net> wrote:

The three rules of Ruby Quiz:

Maybe I missed something, but I needed to
add

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

7

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 Gray II

···

On Mar 2, 2007, at 2:37 PM, Raj Sahae wrote:

8

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

9

Which means I just had to make a static player slayer. :wink:

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

···

On Mar 4, 2007, at 3:55 PM, Christoffer Lernö wrote:

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

-----------
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 Gray II

10

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 Gray II

···

On Mar 4, 2007, at 3:55 PM, Christoffer Lernö wrote:

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

11

Ok sorry no rake on my machine I am ashamed :frowning:

···

On 3/2/07, James Edward Gray II <james@grayproductions.net> wrote:

On Mar 2, 2007, at 9:19 AM, Robert Dober wrote:

> On 3/2/07, Ruby Quiz <james@grayproductions.net> wrote:
>> The three rules of Ruby Quiz:
>>
> 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 Gray II

--
We have not succeeded in answering all of our questions.
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

12

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

···

On 3/2/07, James Edward Gray II <james@grayproductions.net> wrote:

On Mar 2, 2007, at 2:37 PM, Raj Sahae 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 Gray II

--
We have not succeeded in answering all of our questions.
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

13

Observer is such a cheater... :wink:

# 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

14

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 Gray II

···

On Mar 2, 2007, at 4:18 PM, Robert Dober 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?

15

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

···

On Mar 2, 2007, at 23:18 , Robert Dober 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?

16

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

James Edward Gray II

···

On Mar 2, 2007, at 4:27 PM, Christoffer Lernö wrote:

On Mar 2, 2007, at 23:18 , Robert Dober 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...

17

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.

18

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

Robert

···

On 3/2/07, Raj Sahae <rajsahae@gmail.com> 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.

--
We have not succeeded in answering all of our questions.
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