From: Ruby Quiz <james@...>
Date: 2007-03-08T23:00:21+09:00
Subject: [SUMMARY] GOPS (#116)

When I was first solving this quiz I built a suite of functions that measured
bidding power remaining and the ratio of your current score to the guaranteed
victory score of 46 points.  I then tried to fine tune a bot that made decisions
based on these factors.  I couldn't seem to find a good balance for that though
and the bot did not play well.

Ola Leifler took the tuning out of the programmer's hands and asked the computer
to do that part too.  Using a genetic algorithm library, Ola generated pure ruby
card selection routines just by having the computer play itself and find what
was winning.  That code is a very interesting approach to this problem and worth
a look.

I took a different path.  Since I couldn't seem to nail a solid strategy, I
focused in on the details of game play and how I might use those to my
advantage.

My best realization is that sometimes you have "sure wins."  That is to say when
your opponent has played the King and you have not, you have one card you can
take without fail.  When the opponent throws a Queen, it's two cards.  You can
then plan which cards to capture with your sure wins.

You always know the bid cards still to be played by taking the full suit and
removing any cards you have already bid on.  Given that, you can set your sure
win King aside to take the best card left and plan to use your sure win Queen on
the second best.

The only question remaining is, what do we play when we don't have a sure win
play.  I chose a simple throw-the-lowest-card strategy, in the hopes it would
draw out the opponent's high cards without me spending mine.  A better backup
strategy, like one that watched for the critical 46 point barrier in bids left
plus our current score, could probably make this bot stronger.

That's the description.  Now we're ready for the translation into code.  It
begins like this:

	#!/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
	
	# ...

The Player class just provides the tools to represent the cards a bot has to
play as well as the cards they have won.  This is common functionality needed
between my bot and the opponent bot, so I factored it out into this base class. 
The play_card() method is used to remove a card from the bot's remaining hand,
and win_card() just adds a bid card to the bot's winnings.

Now we move into the actual Planner bot code:

	# ...
	
	class Planner < Player
	  def initialize
	    super
	    
	    @bids_left = CARDS.dup
	    @opponent  = Player.new
	    
	    @sure_wins = Hash.new
	  end
	  
	  # ...

Here I just setup a way to track remaining bids, the opponent, and the sure wins
I have found.  Note that the opponent is just a bare Player object while Planner
subclasses Player to add this additional tracking and an interface.

The next two methods provide the bot's game interface:

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

The bid_on_card() method is called each time this bot is expected to play.  The
bid card is passed into the method so the bot will know what it is trying to
win.  As you can see, this method just records the bid card and delegates card
selection logic to choose_a_card().  We will look into that logic shortly.

After a play is made, the server sends the opponent's response which can be
passed to record_result().  This method figures out who won the card, if anyone,
and places it in the correct winnings.  This bot doesn't really make use of
winnings, but I wanted to implement the whole game protocol in case I needed it
later.  After recording the win, we remove both plays from from the bots and the
bid from remaining bid cards.

Up until now we've really just been working with the game itself.  You can take
all this code and just add a choose_a_card() method to try your own ideas. 
Here's the logic for this bot:

	  # ...
	  
	  private
	  
	  def choose_a_card
	    find_sure_wins
	    
	    @sure_wins[@bidding_for] || @cards_left.min
	  end
	  
	  def find_sure_wins
	    ((@opponent.cards_left.max + 1)..13).to_a.reverse_each do |card|
	      next unless @cards_left.include?       card
	      next if     @sure_wins.values.include? card
	      
	      @sure_wins[(@bids_left - @sure_wins.keys).max] = card
	    end
	  end
	end
	
	# ...

This is the code representation of the strategy I described earlier.  First,
choose_a_card() hunts for any sure wins by calling find_sure_wins().  After that
a move is made by picking a sure win when there is one or throwing our lowest
card when there isn't.

The real action is in find_sure_wins().  Here we walk a list of all cards larger
than the opponent's highest card, in reverse.  Now we skip over any cards we
don't have and cards we already have plans for.  For the rest of the cards, we
just assign that play to the highest bid card yet to come up or be assigned. 
Those are our sure wins.

The final bit of code just connects the bot interface to STDIN and STDOUT:

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

In this code we begin by making an instance of the bot.  We then loop over the
rounds of play, reading the bid card and handing that to bid_on_card().  We pass
whatever play is returned to STDOUT and flush() the output so the server sees
the card.  Finally, the opponent's play is read and passed to record_result().

My thanks to all who made bots.  I can't believe how hard even some of the
trivial bots were to play against.

Tomorrow, we will build my favorite computer simulation...