[QUIZ] GOPS (#116)

[Ruby Quiz]

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

 

[Robert Dober]

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

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

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

 

[Robert Dober]

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

Ok sorry no rake on my machine I am ashamed

 

[Raj Sahae]

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

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

 

[Robert Dober]

This quiz focuses on just two players...


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

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 Edward Gray 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?

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

 

[Christoffer Lernö]

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

Well the tricky part with this quiz is that if you want to make =20
sure you have a strong bot you have to invent strong bots for it to =20=

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

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

James Edward Gray II=

 

[Raj Sahae]

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 Dober]

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

 

[Christoffer Lernö]

--Apple-Mail-4--682906539
Content-Transfer-Encoding: 7bit
Content-Type: text/plain;
charset=US-ASCII;
delsp=yes;
format=flowed

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

--Apple-Mail-4--682906539
Content-Transfer-Encoding: 7bit
Content-Type: text/x-ruby-script;
x-unix-mode=0644;
name=muppet.rb
Content-Disposition: attachment;
filename=muppet.rb

#!/usr/bin/env ruby -w

# Muppet: The Static bot
# Using an array-based bot with static responses
# was originally conceived by my co-worker Daniel Wikstrom.
# This particular strategy was generated by randomly
# creating strategies and then letting the strategies to
# fight each other.
strategy = [4, 2, 5, 6, 1, 7, 11, 8, 12, 3, 13, 9, 10]

13.times do
$stdout.puts strategy[$stdin.gets[/\d+/].to_i - 1]
$stdout.flush
$stdin.gets
end


--Apple-Mail-4--682906539
Content-Transfer-Encoding: 7bit
Content-Type: text/plain;
charset=US-ASCII;
format=flowed



--Apple-Mail-4--682906539--

 

[Christoffer Lernö]

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

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 =20
against multiple static bots without clearing his memory, but the =20
result is still fairly entertaining:

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

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

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

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

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

My initial plan was to make him smarter, but I found not being passed =20=

a bot name a pretty big barrier to that.

Here's the code:

#!/usr/bin/env ruby -w

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

def initialize
@cards_left =3D CARDS.dup
@wins =3D 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 =3D "memory.dump"

def initialize
super

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

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

def bid_on_card(card)
@bidding_for =3D card
@last_play =3D 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] =3D 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 =3D @memory[@bidding_for]
expected =3D=3D 13 ? 1 : expected + 1
end
end
end

if __FILE__ =3D=3D $PROGRAM_NAME
observant =3D 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

 

[Christoffer Lernö]

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]

--Apple-Mail-2--622601840
Content-Type: multipart/mixed; boundary=Apple-Mail-1--622602060


--Apple-Mail-1--622602060
Content-Transfer-Encoding: 7bit
Content-Type: text/plain;
charset=US-ASCII;
delsp=yes;
format=flowed

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



--Apple-Mail-1--622602060
Content-Transfer-Encoding: 7bit
Content-Type: text/x-ruby-script;
x-unix-mode=0700;
x-mac-creator=454D4178;
name=drp_bot.rb
Content-Disposition: attachment;
filename=drp_bot.rb

#!/usr/bin/env ruby

require 'drp'
require 'logger'
require File.join(File.join(File.expand_path(File.dirname(__FILE__)), *%w[.. lib]), 'gops.rb')


class Array

def random_element
self[rand*size]
end

def sum
inject(0) {|sum,x|x+sum}
end

end

class BotGenerator

extend DRP::RuleEngine

begin_rules


# Highest
def draw_card
"@cards.max"
end

# Lowest
def draw_card
"@cards.min"
end

# A number from 1 to n
def num(n)
(rand*(n+1)).to_i.to_s
end

def array_collator
%w[min max first last sum].random_element
end

def bin_op
%w[&& ||].random_element
end

def op
%w[== < > <= >=].random_element
end

def stack
["(1..13).to_a-",""].random_element+
(%w[@played_cards @competition_cards @opponent_cards].random_element)
end

def num_or_card
s=stack
"(if not (#{s}).empty? \n\t then \n\t\t(#{s}).#{array_collator}\n\t else \n\t\t#{num_or_card}\n end)"
end

# No matter how many cards are played, we can still compare between
# a card and all possible values

def num_or_card
num(13)
end

def num_or_card
"score"
end

def comparisons
"#{comparison} #{bin_op} (#{comparisons})"
end

def comparisons
comparison
end

def comparison
%w[true false].random_element
end

# generate a condition and draw statement, with nice indentation for
# debugging
def select_card_exp(indent)
%{#{" "*indent unless indent==2}if #{comparisons}
#{" "*indent}then
#{" "*(indent+1)}#{draw_card}
#{" "*indent}else
#{select_card_exp(indent+1)}
#{" "*indent}end}
end

def select_card_exp(indent)
(" "*indent)+draw_card
end

def select_card_block
%{Proc.new do
card=#{select_card_exp(2)}
@played_cards << card
@cards-=[card]
card
end.call}
end

weight 3

def comparison
"#{num_or_card} #{op} #{num_or_card}"
end


# Function of the played cards
def draw_card
"@cards.detect {|card| card #{op} #{num_or_card}} || #{draw_card}"
end

end_rules

end


module GOPS
class Player

# Release resources so fork remains available
def close_connection
@bot.close
end

end
end


class DRPBot < GOPS:layer


attr_reader :name, :cards

def play_card(competition_card)
@competition_cards << competition_card
instance_eval(@draw_card_function)
end

def send_opponents_play(played_card)
@opponent_cards << played_card
end

def win_card(card)
@winnings << card
end

def score
@winnings.sum
end

attr_accessor :draw_card_function

def initialize
@name = "DRP Bot"
@logger = Logger.new(STDOUT)
@generator=BotGenerator.new
init_variables
@[email protected]_card_block
# @logger.debug("Draw card function:\n\n#{@draw_card_function}")
end

def init_variables
@cards=GOPS::CARDS.clone
@competition_cards=[]
@opponent_cards=[]
@played_cards=[]
@winnings=[]
# @logger.debug("Current draw card function:\n#{@draw_card_function}")
end

def play
@score=0
13.times do |i|
# competition card
comp_card=STDIN.gets.sub(/Competition card:\s+(\d+)/,"\1").to_i
@competition_cards << comp_card
my_bid=instance_eval(@draw_card_function)
STDOUT.puts my_bid
STDOUT.flush
# opponent's bid
opponent_bid=STDIN.gets.sub(/Opponent's bid:\s+(\d+)/,"\1").to_i
@opponent_cards << opponent_bid
@score += comp_card if my_bid > opponent_bid
end
@score
end

attr_accessor :genes_scores

# Train for <time> seconds against different opponents
def learn(time=30)
@genes_scores={}
t0=Time.new
while Time.new-t0<time do
["mimic", "ordered", "random"].each do |opponent_name|
rounds=0
@genes_scores[@draw_card_function]=0
# Try each "gene" 10 times against other opponents to get a
# more stable measure of performance
10.times do
opponent= GOPS:layer.new(opponent_name)
game=GOPS::Game.new(self,opponent)
init_variables
game.play
opponent.close_connection
@genes_scores[@draw_card_function]+=1 if game.winner==self
end
rounds+=1
end
@[email protected]_card_block
end
@draw_card_function=(@genes_scores.max do |gene_score1,gene_score2|
gene_score1[1] <=> gene_score2[1]
end).first
@logger.debug("Best draw card function after training:\n#{@draw_card_function}")
end

end

if __FILE__ == $PROGRAM_NAME
# DRPBot.new.learn
DRPBot.new.play
end

--Apple-Mail-1--622602060--

--Apple-Mail-2--622601840
content-type: application/pgp-signature; x-mac-type=70674453;
name=PGP.sig
content-description: This is a digitally signed message part
content-disposition: inline; filename=PGP.sig
content-transfer-encoding: 7bit

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.1 (Darwin)

iD8DBQFF7CvKf0+pE7og/mQRAtz7AJ0TKxi7ye+JQNJuxgLc43m266lSJwCdFtF+
ia8oezLzcQ5fVbQpkGe0EpE=
=/Yqu
-----END PGP SIGNATURE-----

--Apple-Mail-2--622601840--

 

[James Edward Gray II]

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 =20
example, after the opponent has played his King, ours is a sure win. =20=

At that point we find the highest bid card remaining and set the King =20=

aside for winning that. Then we start watching for the Queen...

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

Here's the code:

#!/usr/bin/env ruby -w

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

def initialize
@cards_left =3D CARDS.dup
@wins =3D 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 =3D CARDS.dup
@opponent =3D Player.new

@sure_wins =3D Hash.new
end

def bid_on_card(card)
@bidding_for =3D card
@last_play =3D 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 =3D @bids_left - @sure_wins.keys

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

if __FILE__ =3D=3D $PROGRAM_NAME
planner =3D 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