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…