OSDN Git Service

Corrected making win_loss_matrix.
[shogi-server/shogi-server.git] / 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 # PREREQUIRE
35 # ==========
36 #
37 #   Ruby bindings for the GNU Scientific Library (GSL) is required.
38 #   You can download it from  http://rb-gsl.rubyforge.org/
39 #   Or, if you use Debian, 
40 #     $ sudo aptitude install libgsl-ruby1.8
41 #
42
43 require 'yaml'
44 require 'time'
45 require 'gsl'
46
47 #################################################
48 # Constants
49 #
50
51 # Count out players who play less games than $GAMES_LIMIT
52 $GAMES_LIMIT = $DEBUG ? 0 : 10
53 WIN_MARK  = "win"
54 LOSS_MARK = "lose"
55 DRAW_MARK = "draw"
56
57 # Holds players
58 $players = Hash.new
59 # Holds the last time when a player gamed
60 $players_time = Hash.new { Time.at(0) }
61
62
63 #################################################
64 # Keeps the value of the lowest key
65 #
66 class Record
67   def initialize
68     @lowest = []
69   end
70
71   def set(key, value)
72     if @lowest.empty? || key < @lowest[0]
73       @lowest = [key, value]
74     end
75   end
76
77   def get
78     if @lowest.empty?
79       nil
80     else
81       @lowest[1]
82     end
83   end
84 end
85
86 #################################################
87 # Calculates rates of every player from a Win Loss GSL::Matrix
88 #
89 class Rating
90   include Math
91
92   # The model of the win possibility is 1/(1 + 10^(-d/400)).
93   # The equation in this class is 1/(1 + e^(-Kd)).
94   # So, K should be calculated like this.
95   K = Math.log(10.0) / 400.0
96   
97   # Convergence limit to stop Newton method.
98   ERROR_LIMIT = 1.0e-3
99   # Stop Newton method after this iterations.
100   COUNT_MAX = 500
101
102   # Average rate among the players
103   AVERAGE_RATE = 1000
104
105   
106   ###############
107   # Class methods
108   #  
109   
110   ##
111   # Calcurates the average of the vector.
112   #
113   def Rating.average(vector, mean=0.0)
114     sum = Array(vector).inject(0.0) {|sum, n| sum + n}
115     vector -= GSL::Vector[*Array.new(vector.size, sum/vector.size - mean)]
116     vector
117   end
118
119   ##################
120   # Instance methods
121   #
122   def initialize(win_loss_matrix)
123     @record = Record.new
124     @n = win_loss_matrix
125     case @n
126     when GSL::Matrix, GSL::Matrix::Int
127       @size = @n.size1
128     when ::Matrix
129       @size = @n.row_size
130     else
131       raise ArgumentError
132     end
133     initial_rate
134   end
135   attr_reader :rate, :n
136
137   def player_vector
138     GSL::Vector[*
139       (0...@size).collect {|k| yield k}
140     ]
141   end
142
143   def each_player
144     (0...@size).each {|k| yield k}
145   end
146
147   ##
148   # The possibility that the player k will beet the player i.
149   #
150   def win_rate(k,i)
151     1.0/(1.0 + exp(@rate[i]-@rate[k]))
152   end
153
154   ##
155   # Most possible equation
156   #
157   def func_vector
158     player_vector do|k| 
159       sum = 0.0
160       each_player do |i|
161         next if i == k
162         sum += @n[k,i] * win_rate(i,k) - @n[i,k] * win_rate(k,i) 
163       end
164       sum * 2.0
165     end
166   end
167
168   ##
169   #           / f0/R0 f0/R1 f0/R2 ... \
170   # dfk/dRj = | f1/R0 f1/R1 f1/R2 ... |
171   #           \ f2/R0 f2/R1 f2/R2 ... /
172   def d_func(k,j)
173     sum = 0.0
174     if k == j
175       each_player do |i|
176         next if i == k
177         sum += win_rate(i,k) * win_rate(k,i) * (@n[k,i] + @n[i,k])
178       end
179       sum *= -2.0
180     else # k != j
181       sum = 2.0 * win_rate(j,k) * win_rate(k,j) * (@n[k,j] + @n[j,k])
182     end
183     sum
184   end
185
186   ##
187   # Jacobi matrix of the func().
188   #   m00 m01
189   #   m10 m11
190   #
191   def j_matrix
192     GSL::Matrix[*
193       (0...@size).collect do |k|
194         (0...@size).collect do |j|
195           d_func(k,j)
196         end
197       end
198     ]
199   end
200
201   ##
202   # The initial value of the rate, which is of very importance for Newton method.
203   # This is based on my huristics; the higher the win probablity of a player is, 
204   # the greater points he takes.
205   #
206   def initial_rate
207     possibility = 
208       player_vector do |k|
209         v = GSL::Vector[0, 0]
210         each_player do |i|
211           next if k == i
212           v += GSL::Vector[@n[k,i], @n[i,k]]
213         end
214         v.nrm2 < 1 ? 0 : v[0] / (v[0] + v[1])
215       end
216     rank = possibility.sort_index
217     @rate = player_vector do |k|
218       K*500 * (rank[k]+1) / @size
219     end
220     average!
221   end
222
223   ##
224   # Resets @rate as the higher the current win probablity of a player is, 
225   # the greater points he takes. 
226   #
227   def initial_rate2
228     @rate = @record.get || @rate
229     rank = @rate.sort_index
230     @rate = player_vector do |k|
231       K*@count*1.5 * (rank[k]+1) / @size
232     end
233     average!
234   end
235
236   # mu is the deaccelrating parameter in Deaccelerated Newton method
237   def deaccelrate(mu, old_rate, a, old_f_nrm2)
238     @rate = old_rate - a * mu
239     if func_vector.nrm2 < (1 - mu / 4.0 ) * old_f_nrm2 then
240       return
241     end
242     if mu < 1e-4
243       @record.set(func_vector.nrm2, @rate)
244       initial_rate2
245       return
246     end
247     $stderr.puts "mu: %f " % [mu] if $DEBUG
248     deaccelrate(mu*0.5, old_rate, a, old_f_nrm2)
249   end
250
251   ##
252   # Main process to calculate ratings.
253   #
254   def rating
255     # Counter to stop the process. 
256     # Calulation in Newton method may fall in an infinite loop
257     @count = 0
258
259     # Main loop
260     begin
261       # Solve the equation: 
262       #   J*a=f
263       #   @rate_(n+1) = @rate_(n) - a
264       #
265       # f.nrm2 should approach to zero.
266       f = func_vector
267       j = j_matrix
268
269       # $stderr.puts "j: %s" % [j.inspect] if $DEBUG
270       $stderr.puts "f: %s -> %f" % [f.to_a.inspect, f.nrm2] if $DEBUG
271
272       # GSL::Linalg::LU.solve or GSL::Linalg::HH.solve would be available instead.
273       a = GSL::Linalg::SV.solve(j, f)
274       a = self.class.average(a)
275       # $stderr.puts "a: %s -> %f" % [a.to_a.inspect, a.nrm2] if $DEBUG
276       
277       # Deaccelerated Newton method
278       # GSL::Vector object should be immutable.
279       old_rate   = @rate
280       old_f      = f
281       old_f_nrm2 = old_f.nrm2
282       deaccelrate(1.0, old_rate, a, old_f_nrm2)
283       @record.set(func_vector.nrm2, @rate)
284
285       $stderr.printf "|error| : %5.2e\n", a.nrm2 if $DEBUG
286
287       @count += 1
288       if @count > COUNT_MAX
289         $stderr.puts "Values seem to oscillate. Stopped the process."
290         $stderr.puts "f: %s -> %f" % [func_vector.to_a.inspect, func_vector.nrm2]
291         break
292       end
293
294     end while (a.nrm2 > ERROR_LIMIT * @rate.nrm2)
295     
296     @rate = @record.get
297     $stderr.puts "resolved f: %s -> %f" %
298       [func_vector.to_a.inspect, func_vector.nrm2] if $DEBUG
299
300     @rate *= 1.0/K
301     finite!
302     self
303   end
304
305   ##
306   # Make the values of @rate finite.
307   #
308   def finite!
309     @rate = @rate.collect do |a|
310       if a.infinite?
311         a.infinite? * AVERAGE_RATE * 100
312       else
313         a
314       end
315     end
316   end
317
318   ##
319   # Flatten the values of @rate.
320   #
321   def average!(mean=0.0)
322     @rate = self.class.average(@rate, mean)
323   end
324
325   ##
326   # Make the values of @rate integer.
327   #
328   def integer!
329     @rate = @rate.collect do |a|
330       if a.finite?
331         a.to_i
332       elsif a.nan?
333         0
334       elsif a.infinite?
335         a.infinite? * AVERAGE_RATE * 100
336       end
337     end
338   end
339 end
340
341
342
343 #################################################
344 # Main methods
345 #
346
347 def mk_matrix(players)
348         keys = players.keys.sort
349   size = keys.size
350   matrix =
351           Matrix::Int[*
352                 ((0...size).collect do |k|
353       p1 = keys[k]
354       p1_hash = players[p1]
355                   ((0...size).collect do |j|
356                           if k == j
357                                   0
358                           else
359           p2 = keys[j]
360           v = p1_hash[p2] || Vector[0,0]
361                                   v[0]
362                           end
363                   end)
364                 end)]
365   return matrix, keys
366 end
367
368 def delete_row(matrix, keys, delete_index)
369   size = keys.size
370   copied_cols = []
371   (0...size).each do |i|
372     next if i == delete_index
373     row = matrix.get_row(i)  # get_row returns a copy of the row
374     row.delete_at(delete_index)
375     copied_cols << row
376   end
377   new_matrix = Matrix::Int[*copied_cols]
378   new_keys = keys.clone
379   new_keys.delete_at(delete_index)
380   return new_matrix, new_keys
381 end
382
383 def filter(matrix, keys)
384   $stderr.puts keys.inspect if $DEBUG
385   $stderr.puts matrix.inspect if $DEBUG
386   size = keys.size
387   delete = []  
388   (0...size).each do |i|
389     row = matrix.row(i)
390     col = matrix.col(i)
391     win  = row.sum
392     loss = col.sum
393     if win < 1 || loss < 1 || win + loss < $GAMES_LIMIT
394       delete << i
395     end
396   end
397
398   # The recursion ends if there is nothing to delete
399   return matrix, keys if delete.empty?
400   
401   delete.reverse.each do |i|
402     matrix, keys = delete_row(matrix, keys, i)
403   end
404   filter(matrix, keys)
405 end
406
407 def mk_win_loss_matrix(players)
408   matrix, keys = mk_matrix(players)
409   filter(matrix, keys)
410 end
411
412 def _add_win_loss(winner, loser)
413   $players[winner] ||= Hash.new { GSL::Vector[0,0] }
414   $players[loser]  ||= Hash.new { GSL::Vector[0,0] }
415   $players[winner][loser] += GSL::Vector[1,0]
416   $players[loser][winner] += GSL::Vector[0,1]
417 end
418
419 def _add_time(player, time)
420   $players_time[player] = time if $players_time[player] < time
421 end
422
423 def add(black_mark, black_name, white_name, white_mark, time)
424   if black_mark == WIN_MARK && white_mark == LOSS_MARK
425     _add_win_loss(black_name, white_name)
426   elsif black_mark == LOSS_MARK && white_mark == WIN_MARK
427     _add_win_loss(white_name, black_name)
428   elsif black_mark == DRAW_MARK && white_mark == DRAW_MARK
429     return
430   else
431     raise "Never reached!"
432   end
433   _add_time(black_name, time)
434   _add_time(white_name, time)
435 end
436
437 def identify_id(id)
438   if /@NORATE\+/ =~ id # the player having @NORATE in the name should not be rated
439     return nil
440   end
441   id.gsub(/@.*?\+/,"+")
442 end
443
444 def grep(file)
445   str = File.open(file).read
446
447   if /^N\+(.*)$/ =~ str then black_name = $1.strip end
448   if /^N\-(.*)$/ =~ str then white_name = $1.strip end
449
450   if /^'summary:(.*)$/ =~ str
451     dummy, p1, p2 = $1.split(":").map {|a| a.strip}    
452     p1_name, p1_mark = p1.split(" ")
453     p2_name, p2_mark = p2.split(" ")
454     if p1_name == black_name
455       black_name, black_mark = p1_name, p1_mark
456       white_name, white_mark = p2_name, p2_mark
457     elsif p2_name == black_name
458       black_name, black_mark = p2_name, p2_mark
459       white_name, white_mark = p1_name, p1_mark
460     else
461       raise "Never reach!: #{black} #{white} #{p1} #{p2}"
462     end
463   end
464   if /^'\$END_TIME:(.*)$/ =~ str
465     time = Time.parse($1.strip)
466   end
467   if /^'rating:(.*)$/ =~ str
468     black_id, white_id = $1.split(":").map {|a| a.strip}
469     black_id = identify_id(black_id)
470     white_id = identify_id(white_id)
471     if black_id && white_id && (black_id != white_id)
472       add(black_mark, black_id, white_id, white_mark, time)
473     end
474   end
475 end
476
477 def usage
478   $stderr.puts <<-EOF
479 USAGE: #{$0} dir [...]
480   EOF
481   exit 1
482 end
483
484 def main
485   usage if ARGV.empty?
486   while dir = ARGV.shift do
487     Dir.glob( File.join(dir, "**", "*.csa") ) {|f| grep(f)}
488   end
489
490   win_loss_matrix, keys = mk_win_loss_matrix($players)
491   rating = Rating.new(win_loss_matrix)
492   rating.rating
493   rating.average!(Rating::AVERAGE_RATE)
494   rating.integer!
495
496   yaml = {}
497   keys.each_with_index do |p, i| # player_id, index#
498     win  = win_loss_matrix.row(i).sum
499     loss = win_loss_matrix.col(i).sum
500
501     yaml[p] = 
502       { 'name' => p.split("+")[0],
503         'rate' => rating.rate[i],
504         'last_modified' => $players_time[p].dup,
505         'win'  => win,
506         'loss' => loss}
507   end
508   puts yaml.to_yaml
509 end
510
511 if __FILE__ == $0
512   main
513 end
514
515 # vim: ts=2 sw=2 sts=0