OSDN Git Service

For ease to see in the players.yaml.
[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                                           #      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].dup,
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