[QUIZ] Lost Cities (#51)
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:
3. Enjoy!
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
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:
http://rubyquiz.com/lost_cities.rb
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:
#!/usr/local/bin/ruby -w
class DumbPlayer < Player
def initialize
@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!
Benedikt Heinen
(partially) related to that:
There is some more info about the game (including rules [incl. italian and
spanish translations]) at:
http://www.boardgamegeek.com/viewitem.php3?gameid=50
Benedikt
ALLIANCE, n. In international politics, the union of two thieves who
have their hands so deeply inserted in each other's pockets that
they cannot separately plunder a third.
(Ambrose Bierce, The Devil's Dictionary)
Bob Showalter
AI's. When you include this module in your Player class, it adds a
number of attributes and methods to help you with the current game
state. It automatically determines what cards are in your hand, which
cards have been played, which cards are known to be in your opponents
hand (because they were picked up from the discard piles). It can tell
which cards are playable or not (by you or by your opponent), and more.
It's designed to work seamlessly with James' lost_cities.rb game engine
and with Daniel Sheppard's harness.
player_helper.rb:
# = PlayerHelper
#
# include this module in your player class to provide
# parsing of the game data provided through the show
# method.
#
# Your player class needs to provide two methods:
#
# play_card - called when it's your turn to play a card.
# return the card to play, or 'd' + card to
# discard a card.
# draw_card - called when it's your turn to draw a card.
# return the pile to draw from [domjv], or 'n'
# to draw from the deck.
#
# The default methods implement the DumbPlayer logic, so the
# simplest player would be:
#
# require 'player_helper'
# class SimplePlayer < Player
# include PlayerHelper
# end
#
module PlayerHelper
# Last error message returned from engine, or nil if no error
attr_reader :error
# Hash by land. Each entry is an Array of Game::Card's discarded
# for that land.
attr_reader :discards
# Array of "unseen" Game::Card's. These are either in the deck or in
# the opponents hand (but not seen by the current player)
attr_reader :unseen
# Number of cards still available in the deck
attr_reader :deck
# Current player's hand (Array of Game::Card's)
attr_reader :my_hand
# Hash by land for current player. Each entry is an Array of
# Game::Card's played to that land.
attr_reader :my_lands
# Cards *known* to be in opponent's hand (Array of Game::Card's).
# These are determined by the discards the opponent picks up. Cards
# that the opponent was initially dealt or have drawn from the deck
# will appear in :unseen
attr_reader :op_hand
# Hash by land for Opponent. Each entry is an Array of
# Game::Card's played to that land.
attr_reader :op_lands
@@echo = false
def self.included(klass)
# enables echoing of game data from engine
def klass.echo_on
@@echo = true
end
# disables echoing of game data from engine
def klass.echo_off
@@echo = false
end
end
# intializes game state data
def initialize
super
@op_hand = Array.new
@my_hand = Array.new
@unseen = Array.new
@op_lands = Hash.new
@discards = Hash.new
@my_lands = Hash.new
Game::LANDS.each do |land|
@op_lands[land] = Array.new
@discards[land] = Array.new
@my_lands[land] = Array.new
end
moveover
gameover
end
# draws one or more cards in readable format
def draw_cards(*cards)
cards.flatten.map {|c| c.to_s}.join(' ')
end
# clears some game state data when game ends. helpful when the
# same player object is used for multiple games.
def gameover
op_hand.clear
end
def show( game_data )
puts game_data.chomp if @@echo
game_data.strip!
if game_data =~ /^(\S+):/ && @my_lands.has_key?($1.downcase)
@land = $1.downcase
return
end
case game_data
when /Hand:\s+(.+?)\s*$/
my_hand.replace($1.split.map { |c| Game::Card.parse(c) })
when /Opponent:(.*?)(?:\(|$)/
op_lands[@land].replace($1.split.map { |c|
Game::Card.parse("#{c}#{@land[0,1]}") })
when /Discards:(.*?)(?:\(|$)/
discards[@land].replace($1.split.map { |c|
Game::Card.parse("#{c}#{@land[0,1]}") })
when /You:(.*?)(?:\(|$)/
my_lands[@land].replace($1.split.map { |c|
Game::Card.parse("#{c}#{@land[0,1]}") })
when /Your opponent (?:plays|discards) the (\w+)/
c = Game::Card.parse($1)
i = op_hand.index(c)
op_hand.delete_at(i) if i
when /Your opponent picks up the (\w+)/
op_hand << Game::Card.parse($1)
when /Draw from\?/
@action = :draw_card
when /Your play\?/
@action = :play_card
when /^Error:/
@error = game_data
when /Deck:.*?(\d+)/
@deck = $1
when /Game over\./
gameover
else
#puts "Unhandled game_data: #{game_data}"
end
end
def move
find_unseen if error.nil?
send(@action)
ensure
moveover
end
# returns a full deck of cards
def full_deck
Game::LANDS.collect do |land|
(['Inv'] * 3 + (2 .. 10).to_a).collect do |value|
Game::Card.new(value, land)
end
end.flatten
end
# after all the board data has been received, determines
# which cards from the deck have not yet been seen. these
# are either in the deck or known to be in the opponent's hand.
def find_unseen
unseen.replace(full_deck)
(my_hand + op_hand + my_lands.values +
op_lands.values + discards.values).flatten.each do |c|
i = unseen.index(c) or next
unseen.delete_at(i)
end
end
def moveover
@error = nil
end
# naive draw method: always draws from deck
# (override this in your player)
def draw_card
"n"
end
# naive play method: plays first playable card in hand,
# or if no legal play, just discards the first card in
# the hand.
# (override this in your player)
def play_card
card = @my_hand.find { |c| live?(c) }
return card.to_play if card
"d" + @my_hand.first.to_play
end
# returns true if card is playable on given lands. cards
# that are not live can never be played, so are just dead
# weight in your hand (although they may be useful to your
# opponent; you can check this with live?(card, op_lands).)
def live?(card, lands = @my_lands)
lands[card.land].empty? or lands[card.land].last <= card
end
end
# extend the Game::Card class with some helpers
class Game::Card
# define a comparison by rank and land.
# useful for sorting hands, etc.
include Comparable
def <=>(other)
result = value.to_i <=> other.value.to_i
if result == 0
result = land <=> other.land
end
result
end
# returns true if two cards have same land
def same_land?(other)
land == other.land
end
# parse a card as shown by Game#draw_cards back to a
# Game::Card object. Investment cards can be specified
# as 'I' or 'Inv'.
def self.parse(s)
value, land = s.strip.downcase.match(/(.+)(.)/).captures
if value =~ /^i(nv)?$/
value = 'Inv'
else
value = value.to_i
value.between?(2,10) or raise "Invalid value"
end
land = Game::LANDS.detect {|l| l[0,1] == land} or
raise "Invalid land"
new(value, land)
end
# converts a card to its string representation (value + land)
def to_s
"#{value}#{land[0,1].upcase}"
end
# converts a card to its play representation
def to_play
"#{value.is_a?(String) ? value[0,1] : value}#{land[0,1]}".downcase
end
end
James Edward Gray II
tweaking the risk analysis. Here's my passible first crack at a
solution.
Hopefully someone will step in with a player that slaughters him...
James Edward Gray II
#!/usr/local/bin/ruby -w
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
end
def show( game_data )
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 =~ /^\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
end
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 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
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
end
__END__
Daniel Sheppard
trying to draw cards from a pile that it can't, resulting in an infinite
loop of "There are no cards there" errors. This could be due to
line-wrapping in the email though - I already had to fix up this code:
cards.last != @last_discard and cards.any? { |card| playable?
(card) }
So that it was all on one line, otherwise it tries to call playable with
no args.
(to make your player work with my tester, I also changed all references
of "@hand" to "@my_hand").
You player works successfully against the dumb_player - I guess that's
how you tested it. But it doesn't play against itself or my player
(which I'll post in a couple of hours).
When you designed your game, you probably should have kept the player
intelligence separate from the player record keeping. I probably would
have also put the human-readable rendering of the output in the client
and made the server just spit out the data - but I'm guessing the
original focus of your game was PvP, and these suggestions only really
affect the design in the AI situation.
#####################################################################################
This email has been scanned by MailMarshal, an email content filter.
#####################################################################################
Bob Showalter
> I've developed a "helper" module to assist those working on Lost Cities
> AI's.
Erm, that echo_on/echo_off thing didn't work they way I wanted it to.
Here's an attempt to fix it. What I'm trying to do is to let you do this:
class MyPlayer < Player
include PlayerHelper
echo_on # enable echoing
def play_card
...blah blah
end
end
So I want echo_on to be a class or module method, and have a class
variable in MyPlayer that tracks the echo flag. My first version had a
single echo flag shared across all classes that included PlayerHelper.
Being a clueless Ruby noob, I'm probably going about it the wrong way.
I don't think I'm smart enought to create an actual AI, but this much
has been fun...
Here's the new version:
module PlayerHelper
# in the opponents hand (but not seen by the current player)
attr_reader :unseen
# Number of cards still available in the deck
attr_reader :deck
# Current player's hand (Array of Game::Card's)
attr_reader :my_hand
# Hash by land for current player. Each entry is an Array of
# Game::Card's played to that land.
attr_reader :my_lands
# Cards *known* to be in opponent's hand (Array of Game::Card's).
# These are determined by the discards the opponent picks up. Cards
# that the opponent was initially dealt or have drawn from the deck
# will appear in :unseen
attr_reader :op_hand
# Hash by land for Opponent. Each entry is an Array of
# Game::Card's played to that land.
attr_reader :op_lands
def self.included(klass)
end
def show( game_data )
puts game_data.chomp if self.class.class_eval "@echo"
Daniel Sheppard
http://members.iinet.net.au/~soxbox/ruby_quiz_51/
Designing an AI for a game which you've never played is a pretty
daunting task. I created a RulePlayer that evaluates each possible card
based on Rules. I then created a bunch of rules that seemed to make
sense to me. However, I didn't know enough to be able to prioritize my
rules. Never playing the game, I don't know what strategies work, and
which ones fall on their faces. 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.
The bred_player.rb loads up the data from the yaml file into a player
suitable for use with the game.
The lost_cities_test.rb file is almost the same as that posted earlier -
it pits players against each other in much the same way as the breeder
file does - I just made it ignore players that require arguments to
initialize, so that I could have the RulePlayer and MultiplierPlayer
ignored.
After a few rounds of breeding, it seems that the only rules of any
worth that I picked up are PlayLowestFirst and MaximumScoreEndGame. I
tried manually introducing some of the other rules, but they kept on
getting bred out. Both of those a rules only affecting the playing of
cards - it seems that my rules affecting the drawing and discarding of
cards are pretty much useless, or just aren't being given the right
weighting.
Rules::PlayLowestFirst 1.0000
Rules::MaximumScoreEndGame 1.0000
Rules::IgnoreUnusable 0.0000
Rules::DiscardUnusable 0.0000
Rules::DepriveOpponent 0.0000
Rules::AvoidLateInvestment 0.0000
Rules::ExpectedInvestmentValue 0.0000
Things to note:
- The KnownGame class keeps track of any cards the opponent
picks up, so that you know part of the opponent's hand. My rules don't
take advantage of this, but I think it would be great if used wisely.
- The breeder plays only 5 games with each pairing, and uses the
same 5 decks across all pairings (by using random seeds). This might
result in players getting dismissed due to an unlucky deck, but it runs
too slowly to up it any further.
- If the game takes longer than 300 turns, it's considered a
writeoff, and the players involved are put at the end of the list - this
is usually because both player is a little bit enthusiastic about
picking up discards, and nobody draws from the deck. I don't know if
this will affect legitimate strategies.
- This type of system is notorious for breeding players that are
good at playing against themselves. I always check the player in a
series of known games against dumb_player.rb to make sure that it's
actually degenerating in general play.
It seems to come out pretty well against DumbPlayer, and kicks
RiskPlayer's butt (who always seems to get beaten by DumbPlayer too).
> ruby lost_cities_test.rb 100 543991 dumb_player.rb bred_player.rb
Class Wins Avg. Min. Max.
BredPlayer 55 -2.19 -81.00 47.00
DumbPlayer 45 -9.40 -74.00 78.00
> ruby lost_cities_test.rb 10 543991 dumb_player.rb risk_player
> bred_player.rb
Class Wins Avg. Min. Max.
BredPlayer 14 -4.85 -74.00 29.00
DumbPlayer 13 -19.20 -73.00 28.00
RiskPlayer 3 -60.95 -108.00 -22.00
James Edward Gray II
> Hmmm.... tried running your client through my tester, and it ends up
> trying to draw cards from a pile that it can't, resulting in an
> infinite
> loop of "There are no cards there" errors.
I didn't test my player using your tester, so it may not work there.
> You player works successfully against the dumb_player - I guess that's
> how you tested it.
Na, I played against it.
> When you designed your game, you probably should have kept the player
> intelligence separate from the player record keeping.
Well, I did design it for the players to be at opposite ends of a
socket, communicating through a protocol.
I do agree that I made a few mistakes in the design though. Sorry
about that.
James Edward Gray II
James Edward Gray II
> Here's my overly complicated player.
This is really cool stuff. Thanks for sharing!
James Edward Gray II
Anthony Moralez
On 10/18/05, Daniel Sheppard <dan...@pronto.com.au> wrote:
> Hmmm.... tried running your client through my tester, and it ends up
> trying to draw cards from a pile that it can't, resulting in an infinite
> loop of "There are no cards there" errors. This could be due to
> line-wrapping in the email though - I already had to fix up this code:
>
> cards.last != @last_discard and cards.any? { |card| playable?
> (card) }
>
> So that it was all on one line, otherwise it tries to call playable with
> no args.
>
> (to make your player work with my tester, I also changed all references
> of "@hand" to "@my_hand").
Thanks for those fixes. I found the other problem. Risk player keeps
track of the discards and his last discard but never notices if he
picks one up. Below are the fixes I used to get it to run. But I
think I might have changed it's behavior.
> > -----Original Message-----
> > From: James Edward Gray II [mailto:ja...@grayproductions.net]
> > Sent: Wednesday, 19 October 2005 8:18 AM
> > To: ruby-talk ML
> > Subject: Re: [SOLUTION] Lost Cities (#51)
> >
> > 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
@piles[:discard][discard.land].delete 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 (not cards.find { |card| @my_hand.include? card } ) and
James Edward Gray II
> Thanks for those fixes. I found the other problem. Risk player keeps
> track of the discards and his last discard but never notices if he
> picks one up.
Oh, good find. That's a bug.
Actually, he never notices if ANYONE picks up a discard. Oops.
Attached is a fixed version, zipped to prevent wrapping issues.
My thanks to you both, for helping me fix this.
James Edward Gray II
James Edward Gray II
> #!/usr/local/bin/ruby -w
>
> class DumbPlayer < Player
> def initialize
super
> @data = ""
>
> @plays = nil
> @discard = nil
> end
# ...
The above addition allows DumbPlayer to play from the server side as
well as the client. This is an oversight on my part. Sorry.
James Edward Gray II
Anthony Moralez
know it's pretty silly but against other AI's it might work. Against a
human not terribly challenging but you do have to score more than 0.
discard_player.rb:
class DiscardPlayer < Player
def initialize
@data = ""
super
end
def show( game_data )
@data << game_data
end
def move
if @data.include?("Draw from?")
"n"
else
if @data =~ /Hand: (.+?)\s*$/
"d#{$1.split.first.sub(/nv/,"")}"
end
end
ensure
@data = ""
end
end
Anthony Moralez
initialize method also.
Adam Shelly
My first idea was to build a bunch of rules based on notes I took
while playing the game:
"save high runs. play sequential cards right away. play inv early,
or hold til have more cards.
check opponent plays to recognize cards you shouldn't wait for"
But the rules were getting more and more complicated to code. So I
simplified and made a bunch of rules that assigned 1 or 0 to each card
based on simple facts
inSequence, lowCard, holding10points, useless2me..
Then I added weights for each rule, and used them to rank the cards
along 2 axes: Play..Hold and Keep..Discard. The card in the hand
with the biggest value is then played or discarded.
There are actually 2 sets of weights, one for early in the game, and
one for late in the game.
Then I played a bunch of games, and hand tuned the rules to try to
prevent stupid choices.
My next goal was to fill an arena with players and have an
evolutionary process - winners replace losers with a child with a
randomly modified weight; repeat until one dominates. But I haven't
had made much progress this way yet. So here's my original
hand-tuned version. It consistently beats risk_player and
discard_player. It beat me once or twice. But it can only beat
dumb_player 2/3rds of the time...
-Adam
Adam Shelly
> My next goal was to fill an arena with players and have an
> evolutionary process - winners replace losers with a child with a
> randomly modified weight; repeat until one dominates.
I saw Daniel Sheppard's solution after I posted mine. I'm impressed.
I modified my arena based on some ideas from his breeder and tried
to evolve my ruleset all day. I'm not sure it got much better, but I
think it beats me more often.
To run, add these 2 files to the same directory as the other one
-EvolvedPlayer.rb------
require 'ads_lc_player'
class EvolvedPlayer < ADS_LC_Player
def initialize
super
load "gene.yaml"
end
#fix for bug in ADS_LC_Player where it would draw from a discard
#right after playing on that suit and making the wanted card useless
def draw_card
@dwanted.each_with_index{|w,i|
if w && (@dpile[i][-1] > (@land[i][-1]||0))
@dpile[i].pop
return [S.index(i)].pack("C")
end
}
@deckcount-=1
"n"
end
end
-------
-gene.yaml-----
--- !ruby/object:Gene
drules:
:rule_noPartners:
- -0.3
- -0.3
:rule_useless2me:
- -0.5
- 0.1
:rule_wantFromDiscard:
- 0.3
- 0.5
:rule_useless2him:
- -0.2
- 0.1
:rule_belowLowestPlayable:
- -0.2
- 0.0
:rule_useful2him:
- 0.4
- 0.5
:rule_dontDiscardForever:
- 0.5
- 1
:rule_useful2me:
- 0.3
- 0.424953141133301
:rule_singleton:
- -0.269603526452556
- -0.1
:rule_heHasPlayed:
- 0.1
- 0.3
name: hgklnqu
parent: hgklnq
prules:
:rule_highestInHand:
- -0.1
- -0.0132171112811193
:rule_investments:
- 0.10915231165709
- -0.214938909909688
:rule_suitStarted:
- 0.7
- 0.9
:rule_group15:
- 0.6
- -0.338061462133191
:rule_inSequence:
- 0.654255492263474
- 0.905814079008997
:rule_heHasPlayed10:
- -0.2
- 0.0
:rule_2followsInvest:
- 0.3
- 0.5
:rule_onInvestments:
- 0.5
- 0.7
:rule_closeToPrevious:
- 0.571291934791952
- 0.5
:rule_group20:
- 0.7
- -0.24812678352464
:rule_lowCard:
- 0.1
- 0.0
:rule_heHasPlayed20:
- -0.3
- 0.0
:rule_multiplier2:
- 0.4
- 0.8
:rule_holdingInvestments:
- -0.458828900489379
- 0.0
:rule_finishGame:
- 0.0
- 2.06754154443775
:rule_handNegative:
- 0.5
- 0.9
:rule_group25:
- 0.9
- -0.17002231310729
:rule_lowCards:
- 0.253758069175279
- 0.0
:rule_possibleBelow:
- -0.2
- -0.0697354671487119
:rule_multiplier3:
- 0.649637156224344
- 1.07591888221214
:rule_investmentWithHope:
- 0.726016686472576
- 0.425265068525914
:rule_total20:
- 0.35
- 1.0
:rule_mustPlays:
- -0.32988673124928
- 1.0
:rule_highCard:
- -0.3
- 0.1
:rule_investmentWithoutHope:
- -0.6
- -1.0
:rule_possibleManyBelow:
- -0.46776403458789
- -0.1
:rule_onUnplayed:
- -0.819403649667397
- -1.0
:rule_total25:
- 0.6
- 1.0
:rule_highCards:
- -0.2
- 0.2
:rule_lowerInHand:
- -0.88520639540273
- -0.4
:rule_heHasPlayed:
- -0.14072827748023
- 0.0
:rule_group10:
- 0.61925460502971
- -0.4
-----
Daniel Sheppard
the discovery that I'd misunderstood the scoring system - I decided to
write another player from scratch (though reusing the knowledge gatherer
from my bredplayer).
http://members.iinet.net.au/~soxbox/always_positive.rb
My new player will not play any cards into a land unless he has enough
cards and enough time to overcome the -20 starting penalty for a land.
He'll pick up any cards that help him, and once he hits the endgame,
will start playing high-cards rather than low.
Some areas where you'd probably get some improvement are in the
discarding of cards, which is pretty rudimentary. It should probably
discard in order of unusable_for_anybody_ever ->
unusable_for_opponent_ever -> minimise_opponent_points. He'd probably be
improved further by actually taking a chance towards the start of the
game if it can't get a guaranteed hand.
Playing all the players against each other with 50 games in each matchup
(everybody plays 300 total):
Class Wins Avg. Min. Max. Time
AlwaysPositive 222 22.52 0.00 76.00 31.49
ADS_LC_Player 220 41.05 -71.00 266.00 80.94
EvolvedPlayer 203 27.52 -101.00 217.00 75.84
BredPlayer 164 3.75 -149.00 91.00 63.58
DiscardPlayer 113 0.00 0.00 0.00 11.45
DumbPlayer 110 -11.44 -88.00 65.00 14.26
RiskPlayer 16 -41.51 -120.00 -7.00 25.13
As the top 3 are so close, I did separates run of 200 games between each
of them:
Class Wins Avg. Min. Max. Time
ADS_LC_Player 121 39.94 -44.00 154.00 49.91
AlwaysPositive 78 28.09 0.00 104.00 21.63
So it seems that ADS_LC_Player is actually better than the evolved
player (so much for genetics), and they're both better than my
AlwaysPositive player, but I came out on top in the full match because I
ALWAYS beat RiskPlayer and either win or draw against DiscardPlayer.
I'm guessing that my player would be better at beating an amateur
player, but the ADS_LC_Player would provide more challenge for an
experienced player.
The "Time" column is indicative only - it measures the time taken for
the game.play and game.draw moves to occur, but that also includes a
bunch of show calls to both players, so it skews the figures.
Ruby Quiz
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 'rule_player'
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:
#!/usr/local/bin/ruby -w
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:
def show( game_data )
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:
# ...
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.