X-Git-Url: http://git.sourceforge.jp/view?p=shogi-server%2Fshogi-server.git;a=blobdiff_plain;f=mk_rate;h=e3350e588e1f0e8fb1f9f1bf78bd6843fbb2aa63;hp=29310ba26513edd6c6109ad00651dde65c0b57ef;hb=8ce6e11bef2f8e46de3816e465a7c127115c4bc1;hpb=946a136e49d5c35e0fb2fad668416c7398496a9a diff --git a/mk_rate b/mk_rate index 29310ba..e3350e5 100755 --- a/mk_rate +++ b/mk_rate @@ -1,57 +1,109 @@ #!/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: +# $Id$ +# +# Author:: Daigo Moriwaki +# Homepage:: http://sourceforge.jp/projects/shogi-server/ +# +#-- +# Copyright (C) 2006-2009 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 CSA files, calculates rating scores of each player, and then +# outputs a yaml file (players.yaml) that Shogi-server can recognize. +# +# == Usage +# +# ./mk_rate [options] DIR.. +# +# DIR:: +# CSA files are recursively looked up the directories. +# +# --half-life:: +# n [days] (default 60) +# +# --half-life-ignore:: +# m [days] (default 7) +# after m days, the half-life effect works +# +# --fixed-rate-player:: +# player whose rate is fixed at the rate +# +# --fixed-rate:: +# rate +# +# --help:: +# show this message +# +# == PREREQUIRE +# +# Sample Command lines that isntall prerequires will work on Debian. +# +# * Ruby 1.8.7 +# +# $ sudo aptitude install ruby1.8 +# +# * Rubygems +# +# $ sudo aptitude install rubygems +# +# * Ruby bindings for the GNU Scientific Library (GSL[http://rb-gsl.rubyforge.org/]) +# +# $ sudo aptitude install libgsl-ruby1.8 +# +# * RGL: {Ruby Graph Library}[http://rubyforge.org/projects/rgl/] +# +# $ sudo gem install rgl +# +# == Run +# # $ ./mk_rate . > players.yaml # -# 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 [ten] (rated) games. +# or, if you do not want the file to be update in case of errors, +# +# $ ./mk_rate . && ./mk_rate . > players.yaml # +# == How players are rated # -# PREREQUIRE -# ========== +# The conditions that games and players are rated as following: # -# Ruby bindings for the GNU Scientific Library (GSL) is required. -# You can download it from http://rb-gsl.rubyforge.org/ -# Or, if you use Debian, -# $ sudo aptitude install libgsl-ruby1.8 +# * 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. # require 'yaml' require 'time' +require 'getoptlong' require 'gsl' +require 'rubygems' +require 'rgl/adjacency' +require 'rgl/connected_components' ################################################# # Constants # # Count out players who play less games than $GAMES_LIMIT -$GAMES_LIMIT = $DEBUG ? 0 : 10 +$GAMES_LIMIT = $DEBUG ? 0 : 15 WIN_MARK = "win" LOSS_MARK = "lose" +DRAW_MARK = "draw" # Holds players $players = Hash.new @@ -122,7 +174,7 @@ class Rating @record = Record.new @n = win_loss_matrix case @n - when GSL::Matrix + when GSL::Matrix, GSL::Matrix::Int @size = @n.size1 when ::Matrix @size = @n.row_size @@ -198,9 +250,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 = @@ -269,7 +321,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 @@ -322,6 +375,13 @@ class Rating end ## + # Translate by value + # + def translate!(value) + @rate += value + end + + ## # Make the values of @rate integer. # def integer! @@ -337,40 +397,205 @@ class Rating end end - - ################################################# -# Main methods +# Encapsulate a pair of keys and win loss matrix. +# - keys is an array of player IDs; [gps+123, foo+234, ...] +# - matrix holds games # where player i (row index) beats player j (column index). +# The row and column indexes match with the keys. +# +# This object should be immutable. If an internal state is being modified, a +# new object is always returned. # +class WinLossMatrix -def mk_win_loss_matrix(players) - keys = players.keys.sort.reject do |k| - players[k].values.inject(0) {|sum, v| sum + v[0] + v[1]} < $GAMES_LIMIT + ############### + # Class methods + # + + def self.mk_matrix(players) + keys = players.keys.sort + size = keys.size + matrix = + GSL::Matrix[* + ((0...size).collect do |k| + p1 = keys[k] + p1_hash = players[p1] + ((0...size).collect do |j| + if k == j + 0 + else + p2 = keys[j] + v = p1_hash[p2] || Vector[0,0] + v[0] + end + end) + end)] + return WinLossMatrix.new(keys, matrix) end - size = keys.size + def self.mk_win_loss_matrix(players) + obj = mk_matrix(players) + return obj.filter + end - matrix = - GSL::Matrix[* - ((0...size).collect do |k| - ((0...size).collect do |j| - if k == j - 0 - else - v = players[keys[k]][keys[j]] - v[0] + ################## + # Instance methods + # + + # an array of player IDs; [gps+123, foo+234, ...] + attr_reader :keys + + # matrix holds games # where player i (row index) beats player j (column index). + # The row and column indexes match with the keys. + attr_reader :matrix + + def initialize(keys, matrix) + @keys = keys + @matrix = matrix + end + + ## + # Returns the size of the keys/matrix + # + def size + if @keys + @keys.size + else + nil + end + end + + ## + # Removes players in a rows such as [1,3,5], and then returns a new + # object. + # + def delete_rows(rows) + rows = rows.sort.reverse + + copied_cols = [] + (0...size).each do |i| + next if rows.include?(i) + row = @matrix.row(i).clone + rows.each do |j| + row.delete_at(j) end - end) - end)] - - return matrix, keys + copied_cols << row + end + if copied_cols.size == 0 + new_matrix = GSL::Matrix.new + else + new_matrix = GSL::Matrix[*copied_cols] + end + + new_keys = @keys.clone + rows.each do |j| + new_keys.delete_at(j) + end + + return WinLossMatrix.new(new_keys, new_matrix) + end + + ## + # Removes players who do not pass a criteria to be rated, and returns a + # new object. + # + def filter + $stderr.puts @keys.inspect if $DEBUG + $stderr.puts @matrix.inspect if $DEBUG + delete = [] + (0...size).each do |i| + row = @matrix.row(i) + col = @matrix.col(i) + win = row.sum + loss = col.sum + if win < 1 || loss < 1 || win + loss < $GAMES_LIMIT + delete << i + end + end + + # The recursion ends if there is nothing to delete + return self if delete.empty? + + new_obj = delete_rows(delete) + new_obj.filter + end + + ## + # Cuts self into connecting groups such as each player in a group has at least + # one game with other players in the group. Returns them as an array. + # + def connected_subsets + g = RGL::AdjacencyGraph.new + (0...size).each do |k| + (0...size).each do |i| + next if k == i + if @matrix[k,i] > 0 + g.add_edge(k,i) + end + end + end + + subsets = [] + g.each_connected_component do |c| + new_keys = [] + c.each do |v| + new_keys << keys[v.to_s.to_i] + end + subsets << new_keys + end + + subsets = subsets.sort {|a,b| b.size <=> a.size} + + result = subsets.collect do |keys| + matrix = + GSL::Matrix[* + ((0...keys.size).collect do |k| + p1 = @keys.index(keys[k]) + ((0...keys.size).collect do |j| + if k == j + 0 + else + p2 = @keys.index(keys[j]) + @matrix[p1,p2] + end + end) + end)] + WinLossMatrix.new(keys, matrix) + end + + return result + end + + def to_s + "size : #{@keys.size}" + "\n" + + @keys.inspect + "\n" + + @matrix.inspect + end + +end + + +################################################# +# Main methods +# + +# Half-life effect +# After NHAFE_LIFE days value will get half. +# 0.693 is constant, where exp(0.693) ~ 0.5 +def half_life(days) + if days < $options["half-life-ignore"] + return 1.0 + else + Math::exp(-0.693/$options["half-life"]*(days-$options["half-life-ignore"])) + end end -def _add_win_loss(winner, loser) +def _add_win_loss(winner, loser, time) + how_long_days = (Time.now - 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] - $players[loser][winner] += GSL::Vector[0,1] + $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_time(player, time) @@ -379,9 +604,11 @@ end def add(black_mark, black_name, white_name, white_mark, time) if black_mark == WIN_MARK && white_mark == LOSS_MARK - _add_win_loss(black_name, white_name) + _add_win_loss(black_name, white_name, time) elsif black_mark == LOSS_MARK && white_mark == WIN_MARK - _add_win_loss(white_name, black_name) + _add_win_loss(white_name, black_name, time) + elsif black_mark == DRAW_MARK && white_mark == DRAW_MARK + return else raise "Never reached!" end @@ -389,66 +616,182 @@ def add(black_mark, black_name, white_name, white_mark, time) _add_time(white_name, time) 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 - dummy, p1, p2 = $1.split(":").map {|a| a.strip} - 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} #{p1} #{p2}" - end +def identify_id(id) + if /@NORATE\+/ =~ id # the player having @NORATE in the name should not be rated + return nil end - if /^'\$END_TIME:(.*)$/ =~ str - time = Time.parse($1.strip) + id.gsub(/@.*?\+/,"+") +end + +# Parse a game result line +# +def parse(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 /^'rating:(.*)$/ =~ str - black_id, white_id = $1.split(":").map {|a| a.strip} + + return if state == "abnormal" + time = Time.parse(time) + 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 end -def usage - $stderr.puts <<-EOF -USAGE: #{$0} dir [...] - EOF - exit 1 +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(io) + io.puts < p.split("+")[0], - 'rate' => rating.rate[i], - 'last_modified' => $players_time[p].dup, - 'win' => win_loss[0], - 'loss' => win_loss[1]} + $options = Hash::new + parser = GetoptLong.new( + ["--half-life", GetoptLong::REQUIRED_ARGUMENT], + ["--half-life-ignore", GetoptLong::REQUIRED_ARGUMENT], + ["--help", "-h", GetoptLong::NO_ARGUMENT], + ["--fixed-rate-player", GetoptLong::REQUIRED_ARGUMENT], + ["--fixed-rate", GetoptLong::REQUIRED_ARGUMENT]) + parser.quiet = true + begin + parser.each_option do |name, arg| + name.sub!(/^--/, '') + $options[name] = arg.dup + end + if ( $options["fixed-rate-player"] && !$options["fixed-rate"]) || + (!$options["fixed-rate-player"] && $options["fixed-rate"]) || + ( $options["fixed-rate-player"] && $options["fixed-rate"].to_i <= 0) + usage($stderr) + exit 1 + end + rescue + usage($stderr) + raise parser.error_message + end + if $options["help"] + usage($stdout) + exit 0 + end + $options["half-life"] ||= 60 + $options["half-life"] = $options["half-life"].to_i + $options["half-life-ignore"] ||= 7 + $options["half-life-ignore"] = $options["half-life-ignore"].to_i + $options["fixed-rate"] = $options["fixed-rate"].to_i if $options["fixed-rate"] + + if ARGV.empty? + while line = $stdin.gets do + parse line.strip + end + else + while file = ARGV.shift do + File.open(file) do |f| + f.each_line do |line| + parse line.strip + end + end + end + end + + yaml = {} + yaml["players"] = {} + rating_group = 0 + if $players.size > 0 + obj = WinLossMatrix::mk_win_loss_matrix($players) + obj.connected_subsets.each do |win_loss_matrix| + yaml["players"][rating_group] = {} + + rating = Rating.new(win_loss_matrix.matrix) + rating.rating + 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 + + yaml["players"][rating_group][p] = + { 'name' => p.split("+")[0], + 'rating_group' => rating_group, + 'rate' => rating.rate[i], + 'last_modified' => $players_time[p].dup, + 'win' => win, + 'loss' => loss} + end + 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