[shogi-server] shogi_server/pairing.rb: Attempt more trials

LeastDiff attempts more trials, depending of a number of players to be matched.

diff --git a/changelog b/changelog
index ccba8ed..863491d 100644 (file)
--- a/changelog
+++ b/changelog
@@ -18,6 +18,9 @@
            b) Least_Time_Per_Move will be 0 for floodgate-600-10 games;
               otherwise 1.
          (Closes: #35839)
+       * [shogi-server] shogi_server/pairing.rb:
+         - LeastDiff attempts more trials, depending of a number of players
+           to be matched.
 
 2015-11-27  Daigo Moriwaki <daigo at debian dot org>
 

diff --git a/shogi_server/pairing.rb b/shogi_server/pairing.rb
index a38f929..cc2ea62 100644 (file)
--- a/shogi_server/pairing.rb
+++ b/shogi_server/pairing.rb
@@ -514,6 +514,22 @@ module ShogiServer
       ret
     end
 
+    # Total combinations of possible games among n players
+    #   nC2 * (n-2)C2 * ... * 2C2 / (n/2)!
+    def total_posibilities(n)
+      n -= 1 if n.odd?
+      return 1 if n <= 2
+
+      ret = 1
+      i = n
+      while i >= 2 do
+        ret *= ::ShogiServer::nCk(i,2)
+        i -= 2
+      end
+      ret /= ::ShogiServer::factorial(n/2)
+      return ret
+    end
+
     def match(players)
       super
       if players.size < 3
@@ -524,12 +540,16 @@ module ShogiServer
       # 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 
+
+      # Increase trials, depending on a number of players
+      trials = [300, total_posibilities(players.size)/3].min
+      trials = [10, trials].max
+      log_message("Floodgate: %d trials" % [trials])
+      trials.times do
         m = random_match(players)
         matches << m
         scores << calculate_diff_with_penalty(m, history)

diff --git a/shogi_server/util.rb b/shogi_server/util.rb
index e1813d3..76f4526 100644 (file)
--- a/shogi_server/util.rb
+++ b/shogi_server/util.rb
@@ -42,6 +42,25 @@ module ShogiServer
   end
   module_function :shuffle
 
+  def factorial(n)
+    return 1 if n<=1
+    ret = 1
+    while n >= 2
+      ret *= n
+      n -= 1
+    end
+    return ret
+  end
+  module_function :factorial
+
+  def nCk(n, k)
+    return 0 if n < k
+    numerator   = factorial(n)
+    denominator = factorial(k) * factorial(n - k)
+    return numerator / denominator
+  end
+  module_function :nCk
+
   # See if the file is writable. The file will be created if it does not exist
   # yet.
   # Return true if the file is writable, otherwise false.

diff --git a/test/TC_pairing.rb b/test/TC_pairing.rb
index 94274fa..86970ca 100644 (file)
--- a/test/TC_pairing.rb
+++ b/test/TC_pairing.rb
@@ -499,6 +499,12 @@ class TestLeastDiff < Test::Unit::TestCase
     assert_pairs([@a,@b,@h], players)
   end
 
+  def test_match_many_players
+    players = [@a,@b,@h,@a,@b,@h,@a,@b,@h,@a,@b,@h,@a,@b,@h,@a,@b,@h,@a,@b,@h,@a,@b,@h,@a,@b,@h,@a,@b,@h]
+    r = @pairing.match(players)
+    assert true
+  end
+
   def test_calculate_diff_with_penalty
     players = [@a,@b]
     assert_equal(@b.rate-@a.rate, @pairing.calculate_diff_with_penalty(players,nil))
@@ -597,6 +603,13 @@ class TestLeastDiff < Test::Unit::TestCase
 
     assert_equal(@b.rate-200, @pairing.get_player_rate(@x, @history))
   end
+
+  def test_total_posibilities
+    assert_equal 1, @pairing.total_posibilities(2)
+    assert_equal 1, @pairing.total_posibilities(3)
+    assert_equal 3, @pairing.total_posibilities(4)
+    assert_equal 945, @pairing.total_posibilities(10)
+  end
 end
 
 class TestExcludeUnratedPlayers < Test::Unit::TestCase

diff --git a/test/TC_util.rb b/test/TC_util.rb
index 79ac945..285c835 100644 (file)
--- a/test/TC_util.rb
+++ b/test/TC_util.rb
@@ -61,3 +61,22 @@ class TestMkdir < Test::Unit::TestCase
   end
 
 end
+
+class TestFactorial < Test::Unit::TestCase
+  def test_factorial
+    assert_equal 1, ShogiServer::factorial(0)
+    assert_equal 1, ShogiServer::factorial(1)
+    assert_equal 2, ShogiServer::factorial(2)
+    assert_equal 6, ShogiServer::factorial(3)
+  end
+end
+
+class TestnCk < Test::Unit::TestCase
+  def test_nCk
+    assert_equal 0, ShogiServer::nCk(2,5)
+    assert_equal 1, ShogiServer::nCk(2,2)
+    assert_equal 6, ShogiServer::nCk(4,2)
+    assert_equal 11*5*9, ShogiServer::nCk(12,4)
+  end
+end
+