4 ## Copyright (C) 2006 Daigo Moriwaki <daigo at debian dot org>
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.
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.
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
21 # This calculates rating scores of every players from CSA files, and outputs a
22 # yaml file (players.yaml) that Shogi Server can read.
25 # $ ./mk_rate . > players.yaml
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:
31 # * (Rated) players, who played more than $GAMES_LIMIT [ten] (rated) games.
38 #################################################
41 $GAMES_LIMIT = $DEBUG ? 0 : 10
46 $players_time = Hash.new { Time.at(0) }
49 #################################################
50 # Calculates rates of every player from a Win Loss GSL::Matrix
55 # The model of the win possibility is 1/(1 + 10^(-d/400))
56 # The equation in this class is 1/(1 + e^(-Kd))
57 # So, K should be like this.
58 K = Math.log(10.0) / 400.0
60 # Convergence limit to stop Newton method.
63 # Average rate among the players
69 def Rating.average(vector, mean=0.0)
70 sum = Array(vector).inject(0.0) {|sum, n| sum + n}
71 vector -= GSL::Vector[*Array.new(vector.size, sum/vector.size - mean)]
78 def initialize(win_loss_matrix)
88 # 0 is the initial value
95 (0...@size).collect {|k| yield k}
100 (0...@size).each {|k| yield k}
104 # The possibility that the player k will beet the player i.
107 1.0/(1.0 + exp(@rate[i]-@rate[k]))
111 # Most possible equation
118 sum += @n[k,i] * win_rate(i,k) - @n[i,k] * win_rate(k,i)
125 # / f0/R0 f0/R1 f0/R2 ... \
126 # fk/Rj = | f1/R0 f1/R1 f1/R2 ... |
127 # \ f2/R0 f2/R1 f2/R2 ... /
133 sum += win_rate(i,k) * win_rate(k,i) * (@n[k,i] + @n[i,k])
137 sum = win_rate(j,k) * win_rate(k,j) * (@n[k,j] + @n[j,k])
144 # Jacobi matrix of the func().
150 (0...@size).collect do |k|
151 (0...@size).collect do |j|
159 # The initial value of the rate, which is of very importance for Newton method.
160 # This is based on my huristics.
165 v = GSL::Vector[0.0, 0.0]
168 v += GSL::Vector[@n[k,i], @n[i,k]]
170 v[0] + v[1] == 0 ? 0.001 : v[0] / (v[0] + v[1])
172 rank = possibility.sort_index
174 K*500 * (rank[k]+1) / (@size)
179 # Main method to calculate ratings.
182 # Counter to stop the process.
183 # Calulation in Newton method may fall in an infinite loop
185 # Mu parameter in Deaccelerated Newton method
190 # Solve the equation:
192 # @rate_(n+1) = @rate_(n) - a
196 # f.nrm2 should approach to zero.
197 $stderr.puts "f: %s -> %f" % [f.to_a.inspect, f.nrm2] if $DEBUG
199 # LU is not available because J may not be a normal matrix.
200 # a = GSL::Linalg::LU.solve(j, f)
201 a = GSL::Linalg::SV.solve(j, f)
202 a = self.class.average(a)
204 # Deaccelerated Newton method
206 old_rate = Vector.alloc(@rate)
207 old_f = Vector.alloc(f)
208 @rate = old_rate - a * mu
210 if func_vector.nrm2 < (1.0 - mu / 4.0) * old_f.nrm2
215 @rate = old_rate - a * mu
218 $stderr.printf "|error| : %5.2e\n", a.nrm2 if $DEBUG
222 $stderr.puts "Values seem to oscillate. Stopped the process."
223 $stderr.puts "f: %s -> %f" % [f.to_a.inspect, f.nrm2]
227 end while (a.nrm2 > ERROR_LIMIT * @rate.nrm2)
228 #end while ( !(0..0.01).include?(func_vector.nrm2) )
230 $stderr.puts "resolved f: %s -> %f" %
231 [func_vector.to_a.inspect, func_vector.nrm2] if $DEBUG
239 @rate = @rate.collect do |a|
241 a.infinite? * AVERAGE_RATE * 100
248 def average!(mean=0.0)
249 @rate = self.class.average(@rate, mean)
253 @rate = @rate.collect do |a|
259 a.infinite? * AVERAGE_RATE * 100
267 #################################################
271 def mk_win_loss_matrix(players)
272 keys = players.keys.sort.reject do |k|
273 players[k].values.inject(0) {|sum, v| sum + v[0] + v[1]} < $GAMES_LIMIT
280 ((0...size).collect do |k|
281 ((0...size).collect do |j|
285 v = players[keys[k]][keys[j]]
294 def _add_win_loss(winner, loser)
295 $players[winner] ||= Hash.new { GSL::Vector[0,0] }
296 $players[loser] ||= Hash.new { GSL::Vector[0,0] }
297 $players[winner][loser] += GSL::Vector[1,0]
298 $players[loser][winner] += GSL::Vector[0,1]
301 def _add_time(player, time)
302 $players_time[player] = time if $players_time[player] < time
305 def add(black_mark, black_name, white_name, white_mark, time)
306 if black_mark == WIN_MARK && white_mark == LOSS_MARK
307 _add_win_loss(black_name, white_name)
308 elsif black_mark == LOSS_MARK && white_mark == WIN_MARK
309 _add_win_loss(white_name, black_name)
311 raise "Never reached!"
313 _add_time(black_name, time)
314 _add_time(white_name, time)
318 str = File.open(file).read
320 if /^N\+(.*)$/ =~ str then black_name = $1.strip end
321 if /^N\-(.*)$/ =~ str then white_name = $1.strip end
323 if /^'summary:(.*)$/ =~ str
324 dummy, p1, p2 = $1.split(":").map {|a| a.strip}
325 p1_name, p1_mark = p1.split(" ")
326 p2_name, p2_mark = p2.split(" ")
327 if p1_name == black_name
328 black_name, black_mark = p1_name, p1_mark
329 white_name, white_mark = p2_name, p2_mark
330 elsif p2_name == black_name
331 black_name, black_mark = p2_name, p2_mark
332 white_name, white_mark = p1_name, p1_mark
334 raise "Never reach!: #{black} #{white} #{p1} #{p2}"
337 if /^'\$END_TIME:(.*)$/ =~ str
338 time = Time.parse($1.strip)
340 if /^'rating:(.*)$/ =~ str
341 black_id, white_id = $1.split(":").map {|a| a.strip}
342 add(black_mark, black_id, white_id, white_mark, time)
348 USAGE: #{$0} dir [...]
355 while dir = ARGV.shift do
356 Dir.glob( File.join(dir, "**", "*.csa") ) {|f| grep(f)}
359 win_loss_matrix, keys = mk_win_loss_matrix($players)
360 $stderr.puts keys.inspect if $DEBUG
361 $stderr.puts win_loss_matrix.inspect if $DEBUG
362 rating = Rating.new(win_loss_matrix)
364 rating.average!(Rating::AVERAGE_RATE)
368 keys.each_with_index do |p, i| # player_id, index#
369 win_loss = $players[p].values.inject(GSL::Vector[0,0]) {|sum, v| sum + v}
370 win = win_loss_matrix
372 { 'name' => p.split("+")[0],
373 'rate' => rating.rate[i],
374 'last_modified' => $players_time[p].dup,
375 'win' => win_loss[0],
376 'loss' => win_loss[1]}
385 # vim: ts=2 sw=2 sts=0