OSDN Git Service

Add mk_rate.
[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 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|
220                 yaml[p] = 
221                         { 'name' => p.split("+")[0],
222                     'rate' => rating.rate[i],
223                     'last_modified' => $players_time[p]}
224         end
225         puts yaml.to_yaml
226 end
227
228 if __FILE__ == $0
229         main
230 end
231
232 # vim: ts=2 sw=2 sts=0