Gops (#116)

bbazzarrakk · March 2, 2007, 2:35pm

The three rules of Ruby Q.:

Please do not post any solutions or spoiler discussion for this quiz
until
48 hours have passed from the time on this message.
Support Ruby Q. by submitting ideas as often as you can:

http://www.rubyquiz.com/

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:

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

bbazzarrakk · March 2, 2007, 4:19pm

On 3/2/07, Ruby Q. [email protected] 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

bbazzarrakk · March 2, 2007, 4:25pm

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

On 3/2/07, Ruby Q. [email protected] 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

bbazzarrakk · March 2, 2007, 9:38pm

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

bbazzarrakk · March 2, 2007, 4:29pm

On 3/2/07, James Edward G. II [email protected] wrote:

on top of test/ts_all.rb

James Edward G. II

Ok sorry no rake on my machine I am ashamed

bbazzarrakk · March 2, 2007, 10:06pm

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

bbazzarrakk · March 2, 2007, 11:18pm

On 3/2/07, James Edward G. II [email protected] 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

bbazzarrakk · March 2, 2007, 11:27pm

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

bbazzarrakk · March 2, 2007, 11:28pm

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

bbazzarrakk · March 2, 2007, 11:31pm

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

bbazzarrakk · March 2, 2007, 11:35pm

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.

bbazzarrakk · March 3, 2007, 12:11am

On 3/2/07, Raj S. [email protected] 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

Robert

bbazzarrakk · March 4, 2007, 10:55pm

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

bbazzarrakk · March 4, 2007, 11:13pm

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

bbazzarrakk · March 5, 2007, 1:49am

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

bbazzarrakk · March 5, 2007, 3:40pm

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

bbazzarrakk · March 5, 2007, 8:49am

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

bbazzarrakk · March 6, 2007, 4:32pm

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