Commit: 24fee2243d10ec025357d52d8034cbc1dcf48338 - shogi-server (git)

shogi-server source

Commit MetaInfo

• Revision: 24fee2243d10ec025357d52d8034cbc1dcf48338 (tree)
• Zeit: 2013-03-20 17:23:36
• Autor: Daigo Moriwaki <beatles@user...>
• Commiter: Daigo Moriwaki

Log Message

[shogi-server] New pairing algorithm: ShogiServer::Pairing::LeastDiff

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.

Ändern Zusammenfassung

• modified: changelog
• modified: shogi_server/league/floodgate.rb
• modified: shogi_server/pairing.rb
• modified: test/TC_floodgate.rb
• modified: test/TC_pairing.rb

Diff

--- a/changelog
+++ b/changelog
@@ -1,3 +1,13 @@
[phone]  Daigo Moriwaki <daigo at debian dot org>
+
+	* [shogi-server]
+	  - New pairing algorithm: ShogiServer::Pairing::LeastDiff
+	    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.
+
 2012-12-30  Daigo Moriwaki <daigo at debian dot org>
 
 	* [shogi-server]

--- a/shogi_server/league/floodgate.rb
+++ b/shogi_server/league/floodgate.rb
@@ -257,6 +257,18 @@ class League
         return rc[:loser] == player_id
       end
 
+      def last_opponent(player_id)
+        rc = last_valid_game(player_id)
+        return nil unless rc
+        if rc[:black] == player_id
+          return rc[:white]
+        elsif rc[:white] == player_id
+          return rc[:black]
+        else
+          return nil
+        end
+      end
+
       def last_valid_game(player_id)
         records = nil
         @@mutex.synchronize do
@@ -269,6 +281,28 @@ class League
         end
         return rc
       end
+
+      def win_games(player_id)
+        records = nil
+        @@mutex.synchronize do
+          records = @records.reverse
+        end
+        rc = records.find_all do |rc|
+          rc[:winner] == player_id && rc[:loser]
+        end
+        return rc
+      end
+
+      def loss_games(player_id)
+        records = nil
+        @@mutex.synchronize do
+          records = @records.reverse
+        end
+        rc = records.find_all do |rc|
+          rc[:winner] && rc[:loser] == player_id
+        end
+        return rc
+      end
     end # class History
 
 

--- a/shogi_server/pairing.rb
+++ b/shogi_server/pairing.rb
@@ -25,7 +25,7 @@ module ShogiServer
 
     class << self
       def default_factory
-        return swiss_pairing
+        return least_diff_pairing
       end
 
       def sort_by_rate_with_randomness
@@ -52,6 +52,14 @@ module ShogiServer
                 StartGameWithoutHumans.new]
       end
 
+      def least_diff_pairing
+        return [LogPlayers.new,
+                ExcludeSacrificeGps500.new,
+                MakeEven.new,
+                LeastDiff.new,
+                StartGameWithoutHumans.new]
+      end
+
       def match(players)
         logics = default_factory
         logics.inject(players) do |result, item|
@@ -62,6 +70,10 @@ module ShogiServer
     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])
@@ -232,17 +244,18 @@ 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, desc=false)
+    def match(players)
       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
+      players.reverse! if @desc
       log_players(players) do |one|
         "%s %d (+ randomness %d)" % [one.name, one.rate, cur_rate[one] - one.rate]
       end
@@ -267,12 +280,12 @@ module ShogiServer
       rest = players - winners
 
       log_message("Floodgate: Ordering %d winners..." % [winners.size])
-      sbrwr_winners = SortByRateWithRandomness.new(800, 2500)
-      sbrwr_winners.match(winners, true)
+      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)
-      sbrwr_losers.match(rest, true)
+      sbrwr_losers = SortByRateWithRandomness.new(200, 400, true)
+      sbrwr_losers.match(rest)
 
       players.clear
       [winners, rest].each do |group|
@@ -364,4 +377,137 @@ module ShogiServer
     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
+
+    def average_rate(players)
+      n=0
+      sum=0
+      players.find_all{|p| p.rate}.each do |p|
+        n += 1
+        sum += p.rate
+      end
+
+      return n > 0 ? sum/n : 2150 # interger
+    end
+
+    # Returns a player's rate value.
+    # 1. If it has a valid rate, return the rate.
+    # 2. If it has no valid rate, return average of the following values:
+    #   a. For games it won, the opponent's rate + 100
+    #   b. For games it lost, the opponent's rate - 100
+    #   (if the opponent has no valid rate, count out the game)
+    #   (if there are not such games, return 2150 (default value)
+    #
+    def get_player_rate(player, history)
+      return player.rate if player.rate != 0
+      return 2150 unless history
+
+      count = 0
+      sum = 0
+
+      history.win_games(player.player_id).each do |g|
+        next unless g[:loser]
+        name = g[:loser].split("+")[0]
+        p = $league.find(name)
+        if p && p.rate != 0
+          count += 1
+          sum += p.rate + 100
+        end
+      end
+      history.loss_games(player.player_id).each do |g|
+        next unless g[:winner]
+        name = g[:winner].split("+")[0]
+        p = $league.find(name)
+        if p && p.rate != 0
+          count += 1
+          sum += p.rate - 100
+        end
+      end
+
+      estimate = (count == 0 ? 2150 : sum/count)
+      log_message("Floodgate: Estimated rate of %s is %d" % [player.name, estimate])
+      return estimate
+    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
+
+      # 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)" % [min_score, min_score/players.size])
+
+      players = matches[min_index]
+    end
+  end
+
 end # ShogiServer

--- a/test/TC_floodgate.rb
+++ b/test/TC_floodgate.rb
@@ -395,6 +395,22 @@ class TestFloodgateHistory < Test::Unit::TestCase
     assert !@history.last_win?("foo")
     assert !@history.last_lose?("hoge")
     assert @history.last_lose?("foo")
+
+    assert_equal("foo", @history.last_opponent("hoge"))
+    assert_equal("hoge", @history.last_opponent("foo"))
+
+    games = @history.win_games("hoge")
+    assert_equal(1, games.size )
+    assert_equal("wdoor+floodgate-900-0-hoge-foo-2", games[0][:game_id])
+    games = @history.win_games("foo")
+    assert_equal(1, games.size )
+    assert_equal("wdoor+floodgate-900-0-hoge-foo-1", games[0][:game_id])
+    games = @history.loss_games("hoge")
+    assert_equal(1, games.size )
+    assert_equal("wdoor+floodgate-900-0-hoge-foo-1", games[0][:game_id])
+    games = @history.loss_games("foo")
+    assert_equal(1, games.size )
+    assert_equal("wdoor+floodgate-900-0-hoge-foo-2", games[0][:game_id])
   end
 end
 

--- a/test/TC_pairing.rb
+++ b/test/TC_pairing.rb
@@ -1,11 +1,11 @@
 $:.unshift File.join(File.dirname(__FILE__), "..")
 require 'test/unit'
 require 'shogi_server'
+require 'shogi_server/league.rb'
 require 'shogi_server/player'
 require 'shogi_server/pairing'
 require 'test/mock_log_message'
 
-
 def same_pair?(a, b)
   unless a.size == 2 && b.size == 2
     return false
@@ -327,4 +327,246 @@ class TestStartGameWithoutHumans < Test::Unit::TestCase
   end
 end
 
+class TestLeastDiff < Test::Unit::TestCase
+
+  class MockLeague
+    def initialize
+      @players = []
+    end
+
+    def add(player)
+      @players << player
+    end
+
+    def find(name)
+      @players.find do |p|
+        p.name == name
+      end
+    end
+  end
+
+  def setup
+    $league = MockLeague.new
+
+    @pairing= ShogiServer::LeastDiff.new
+    $paired = []
+    $called = 0
+    def @pairing.start_game(p1,p2)
+      $called += 1
+      $paired << [p1,p2]
+    end
+
+    @file = Pathname.new(File.join(File.dirname(__FILE__), "floodgate_history.yaml"))
+    @history = ShogiServer::League::Floodgate::History.new @file
+
+    @a = ShogiServer::BasicPlayer.new
+    @a.player_id = "a"
+    @a.name = "a"
+    @a.win  = 1
+    @a.loss = 2
+    @a.rate = 500
+    @b = ShogiServer::BasicPlayer.new
+    @b.player_id = "b"
+    @b.name = "b"
+    @b.win  = 10
+    @b.loss = 20
+    @b.rate = 800
+    @c = ShogiServer::BasicPlayer.new
+    @c.player_id = "c"
+    @c.name = "c"
+    @c.win  = 100
+    @c.loss = 200
+    @c.rate = 1000
+    @d = ShogiServer::BasicPlayer.new
+    @d.player_id = "d"
+    @d.name = "d"
+    @d.win  = 1000
+    @d.loss = 2000
+    @d.rate = 1500
+    @e = ShogiServer::BasicPlayer.new
+    @e.player_id = "e"
+    @e.name = "e"
+    @e.win  = 3000
+    @e.loss = 3000
+    @e.rate = 2000
+    @f = ShogiServer::BasicPlayer.new
+    @f.player_id = "f"
+    @f.name = "f"
+    @f.win  = 4000
+    @f.loss = 4000
+    @f.rate = 2150
+    @g = ShogiServer::BasicPlayer.new
+    @g.player_id = "g"
+    @g.name = "g"
+    @g.win  = 5000
+    @g.loss = 5000
+    @g.rate = 2500
+    @h = ShogiServer::BasicPlayer.new
+    @h.player_id = "h"
+    @h.name = "h"
+    @h.win  = 6000
+    @h.loss = 6000
+    @h.rate = 3000
+    @x = ShogiServer::BasicPlayer.new
+    @x.player_id = "x"
+    @x.name = "x"
+
+    $league.add(@a)
+    $league.add(@b)
+    $league.add(@c)
+    $league.add(@d)
+    $league.add(@e)
+    $league.add(@f)
+    $league.add(@g)
+    $league.add(@h)
+    $league.add(@x)
+  end
+
+  def teardown
+    @file.delete if @file.exist?
+  end
+
+  def assert_pairs(x_array, y_array)
+    if (x_array.size != y_array.size)
+      assert_equal(x_array.size, y_array.size)
+      return
+    end
+    i = 0
+
+    if (x_array.size == 1)
+      assert_equal(x_array[0].name, y_array[0].name)
+      return
+    end
+
+    ret = true
+    while i < x_array.size
+      if i == x_array.size-1
+        assert_equal(x_array[i].name, y_array[i].name)
+        break
+      end
+      px1 = x_array[i]
+      px2 = x_array[i+1]
+      py1 = y_array[i]
+      py2 = y_array[i+1]
+
+      if ! ((px1.name == py1.name && px2.name == py2.name) ||
+            (px1.name == py2.name && px2.name == py1.name))
+        ret = false
+      end
+      i += 2
+    end
+
+    assert(ret)
+  end
+
+  def test_match_one_player
+    players = [@a]
+    assert_equal(0, @pairing.calculate_diff_with_penalty(players,nil))
+    r = @pairing.match(players)
+    assert_pairs([@a], r)
+  end
+
+  def test_match_two_players
+    players = [@a,@b]
+    assert_equal(@[e-mail], @pairing.calculate_diff_with_penalty([@a,@b],nil))
+    assert_equal(@[e-mail], @pairing.calculate_diff_with_penalty([@b,@a],nil))
+    r = @pairing.match(players)
+    assert_pairs([@a,@b], r)
+  end
+
+  def test_match_three_players
+    players = [@a,@b,@h]
+    assert_equal(300,  @pairing.calculate_diff_with_penalty([@a,@b,@h],nil))
+    assert_equal(2200, @pairing.calculate_diff_with_penalty([@b,@h,@a],nil))
+    r = @pairing.match(players)
+    assert_pairs([@a,@b,@h], r)
+  end
+
+  def test_calculate_diff_with_penalty
+    players = [@a,@b]
+    assert_equal(@[e-mail], @pairing.calculate_diff_with_penalty(players,nil))
+
+    dummy = nil
+    def @history.make_record(game_result)
+      {:game_id => "wdoor+floodgate-900-0-a-b-1", 
+       :black => "b",  :white => "a",
+       :winner => "a", :loser => "b"}
+    end
+    @history.update(dummy)
+    assert_equal(@[e-mail]+400, @pairing.calculate_diff_with_penalty(players, @history))
+  end
+
+  def test_calculate_diff_with_penalty2
+    players = [@a,@b,@g,@h]
+    assert_equal(@[e-mail][e-mail][e-mail], @pairing.calculate_diff_with_penalty(players,nil))
+  end
+
+  def test_calculate_diff_with_penalty2_1
+    players = [@a,@b,@g,@h]
+    assert_equal(@[e-mail][e-mail][e-mail], @pairing.calculate_diff_with_penalty(players,nil))
+    dummy = nil
+    def @history.make_record(game_result)
+      {:game_id => "wdoor+floodgate-900-0-a-b-1", 
+       :black => "b",  :white => "a",
+       :winner => "a", :loser => "b"}
+    end
+    @history.update(dummy)
+    assert_equal(@[e-mail][e-mail][e-mail], @pairing.calculate_diff_with_penalty(players, @history))
+  end
+
+  def test_calculate_diff_with_penalty2_2
+    players = [@a,@b,@g,@h]
+    assert_equal(@[e-mail][e-mail][e-mail], @pairing.calculate_diff_with_penalty(players,nil))
+    dummy = nil
+    def @history.make_record(game_result)
+      {:game_id => "wdoor+floodgate-900-0-a-b-1", 
+       :black => "g",  :white => "h",
+       :winner => "h", :loser => "g"}
+    end
+    @history.update(dummy)
+    assert_equal(@[e-mail][e-mail][e-mail], @pairing.calculate_diff_with_penalty(players, @history))
+    #assert_equal(@[e-mail][e-mail][e-mail]+400, @pairing.calculate_diff_with_penalty(players, [@b,@a,@h,@g]))
+  end
+
+  def test_calculate_diff_with_penalty2_3
+    players = [@a,@b,@g,@h]
+    assert_equal(@[e-mail][e-mail][e-mail], @pairing.calculate_diff_with_penalty(players,nil))
+    dummy = nil
+    def @history.make_record(game_result)
+      {:game_id => "wdoor+floodgate-900-0-a-b-1", 
+       :black => "g",  :white => "h",
+       :winner => "h", :loser => "g"}
+    end
+    @history.update(dummy)
+    def @history.make_record(game_result)
+      {:game_id => "wdoor+floodgate-900-0-a-b-1", 
+       :black => "b",  :white => "a",
+       :winner => "a", :loser => "b"}
+    end
+    @history.update(dummy)
+    assert_equal(@[e-mail][e-mail][e-mail]+400, @pairing.calculate_diff_with_penalty(players, @history))
+  end
+
+  def test_get_player_rate_0
+    assert_equal(2150, @pairing.get_player_rate(@x, @history))
+
+    dummy = nil
+    def @history.make_record(game_result)
+      {:game_id => "wdoor+floodgate-900-0-x-a-1", 
+       :black => "x",  :white => "a",
+       :winner => "x", :loser => "a"}
+    end
+    @history.update(dummy)
+    assert_equal(@a.rate+100, @pairing.get_player_rate(@x, @history))
+
+    def @history.make_record(game_result)
+      {:game_id => "wdoor+floodgate-900-0-x-b-1", 
+       :black => "x",  :white => "b",
+       :winner => "b", :loser => "x"}
+    end
+    @history.update(dummy)
+
+    assert_equal((@[e-mail]-100)/2, @pairing.get_player_rate(@x, @history))
+  end
+end