OSDN Git Service

Renewed year of copyright notice in each file.
[shogi-server/shogi-server.git] / shogi_server / pairing.rb
index 18f0925..6a660ec 100644 (file)
@@ -1,7 +1,7 @@
 ## $Id$
 
 ## Copyright (C) 2004 NABEYA Kenichi (aka nanami@2ch)
-## Copyright (C) 2007-2008 Daigo Moriwaki (daigo at debian dot org)
+## Copyright (C) 2007-2012 Daigo Moriwaki (daigo at debian dot org)
 ##
 ## This program is free software; you can redistribute it and/or modify
 ## it under the terms of the GNU General Public License as published by
 ## along with this program; if not, write to the Free Software
 ## Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 
+require 'shogi_server/util'
+
 module ShogiServer
 
   class Pairing
 
     class << self
-      def default_pairing
-        #return SwissPairing.new
-        return ExcludeSacrifice.new(SwissPairing.new)
-        #return RandomPairing.new
-        #return ExcludeSacrifice.new(RandomPairing.new)
+      def default_factory
+        return swiss_pairing
       end
-    end
 
-    def match(players)
-      if players.size < 2
-        log_message("Floodgate[%s]: too few players [%d]" % 
-                    [self.class, players.size])
-      else
-        log_message("Floodgate[%s]: found %d players. Pairing them..." % 
-                    [self.class, players.size])
+      def sort_by_rate_with_randomness
+        return [LogPlayers.new,
+                ExcludeSacrificeGps500.new,
+                MakeEven.new,
+                SortByRateWithRandomness.new(1200, 2400),
+                StartGameWithoutHumans.new]
       end
-    end
 
-    def start_game(p1, p2)
-      p1.sente = true
-      p2.sente = false
-      Game.new(p1.game_name, p1, p2)
+      def random_pairing
+        return [LogPlayers.new,
+                ExcludeSacrificeGps500.new,
+                MakeEven.new,
+                Randomize.new,
+                StartGameWithoutHumans.new]
+      end
+
+      def swiss_pairing
+        return [LogPlayers.new,
+                ExcludeSacrificeGps500.new,
+                MakeEven.new,
+                Swiss.new,
+                StartGameWithoutHumans.new]
+      end
+
+      def match(players)
+        logics = default_factory
+        logics.inject(players) do |result, item|
+          item.match(result)
+          result
+        end
+      end
+    end # class << self
+
+
+    def match(players)
+      # to be implemented
+      log_message("Floodgate: %s" % [self.class.to_s])
     end
 
     def include_newbie?(players)
       return players.find{|a| a.rate == 0} == nil ? false : true
     end
 
-    def delete_player_at_random(players)
-      return players.delete_at(rand(players.size))
+    def less_than_one?(players)
+      if players.size < 1
+        log_warning("Floodgate: There should be at least one player.")
+        return true
+      else
+        return false
+      end
     end
 
-    def delete_player_at_random_except(players, a_player)
-      candidates = players - [a_player]
-      return delete_player_at_random(candidates)
+    def log_players(players)
+      str_array = players.map do |one|
+        if block_given?
+          yield one
+        else
+          one.name
+        end
+      end
+      if str_array.empty?
+        log_message("Floodgate: [Players] Nobody found.")
+      else
+        log_message("Floodgate: [Players] %s." % [str_array.join(", ")])
+      end
     end
-    
-    def delete_most_playing_player(players)
-      # TODO ??? undefined method `<=>' for nil:NilClass
-      max_player = players.max {|a,b| a.win + a.loss <=> b.win + b.loss}
-      return players.delete(max_player)
+  end # Pairing
+
+
+  class LogPlayers < Pairing
+    def match(players)
+      super
+      log_players(players)
+    end
+  end
+
+  class AbstractStartGame < Pairing
+    def start_game(p1, p2)
+      log_message("Floodgate: Starting a game: BLACK %s vs WHITE %s" % [p1.name, p2.name])
+      p1.sente = true
+      p2.sente = false
+      board = Board.new
+      board.initial
+      Game.new(p1.game_name, p1, p2, board)
+    end
+
+    def start_game_shuffle(pair)
+      pair.shuffle!
+      start_game(pair.first, pair.last)
     end
+  end
+
+  class StartGame < AbstractStartGame
+    def match(players)
+      super
+      if players.size < 2
+        log_warning("Floodgate: There should be more than one player (%d)." % [players.size])
+        return
+      end
+      if players.size.odd?
+        log_warning("Floodgate: There are odd players (%d). %s will not be matched." % 
+                    [players.size, players.last.name])
+      end
 
-    def delete_least_rate_player(players)
-      min_player = players.min {|a,b| a.rate <=> b.rate}
-      return players.delete(min_player)
+      log_players(players)
+      while (players.size >= 2) do
+        pair = players.shift(2)
+        start_game_shuffle(pair)
+      end
     end
+  end
 
-    def pairing_and_start_game(players)
-      return if players.size < 2
-      if players.size % 2 == 1
-        log_warning("#Players should be even: %d" % [players.size])
+  # This tries to avoid a human-human match
+  #
+  class StartGameWithoutHumans < AbstractStartGame
+    def match(players)
+      super
+      log_players(players)
+      if players.size < 2
+        log_warning("Floodgate: There should be more than one player (%d)." % [players.size])
+        return
+      elsif players.size == 2
+        start_game_shuffle(players)
         return
       end
-      sorted = players.sort{ rand < 0.5 ? 1 : -1 }
 
-      pairs = [[sorted.shift]]
-      while !sorted.empty? do
-        if pairs.last.size < 2
-          pairs.last << sorted.shift
+      loop do 
+        humans = get_human_indexes(players)
+        log_message("Floodgate: There are (still) %d humans." % [humans.size])
+        break if humans.size < 2
+
+        pairing_possible = false
+        for i in 0..(humans.size-2)  # -2
+          next if humans[i].odd?
+          if humans[i]+1 == humans[i+1]
+            pairing_possible = i
+            break
+          end
+        end
+        unless pairing_possible
+          log_message("Floodgate: No possible human-human match found")
+          break
+        end
+
+        current_index = pairing_possible
+        j = (current_index == 0 ? current_index : current_index-1)
+        while j < players.size
+          break if players[j].is_computer?
+          j += 1
+        end
+
+        pairing_indexes = []
+        if j == players.size 
+          # no computer player found
+          pairing_indexes << current_index << current_index+1
         else
-          pairs << [sorted.shift]
-        end 
+          # a comupter player found
+          pairing_indexes << current_index << j
+        end
+
+        pair = []
+        pair << players.delete_at(pairing_indexes.max)
+        pair << players.delete_at(pairing_indexes.min)
+        start_game_shuffle(pair)
+      end # loop
+
+      while (players.size >= 2) do
+        pair = players.shift(2)
+        start_game_shuffle(pair)
       end
-      pairs.each do |pair|
-        start_game(pair.first, pair.last)
+    end
+
+    private
+
+    def get_human_indexes(players)
+      ret = []
+      for i in 0..(players.size-1)
+        ret << i if players[i].is_human?
       end
+      return ret
     end
-  end # Pairing
+  end
 
-  class RandomPairing < Pairing
+  class Randomize < Pairing
     def match(players)
       super
-      return if players.size < 2
+      log_message("Floodgate: Randomize... before")
+      log_players(players)
+      players.shuffle!
+      log_message("Floodgate: Randomized after")
+      log_players(players)
+    end
+  end # RadomPairing
+
+  class SortByRate < Pairing
+    def match(players)
+      super
+      log_message("Floodgate: Ordered by rate")
+      players.sort! {|a,b| a.rate <=> b.rate} # decendent order
+      log_players(players)
+    end
+  end
 
-      if players.size % 2 == 1
-        delete_player_at_random(players)
+  class SortByRateWithRandomness < Pairing
+    def initialize(rand1, rand2)
+      super()
+      @rand1, @rand2 = rand1, rand2
+    end
+
+    def match(players, desc=false)
+      super(players)
+      cur_rate = Hash.new
+      players.each{|a| cur_rate[a] = a.rate ? a.rate + rand(@rand1) : rand(@rand2)}
+      players.sort!{|a,b| cur_rate[a] <=> cur_rate[b]}
+      players.reverse! if desc
+      log_players(players) do |one|
+        "%s %d (+ randomness %d)" % [one.name, one.rate, cur_rate[one] - one.rate]
       end
-      pairing_and_start_game(players)
     end
-  end # RadomPairing
+  end
 
-  class SwissPairing < Pairing
+  class Swiss < Pairing
     def match(players)
       super
-      return if players.size < 2
-
-      win_players = players.find_all {|a| a.last_game_win?}
-      remains     = players - win_players
-      if win_players.size >= 2
-        if win_players.size % 2 == 1
-#          if include_newbie?(win_players)
-            remains << delete_player_at_random(win_players)
-#          else
-#            remains << delete_least_rate_player(win_players)
-#          end
-        end         
-        pairing_and_start_game(win_players)
-      else
-        remains.concat(win_players)
+      if players.size < 3
+        log_message("Floodgate: players are small enough to skip Swiss pairing: %d" % [players.size])
+        return
+      end
+
+      path = ShogiServer::League::Floodgate.history_file_path(players.first.game_name)
+      history = ShogiServer::League::Floodgate::History.factory(path)
+
+      winners = []
+      if history
+        winners = players.find_all {|pl| history.last_win?(pl.player_id)}
       end
-      return if remains.size < 2
-      if remains.size % 2 == 1
-        delete_player_at_random(remains)
-        # delete_most_playing_player(remains)
+      rest = players - winners
+
+      log_message("Floodgate: Ordering %d winners..." % [winners.size])
+      sbrwr_winners = SortByRateWithRandomness.new(800, 2500)
+      sbrwr_winners.match(winners, true)
+
+      log_message("Floodgate: Ordering the rest (%d)..." % [rest.size])
+      sbrwr_losers = SortByRateWithRandomness.new(200, 400)
+      sbrwr_losers.match(rest, true)
+
+      players.clear
+      [winners, rest].each do |group|
+        group.each {|pl| players << pl}
       end
-      pairing_and_start_game(remains)
     end
-  end # SwissPairing
+  end
 
-  class ExcludeSacrifice
-    attr_accessor :sacrifice
+  class DeletePlayerAtRandom < Pairing
+    def match(players)
+      super
+      return if less_than_one?(players)
+      one = players.sample
+      log_message("Floodgate: Deleted %s at random" % [one.name])
+      players.delete(one)
+      log_players(players)
+    end
+  end
+
+  class DeletePlayerAtRandomExcept < Pairing
+    def initialize(except)
+      super()
+      @except = except
+    end
+
+    def match(players)
+      super
+      log_message("Floodgate: Deleting a player at rondom except %s" % [@except.name])
+      players.delete(@except)
+      DeletePlayerAtRandom.new.match(players)
+      players.push(@except)
+    end
+  end
+  
+  class DeleteMostPlayingPlayer < Pairing
+    def match(players)
+      super
+      one = players.max_by {|a| a.win + a.loss}
+      log_message("Floodgate: Deleted the most playing player: %s (%d)" % [one.name, one.win + one.loss])
+      players.delete(one)
+      log_players(players)
+    end
+  end
+
+  class DeleteLeastRatePlayer < Pairing
+    def match(players)
+      super
+      one = players.min_by {|a| a.rate}
+      log_message("Floodgate: Deleted the least rate player %s (%d)" % [one.name, one.rate])
+      players.delete(one)
+      log_players(players)
+    end
+  end
 
-    def initialize(pairing)
-      @pairing  = pairing
-      @sacrifice = "gps500+e293220e3f8a3e59f79f6b0efffaa931"
+  class ExcludeSacrifice < Pairing
+    attr_reader :sacrifice
+
+    # @sacrifice a player id to be eliminated
+    def initialize(sacrifice)
+      super()
+      @sacrifice = sacrifice
     end
 
     def match(players)
+      super
       if @sacrifice && 
-         players.size % 2 == 1 && 
+         players.size.odd? && 
          players.find{|a| a.player_id == @sacrifice}
-        log_message("Floodgate: first, exclude %s" % [@sacrifice])
-        players.delete_if{|a| a.player_id == @sacrifice}
+         log_message("Floodgate: Deleting the sacrifice %s" % [@sacrifice])
+         players.delete_if{|a| a.player_id == @sacrifice}
+         log_players(players)
       end
-      @pairing.match(players)
     end
+  end # class ExcludeSacrifice
+
+  class ExcludeSacrificeGps500 < ExcludeSacrifice
+    def initialize
+      super("gps500+e293220e3f8a3e59f79f6b0efffaa931")
+    end
+  end
 
-    # Delegate to @pairing
-    def method_missing(message, *arg)
-      @pairing.send(message, *arg)
+  class MakeEven < Pairing
+    def match(players)
+      super
+      return if players.size.even?
+      log_message("Floodgate: There are odd players (%d). Deleting one of them..." % 
+                  [players.size])
+      DeletePlayerAtRandom.new.match(players)
     end
-  end # class ExcludeSacrifice
+  end
+
 end # ShogiServer