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                                           #      1
  81                                           # --------------
  82                                           #  1 + exp(y-x)
  83                                           1.0/(1.0+exp(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
 112                         $stderr.printf "|error| : %5.2e\n", errorVector.r if $DEBUG
 113
 114                 end while (errorVector.r > ERROR_LIMIT * @rate.r)
 115
 116     @rate *= 1.0/K
 117                 self
 118         end
 119
 120   def average!(mean=0.0)
 121     @rate = self.class.average(@rate, mean)
 122         end
 123
 124         def integer!
 125     @rate = @rate.map {|a| a.to_i}
 126         end
 127 end
 128
 129
 130
 131 #################################################
 132 # Main methods
 133 #
 134
 135 def mk_win_loss_matrix(players)
 136         keys = players.keys.sort.reject do |k|
 137                 players[k].values.inject(0) {|sum, v| sum + v[0] + v[1]} < $GAMES_LIMIT
 138         end
 139
 140         size = keys.size
 141
 142         matrix =
 143           Matrix[*
 144                 ((0...size).collect do |k|
 145                 ((0...size).collect do |j|
 146                         if k == j
 147                                 0
 148                         else
 149                                 v = players[keys[k]][keys[j]]
 150                                 v[0]
 151                         end
 152                 end)
 153                 end)]
 154
 155         return matrix, keys
 156 end
 157
 158 def _add_win_loss(winner, loser)
 159         $players[winner] ||= Hash.new { Vector[0,0] }
 160         $players[loser]  ||= Hash.new { Vector[0,0] }
 161   $players[winner][loser] += Vector[1,0]
 162         $players[loser][winner] += Vector[0,1]
 163 end
 164
 165 def _add_time(player, time)
 166         $players_time[player] = time if $players_time[player] < time
 167 end
 168
 169 def add(black_mark, black_name, white_name, white_mark, time)
 170         if black_mark == WIN_MARK && white_mark == LOSS_MARK
 171                 _add_win_loss(black_name, white_name)
 172         elsif black_mark == LOSS_MARK && white_mark == WIN_MARK
 173                 _add_win_loss(white_name, black_name)
 174         else
 175                 raise "Never reached!"
 176         end
 177         _add_time(black_name, time)
 178         _add_time(white_name, time)
 179 end
 180
 181 def grep(file)
 182         str = File.open(file).read
 183
 184   if /^N\+(.*)$/ =~ str then black_name = $1.strip end
 185   if /^N\-(.*)$/ =~ str then white_name = $1.strip end
 186
 187         if /^'summary:(.*)$/ =~ str
 188                 dummy, p1, p2 = $1.split(":").map {|a| a.strip}
 189     p1_name, p1_mark = p1.split(" ")
 190     p2_name, p2_mark = p2.split(" ")
 191     if p1_name == black_name
 192       black_name, black_mark = p1_name, p1_mark
 193       white_name, white_mark = p2_name, p2_mark
 194     elsif p2_name == black_name
 195       black_name, black_mark = p2_name, p2_mark
 196       white_name, white_mark = p1_name, p1_mark
 197     else
 198       raise "Never reach!: #{black} #{white} #{p1} #{p2}"
 199     end
 200         end
 201         if /^'\$END_TIME:(.*)$/ =~ str
 202     time = Time.parse($1.strip)
 203         end
 204         if /^'rating:(.*)$/ =~ str
 205           black_id, white_id = $1.split(":").map {|a| a.strip}
 206           add(black_mark, black_id, white_id, white_mark, time)
 207         end
 208 end
 209
 210 def usage
 211         $stderr.puts <<-EOF
 212 USAGE: #{$0} dir [...]
 213         EOF
 214         exit 1
 215 end
 216
 217 def main
 218         usage if ARGV.empty?
 219         while dir = ARGV.shift do
 220                 Dir.glob( File.join(dir, "**", "*.csa") ) {|f| grep(f)}
 221         end
 222
 223         win_loss_matrix, keys = mk_win_loss_matrix($players)
 224   $stderr.puts keys.inspect if $DEBUG
 225   $stderr.puts win_loss_matrix.inspect if $DEBUG
 226         rating = Rating.new(win_loss_matrix)
 227         rating.rating
 228         rating.average!(AVERAGE_RATE)
 229         rating.integer!
 230
 231         yaml = {}
 232         keys.each_with_index do |p, i| # player_id, index#
 233                 win_loss = $players[p].values.inject(Vector[0,0]) {|sum, v| sum + v}
 234     win = win_loss_matrix
 235                 yaml[p] =
 236                         { 'name' => p.split("+")[0],
 237                     'rate' => rating.rate[i],
 238                     'last_modified' => $players_time[p],
 239                     'win'  => win_loss[0],
 240                     'loss' => win_loss[1]}
 241         end
 242         puts yaml.to_yaml
 243 end
 244
 245 if __FILE__ == $0
 246         main
 247 end
 248
 249 # vim: ts=2 sw=2 sts=0