OSDN Git Service

dc6813e7e8710054b37c95a0782aa9a62a55a325
[shogi-server/shogi-server.git] / mk_rate
1 #!/usr/bin/ruby
2 ## $Id$
3
4 ## Copyright (C) 2006-2008 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 #   $ ./mk_rate . && ./mk_rate . > players.yaml
27 #
28 # The conditions that games and players are rated as following:
29 #   * Rated games, which were played by both rated players.
30 #   * Rated players, who logged in the server with a name followed by a trip:
31 #     "name,trip".
32 #   * (Rated) players, who played more than $GAMES_LIMIT [15] (rated) games. 
33 #
34 #
35 # PREREQUIRE
36 # ==========
37 #
38 # Sample Commands to isntall prerequires will work for Debian.
39 #
40 # * Rubygems
41 #   $ sudo aptitude install rubygems
42 #
43 # * Ruby bindings for the GNU Scientific Library (GSL)
44 #   $ sudo aptitude install libgsl-ruby1.8
45 #   Or, download it from  http://rb-gsl.rubyforge.org/ .
46 #
47 # * RGL: Ruby Graph Library
48 #   $ sudo gem install rgl
49 #   Or, download it from http://rubyforge.org/projects/rgl/ .
50 #
51
52 require 'yaml'
53 require 'time'
54 require 'gsl'
55 require 'rubygems'
56 require 'rgl/adjacency'
57 require 'rgl/connected_components'
58
59 #################################################
60 # Constants
61 #
62
63 # Count out players who play less games than $GAMES_LIMIT
64 $GAMES_LIMIT = $DEBUG ? 0 : 15
65 WIN_MARK  = "win"
66 LOSS_MARK = "lose"
67 DRAW_MARK = "draw"
68
69 # Holds players
70 $players = Hash.new
71 # Holds the last time when a player gamed
72 $players_time = Hash.new { Time.at(0) }
73
74
75 #################################################
76 # Keeps the value of the lowest key
77 #
78 class Record
79   def initialize
80     @lowest = []
81   end
82
83   def set(key, value)
84     if @lowest.empty? || key < @lowest[0]
85       @lowest = [key, value]
86     end
87   end
88
89   def get
90     if @lowest.empty?
91       nil
92     else
93       @lowest[1]
94     end
95   end
96 end
97
98 #################################################
99 # Calculates rates of every player from a Win Loss GSL::Matrix
100 #
101 class Rating
102   include Math
103
104   # The model of the win possibility is 1/(1 + 10^(-d/400)).
105   # The equation in this class is 1/(1 + e^(-Kd)).
106   # So, K should be calculated like this.
107   K = Math.log(10.0) / 400.0
108   
109   # Convergence limit to stop Newton method.
110   ERROR_LIMIT = 1.0e-3
111   # Stop Newton method after this iterations.
112   COUNT_MAX = 500
113
114   # Average rate among the players
115   AVERAGE_RATE = 1000
116
117   
118   ###############
119   # Class methods
120   #  
121   
122   ##
123   # Calcurates the average of the vector.
124   #
125   def Rating.average(vector, mean=0.0)
126     sum = Array(vector).inject(0.0) {|sum, n| sum + n}
127     vector -= GSL::Vector[*Array.new(vector.size, sum/vector.size - mean)]
128     vector
129   end
130
131   ##################
132   # Instance methods
133   #
134   def initialize(win_loss_matrix)
135     @record = Record.new
136     @n = win_loss_matrix
137     case @n
138     when GSL::Matrix, GSL::Matrix::Int
139       @size = @n.size1
140     when ::Matrix
141       @size = @n.row_size
142     else
143       raise ArgumentError
144     end
145     initial_rate
146   end
147   attr_reader :rate, :n
148
149   def player_vector
150     GSL::Vector[*
151       (0...@size).collect {|k| yield k}
152     ]
153   end
154
155   def each_player
156     (0...@size).each {|k| yield k}
157   end
158
159   ##
160   # The possibility that the player k will beet the player i.
161   #
162   def win_rate(k,i)
163     1.0/(1.0 + exp(@rate[i]-@rate[k]))
164   end
165
166   ##
167   # Most possible equation
168   #
169   def func_vector
170     player_vector do|k| 
171       sum = 0.0
172       each_player do |i|
173         next if i == k
174         sum += @n[k,i] * win_rate(i,k) - @n[i,k] * win_rate(k,i) 
175       end
176       sum * 2.0
177     end
178   end
179
180   ##
181   #           / f0/R0 f0/R1 f0/R2 ... \
182   # dfk/dRj = | f1/R0 f1/R1 f1/R2 ... |
183   #           \ f2/R0 f2/R1 f2/R2 ... /
184   def d_func(k,j)
185     sum = 0.0
186     if k == j
187       each_player do |i|
188         next if i == k
189         sum += win_rate(i,k) * win_rate(k,i) * (@n[k,i] + @n[i,k])
190       end
191       sum *= -2.0
192     else # k != j
193       sum = 2.0 * win_rate(j,k) * win_rate(k,j) * (@n[k,j] + @n[j,k])
194     end
195     sum
196   end
197
198   ##
199   # Jacobi matrix of the func().
200   #   m00 m01
201   #   m10 m11
202   #
203   def j_matrix
204     GSL::Matrix[*
205       (0...@size).collect do |k|
206         (0...@size).collect do |j|
207           d_func(k,j)
208         end
209       end
210     ]
211   end
212
213   ##
214   # The initial value of the rate, which is of very importance for Newton
215   # method.  This is based on my huristics; the higher the win probablity of
216   # a player is, the greater points he takes.
217   #
218   def initial_rate
219     possibility = 
220       player_vector do |k|
221         v = GSL::Vector[0, 0]
222         each_player do |i|
223           next if k == i
224           v += GSL::Vector[@n[k,i], @n[i,k]]
225         end
226         v.nrm2 < 1 ? 0 : v[0] / (v[0] + v[1])
227       end
228     rank = possibility.sort_index
229     @rate = player_vector do |k|
230       K*500 * (rank[k]+1) / @size
231     end
232     average!
233   end
234
235   ##
236   # Resets @rate as the higher the current win probablity of a player is, 
237   # the greater points he takes. 
238   #
239   def initial_rate2
240     @rate = @record.get || @rate
241     rank = @rate.sort_index
242     @rate = player_vector do |k|
243       K*@count*1.5 * (rank[k]+1) / @size
244     end
245     average!
246   end
247
248   # mu is the deaccelrating parameter in Deaccelerated Newton method
249   def deaccelrate(mu, old_rate, a, old_f_nrm2)
250     @rate = old_rate - a * mu
251     if func_vector.nrm2 < (1 - mu / 4.0 ) * old_f_nrm2 then
252       return
253     end
254     if mu < 1e-4
255       @record.set(func_vector.nrm2, @rate)
256       initial_rate2
257       return
258     end
259     $stderr.puts "mu: %f " % [mu] if $DEBUG
260     deaccelrate(mu*0.5, old_rate, a, old_f_nrm2)
261   end
262
263   ##
264   # Main process to calculate ratings.
265   #
266   def rating
267     # Counter to stop the process. 
268     # Calulation in Newton method may fall in an infinite loop
269     @count = 0
270
271     # Main loop
272     begin
273       # Solve the equation: 
274       #   J*a=f
275       #   @rate_(n+1) = @rate_(n) - a
276       #
277       # f.nrm2 should approach to zero.
278       f = func_vector
279       j = j_matrix
280
281       # $stderr.puts "j: %s" % [j.inspect] if $DEBUG
282       $stderr.puts "f: %s -> %f" % [f.to_a.inspect, f.nrm2] if $DEBUG
283
284       # GSL::Linalg::LU.solve or GSL::Linalg::HH.solve would be available instead.
285       #a = GSL::Linalg::HH.solve(j, f)
286       a, = GSL::MultiFit::linear(j, f)
287       a = self.class.average(a)
288       # $stderr.puts "a: %s -> %f" % [a.to_a.inspect, a.nrm2] if $DEBUG
289       
290       # Deaccelerated Newton method
291       # GSL::Vector object should be immutable.
292       old_rate   = @rate
293       old_f      = f
294       old_f_nrm2 = old_f.nrm2
295       deaccelrate(1.0, old_rate, a, old_f_nrm2)
296       @record.set(func_vector.nrm2, @rate)
297
298       $stderr.printf "|error| : %5.2e\n", a.nrm2 if $DEBUG
299
300       @count += 1
301       if @count > COUNT_MAX
302         $stderr.puts "Values seem to oscillate. Stopped the process."
303         $stderr.puts "f: %s -> %f" % [func_vector.to_a.inspect, func_vector.nrm2]
304         break
305       end
306
307     end while (a.nrm2 > ERROR_LIMIT * @rate.nrm2)
308     
309     @rate = @record.get
310     $stderr.puts "resolved f: %s -> %f" %
311       [func_vector.to_a.inspect, func_vector.nrm2] if $DEBUG
312
313     @rate *= 1.0/K
314     finite!
315     self
316   end
317
318   ##
319   # Make the values of @rate finite.
320   #
321   def finite!
322     @rate = @rate.collect do |a|
323       if a.infinite?
324         a.infinite? * AVERAGE_RATE * 100
325       else
326         a
327       end
328     end
329   end
330
331   ##
332   # Flatten the values of @rate.
333   #
334   def average!(mean=0.0)
335     @rate = self.class.average(@rate, mean)
336   end
337
338   ##
339   # Make the values of @rate integer.
340   #
341   def integer!
342     @rate = @rate.collect do |a|
343       if a.finite?
344         a.to_i
345       elsif a.nan?
346         0
347       elsif a.infinite?
348         a.infinite? * AVERAGE_RATE * 100
349       end
350     end
351   end
352 end
353
354 #################################################
355 # Encapsulate a pair of keys and win loss matrix.
356 #   - keys is an array of player IDs; [gps+123, foo+234, ...]
357 #   - matrix holds games # where player i (row index) beats player j (column index).
358 #     The row and column indexes match with the keys.
359 #
360 # This object should be immutable. If an internal state is being modified, a
361 # new object is always returned.
362 #
363 class WinLossMatrix
364
365   ###############
366   # Class methods
367   #  
368
369   def self.mk_matrix(players)
370     keys = players.keys.sort
371     size = keys.size
372     matrix =
373       GSL::Matrix[*
374       ((0...size).collect do |k|
375         p1 = keys[k]
376         p1_hash = players[p1]
377         ((0...size).collect do |j|
378           if k == j
379             0
380           else
381             p2 = keys[j]
382             v = p1_hash[p2] || Vector[0,0]
383             v[0]
384           end
385         end)
386       end)]
387     return WinLossMatrix.new(keys, matrix)
388   end
389
390   def self.mk_win_loss_matrix(players)
391     obj = mk_matrix(players)
392     return obj.filter
393   end
394
395   ##################
396   # Instance methods
397   #
398
399   # an array of player IDs; [gps+123, foo+234, ...]
400   attr_reader :keys
401
402   # matrix holds games # where player i (row index) beats player j (column index).
403   # The row and column indexes match with the keys.
404   attr_reader :matrix
405
406   def initialize(keys, matrix)
407     @keys   = keys
408     @matrix = matrix
409   end
410
411   ##
412   # Returns the size of the keys/matrix
413   #
414   def size
415     if @keys
416       @keys.size
417     else
418       nil
419     end
420   end
421
422   ##
423   # Removes a delete_index'th player and returns a new object.
424   #
425   def delete_row(delete_index)
426     copied_cols = []
427     (0...size).each do |i|
428       next if i == delete_index
429       row = @matrix.row(i).clone
430       row.delete_at(delete_index)
431       copied_cols << row
432     end
433     if copied_cols.size == 0
434       new_matrix = GSL::Matrix.new
435     else
436       new_matrix = GSL::Matrix[*copied_cols]
437     end
438     new_keys = @keys.clone
439     new_keys.delete_at(delete_index)
440     return WinLossMatrix.new(new_keys, new_matrix)
441   end
442
443   ##
444   # Removes players in a rows; [1,3,5]
445   #
446   def delete_rows(rows)
447     obj = self
448     rows.sort.reverse.each do |index|
449       obj = obj.delete_row(index)
450     end
451     obj
452   end
453
454   ##
455   # Removes players who do not pass a criteria to be rated, and returns a
456   # new object.
457   # 
458   def filter
459     $stderr.puts @keys.inspect if $DEBUG
460     $stderr.puts @matrix.inspect if $DEBUG
461     delete = []  
462     (0...size).each do |i|
463       row = @matrix.row(i)
464       col = @matrix.col(i)
465       win  = row.sum
466       loss = col.sum
467       if win < 1 || loss < 1 || win + loss < $GAMES_LIMIT
468         delete << i
469       end
470     end
471
472     # The recursion ends if there is nothing to delete
473     return self if delete.empty?
474
475     new_obj = delete_rows(delete)
476     new_obj.filter
477   end
478
479   ##
480   # Cuts self into connecting groups such as each player in a group has at least
481   # one game with other players in the group. Returns them as an array.
482   #
483   def connected_subsets
484     g = RGL::AdjacencyGraph.new
485     (0...size).each do |k|
486       (0...size).each do |i|
487         next if k == i
488         if @matrix[k,i] > 0
489           g.add_edge(k,i)
490         end
491       end
492     end
493
494     subsets = []
495     g.each_connected_component do |c|
496       new_keys = []      
497       c.each do |v|
498         new_keys << keys[v.to_s.to_i]
499       end
500       subsets << new_keys
501     end
502
503     subsets = subsets.sort {|a,b| b.size <=> a.size}
504
505     result = subsets.collect do |keys|
506       matrix =
507         GSL::Matrix[*
508         ((0...keys.size).collect do |k|
509           p1 = @keys.index(keys[k])
510           ((0...keys.size).collect do |j|
511             if k == j
512               0
513             else
514               p2 = @keys.index(keys[j])
515               @matrix[p1,p2]
516             end
517           end)
518         end)]
519       WinLossMatrix.new(keys, matrix)
520     end
521
522     return result
523   end
524
525   def to_s
526     "size : #{@keys.size}" + "\n" +
527     @keys.inspect + "\n" + 
528     @matrix.inspect
529   end
530
531 end
532
533
534 #################################################
535 # Main methods
536 #
537
538 # Half-life effect
539 # After NHAFE_LIFE days value will get half.
540 # 0.693 is constant, where exp(0.693) ~ 0.5
541 NHALF_LIFE=60
542 def half_life(days)
543   if days < 7
544     return 1.0
545   else
546     Math::exp(-0.693/NHALF_LIFE*(days-7))
547   end
548 end
549
550 def _add_win_loss(winner, loser, time)
551   how_long_days = (Time.now - time)/(3600*24)
552   $players[winner] ||= Hash.new { GSL::Vector[0,0] }
553   $players[loser]  ||= Hash.new { GSL::Vector[0,0] }
554   $players[winner][loser] += GSL::Vector[1.0*half_life(how_long_days),0]
555   $players[loser][winner] += GSL::Vector[0,1.0*half_life(how_long_days)]
556 end
557
558 def _add_time(player, time)
559   $players_time[player] = time if $players_time[player] < time
560 end
561
562 def add(black_mark, black_name, white_name, white_mark, time)
563   if black_mark == WIN_MARK && white_mark == LOSS_MARK
564     _add_win_loss(black_name, white_name, time)
565   elsif black_mark == LOSS_MARK && white_mark == WIN_MARK
566     _add_win_loss(white_name, black_name, time)
567   elsif black_mark == DRAW_MARK && white_mark == DRAW_MARK
568     return
569   else
570     raise "Never reached!"
571   end
572   _add_time(black_name, time)
573   _add_time(white_name, time)
574 end
575
576 def identify_id(id)
577   if /@NORATE\+/ =~ id # the player having @NORATE in the name should not be rated
578     return nil
579   end
580   id.gsub(/@.*?\+/,"+")
581 end
582
583 def grep(file)
584   str = File.open(file).read
585
586   if /^N\+(.*)$/ =~ str then black_name = $1.strip end
587   if /^N\-(.*)$/ =~ str then white_name = $1.strip end
588
589   if /^'summary:(.*)$/ =~ str
590     state, p1, p2 = $1.split(":").map {|a| a.strip}    
591     return if state == "abnormal"
592     p1_name, p1_mark = p1.split(" ")
593     p2_name, p2_mark = p2.split(" ")
594     if p1_name == black_name
595       black_name, black_mark = p1_name, p1_mark
596       white_name, white_mark = p2_name, p2_mark
597     elsif p2_name == black_name
598       black_name, black_mark = p2_name, p2_mark
599       white_name, white_mark = p1_name, p1_mark
600     else
601       raise "Never reach!: #{black} #{white} #{p3} #{p2}"
602     end
603   end
604   if /^'\$END_TIME:(.*)$/ =~ str
605     time = Time.parse($1.strip)
606   end
607   if /^'rating:(.*)$/ =~ str
608     black_id, white_id = $1.split(":").map {|a| a.strip}
609     black_id = identify_id(black_id)
610     white_id = identify_id(white_id)
611     if black_id && white_id && (black_id != white_id)
612       add(black_mark, black_id, white_id, white_mark, time)
613     end
614   end
615 end
616
617 def usage
618   $stderr.puts <<-EOF
619 USAGE: #{$0} dir [...]
620   EOF
621   exit 1
622 end
623
624 def validate(yaml)
625   yaml["players"].each do |group_key, group|
626     group.each do |player_key, player|
627       rate = player['rate']
628       next unless rate
629       if rate > 10000 || rate < -10000
630         return false
631       end
632     end
633   end
634   return true
635 end
636
637 def main
638   usage if ARGV.empty?
639   while dir = ARGV.shift do
640     Dir.glob( File.join(dir, "**", "*.csa") ) {|f| grep(f)}
641   end
642
643   yaml = {} 
644   yaml["players"] = {}
645   rating_group = 0
646   if $players.size > 0
647     obj = WinLossMatrix::mk_win_loss_matrix($players)
648     obj.connected_subsets.each do |win_loss_matrix|
649       yaml["players"][rating_group] = {}
650
651       rating = Rating.new(win_loss_matrix.matrix)
652       rating.rating
653       rating.average!(Rating::AVERAGE_RATE)
654       rating.integer!
655
656       win_loss_matrix.keys.each_with_index do |p, i| # player_id, index#
657         win  = win_loss_matrix.matrix.row(i).sum
658         loss = win_loss_matrix.matrix.col(i).sum
659
660         yaml["players"][rating_group][p] = 
661           { 'name' => p.split("+")[0],
662             'rating_group' => rating_group,
663             'rate' => rating.rate[i],
664             'last_modified' => $players_time[p].dup,
665             'win'  => win,
666             'loss' => loss}
667       end
668       rating_group += 1
669     end
670   end
671   rating_group -= 1
672   non_rated_group = 999 # large enough
673   yaml["players"][non_rated_group] = {}
674   $players.each_key do |id|
675     # skip players who have already been rated
676     found = false
677     (0..rating_group).each do |i|
678        found = true if yaml["players"][i][id]
679        break if found
680     end
681     next if found
682
683     v = GSL::Vector[0, 0]
684     $players[id].each_value {|value| v += value}
685     next if v[0] < 1 && v[1] < 1
686
687     yaml["players"][non_rated_group][id] =
688       { 'name' => id.split("+")[0],
689         'rating_group' => non_rated_group,
690         'rate' => 0,
691         'last_modified' => $players_time[id].dup,
692         'win'  => v[0],
693         'loss' => v[1]}
694   end
695   unless validate(yaml)
696     $stderr.puts "Aborted. It did not result in valid ratings."
697     $stderr.puts yaml.to_yaml if $DEBUG
698     exit 10
699   end
700   puts yaml.to_yaml
701 end
702
703 if __FILE__ == $0
704   main
705 end
706
707 # vim: ts=2 sw=2 sts=0