### ### ### 日本将棋連盟の Web Site より勝敗表を取得しレーティング計算を行う ### ### 2003-04-13 written by suchowan =begin 【レーティング】 レーティングシステムについて考察しました。 １局の重みを一定にするという*ゆるい*要請だけでレーティング関数の関数形が 決まってしまうという点が興味深く思われます。 i,j,k : 競技者(in [1,..,N]) (1) n(i,j) : i が j に勝った回数（これらの集合が勝敗表） (2) R(i) : i のレート (3) p(R(i)-R(j)) : i が j に勝つ確率 (4) レーティングシステムでは、p が(4)式のように書けると仮定します。 ここに p-1/2 は奇関数となります。 P : 勝敗表が実現する確率 (5) P を最大にするように R を求めるには（最尤法）、連立方程式 d ------- log P = 0 (6) dR(k) を解けば良いわけです。P を具体的に書くと、 n(i,j)!n(j,i)! n(i,j) n(j,i) P = Π ---------------- p(R(i)-R(j)) p(R(j)-R(i)) (7) i>j (n(i,j)+n(j,i))! よって、(6)式は、 d + Σ n(i,k)------- log p(R(i)-R(k)) i<>k dR(k) d + Σ n(k,j)------- log p(R(k)-R(j)) = 0 (8) j<>k dR(k) これを逐次近似で解こうとするのがレーティングシステムです。つまり、 ΔR(k,j) : k が j に勝ったとき、 j から k に移動するレート (9) とすると、 d ΔR(k,j) = ------- log p(R(k)-R(j)) (10) dR(k) p-1/2 は奇関数ですので、 ΔR(k,j) : ΔR(j,k) = p(R(j)-R(k)) : p(R(k)-R(j)) (11) は、関数形の詳細が不明でも結論できます。すなわち、 d ---- log p(R) = K(p)[1-p(R)] (12) dR 一般に K は p の偶関数ですが、最も簡単な場合を考えて K が定数として(12) 式の微分方程式（ごく初等的）を解くと、 1 p(R) = ------------ (13) 1+exp(-KR) よって、 1 exp(KR(i)) p(R(i)-(R(j)) = --------------------- = ------------------------ (14) 1+exp(-K(R(i)-(R(j))) exp(KR(i)) + exp(KR(j)) 定数 K の値は、レートの単位の取り方に帰着するので本質的ではありません。 式(14) が成立するとき、式(8)の最尤条件は厳密に、 Σ [ n(k,i) p(R(i)-R(k)) - n(i,k) p(R(k)-R(i)) ] = 0 (15) j<>k です。つまり K が定数ならば、対戦者によらず１局の重みが一定になります。 このため完全総当たりリーグ戦では、勝敗の偏りに関係なく、きちんと最尤法 で求めたレートの順位と、単純な勝率の順位は必ず一致するはずです（引き分け を半星として）。 > R(i) : i のレート (3) > p(R(i)-R(j)) : i が j に勝つ確率 (4) の R を確率変数、 p を累積度数関数(*)ととらえると、もっといろいろ意味のあ りそうなバリエーションを考えることが可能です（しかし(4)自体が理想化なので 「正確」さはもともと定義できない）。 2 (*) (14)を微分して得られる確率密度関数は sech の形をしています。これを フーリエ変換したものの平方根を逆フーリエ変換したものが、初等関数で書ける と見通しがよいのですが… [Bradley-Terry モデルに関する参考文献] 竹内啓・藤野和建『スポーツの数理科学』(共立出版 1988) =end require 'socket' require 'matrix' class RatingTable ####################################### ## クラス定数 ## # レーティング単位(3勝1敗ペースの勝率に対するレーティング差) RateUnit = 200.0 # レーティング平均値(駒音掲示板の「みなかみ」さんの値に整合させたもの) RateMean = 2600.0 # 勝数閾値(この勝数未満の棋士は評価対象外) WinsLimit = 5 # 敗数閾値(この敗数未満の棋士は評価対象外) LossesLimit = 5 # 収束の許容誤差 ErrorLimit = 1e-5 @@Class ={ "羽生善治"=>'A', "木村一基"=>'B2', "松尾　歩"=>'C1', "佐藤康光"=>'A', "郷田真隆"=>'B1', "森内俊之"=>'A', "深浦康市"=>'B1', "丸山忠久"=>'A', "屋敷伸之"=>'C1', "久保利明"=>'A', "行方尚史"=>'B2', "谷川浩司"=>'A', "中川大輔"=>'B1', "田村康介"=>'C2', "畠山　鎮"=>'B2', "山ｱ隆之"=>'C2', "藤井　猛"=>'A', "高橋道雄"=>'B1', "杉本昌隆"=>'B2', "阿部　隆"=>'B1', "森下　卓"=>'B1', "鈴木大介"=>'A', "井上慶太"=>'B1', "伊奈祐介"=>'C2', "中田宏樹"=>'C1', "神崎健二"=>'C1', "野月浩貴"=>'C1', "塚田泰明"=>'B2', "豊川孝弘"=>'C1', "青野照市"=>'A', "畠山成幸"=>'B2', "岡崎　洋"=>'C1', "北浜健介"=>'B1', "佐藤秀司"=>'B2', "堀口一史座"=>'B2', "飯塚祐紀"=>'C1', "北島忠雄"=>'C1', "島　朗"=>'A', "野秀行"=>'C2', "土佐浩司"=>'B2', "中村　修"=>'B1', "先崎　学"=>'B1', "小倉久史"=>'C1', "矢倉規広"=>'C2', "阿久津主税"=>'C2', "真田圭一"=>'C1', "淡路仁茂"=>'C1', "長沼　洋"=>'C1', "中田　功"=>'C1', "佐々木慎"=>'C2', "増田裕司"=>'C2', "橋本崇載"=>'C2', "伊藤　果"=>'F', "千葉幸生"=>'C2', "日浦市郎"=>'C1', "飯島栄治"=>'C2', "富岡英作"=>'B2', "加藤一二三"=>'B1', "泉　正樹"=>'B2', "南　芳一"=>'B2', "佐藤紳哉"=>'C2', "中尾敏之"=>'C2', "小野修一"=>'B2', "藤原直哉"=>'C2', "三浦弘行"=>'A', "中座　真"=>'C1', "渡辺　明"=>'C1', "田中寅彦"=>'B1', "加瀬純一"=>'F', "勝又清和"=>'C1', "有吉道夫"=>'C1', "石川陽生"=>'C1', "小阪　昇"=>'C2', "中原　誠"=>'F', "小林健二"=>'C1', "桐山清澄"=>'B2', "木下浩一"=>'C2', "内藤國雄"=>'B2', "近藤正和"=>'C2', "所司和晴"=>'C1', "浦野真彦"=>'B2', "高田尚平"=>'C2', "小林裕士"=>'C1', "松本佳介"=>'C2', "山本真也"=>'C2', "森けい二"=>'B2', "伊藤　能"=>'C2', "神谷広志"=>'B1', "武市三郎"=>'C2', "伊藤博文"=>'C2', "西村一義"=>'C1', "真部一男"=>'C1', "金沢孝史"=>'C2', "室岡克彦"=>'C1', "福崎文吾"=>'B2', "川上　猛"=>'C2', "米長邦雄"=>'F', "武者野勝巳"=>'F', "石田和雄"=>'B2', "堀口弘治"=>'C1', "有森浩三"=>'C1', "安用寺孝功"=>'C2', "大内延介"=>'C1', "脇　謙二"=>'B2', "西川慶二"=>'B2', "大島映二"=>'C2', "勝浦　修"=>'F', "大野八一雄"=>'C2', "桐谷広人"=>'F', "本間　博"=>'F', "平藤真吾"=>'C2', "鈴木輝彦"=>'F', "達　正光"=>'C2', "児玉孝一"=>'C1', "野田敬三"=>'C2', "飯野健二"=>'F', "植山悦行"=>'C2', "安西勝一"=>'C2', "神吉宏充"=>'F', "東　和男"=>'C1', "菊地常夫"=>'F', "田中魁秀"=>'C1', "小林　宏"=>'C1', "上野裕和"=>'C2', "田丸　昇"=>'B2', "窪田義行"=>'C1', "滝誠一郎"=>'F', "森安正幸"=>'F', "桜井　昇"=>'C2', "森　信雄"=>'F', "前田祐司"=>'C2', "沼　春雄"=>'F', "村田智弘"=>'C2', "宮田敦史"=>'C2', "大平武洋"=>'C2', "熊坂　学"=>'C2', "島本　亮"=>'C2', "藤倉勇樹"=>'C2', "櫛田陽一"=>'F', "横山泰明"=>'C2', "西尾　明"=>'C2', "宮田利男"=>'F' } ####################################### ## 勝敗表作成メソッド(Matrix形式) ## # テスト用勝敗表(例) def testWinLossMatrix @Target = ['A','B','C'] @Size = @Target.size @WinLossMatrix = Matrix[[0,3,9],[1,0,3],[1,1,0]] end # 2000年度年間勝敗表(例) def year2000WinLossMatrix @Target = ['名人A級','B級1組','B級2組','C級1組','C級2組','フリーC'] @Size = @Target.size @WinLossMatrix = Matrix[ # 週刊将棋2001年9月12日号のデータ [ 0, 59, 52, 39, 29, 12], # 名人およびA級 [ 40, 0, 37, 29, 27, 10], # B級1組 [ 33, 35, 0, 50, 92, 41], # B級2組 [ 21, 19, 51, 0, 140, 80], # C級1組 [ 5, 21, 82, 103, 0, 124], # C級2組 [ 2, 6, 9, 34, 44, 0], # フリークラス ] end # 個人勝敗表 def personalWinLossMatrix(argv) # # 初期設定 # @WinLossHash = {} # 勝敗表(ハッシュ形式) # # HTTP セッション # argv.each do |date| s = TCPsocket::open('www.shogi.or.jp', 80) $stderr.print "GET /kisen/#{date}all.html HTTP 1.0\n" s.print "GET /kisen/#{date}all.html HTTP 1.0\r\n\r\n" s.read.split(/
/)[1].gsub(/(.*?)<\/tr>/) do |p| # 対局日の読み込み if ( p =~ / *(.+?)月 *(.+?)日/) then month, day = $1, $2 end # 余分な行の読み捨て row = p.split(/<\/td>/) next if row.size <= 5 # 一局の結果の読み込み case row[4] # 勝 敗 when '○', '□' then winLoss = [row[3], row[1]] when '●', '■' then winLoss = [row[1], row[3]] end # テレビ棋戦・女流棋戦・千日手を除外 next if (row[4] =~ /^千?$/ || row[4] =~ '　' || row[5] =~ /女流|レディース|倉敷藤花|鹿島杯/) # 人名表記の「空白」の揺れ、森けい二九段を正規化 winLoss.each do |name| name.sub!(/　雞/, 'けい') name.gsub! (/眞/, '真') name.gsub! (/[ 　]+/, '　') name.gsub! (/^.*アマ$/, 'アマ') end win, loss = *winLoss # 勝敗表の更新 @WinLossHash[win] ||= {'Wins'=>0, 'Losses'=>0} @WinLossHash[win] ['Wins'] += 1 @WinLossHash[loss] ||= {'Wins'=>0, 'Losses'=>0} @WinLossHash[loss] ['Losses'] += 1 if (!@WinLossHash[win] [loss]) then @WinLossHash[win] [loss] = 1 else @WinLossHash[win] [loss] += 1 end end s.close end # # 勝敗表の作成 # @Target = @WinLossHash.keys.reject do |x| @WinLossHash[x]['Wins'] < WinsLimit || @WinLossHash[x]['Losses'] < LossesLimit end @Size = @Target.size @WinLossMatrix = Matrix[* ((0...@Size).collect do |k| ((0...@Size).collect do |i| @WinLossHash[@Target[k]][@Target[i]] || 0 end) end) ] end ####################################### ## レーティング値を計算する ## def rating # レートテーブルの初期値(オール 0) @Rate = Vector[*Array.new(@Size,0)] begin # レーティング・テーブルが予測する勝率行列 @WinRateMatrix = Matrix[* (@Rate.collect do |x| (@Rate.collect do |y| # exp(x) # --------------- # exp(x) + exp(y) 1/(1+Math.exp(y-x)) end) end) ] # 収束補正量の理論値 errorVector = Vector[* ((0...@Size).collect do |k| numerator = 0 # 分子 #--------------------- denominator = 0 # 分母 (0...@Size).each do |i| numerator += @WinLossMatrix[k,i] * @WinRateMatrix[i,k] - @WinRateMatrix[k,i] * @WinLossMatrix[i,k] #------------------------------------------------------ denominator += @WinRateMatrix[i,k] * @WinRateMatrix[k,i] * (@WinLossMatrix[k,i] + @WinLossMatrix[i,k]) end # 0/0 形の場合は、補正なしとする (numerator == 0) ? 0 : numerator / denominator # <=これが問題 end) ] # 収束補正量の平均値を 0 とする(平行移動しても結果は変わらない) errorMean = 0 Array(errorVector).each do |error| errorMean += error end errorVector -= Vector[*Array.new(@Size,errorMean/@Size)] # 収束補正の実行 @Rate += errorVector $stderr.printf "|error| : %5.2e\n", errorVector.r end while (errorVector.r > ErrorLimit) $stderr.printf "\n" self end ####################################### ## 解析結果 ## def result # # 日本将棋連盟の Web のデータを使用した場合 # if (@WinLossHash) then # レーティングの降順インデックスをつくる index = (0...@Size).sort do |x,y| @Rate[y] <=> @Rate[x] end # 結果 printf "以下の#{@Size}棋士を評価しました:\n\n" (0...@Size).each do |k| name = @Target[index[k]] printf("%3d %-14s (%-2s) [%5d] %3d勝%3d敗\n", k+1, name, @@Class[name] , @Rate[index[k]] / Math.log(3) * RateUnit + RateMean, @WinLossHash[name]['Wins'], @WinLossHash[name]['Losses']) end else # # 週刊将棋の集計データを使用した場合 # # 表題 printf "\n\n 【計算結果】 注:「対 n 勝数」は勝数の\"予測数(実績数)\"" printf "\n\n No 名前 [ Rate]:" (0...@Size).each do |i| printf(" 対%2d 勝数", i+1) end print "\n" # 内容 (0...@Size).each do |k| # プレーヤー(レート) printf("%2d %-8s[%5d]:", k+1, @Target[k], @Rate[k] / Math.log(3) * RateUnit + RateMean) (0...@Size).each do |i| # 予測(実績) printf("%5.1f(%3d)", @WinRateMatrix[k,i] * (@WinLossMatrix[k,i]+@WinLossMatrix[i,k]), @WinLossMatrix[k,i]) end print "\n" end print "\n" end end ####################################### ## 初期設定 ## def initialize(argv=nil) if (argv) then personalWinLossMatrix(argv) else year2000WinLossMatrix end end end ########################################## ## ## メイン・ルーチン ## ## # 2003年度成績から得るクラス別レーティング RatingTable.new.rating.result # 個人レーティング(暦年2004年1月までの1年のデータに基づくレーティング) RatingTable.new( ['2004/01', '2003/2', '2003/3', '2003/4', '2003/5', '2003/6', '2003/7', '2003/8', '2003/9', '2003/10','2003/11','2003/12']).rating.result