mk_rate

   1 #!/usr/bin/ruby
   2 ## $Id$
   3
   4 ## Copyright (C) 2006 Daigo Moriwaki <daigo at debian dot org>
   5 ##
   6 ## This program is free software; you can redistribute it and/or modify
   7 ## it under the terms of the GNU General Public License as published by
   8 ## the Free Software Foundation; either version 2 of the License, or
   9 ## (at your option) any later version.
  10 ##
  11 ## This program is distributed in the hope that it will be useful,
  12 ## but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 ## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 ## GNU General Public License for more details.
  15 ##
  16 ## You should have received a copy of the GNU General Public License
  17 ## along with this program; if not, write to the Free Software
  18 ## Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  19
  20 #
  21 # This calculates rating scores of every players from CSA files, and outputs a
  22 # yaml file (players.yaml) that Shogi Server can read.
  23 #
  24 # Sample:
  25 #   $ ./mk_rate . > players.yaml
  26 #
  27 # The conditions that games and players are rated as following:
  28 #   * Rated games, which were played by both rated players.
  29 #   * Rated players, who logged in the server with a name followed by a trip:
  30 #     "name,trip".
  31 #   * (Rated) players, who played more than $GAMES_LIMIT [ten] (rated) games.
  32 #
  33
  34 require 'yaml'
  35 require 'matrix'
  36 require 'time'
  37
  38 #################################################
  39 # Constants
  40 #
  41 $GAMES_LIMIT = $DEBUG ? 0 : 10
  42 WIN_MARK  = "win"
  43 LOSS_MARK = "lose"
  44 AVERAGE_RATE = 1100
  45
  46 $players = Hash.new
  47 $players_time = Hash.new { Time.at(0) }
  48
  49
  50 #################################################
  51 # Calculates rates of every player from a Win Loss Matrix
  52 #
  53 class Rating
  54         include Math
  55
  56   K = Math.log(10.0) / 400.0
  57   ERROR_LIMIT = 1.0e-5
  58
  59         def Rating.average(vector, mean=0.0)
  60                 sum = Array(vector).inject(0.0) {|sum, n| sum + n}
  61                 vector -= Vector[*Array.new(vector.size, sum/vector.size - mean)]
  62           vector
  63         end
  64
  65         def initialize(win_loss_matrix)
  66     @win_loss_matrix = win_loss_matrix
  67                 @size = @win_loss_matrix.row_size
  68         end
  69         attr_reader :rate
  70
  71         def rating
  72                 # 0 is the initial value
  73                 @rate = Vector[*Array.new(@size,0)]
  74
  75                 begin
  76                         # the probability that x wins y
  77                         @win_rate_matrix = Matrix[*
  78                                 (@rate.collect do |x|
  79                                 (@rate.collect do |y|
  80                                         #     exp(x)
  81                                         # ---------------
  82                                         # exp(x) + exp(y)
  83                                         1.0/(1.0+exp(K*(y-x)))
  84                                 end)
  85                                 end)
  86                         ]
  87
  88                         # delta in Newton method
  89                         errorVector = Vector[*
  90                                 ((0...@size).collect do |k|
  91
  92                                   numerator   = 0.0
  93                                   #---------------------
  94                                   denominator = 0.0
  95
  96                                 (0...@size).each do |i|
  97                                         next if i == k
  98                                         numerator   += @win_loss_matrix[k,i] * @win_rate_matrix[i,k] -
  99                                                              @win_rate_matrix[k,i] * @win_loss_matrix[i,k]
 100                                         #------------------------------------------------------
 101                                         denominator += @win_rate_matrix[i,k] * @win_rate_matrix[k,i] *
 102                                                             (@win_loss_matrix[k,i] + @win_loss_matrix[i,k])
 103                                 end
 104
 105                                 # Remained issue: what to do if zero?
 106                                 (numerator == 0) ? 0 : numerator / denominator
 107                                 end)
 108                         ]
 109
 110                         # gets the next value
 111                         @rate += errorVector * (1.0/K)
 112                         $stderr.printf "|error| : %5.2e\n", errorVector.r if $DEBUG
 113
 114                 end while (errorVector.r > ERROR_LIMIT * @rate.r)
 115
 116                 self
 117         end
 118
 119   def average!(mean=0.0)
 120     @rate = self.class.average(@rate, mean)
 121         end
 122
 123         def integer!
 124     @rate = @rate.map {|a| a.to_i}
 125         end
 126 end
 127
 128
 129
 130 #################################################
 131 # Main methods
 132 #
 133
 134 def mk_win_loss_matrix(players)
 135         keys = players.keys.sort.reject do |k|
 136                 players[k].values.inject(0) {|sum, v| sum + v[0] + v[1]} < $GAMES_LIMIT
 137         end
 138
 139         size = keys.size
 140
 141         matrix =
 142           Matrix[*
 143                 ((0...size).collect do |k|
 144                 ((0...size).collect do |j|
 145                         if k == j
 146                                 0
 147                         else
 148                                 v = players[keys[k]][keys[j]]
 149                                 v[0]
 150                         end
 151                 end)
 152                 end)]
 153
 154         return matrix, keys
 155 end
 156
 157 def _add_win_loss(winner, loser)
 158         $players[winner] ||= Hash.new { Vector[0,0] }
 159         $players[loser]  ||= Hash.new { Vector[0,0] }
 160   $players[winner][loser] += Vector[1,0]
 161         $players[loser][winner] += Vector[0,1]
 162 end
 163
 164 def _add_time(player, time)
 165         $players_time[player] = time if $players_time[player] < time
 166 end
 167
 168 def add(black_mark, black_name, white_name, white_mark, time)
 169         if black_mark == WIN_MARK && white_mark == LOSS_MARK
 170                 _add_win_loss(black_name, white_name)
 171         elsif black_mark == LOSS_MARK && white_mark == WIN_MARK
 172                 _add_win_loss(white_name, black_name)
 173         else
 174                 raise "Never reached!"
 175         end
 176         _add_time(black_name, time)
 177         _add_time(white_name, time)
 178 end
 179
 180 def grep(file)
 181         str = File.open(file).read
 182
 183         black_mark = ""; white_mark = ""
 184         time = nil
 185
 186         str.gsub(/^'summary:(.*)$/) do |line|
 187                 dummy, sente, gote = $1.split(":").map {|a| a.strip}
 188                 black_mark, white_mark = [sente,gote].map {|p| p.split(" ")[1]}
 189         end
 190         str.gsub(/^'\$END_TIME:(.*)$/) do |line|
 191     time = Time.parse($1.strip)
 192         end
 193         if /^'rating:(.*)$/ =~ str
 194           black_name, white_name = $1.split(":").map {|a| a.strip}
 195           add(black_mark, black_name, white_name, white_mark, time)
 196         end
 197 end
 198
 199 def usage
 200         $stderr.puts <<-EOF
 201 USAGE: #{$0} dir [...]
 202         EOF
 203         exit 1
 204 end
 205
 206 def main
 207         usage if ARGV.empty?
 208         while dir = ARGV.shift do
 209                 Dir.glob( File.join("**", "*.csa") ) {|f| grep(f)}
 210         end
 211
 212         win_loss_matrix, keys = mk_win_loss_matrix($players)
 213         rating = Rating.new(win_loss_matrix)
 214         rating.rating
 215         rating.average!(AVERAGE_RATE)
 216         rating.integer!
 217
 218         yaml = {}
 219         keys.each_with_index do |p, i| # player_id, index#
 220                 win_loss = $players[p].values.inject(Vector[0,0]) {|sum, v| sum + v}
 221     win = win_loss_matrix
 222                 yaml[p] =
 223                         { 'name' => p.split("+")[0],
 224                     'rate' => rating.rate[i],
 225                     'last_modified' => $players_time[p],
 226                     'win'  => win_loss[0],
 227                     'loss' => win_loss[1]}
 228         end
 229         puts yaml.to_yaml
 230 end
 231
 232 if __FILE__ == $0
 233         main
 234 end
 235
 236 # vim: ts=2 sw=2 sts=0