OSDN Git Service

Make players into 'connected' groups for a meaningful rating system.'
authorbeatles <beatles@b8c68f68-1e22-0410-b08e-880e1f8202b4>
Mon, 30 Oct 2006 13:14:24 +0000 (13:14 +0000)
committerbeatles <beatles@b8c68f68-1e22-0410-b08e-880e1f8202b4>
Mon, 30 Oct 2006 13:14:24 +0000 (13:14 +0000)
changelog
mk_html
mk_rate
shogi-server

index 30b14a0..cceb816 100644 (file)
--- a/changelog
+++ b/changelog
@@ -1,3 +1,12 @@
+2006-10-30  Daigo Moriwaki <daigo at debian dot org>
+
+       * [mk_rate][mk_html]
+         - Put players into "connected" groups in order to
+           show a correct, meaningful rating. In the group, each player has at
+           least a game with other players.
+         - The format of players.yaml was updated.
+       * [shogi-server] Followed the new format of players.yaml.
+
 2006-10-08  Daigo Moriwaki <daigo at debian dot org>
 
        * [mk_rate] Corrected making win_loss_matrix.
diff --git a/mk_html b/mk_html
index bb20cbe..9203613 100755 (executable)
--- a/mk_html
+++ b/mk_html
@@ -45,11 +45,35 @@ def main
   while l = gets do
     lines << l
   end
-  yaml = YAML::load(lines)
+  file = YAML::load(lines)
+  erb = ERB.new( DATA.read, nil, "%<>" )
+  tables = []
 
-  sorted_keys = yaml.keys.sort {|a,b| yaml[b]['rate'] <=> yaml[a]['rate']}
+  file["players"].each do |key, yaml|
+    sorted_keys = yaml.keys.sort {|a,b| yaml[b]['rate'] <=> yaml[a]['rate']}
+
+  table = ERB.new(<<ENDTABLE, nil, "%<>")
+<% sorted_keys.each do |key| %>
+  <%
+    win  = yaml[key]['win']
+    loss = yaml[key]['loss']
+    win_rate = win.to_f / (win + loss)
+    last_modified = yaml[key]['last_modified']
+  %>
+  <tr>
+    <td class="name"><%=h yaml[key]['name']%></td>
+    <td class="rate"><%="%5d"  % [ yaml[key]['rate'] ]%></td>
+    <td class="ngames"><%="%5d"  % [ win ]%></td>
+    <td class="ngames"><%="%5d"  % [ loss ]%></td>
+    <td class="win_rate"><%="%.3f" % [win_rate]%></td>
+    <td class="last_modified"><%=show_date(last_modified)%></td>
+  </tr>
+<% end %>
+ENDTABLE
+        
+    tables << table.result(binding)
+  end
 
-  erb = ERB.new( DATA.read, nil, "%<>" )
   body = erb.result(binding)
   puts body
 end
@@ -89,6 +113,7 @@ __END__
 
 <h1>Shogi Server Rating</h1>
 
+<% tables.each do |t| %>
 <table>
 <colgroup>
   <col class="name">
@@ -104,26 +129,12 @@ __END__
 </tr>
 </thead>
 <tbody>
-<% sorted_keys.each do |key| %>
-  <%
-    win  = yaml[key]['win']
-    loss = yaml[key]['loss']
-    win_rate = win.to_f / (win + loss)
-    last_modified = yaml[key]['last_modified']
-  %>
-  <tr>
-    <td class="name"><%=h yaml[key]['name']%></td>
-    <td class="rate"><%="%5d"  % [ yaml[key]['rate'] ]%></td>
-    <td class="ngames"><%="%5d"  % [ win ]%></td>
-    <td class="ngames"><%="%5d"  % [ loss ]%></td>
-    <td class="win_rate"><%="%.3f" % [win_rate]%></td>
-    <td class="last_modified"><%=show_date(last_modified)%></td>
-  </tr>
-<% end %>
+<%= t %>
 </tbody>
 </table>
+<% end %>
 
-<p>The average of the rates is 1000. 
+<p>The average of the rates is always 1000. 
 
 <hr/>
 <p class="footer">Last modified at <%=Time.now%>
diff --git a/mk_rate b/mk_rate
index 072891a..4200997 100755 (executable)
--- a/mk_rate
+++ b/mk_rate
 # PREREQUIRE
 # ==========
 #
-#   Ruby bindings for the GNU Scientific Library (GSL) is required.
-#   You can download it from  http://rb-gsl.rubyforge.org/
-#   Or, if you use Debian, 
-#     $ sudo aptitude install libgsl-ruby1.8
+# Sample Commands to isntall prerequires will work for Debian.
+#
+# * Rubygems
+#   $ sudo aptitude install rubygems
+#
+# * Ruby bindings for the GNU Scientific Library (GSL)
+#   $ sudo aptitude install libgsl-ruby1.8
+#   Or, download it from  http://rb-gsl.rubyforge.org/ .
+#
+# * RGL: Ruby Graph Library
+#   $ sudo gem install rgl
+#   Or, download it from http://rubyforge.org/projects/rgl/ .
 #
 
 require 'yaml'
 require 'time'
 require 'gsl'
+require 'rubygems'
+require 'rgl/adjacency'
+require 'rgl/connected_components'
 
 #################################################
 # Constants
@@ -338,77 +349,185 @@ class Rating
   end
 end
 
-
-
 #################################################
-# Main methods
+# Encapsulate a pair of keys and win loss matrix.
+#   - keys is an array of player IDs; [gps+123, foo+234, ...]
+#   - matrix holds games # where player i (row index) beats player j (column index).
+#     The row and column indexes match with the keys.
+#
+# This object should be immutable. If an internal state is being modified, a
+# new object is always returned.
 #
+class WinLossMatrix
 
-def mk_matrix(players)
-       keys = players.keys.sort
-  size = keys.size
-  matrix =
-         Matrix::Int[*
-               ((0...size).collect do |k|
-      p1 = keys[k]
-      p1_hash = players[p1]
-                 ((0...size).collect do |j|
-                         if k == j
-                                 0
-                         else
-          p2 = keys[j]
-          v = p1_hash[p2] || Vector[0,0]
-                                 v[0]
-                         end
-                 end)
-               end)]
-  return matrix, keys
-end
+  ###############
+  # Class methods
+  #  
 
-def delete_row(matrix, keys, delete_index)
-  size = keys.size
-  copied_cols = []
-  (0...size).each do |i|
-    next if i == delete_index
-    row = matrix.get_row(i)  # get_row returns a copy of the row
-    row.delete_at(delete_index)
-    copied_cols << row
-  end
-  new_matrix = Matrix::Int[*copied_cols]
-  new_keys = keys.clone
-  new_keys.delete_at(delete_index)
-  return new_matrix, new_keys
-end
+  def self.mk_matrix(players)
+    keys = players.keys.sort
+    size = keys.size
+    matrix =
+      Matrix::Int[*
+      ((0...size).collect do |k|
+        p1 = keys[k]
+        p1_hash = players[p1]
+        ((0...size).collect do |j|
+          if k == j
+            0
+          else
+            p2 = keys[j]
+            v = p1_hash[p2] || Vector[0,0]
+            v[0]
+          end
+        end)
+      end)]
+    return WinLossMatrix.new(keys, matrix)
+  end
+
+  def self.mk_win_loss_matrix(players)
+    obj = mk_matrix(players)
+    return obj.filter
+  end
+
+  ##################
+  # Instance methods
+  #
+
+  # an array of player IDs; [gps+123, foo+234, ...]
+  attr_reader :keys
 
-def filter(matrix, keys)
-  $stderr.puts keys.inspect if $DEBUG
-  $stderr.puts matrix.inspect if $DEBUG
-  size = keys.size
-  delete = []  
-  (0...size).each do |i|
-    row = matrix.row(i)
-    col = matrix.col(i)
-    win  = row.sum
-    loss = col.sum
-    if win < 1 || loss < 1 || win + loss < $GAMES_LIMIT
-      delete << i
+  # matrix holds games # where player i (row index) beats player j (column index).
+  # The row and column indexes match with the keys.
+  attr_reader :matrix
+
+  def initialize(keys, matrix)
+    @keys   = keys
+    @matrix = matrix
+  end
+
+  ##
+  # Returns the size of the keys/matrix
+  #
+  def size
+    if @keys
+      @keys.size
+    else
+      nil
     end
   end
 
-  # The recursion ends if there is nothing to delete
-  return matrix, keys if delete.empty?
-  
-  delete.reverse.each do |i|
-    matrix, keys = delete_row(matrix, keys, i)
+  ##
+  # Removes a delete_index'th player and returns a new object.
+  #
+  def delete_row(delete_index)
+    copied_cols = []
+    (0...size).each do |i|
+      next if i == delete_index
+      row = @matrix.get_row(i)  # get_row returns a copy of the row
+      row.delete_at(delete_index)
+      copied_cols << row
+    end
+    new_matrix = Matrix::Int[*copied_cols]
+    new_keys = @keys.clone
+    new_keys.delete_at(delete_index)
+    return WinLossMatrix.new(new_keys, new_matrix)
+  end
+
+  ##
+  # Removes players in a rows; [1,3,5]
+  #
+  def delete_rows(rows)
+    obj = self
+    rows.sort.reverse.each do |index|
+      obj = obj.delete_row(index)
+    end
+    obj
+  end
+
+  ##
+  # Removes players who do not pass a criteria to be rated, and returns a new object.
+  # 
+  def filter
+    $stderr.puts @keys.inspect if $DEBUG
+    $stderr.puts @matrix.inspect if $DEBUG
+    delete = []  
+    (0...size).each do |i|
+      row = @matrix.row(i)
+      col = @matrix.col(i)
+      win  = row.sum
+      loss = col.sum
+      if win < 1 || loss < 1 || win + loss < $GAMES_LIMIT
+        delete << i
+      end
+    end
+
+    # The recursion ends if there is nothing to delete
+    return self if delete.empty?
+
+    new_obj = delete_rows(delete)
+    new_obj.filter
+  end
+
+  ##
+  # Cuts self into connecting groups such as each player in a group has at least
+  # one game with other players in the group. Returns them as an array.
+  #
+  def connected_subsets
+    g = RGL::AdjacencyGraph.new
+    (0...size).each do |k|
+      (0...size).each do |i|
+        next if k == i
+        if @matrix[k,i] > 0
+          g.add_edge(k,i)
+        end
+      end
+    end
+
+    subsets = []
+    g.each_connected_component do |c|
+      new_keys = []      
+      c.each do |v|
+        new_keys << keys[v.to_s.to_i]
+      end
+      subsets << new_keys
+    end
+
+    subsets = subsets.sort {|a,b| b.size <=> a.size}
+
+    result = subsets.collect do |keys|
+      matrix =
+        Matrix::Int[*
+        ((0...keys.size).collect do |k|
+          p1 = @keys.index(keys[k])
+          ((0...keys.size).collect do |j|
+            if k == j
+              0
+            else
+              p2 = @keys.index(keys[j])
+              @matrix[p1][p2]
+            end
+          end)
+        end)]
+      WinLossMatrix.new(keys, matrix)
+    end
+
+    return result
+  end
+
+  def to_s
+    "size : #{@keys.size}" + "\n" +
+    @keys.inspect + "\n" + 
+    @matrix.inspect
   end
-  filter(matrix, keys)
-end
 
-def mk_win_loss_matrix(players)
-  matrix, keys = mk_matrix(players)
-  filter(matrix, keys)
 end
 
+
+#################################################
+# Main methods
+#
+
 def _add_win_loss(winner, loser)
   $players[winner] ||= Hash.new { GSL::Vector[0,0] }
   $players[loser]  ||= Hash.new { GSL::Vector[0,0] }
@@ -458,7 +577,7 @@ def grep(file)
       black_name, black_mark = p2_name, p2_mark
       white_name, white_mark = p1_name, p1_mark
     else
-      raise "Never reach!: #{black} #{white} #{p1} #{p2}"
+      raise "Never reach!: #{black} #{white} #{p3} #{p2}"
     end
   end
   if /^'\$END_TIME:(.*)$/ =~ str
@@ -487,23 +606,31 @@ def main
     Dir.glob( File.join(dir, "**", "*.csa") ) {|f| grep(f)}
   end
 
-  win_loss_matrix, keys = mk_win_loss_matrix($players)
-  rating = Rating.new(win_loss_matrix)
-  rating.rating
-  rating.average!(Rating::AVERAGE_RATE)
-  rating.integer!
-
-  yaml = {}
-  keys.each_with_index do |p, i| # player_id, index#
-    win  = win_loss_matrix.row(i).sum
-    loss = win_loss_matrix.col(i).sum
-
-    yaml[p] = 
-      { 'name' => p.split("+")[0],
-        'rate' => rating.rate[i],
-        'last_modified' => $players_time[p].dup,
-        'win'  => win,
-        'loss' => loss}
+  obj = WinLossMatrix::mk_win_loss_matrix($players)
+  yaml = {} 
+  yaml["players"] = {}
+  rating_group = 0
+  obj.connected_subsets.each do |win_loss_matrix|
+    yaml["players"][rating_group] = {}
+
+    rating = Rating.new(win_loss_matrix.matrix)
+    rating.rating
+    rating.average!(Rating::AVERAGE_RATE)
+    rating.integer!
+
+    win_loss_matrix.keys.each_with_index do |p, i| # player_id, index#
+      win  = win_loss_matrix.matrix.row(i).sum
+      loss = win_loss_matrix.matrix.col(i).sum
+
+      yaml["players"][rating_group][p] = 
+        { 'name' => p.split("+")[0],
+          'rating_group' => rating_group,
+          'rate' => rating.rate[i],
+          'last_modified' => $players_time[p].dup,
+          'win'  => win,
+          'loss' => loss}
+    end
+    rating_group += 1
   end
   puts yaml.to_yaml
 end
index 0e99dd7..be06e55 100755 (executable)
@@ -121,16 +121,20 @@ class League
     hash = search(player.id)
     if hash
       # a current user
-      player.name = hash['name']
-      player.rate = hash['rate']
-      player.modified_at = hash['last_modified']
+      player.name         = hash['name']
+      player.rate         = hash['rate']
+      player.modified_at  = hash['last_modified']
+      player.rating_group = hash['rating_group']
     end
   end
 
   def search(id)
     hash = nil
     @db.transaction do
-      hash = @db[id]
+      @db["players"].each do |group, players|
+        hash = players[id]
+        break if hash
+      end
     end
     hash
   end
@@ -138,11 +142,11 @@ class League
   def rated_players
     players = []
     @db.transaction(true) do
-      @db.roots.each do |id|
-        players << id
+      @db["players"].each do |group, players_hash|
+        players << players_hash.keys
       end
     end
-    return players.collect do |id|
+    return players.flatten.collect do |id|
       p = BasicPlayer.new
       p.id = id
       self.load(p)
@@ -164,6 +168,9 @@ class BasicPlayer
 
   # Score in the rating sysem
   attr_accessor :rate
+
+  # Group in the rating system
+  attr_accessor :rating_group
   
   # Last timestamp when the rate was modified
   attr_accessor :modified_at