X-Git-Url: http://git.sourceforge.jp/view?p=shogi-server%2Fshogi-server.git;a=blobdiff_plain;f=mk_rate;h=b5409632582fcfa96fe3bc3f450a72ab0c024c25;hp=919a7c5fef50e90626af34973898cdb607e7165f;hb=62ad30ff63d52c1075d2bea89901b5c4aa7e95d3;hpb=0b30a645a7f898b6f8808cb8586e8fb75b426dda diff --git a/mk_rate b/mk_rate index 919a7c5..b540963 100755 --- a/mk_rate +++ b/mk_rate @@ -1,57 +1,120 @@ -#!/usr/bin/ruby -## $Id$ - -## Copyright (C) 2006 Daigo Moriwaki -## -## This program is free software; you can redistribute it and/or modify -## it under the terms of the GNU General Public License as published by -## the Free Software Foundation; either version 2 of the License, or -## (at your option) any later version. -## -## This program is distributed in the hope that it will be useful, -## but WITHOUT ANY WARRANTY; without even the implied warranty of -## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -## GNU General Public License for more details. -## -## You should have received a copy of the GNU General Public License -## along with this program; if not, write to the Free Software -## Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA - -# -# This calculates rating scores of every players from CSA files, and outputs a -# yaml file (players.yaml) that Shogi Server can read. -# -# Sample: -# $ ./mk_rate . > players.yaml +#!/usr/bin/ruby1.9.1 +# $Id$ # -# The conditions that games and players are rated as following: -# * Rated games, which were played by both rated players. -# * Rated players, who logged in the server with a name followed by a trip: -# "name,trip". -# * (Rated) players, who played more than $GAMES_LIMIT [15] (rated) games. +# Author:: Daigo Moriwaki +# Homepage:: http://sourceforge.jp/projects/shogi-server/ +# +#-- +# Copyright (C) 2006-2012 Daigo Moriwaki +# +# This program is free software; you can redistribute it and/or modify +# it under the terms of the GNU General Public License as published by +# the Free Software Foundation; either version 2 of the License, or +# (at your option) any later version. +# +# This program is distributed in the hope that it will be useful, +# but WITHOUT ANY WARRANTY; without even the implied warranty of +# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +# GNU General Public License for more details. +# +# You should have received a copy of the GNU General Public License +# along with this program; if not, write to the Free Software +# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA +#++ +# +# == Synopsis +# +# mk_rate reads game results files generated by the mk_game_results command, +# calculates rating scores of each player, and then outputs a yaml file +# (players.yaml) that Shogi-server can recognize. +# +# == Usage +# +# ./mk_rate [options] GAME_RESULTS_FILE [...] +# +# ./mk_rate [options] +# +# GAME_RESULTS_FILE:: +# a path to a file listing results of games, which is generated by the +# mk_game_results command. +# In the second style above, the file content can be read from the stdin. +# +# --abnormal-threshold:: +# n [plies] (default 30) +# Games that end with the 'abnormal' status are counted in win/lost games +# for the rating calculation if a game plays more than n plies. Otherwise +# (or if n is zero), abnormal games are counted out of rating games. +# +# --base-date:: +# a base time point for this calculation (default now). Ex. '2009-10-31' +# +# --half-life:: +# n [days] (default 60) +# +# --half-life-ignore:: +# m [days] (default 7) +# after m days, the half-life effect works +# +# --ignore:: +# m [days] (default 365*2) +# old results will be ignored +# +# --fixed-rate-player:: +# player whose rate is fixed at the rate +# +# --fixed-rate:: +# rate +# +# --skip-draw-games:: +# skip draw games. [default: draw games are counted in as 0.5 win and 0.5 +# lost.] +# +# --help:: +# show this message +# +# == PREREQUIRE +# +# Sample Command lines that install prerequires will work on Debian. +# +# * Ruby 1.9.3 or 1.8.7 (including Rubygems) +# +# $ sudo aptitude install ruby1.9.1 # +# * Ruby bindings for the GNU Scientific Library (GSL[http://rb-gsl.rubyforge.org/]) # -# PREREQUIRE -# ========== +# $ sudo aptitude install ruby-gsl # -# Sample Commands to isntall prerequires will work for Debian. +# * RGL: {Ruby Graph Library}[http://rubyforge.org/projects/rgl/] # -# * Rubygems -# $ sudo aptitude install rubygems +# $ sudo gem1.9.1 install rgl # -# * Ruby bindings for the GNU Scientific Library (GSL) -# $ sudo aptitude install libgsl-ruby1.8 -# Or, download it from http://rb-gsl.rubyforge.org/ . +# == Examples # -# * RGL: Ruby Graph Library -# $ sudo gem install rgl -# Or, download it from http://rubyforge.org/projects/rgl/ . +# $ ./mk_rate game_results.txt > players.yaml +# +# $ ./mk_game_results . | ./mk_rate > players.yaml +# +# If you do not want the file to be update in case of errors, +# +# $ ./mk_rate game_results.txt && ./mk_rate game_results.txt > players.yaml +# +# == How players are rated +# +# The conditions that games and players are rated as following: +# +# * Rated games, which were played by both rated players. +# * Rated players, who logged in the server with a name followed by a trip: "name,trip". +# * (Rated) players, who played more than $GAMES_LIMIT [15] (rated) games. # +$:.unshift(File.dirname(File.expand_path(__FILE__))) +require 'utils/csa-filter' require 'yaml' require 'time' -require 'gsl' +require 'getoptlong' +require 'set' require 'rubygems' +require 'gsl' require 'rgl/adjacency' require 'rgl/connected_components' @@ -69,6 +132,8 @@ DRAW_MARK = "draw" $players = Hash.new # Holds the last time when a player gamed $players_time = Hash.new { Time.at(0) } +# Holds history of input lines to check duplicated inputs +$history = Set.new ################################################# @@ -210,9 +275,9 @@ class Rating end ## - # The initial value of the rate, which is of very importance for Newton method. - # This is based on my huristics; the higher the win probablity of a player is, - # the greater points he takes. + # The initial value of the rate, which is of very importance for Newton + # method. This is based on my huristics; the higher the win probablity of + # a player is, the greater points he takes. # def initial_rate possibility = @@ -281,7 +346,8 @@ class Rating $stderr.puts "f: %s -> %f" % [f.to_a.inspect, f.nrm2] if $DEBUG # GSL::Linalg::LU.solve or GSL::Linalg::HH.solve would be available instead. - a = GSL::Linalg::SV.solve(j, f) + #a = GSL::Linalg::HH.solve(j, f) + a, = GSL::MultiFit::linear(j, f) a = self.class.average(a) # $stderr.puts "a: %s -> %f" % [a.to_a.inspect, a.nrm2] if $DEBUG @@ -291,6 +357,7 @@ class Rating old_f = f old_f_nrm2 = old_f.nrm2 deaccelrate(1.0, old_rate, a, old_f_nrm2) + #@rate -= a # Instead, do not deaccelerate @record.set(func_vector.nrm2, @rate) $stderr.printf "|error| : %5.2e\n", a.nrm2 if $DEBUG @@ -307,6 +374,7 @@ class Rating @rate = @record.get $stderr.puts "resolved f: %s -> %f" % [func_vector.to_a.inspect, func_vector.nrm2] if $DEBUG + $stderr.puts "Count: %d" % [@count] if $DEBUG @rate *= 1.0/K finite! @@ -334,6 +402,13 @@ class Rating end ## + # Translate by value + # + def translate!(value) + @rate += value + end + + ## # Make the values of @rate integer. # def integer! @@ -368,7 +443,7 @@ class WinLossMatrix keys = players.keys.sort size = keys.size matrix = - Matrix[* + GSL::Matrix[* ((0...size).collect do |k| p1 = keys[k] p1_hash = players[p1] @@ -377,7 +452,7 @@ class WinLossMatrix 0 else p2 = keys[j] - v = p1_hash[p2] || Vector[0,0] + v = p1_hash[p2] || GSL::Vector[0,0] v[0] end end) @@ -418,35 +493,38 @@ class WinLossMatrix end ## - # Removes a delete_index'th player and returns a new object. + # Removes players in a rows such as [1,3,5], and then returns a new + # object. # - def delete_row(delete_index) + def delete_rows(rows) + rows = rows.sort.reverse + copied_cols = [] (0...size).each do |i| - next if i == delete_index - row = @matrix.get_row(i) # get_row returns a copy of the row - row.delete_at(delete_index) + next if rows.include?(i) + row = @matrix.row(i).clone + rows.each do |j| + row.delete_at(j) + end copied_cols << row end - new_matrix = Matrix[*copied_cols] - new_keys = @keys.clone - new_keys.delete_at(delete_index) - return WinLossMatrix.new(new_keys, new_matrix) - end + if copied_cols.size == 0 + new_matrix = GSL::Matrix.new + else + new_matrix = GSL::Matrix[*copied_cols] + end - ## - # Removes players in a rows; [1,3,5] - # - def delete_rows(rows) - obj = self - rows.sort.reverse.each do |index| - obj = obj.delete_row(index) + new_keys = @keys.clone + rows.each do |j| + new_keys.delete_at(j) end - obj + + return WinLossMatrix.new(new_keys, new_matrix) end ## - # Removes players who do not pass a criteria to be rated, and returns a new object. + # Removes players who do not pass a criteria to be rated, and returns a + # new object. # def filter $stderr.puts @keys.inspect if $DEBUG @@ -497,7 +575,7 @@ class WinLossMatrix result = subsets.collect do |keys| matrix = - Matrix[* + GSL::Matrix[* ((0...keys.size).collect do |k| p1 = @keys.index(keys[k]) ((0...keys.size).collect do |j| @@ -505,7 +583,7 @@ class WinLossMatrix 0 else p2 = @keys.index(keys[j]) - @matrix[p1][p2] + @matrix[p1,p2] end end) end)] @@ -531,23 +609,30 @@ end # Half-life effect # After NHAFE_LIFE days value will get half. # 0.693 is constant, where exp(0.693) ~ 0.5 -NHALF_LIFE=60 def half_life(days) - if days < 7 + if days < $options["half-life-ignore"] return 1.0 else - Math::exp(-0.693/NHALF_LIFE*(days-7)) + Math::exp(-0.693/$options["half-life"]*(days-$options["half-life-ignore"])) end end def _add_win_loss(winner, loser, time) - how_long_days = (Time.now - time)/(3600*24) + how_long_days = ($options["base-date"] - time)/(3600*24) $players[winner] ||= Hash.new { GSL::Vector[0,0] } $players[loser] ||= Hash.new { GSL::Vector[0,0] } $players[winner][loser] += GSL::Vector[1.0*half_life(how_long_days),0] $players[loser][winner] += GSL::Vector[0,1.0*half_life(how_long_days)] end +def _add_draw(player1, player2, time) + how_long_days = ($options["base-date"] - time)/(3600*24) + $players[player1] ||= Hash.new { GSL::Vector[0,0] } + $players[player2] ||= Hash.new { GSL::Vector[0,0] } + $players[player1][player2] += GSL::Vector[0.5*half_life(how_long_days),0.5*half_life(how_long_days)] + $players[player2][player1] += GSL::Vector[0.5*half_life(how_long_days),0.5*half_life(how_long_days)] +end + def _add_time(player, time) $players_time[player] = time if $players_time[player] < time end @@ -558,7 +643,11 @@ def add(black_mark, black_name, white_name, white_mark, time) elsif black_mark == LOSS_MARK && white_mark == WIN_MARK _add_win_loss(white_name, black_name, time) elsif black_mark == DRAW_MARK && white_mark == DRAW_MARK - return + if $options["skip-draw-games"] + return + else + _add_draw(black_name, white_name, time) + end else raise "Never reached!" end @@ -573,58 +662,148 @@ def identify_id(id) id.gsub(/@.*?\+/,"+") end -def grep(file) - str = File.open(file).read - - if /^N\+(.*)$/ =~ str then black_name = $1.strip end - if /^N\-(.*)$/ =~ str then white_name = $1.strip end - - if /^'summary:(.*)$/ =~ str - state, p1, p2 = $1.split(":").map {|a| a.strip} - return if state == "abnormal" - p1_name, p1_mark = p1.split(" ") - p2_name, p2_mark = p2.split(" ") - if p1_name == black_name - black_name, black_mark = p1_name, p1_mark - white_name, white_mark = p2_name, p2_mark - elsif p2_name == black_name - black_name, black_mark = p2_name, p2_mark - white_name, white_mark = p1_name, p1_mark - else - raise "Never reach!: #{black} #{white} #{p3} #{p2}" +# Parse a game result line +# +def parse(line) + if $history.include? line + $stderr.puts "[WARNING] Duplicated: #{line}" + return + end + $history.add line + + time, state, black_mark, black_id, white_id, white_mark, file = line.split("\t") + unless time && state && black_mark && black_id && + white_id && white_mark && file + $stderr.puts "Failed to parse the line : #{line}" + return + end + + if state == "abnormal" + csa = CsaFileReader.new file + if $options["abnormal-threshold"] == 0 || csa.ply <= $options["abnormal-threshold"] + return end end - if /^'\$END_TIME:(.*)$/ =~ str - time = Time.parse($1.strip) + time = Time.parse(time) + return if $options["base-date"] < time + how_long_days = ($options["base-date"] - time)/(3600*24) + if (how_long_days > $options["ignore"]) + return + end + + black_id = identify_id(black_id) + white_id = identify_id(white_id) + + if black_id && white_id && (black_id != white_id) && + black_mark && white_mark + add(black_mark, black_id, white_id, white_mark, time) end - if /^'rating:(.*)$/ =~ str - black_id, white_id = $1.split(":").map {|a| a.strip} - black_id = identify_id(black_id) - white_id = identify_id(white_id) - if black_id && white_id && (black_id != white_id) - add(black_mark, black_id, white_id, white_mark, time) +end + +def validate(yaml) + yaml["players"].each do |group_key, group| + group.each do |player_key, player| + rate = player['rate'] + next unless rate + if rate > 10000 || rate < -10000 + return false + end end end + return true end -def usage - $stderr.puts <<-EOF -USAGE: #{$0} dir [...] - EOF - exit 1 +def usage(io) + io.puts < 0 obj = WinLossMatrix::mk_win_loss_matrix($players) - rating_group = 0 obj.connected_subsets.each do |win_loss_matrix| yaml["players"][rating_group] = {} @@ -633,6 +812,23 @@ def main rating.average!(Rating::AVERAGE_RATE) rating.integer! + if $options["fixed-rate-player"] + # first, try exact match + index = win_loss_matrix.keys.index($options["fixed-rate-player"]) + # second, try regular match + unless index + win_loss_matrix.keys.each_with_index do |p, i| + if %r!#{$options["fixed-rate-player"]}! =~ p + index = i + end + end + end + if index + the_rate = rating.rate[index] + rating.translate!($options["fixed-rate"] - the_rate) + end + end + win_loss_matrix.keys.each_with_index do |p, i| # player_id, index# win = win_loss_matrix.matrix.row(i).sum loss = win_loss_matrix.matrix.col(i).sum @@ -648,6 +844,35 @@ def main rating_group += 1 end end + rating_group -= 1 + non_rated_group = 999 # large enough + yaml["players"][non_rated_group] = {} + $players.each_key do |id| + # skip players who have already been rated + found = false + (0..rating_group).each do |i| + found = true if yaml["players"][i][id] + break if found + end + next if found + + v = GSL::Vector[0, 0] + $players[id].each_value {|value| v += value} + next if v[0] < 1 && v[1] < 1 + + yaml["players"][non_rated_group][id] = + { 'name' => id.split("+")[0], + 'rating_group' => non_rated_group, + 'rate' => 0, + 'last_modified' => $players_time[id].dup, + 'win' => v[0], + 'loss' => v[1]} + end + unless validate(yaml) + $stderr.puts "Aborted. It did not result in valid ratings." + $stderr.puts yaml.to_yaml if $DEBUG + exit 10 + end puts yaml.to_yaml end