My wife and I love to play a card game called Lost Cities. It's an easy two player game.
There are five "suits" representing locations in the world: Deserts, Oceans, Mountains, Jungles, and Volcanoes. Each suit contains three "investment" cards and one each of the numbers 2 through 10.
Eight cards are dealt to each player, then play alternates turns. On your turn, you must do exactly two things: Play a card and draw a card, in that order. When the last card is drawn from the deck, the game ends immediately.
Each play gets an "expedition" pile for each of the five suits, and the players share five discard piles, again one for each suit. To play a card, you may add it to your expedition pile for that suit or place it on the discard pile for that suit.
Your expedition piles must go in order. You may only play a higher card than the last one you played on that pile. Investment cards are low and you may play up to all three of them, even though they are the same card. They must still come before the number cards, of course.
You have two choices when drawing a card. You may take the top card from the deck or the last card played on any of the five discard piles. You may not however, discard a card and then draw it again in the same turn.
When the deck is exhausted, both player's scores are calculated based on the expedition piles. High score wins. (Players generally play a few hands and keep a running tally.)
An expeditions score is calculated by the following formula:
points = (total_of_all_number_cards - 20) * (1 + investment_cards_count) +
bonus_20_points_if_expedition_has_8_cards_or_more
For example, if you had two investment cards and the 6, 8, and 10 in the oceans suit, that expedition is worth 12 points ((24 - 20) * (1 + 2) + 0). Expeditions in which you didn't play a card don't count for or against you. They are disregarded.
That's the whole game. Let's see a few rounds played out, as an example. First, I'm shown my hand and I can select a card to play:
Deserts:
Opponent:
Discards:
You:
Oceans:
Opponent:
Discards:
You:
Mountains:
Opponent:
Discards:
You:
Jungles:
Opponent:
Discards:
You:
Volcanoes:
Opponent:
Discards:
You:
Deck: ############################################ (44)
Hand: InvD 2D 3D 5D 2O 5O 9J 5V
Score: 0 (You) vs. 0 (Opponent). Your play?
id
You play the InvD.
Then I am asked where I would like to draw from. I don't really have a choice yet though, since the discard piles are empty:
Deserts:
Opponent:
Discards:
You: Inv (-40)
Oceans:
Opponent:
Discards:
You:
Mountains:
Opponent:
Discards:
You:
Jungles:
Opponent:
Discards:
You:
Volcanoes:
Opponent:
Discards:
You:
Deck: ############################################ (44)
Hand: 2D 3D 5D 2O 5O 9J 5V
Score: -40 (You) vs. 0 (Opponent). Draw from?
n
You draw a card from the deck.
Then my opponent gets a turn:
Your opponent plays the InvD.
Your opponent draws a card from the deck.
And I get another turn:
Deserts:
Opponent: Inv (-40)
Discards:
You: Inv (-40)
Oceans:
Opponent:
Discards:
You:
Mountains:
Opponent:
Discards:
You:
Jungles:
Opponent:
Discards:
You:
Volcanoes:
Opponent:
Discards:
You:
Deck: ########################################## (42)
Hand: 2D 3D 5D 2O 5O 6M 9J 5V
Score: -40 (You) vs. -40 (Opponent). Your play?
2d
You play the 2D.
Deserts:
Opponent: Inv (-40)
Discards:
You: Inv 2 (-36)
Oceans:
Opponent:
Discards:
You:
Mountains:
Opponent:
Discards:
You:
Jungles:
Opponent:
Discards:
You:
Volcanoes:
Opponent:
Discards:
You:
Deck: ########################################## (42)
Hand: 3D 5D 2O 5O 6M 9J 5V
Score: -36 (You) vs. -40 (Opponent). Draw from?
n
You draw a card from the deck.
We continue on like that until the deck is exhausted.
You can get the code I'm using above at:
That code functions as a trivial line-oriented client and server. To play a card just feed it a card value and suit in the form (?:[i2-9]|10)[domjv]. Add a "d" to the front of that if you wish to discard instead. To draw, just name a pile or ask for a "n"ew card from the deck: [domjvn].
This week's Ruby Quiz? To build an AI for playing Lost Cities, of course!
You can tie into my server's very simple API buy defining a subclass of Player with a show() and move() method. show() is called for each line of data the server sends to you, and move() is called when the server expects a response. Here's a very DumbPlayer to get you going:
class DumbPlayer < Player
def initialize
super
@data = ""
@plays = nil
@discard = nil
end
def show( game_data )
if game_data =~ /^You (?:play|discard)/
@plays = nil
@discard = nil
end
@data << game_data
end
def move
if @data.include?("Draw from?")
draw_card
else
make_move
end
ensure
@data = ""
end
private
def draw_card
"n"
end
def make_move
if @plays.nil? and @data =~ /Hand: (.+?)\s*$/
@plays = $1.split.map { |card| card.sub(/Inv/, "I") }
@discard = "d#{@plays.first}"
end
if @plays.empty?
@discard
else
@plays.shift
end
end
end
If you save that as dumb_player.rb, you could play against it with something like:
$ ruby lost_cities.rb 9016
... then in a different terminal ...
$ ruby lost_cities.rb localhost 9016 dumb_player.rb
Let the games begin!
Quiz Summary
There's nothing too tough in this quiz, but it turned out to be pretty time consuming for me. Not because it required a ton of code for a solution, but because I kept playing against my solution and tweaking its behavior. Of course, as Daniel Sheppard pointed out, I should have tried him against DumbPlayer a little more:
$ ruby lost_cities.rb localhost 61676 risk_player.rb
Final Score: -21 (You) vs. -60 (Opponent).
Congratulations, you win.
$ ruby lost_cities.rb localhost 61676 risk_player.rb
Final Score: -32 (You) vs. -1 (Opponent).
I'm sorry, you lose.
$ ruby lost_cities.rb localhost 61676 risk_player.rb
Final Score: -43 (You) vs. -43 (Opponent).
The game is a draw.
$ ruby lost_cities.rb localhost 61676 risk_player.rb
Final Score: -51 (You) vs. 5 (Opponent).
I'm sorry, you lose.
"You" above would be RiskPlayer and "Opponent" is DumbPlayer. I guess DumbPlayer isn't so dumb and RiskPlayer doesn't take enough risks.
There were also some issues with the server and DumbPlayer that may have made it harder for people to mess around with this problem. I apologize for that.
Daniel's own solution is very interesting, but quite a bit of code to show here. Let me see if I can hit a highlight or two. First, I'll let Daniel explain how the code was built:
Designing an AI for a game which you've never played is a pretty
daunting task... So I let the computer do the work with a little bit
of genetics.
The rule_player.rb file contains the basic framework for parsing the
input and storing the knowledge and also the rules, as well as an
extra player named "MultiplierPlayer" which allows the rules to be
given different weightings
The breeder.rb file contains the breeding system. It creates a bunch
of MultiplierPlayers with different weightings and plays them against
each other round-robin style. The 2 players with the most wins under
their belts get bred to form extra players and the worst players get
dropped. The players are then saved off in a yaml file. Being yaml,
it's easy to edit, so if you think you know better than the breeder,
it's easy to throw your figures into the race.
...
That YAML file is really neat. Here's a peek at a small slice of it:
---
-
-
- 1
- 1
- 0
- 0
- 0
- 0
- 0
# ...
-
- Rules::PlayLowestFirst
- Rules::MaximumScoreEndGame
- Rules::IgnoreUnusable
- Rules::DiscardUnusable
- Rules::DepriveOpponent
- Rules::AvoidLateInvestment
- Rules::ExpectedInvestmentValue
The bottom section has the rules that the genetics system is considering. The top Array lists the weights the winner settled on, favoring the first two rules clearly.
The player that puts the data to use is trivial:
require 'yaml'
class BredPlayer < MultiplierPlayer
def initialize
raise "No Data File" unless File.exist?('data2.yaml')
multipliers, rule_names = File.open('data2.yaml','r') do |f|
YAML::load(f)
end
super(rule_names, multipliers[0])
end
end
This is all designed to work with a testing framework Daniel provided, of course. The really interesting part of Daniel's code, to me, was breeder.rb. If you're at all interested in genetic programming, do look around in there. It even has comments to drive you through the evolution process. Neat stuff.
Though my solution turns out to be a pretty bad player, it does have the elements any smarter solution would need. Its flaw is in the logic, which is just me being a bad teacher for computer strategy. Let's look past that and examine the code anyway:
class RiskPlayer < Player
def self.card_from_string( card )
value, land = card[0..-2], card[-1, 1].downcase
Game::Card.new( value[0] == ?I ? value : value.to_i,
Game::LANDS.find { |l| l[0, 1] == land } )
end
def initialize
@piles = Hash.new do |piles, player|
piles[player] = Hash.new { |pile, land| pile[land] = Array.new }
end
@deck_size = 60
@hand = nil
@last_dicard = nil
@action = nil
@done = false
end
# ...
There's nothing tricky in there. The class method is a helper for converting a String like "InvV" into and actual card object.
Then initialize() just prepares the instance data this class needs to track. The @piles variable looks a little ugly because I wanted it to invent the data structure as needed. It's just a Hash containing three keys: :me, :them, and :discards. Each of those is a Hash that contains an Array pile for each land type.
Now the quiz requires a parser for the protocol. Here's the easiest approach I could come up with:
if @done
puts game_data
else
if game_data =~ /^(Your?)(?: opponent)? (play|discard)s? the (\w+)/
card = self.class.card_from_string($3)
if $2 == "play"
if $1 == "You"
@piles[:me][card.land] << card
else
@piles[:them][card.land] << card
end
else
@piles[:discards][card.land] << card
end
@last_discard = nil if $1 == "Your"
end
if game_data =~ /^You(?:r opponent)? picks? up the (\w+)/
@piles[:discards][self.class.card_from_string($1).land].pop
end
if game_data =~ /^\s*Deck:\s+#+\s+\((\d+)\)/
@deck_size = $1.to_i
end
if game_data =~ /^\s*Hand:((?:\s+\w+)+)/
@hand = $1.strip.split.map { |c| self.class.card_from_string(c) }
end
if game_data.include?("Your play?")
@action = :play_card
elsif game_data.include?("Draw from?")
@action = :draw_card
end
@done = true if game_data.include?("Game over.")
end
end
The server notifies you when everything happens and I think it's easier to just track those notifications than it is to track your own moves and/or parse the game board to figure out where everything is. The messages are easy to break down with light Regexp usage.
The else branch of that top level if statement handles the parsing. First it breaks down play/discard messages and places the card on the indicated pile. It pops cards off the discard piles too, as needed. The next bit reads the deck size and your hand from the game board. The third section tracks whether you were asked to play or draw and the final line watches for a "Game over." which causes the code to print the final score (if branch at the top of the method).
With that in place, we can move our focus to responding to play requests:
def move
send(@action)
end
private
def play_card
plays, discards = @hand.partition { |card| playable? card }
if plays.empty?
discard_card(discards)
else
risks = analyze_risks(plays)
risk = risks.max { |a, b| a.last <=> b.last }
return discard_card(@hand) if risk.last < 0
land = risks.max { |a, b| a.last <=> b.last }.first.land
play = plays.select { |card| card.land == land }.
sort_by { |c| c.value.is_a?(String) ? 0 : c.value }.first
"#{play.value}#{play.land[0, 1]}".sub("nv", "")
end
end
def discard_card( choices )
discard = choices.sort_by do |card|
[ playable?(card) ? 1 : 0, playable?(card, :them) ? 1 : 0,
card.value.is_a?(String) ? 0 : card.value ]
end.first
@last_discard = discard
"d#{discard.value}#{discard.land[0, 1]}".sub("nv", "")
end
def draw_card
want = @piles[:discards].find do |land, cards|
not @piles[:me][land].empty? and
cards.last != @last_discard and cards.any? { |card| playable?(card) }
end
if want
want.first[0, 1]
else
"n"
end
end
def playable?( card, who = :me )
@piles[who][card.land].empty? or
@piles[who][card.land].last.value.is_a?(String) or
( not card.value.is_a?(String) and
@piles[who][card.land].last.value < card.value )
end
# ...
First, move() calls the correct action method based on what the server last requested (:play_card or :draw_card).
The main action method, play_card(), splits hands into playable cards and discards. It analyzes the risks of each play and tries to find something fairly safe. If it has no plays or doesn't like its choices, a handoff is made to discard_card().
The discard method just sorts available discards by some general criteria: Can I play this? Can my opponent? How much is it worth? It tries to find something it can't play, the opponent can't play, and that is low in value. It tosses that.
The other action method, draw_card(), just scans the discard piles for cards it wants. If it sees a goody, it will pull from that pile. Otherwise it defaults to a draw from the deck.
Finally, playable?() is just a tool that will tell you if a card can be played currently, by the indicated player.
The missing piece is the risk analysis method:
def analyze_risks( plays )
plays.inject(Hash.new) do |risks, card|
risks[card] = 0
me_total = ( @piles[:me][card.land] +
plays.select { |c| c.land == card.land }
).inject(0) do |total, c|
if c.value.is_a? String
total
else
total + c.value
end
end
risks[card] += 20 - me_total
them_total = @piles[:them][card.land].inject(0) do |total, c|
if c.value.is_a? String
total
else
total + c.value
end
end
high = card.value.is_a?(String) ? 2 : card.value
risks[card] += ( (high..10).inject { |sum, n| sum + n }
- (me_total + them_total) ) / 2
if @piles[:me][card.land].empty?
lands_played = @piles[:me].inject(0) do |count, (land, cards)|
if cards.empty?
count
else
count + 1
end
end
risks[card] -= (lands_played + 1) * 5
end
risks
end
end
end
WARNING: The above code is what needs tweaking to make the AI player smarter.
This method could do whatever thinking is required. It's just expected to return a Hash of playable cards (keys) and their ratings (values). The play_card() method will play the highest rated card, as long as it isn't negative.
I tried to distill a little of how I play down into computer terms here. The method takes into account how many points it has in a given pile and how many more it could play from its hand. It also adds up the total of the cards still at large (above the highest play it can make), and assumes it could luck into half of those. Finally, it adds a penalty to the rating for each new pile started. It's usually a mistake to play too many piles in Lost Cities, because you don't have time to finish them all off. Again, this logic needs further refinement.
For yet another spin on rules, Adam Shelly sent in a solution yesterday that has a whole bunch of criteria it bases decisions on. Check out this list:
#rules affecting play/hold decision :
#positive values mean play, negative mean hold
@prules = {:rule_inSequence=>[0.6,0.8],
:rule_lowCard=>[0.1,0.0],
:rule_lowCards=>[0.2,0.0],
:rule_highCard=>[-0.3,0.1],
:rule_highCards=>[-0.2,0.2],
:rule_investments=>[0.1,-0.2],
:rule_onInvestments=>[0.5,0.7],
:rule_holdingInvestments=>[-0.2,0.0],
:rule_investmentWithHope=>[0.5,0.3],
:rule_investmentWithoutHope=>[-0.6,-1.0],
:rule_group10=>[0.5,-0.4],
:rule_group15=>[0.6,-0.3],
:rule_group20=>[0.7,-0.2],
:rule_group25=>[0.9,-0.1],
:rule_total20 =>[0.35,1.0],
:rule_total25 =>[0.6,1.0],
:rule_suitStarted=>[0.7,0.9],
:rule_closeToPrevious=>[0.4,0.5],
:rule_multiplier2=>[0.4,0.8],
:rule_multiplier3=>[0.5,0.9],
:rule_onUnplayed=>[-0.5,-1.0],
:rule_heHasPlayed=>[-0.1,0.0],
:rule_heHasPlayed10=>[-0.2,0.0],
:rule_heHasPlayed20=>[-0.3,0.0],
:rule_handNegative=>[0.5,0.9],
:rule_mustPlays=>[-0.3,1.0],
:rule_lowerInHand=>[-0.5,-0.4],
:rule_highestInHand=>[-0.1,-0.01],
:rule_2followsInvest=>[0.3,0.5],
:rule_finishGame=>[0.0,2.0],
:rule_possibleBelow=>[-0.2,-0.05],
:rule_possibleManyBelow=>[-0.4,-0.1]}
#rules affecting keep/discard decision :
#positive values mean keep, negative mean discard
@drules = {:rule_useless2me=>[-0.5, 0.1],
:rule_useless2him=>[-0.2,0.1],
:rule_useful2him=>[0.4,0.5],
:rule_useful2me=>[0.3,0.3],
:rule_heHasPlayed=>[0.1,0.3],
:rule_singleton=>[-0.2,-0.1],
:rule_noPartners=>[-0.3,-0.3],
:rule_wantFromDiscard=>[0.3,0.5],
:rule_belowLowestPlayable=>[-0.2,0.0],
:rule_dontDiscardForever=>[0.5,1]}
# ...
Those numbers are weights, one set for early in the game and another for late. Cards are ranked by these criteria which allows plays/discards to be found. These weights are hand tuned, from Adam's experience.
Many thanks to all who fiddled with the game and especially to those who even tried to build a player.
Tomorrow we have the very core of what makes programmers into programmers... Talking barnyard animals, of course.
