OSDN Git Service

Enhanced syntax of Floodgate time configuration file. Now it supports "set sacrifice...
[shogi-server/shogi-server.git] / shogi_server / pairing.rb
index 01f4fe0..4c2583b 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
@@ -24,35 +24,67 @@ module ShogiServer
   class Pairing
 
     class << self
-      def default_factory
-        return sort_by_rate_with_randomness
+      def default_factory(options)
+        return least_diff_pairing(options)
       end
 
-      def sort_by_rate_with_randomness
-        return [ExcludeSacrificeGps500.new,
+      def sort_by_rate_with_randomness(options)
+        return [LogPlayers.new,
+                ExcludeSacrifice.new(options[:sacrifice]),
                 MakeEven.new,
                 SortByRateWithRandomness.new(1200, 2400),
-                StartGame.new]
+                StartGameWithoutHumans.new]
       end
 
-      def random_pairing
-        return [ExcludeSacrificeGps500.new,
+      def random_pairing(options)
+        return [LogPlayers.new,
+                ExcludeSacrifice.new(options[:sacrifice]),
                 MakeEven.new,
                 Randomize.new,
-                StartGame.new]
+                StartGameWithoutHumans.new]
       end
 
-      def match(players)
-        logics = default_factory
+      def swiss_pairing(options)
+        return [LogPlayers.new,
+                ExcludeSacrifice.new(options[:sacrifice]),
+                MakeEven.new,
+                Swiss.new,
+                StartGameWithoutHumans.new]
+      end
+
+      def least_diff_pairing(options)
+        return [LogPlayers.new,
+                ExcludeSacrifice.new(options[:sacrifice]),
+                MakeEven.new,
+                LeastDiff.new,
+                StartGameWithoutHumans.new]
+      end
+
+      def floodgate_zyunisen(options)
+        return [LogPlayers.new,
+                ExcludeUnratedPlayers.new,
+                ExcludeSacrifice.new(options[:sacrifice]),
+                MakeEven.new,
+                LeastDiff.new,
+                StartGameWithoutHumans.new]
+      end
+
+      def match(players, logics)
         logics.inject(players) do |result, item|
           item.match(result)
+          result
         end
       end
     end # class << self
 
 
+    # Make matches among players.
+    # @param players an array of players, which should be updated destructively
+    #        to pass the new list to subsequent logics.
+    #
     def match(players)
       # to be implemented
+      log_message("Floodgate: %s" % [self.class.to_s])
     end
 
     def include_newbie?(players)
@@ -77,38 +109,125 @@ module ShogiServer
         end
       end
       if str_array.empty?
-        log_message("Floodgate: [Players] None is here.")
+        log_message("Floodgate: [Players] Nobody found.")
       else
         log_message("Floodgate: [Players] %s." % [str_array.join(", ")])
       end
     end
   end # Pairing
 
-  class StartGame < 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])
+        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." % 
+        log_warning("Floodgate: There are odd players (%d). %s will not be matched." % 
                     [players.size, players.last.name])
       end
 
       log_players(players)
       while (players.size >= 2) do
         pair = players.shift(2)
-        pair.shuffle!
-        start_game(pair.first, pair.last)
+        start_game_shuffle(pair)
       end
     end
+  end
 
-    def start_game
-      log_message("Floodgate: BLACK %s; WHITE %s" % [p1.name, p2.name])
-      p1.sente = true
-      p2.sente = false
-      Game.new(p1.game_name, p1, p2)
+  # 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
+
+      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 = humans[i]
+            break
+          end
+        end
+        unless pairing_possible
+          log_message("Floodgate: No possible human-human match found")
+          break
+        end
+
+        current_index = pairing_possible
+        j = [0, current_index - 2].max
+        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
+          # 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
+    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
 
@@ -133,18 +252,52 @@ module ShogiServer
   end
 
   class SortByRateWithRandomness < Pairing
-    def initialize(rand1, rand2)
+    def initialize(rand1, rand2, desc=false)
       super()
       @rand1, @rand2 = rand1, rand2
+      @desc = desc
     end
 
     def match(players)
-      super
+      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]
+        "%s %d (+ randomness %d)" % [one.name, one.rate, cur_rate[one] - one.rate]
+      end
+    end
+  end
+
+  class Swiss < Pairing
+    def match(players)
+      super
+      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
+      rest = players - winners
+
+      log_message("Floodgate: Ordering %d winners..." % [winners.size])
+      sbrwr_winners = SortByRateWithRandomness.new(800, 2500, true)
+      sbrwr_winners.match(winners)
+
+      log_message("Floodgate: Ordering the rest (%d)..." % [rest.size])
+      sbrwr_losers = SortByRateWithRandomness.new(200, 400, true)
+      sbrwr_losers.match(rest)
+
+      players.clear
+      [winners, rest].each do |group|
+        group.each {|pl| players << pl}
       end
     end
   end
@@ -153,7 +306,7 @@ module ShogiServer
     def match(players)
       super
       return if less_than_one?(players)
-      one = players.choice
+      one = players.sample
       log_message("Floodgate: Deleted %s at random" % [one.name])
       players.delete(one)
       log_players(players)
@@ -201,7 +354,7 @@ module ShogiServer
     # @sacrifice a player id to be eliminated
     def initialize(sacrifice)
       super()
-      @sacrifice = sacrifice
+      @sacrifice = sacrifice || "gps500+e293220e3f8a3e59f79f6b0efffaa931"
     end
 
     def match(players)
@@ -226,10 +379,179 @@ module ShogiServer
     def match(players)
       super
       return if players.size.even?
-      log_message("Floodgate: there are odd players: %d. Deleting one..." % 
+      log_message("Floodgate: There are odd players (%d). Deleting one of them..." % 
                   [players.size])
       DeletePlayerAtRandom.new.match(players)
     end
   end
 
+  # This pairing algorithm aims to minimize the total differences of
+  # matching players' rates. It also includes penalyties when a match is
+  # same as the previous one or a match is between human players.
+  # It is based on a discussion with Yamashita-san on
+  # http://www.sgtpepper.net/kaneko/diary/20120511.html.
+  #
+  class LeastDiff < Pairing
+    def random_match(players)
+      players.shuffle
+    end
+
+    # Update estimated rate of a player.
+    # 1. If it has a valid rate, return the rate.
+    # 2. If it has no valid rate, return:
+    #   a. If it won the last game, the opponent's rate + 200
+    #   b. If it lost the last game, the opponent's rate - 200
+    #   c. otherwise, return 2150 (default value)
+    #
+    def estimate_rate(player, history)
+      player.estimated_rate = 2150 # default value
+
+      unless history
+        log_message("Floodgate: Without game history, estimated %s's rate: %d" % [player.name, player.estimated_rate])
+        return
+      end
+
+      g = history.last_valid_game(player.player_id)
+      unless g
+        log_message("Floodgate: Without any valid games in history, estimated %s's rate: %d" % [player.name, player.estimated_rate])
+        return
+      end
+
+      opponent_id = nil
+      win         = true
+      case player.player_id
+      when g[:winner]
+        opponent_id = g[:loser]
+        win = true
+      when g[:loser]
+        opponent_id = g[:winner]
+        win = false
+      else
+        log_warning("Floodgate: The last valid game is invalid for %s!" % [player.name])
+        log_message("Floodgate: Estimated %s's rate: %d" % [player.name, player.estimated_rate])
+        return
+      end
+
+      opponent_name = opponent_id.split("+")[0]
+      p = $league.find(opponent_name)
+      unless p
+        log_message("Floodgate: No active opponent found. Estimated %s's rate: %d" % [player.name, player.estimated_rate])
+        return
+      end
+
+      opponent_rate = 0
+      if p.rate != 0
+        opponent_rate = p.rate
+      elsif p.estimated_rate != 0
+        opponent_rate = p.estimated_rate
+      end
+
+      if opponent_rate != 0
+        player.estimated_rate = opponent_rate + (win ? 200 : -200)
+      end
+
+      log_message("Floodgate: Estimated %s's rate: %d" % [player.name, player.estimated_rate])
+    end
+
+    # Return a player's rate based on its actual rate or estimated rate.
+    #
+    def get_player_rate(player, history)
+      if player.rate != 0
+        return player.rate
+      elsif player.estimated_rate != 0
+        return player.estimated_rate 
+      else
+        estimate_rate(player, history)
+        return player.estimated_rate
+      end
+    end
+
+    def calculate_diff_with_penalty(players, history)
+      pairs = []
+      players.each_slice(2) do |pair|
+        if pair.size == 2
+          pairs << pair
+        end
+      end
+
+      ret = 0
+
+      # 1. Diff of players rate
+      pairs.each do |p1,p2|
+        ret += (get_player_rate(p1,history) - get_player_rate(p2,history)).abs
+      end
+
+      # 2. Penalties
+      pairs.each do |p1,p2|
+        # 2.1. same match
+        if (history &&
+            (history.last_opponent(p1.player_id) == p2.player_id ||
+             history.last_opponent(p2.player_id) == p1.player_id))
+          ret += 400
+        end
+
+        # 2.2 Human vs Human
+        if p1.is_human? && p2.is_human?
+          ret += 800
+        end
+      end
+
+      ret
+    end
+
+    def match(players)
+      super
+      if players.size < 3
+        log_message("Floodgate: players are small enough to skip LeastDiff pairing: %d" % [players.size])
+        return players
+      end
+
+      # Reset estimated rate
+      players.each {|p| p.estimated_rate = 0}
+
+      # 10 trials
+      matches = []
+      scores  = []
+      path = ShogiServer::League::Floodgate.history_file_path(players.first.game_name)
+      history = ShogiServer::League::Floodgate::History.factory(path)
+      10.times do 
+        m = random_match(players)
+        matches << m
+        scores << calculate_diff_with_penalty(m, history)
+      end
+
+      # Debug
+      #scores.each_with_index do |s,i|
+      #  puts
+      #  print s, ": ", matches[i].map{|p| p.name}.join(", "), "\n"
+      #end
+
+      # Select a match of the least score
+      min_index = 0
+      min_score = scores.first
+      scores.each_with_index do |s,i|
+        if s < min_score
+          min_index = i
+          min_score = s
+        end
+      end
+      log_message("Floodgate: the least score %d (%d per player) [%s]" % [min_score, min_score/players.size, scores.join(" ")])
+
+      players.replace(matches[min_index])
+    end
+  end
+
+  # This pairing method excludes unrated players
+  #
+  class ExcludeUnratedPlayers < Pairing
+
+    def match(players)
+      super
+
+      log_message("Floodgate: Deleting unrated players...")
+      players.delete_if{|a| a.rate == 0}
+      log_players(players)
+    end
+  end # class ExcludeUnratedPlayers
+
 end # ShogiServer