by Christoffer Lernö
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:
$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:
Quiz Summary
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:
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...
