# \[SUMMARY\] Lost Cities (#51) **URL:** \ **Category:** ruby-talk\ **Created:** [20 October 2005 13:01 UTC](https://rubytalk.org/t/summary-lost-cities-51/21743 "2005-10-20T13:01:07Z")\ **Posts on this page:** 1\ **Page:** 1
**Author:** ![James\_Edward\_Gray\_II](https://avatars.discourse-cdn.com/v4/letter/j/ea5d25/32.png) [@James\_Edward\_Gray\_II](https://rubytalk.org/u/James_Edward_Gray_II)\ **Post date:** [20 October 2005 13:01 UTC](https://rubytalk.org/t/summary-lost-cities-51/21743/1 "2005-10-20T13:01:07Z")
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 '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: > >     # ... >      >     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.