コンピュータ将棋基礎情報研究所

コンピュータ将棋に関する基礎的な情報を収集し、分析し、発表する所です。英語名称はLaboratory for Fundamental Information on Computer Shogi (LFICS)。

2015年11月

イロレーティングにおけるレート差と勝率との関係式は\[E = \frac{1}{1 + 10^{- \Delta{R} / 400}}\]であり、レート差について解くと\[\Delta{R} = 400 \log_{10}(\frac{E}{1 - E})\]となります。

以下にグラフを示します。黒線はレート差と勝率との関係を表しており、青の横線はそれぞれのレート差の時の勝率、オレンジの矢印はそれぞれの勝率の時のレート差を示しています。レート差が負の場合には選手を入れ替えて考えてみてください。

fig1

イロレーティングについては以下の解説記事をご参照ください。

前回の記事「イロレーティング 1:棋力ってなんだ?」では、Bに対するAの「一般化オッズ」\[F(E_{AB}) = \frac{f(E_{AB})}{f(E_{BA})}\]の関数形に対してイロ教授がある仮定を導入したというところまで記しました。

その仮定とは\[f(E) = E\]という最もシンプルな線形化です。こうすると、「一般化オッズ」は\[F(E_{AB}) = \frac{E_{AB}}{E_{BA}} = \frac{E_{AB}}{1 - E_{AB}}\]となり、これは一般的によく使われているオッズになります。また、「一般化レート」は\[G(E_{AB}) = \log(\frac{E_{AB}}{1 - E_{AB}})\]なので、これを勝率について解くと、\[E_{AB} = \frac{1}{1 + 10^{(R_B - R_A) / 400}}\]となります。ここで、\[G(E_{AB}) = G_{A} - G_{B} = \frac{R_{A} - R_{B}}{400}\]としました。\[G_{A},~ G_{B}\]は、それぞれ平均的な選手に対するA, Bの「一般化レート」であり、\[R_{A},~ R_{B}\]がイロレーティングにおけるレートになります。ここで(対数の底を10とした上で)400で割っているのは、レートが200違う時に勝率が約75%になるようにするためです。実際には約75.97%ですが、10進数でキリのいい数字にしたのでしょう。また、レートの原点は平均が1500になるように選びます。

レート差と勝率との関係については以下の資料ページにまとめておきます。

この仮定がどれくらい有効なのかという研究はチェス等で行われていると聞きますが、私は詳細を把握しておりません。もし機会があれば詳しく調べてみたいと思います。しかしながら、広く普及しているということは大雑把な枠組みとしては有効だと判断されているのだと思います。

最後に、実際にどのようにレートを推定したらよいのかを考えます。

現実には選手の数も対局数も理論的な理想には程遠く、本来必要となる量のごく一部(しかも酷く偏っているサンプルである可能性もある)しか存在しません。その標本から真面目に統計的に推定することはそれなりに大変であり、シンプルさというこの手法の趣旨に反してしまいます。荒っぽくていいので、もっと簡単で随時更新可能な実用的な手法が望まれます。

最も簡単な方法は対局ごとにレートの推定値を前進的に改良していくという方法です。対局前のレートを\[R_{\text{old}}\]とした時、対局の結果を受けて\[R_{\text{new}} = R_{\text{old}} + K (S - E)\]のようにレートを更新します。ここで、Sは勝ちの時は1、負けの時は0、引き分けの時は0.5です。Eは対局前のレートから上で記した計算式によって算出された勝率の推定値です。つまり、推定していた勝率よりも高い結果が出た時にはレートを上方修正し、逆の時には下方修正することで調整していこうということです。Kは正の定数で、調整する時の匙加減を決めます。Kが小さいとなかなか動かず、大きすぎるとガタガタに動いてしまいます。通常は16(もしくは32)が使われることが多いようです。この改良は必ずしも一局ごとに限らず、複数の対局をまとめて処理することも可能です。対局では必ず相手がいて、そちらのレートの方も同様に調整されますので、両方の改良分を合計すると相殺されて0になって、平均値は変わりません。

レートの初期値については最初の地点を平均の1500とします。この時、最初の頃のレート推定値は本来あるべき値から大きくずれている可能性があるわけですが、長く対局を続けていけば適正な値に落ち着くということを想定しています。

しかしながら、実際には対局数がさほど多くない状況で運用されることも多く、本当に初期値依存性が無視できるのかは検討してみる必要があります。また、状況によってはそもそも収束するのかという懸念も出てきます。この辺の問題については、機会があれば改めて論じてみたいと思います。

さらに、現実面での運用を考えると、ゲームの性質上、引き分けを0.5勝0.5敗、つまり互角と考えるのは本当に妥当であるのかもよく考えてみないといけないでしょう(稲庭問題等)。場合によっては引き分けをなかったことにしてレートの改良に用いないという運用の選択肢もありえます。元々、イロレーティングはチェス用に考案されたものですので、将棋向けに修正を検討するべき課題は他にもあるかもしれません。また、実際の棋士の場合には時間が経つとともに棋力が大きく変わったり、引退したりという時間依存の要素も出てきます。ソフトにしてもハードやバージョン、設定の変化等で同様の問題が発生します(例えば、floodgateの場合はその辺は個々の登録者の判断次第)。これらの現実的な対処も運用上、必要になってきます。

イロレーティングはシンプルに作られているため、実用的で頑強な仕組みになっています。その反動として、実際の運用においては人為的な自由度の介在する余地の大きいものになっています。運用の際には「棋力を測定する」という当初の目的を見失わないように柔軟に取り扱っていく必要があるでしょう。

将棋の強さや力量(棋力と言う)というのは客観的、定量的にどのように決定したらいいのでしょうか? これを棋力のレーティング(評価、格付け)の問題と言います。レーティングの手法には様々なものが提案されていますが、ここでは物理学者であるアルパド・イロ教授が考案したイロレーティングについて解説します。この手法は、最もシンプルな方法であり、また、コンピュータ将棋対局場floodgateでも活用され、国際チェス連盟(FIDE)の公式レーティングにも採用され、将棋倶楽部24等でも簡易版が用いられている等、最も普及している方法でもあります。コンピュータ将棋でレーティングやレートという場合には通常、イロレーティングのことを意味しており、欠かすことのできない重要な概念になっています。

最初は一般論としてどのように将棋の強さを測ったらいいのかを考えてみましょう。

AとBが非常に多くの対局を行ってAが勝率0.7(70%)だったとします。この時、AはBよりも強いということが推測されます。しかし、本当にAはBよりも強いのでしょうか? 単に相性がよかっただけで、例えば、Cとの三者の間でじゃんけんの関係になっているのかもしれません。ここで「相性」は棋力とは全く無関係に存在しているものとします。

この「相性」の問題はBを個人から多数の同等の棋力を持つ個人からなる集団に置き換えると解決できます。「そんな集団どうやって用意するの?」という話ですが、これはあくまでも理論上の話なので、例えばパラレルワールドから召還してくるとしましょう。また、多数の集団を作る際には集団間の相性もないように配慮することとします。Aが均質な棋力持つ集団Bに対して無数に対局して勝ち越せば、仮にBの中に相性の悪い人がいて一部に負け越していたとしても、AはBの中の誰よりも強いということができます。同様にCもDも全て集団化していくと、個々の相性の問題を抜きにして、勝率から強さを測ることが可能になります。以下では、そのような架空の集団の概念を暗黙に導入することで、相性の問題を抜きにして話を進めていきます。

さて、AがBに対して勝率\[E_{AB}\]であり、BがCに対して勝率\[E_{BC}\]である時、Cに対するAの勝率\[E_{AC}\]はどうなるでしょうか? 相性の問題はもうないので、この問題は何らかの関係性によって一意に答えが決まるはずです。後で説明しますが、この関係性さえ分かれば、そこから敷衍して棋力の尺度を決めることができます。

この問題は以下のように書き換えることができます:「\[F(E_{AC}) = F(E_{AB}) \cdot F(E_{BC})\]となる正の単調増加関数F(E)を求めよ」。ここで式中の中点は、交換則と結合則を満たせばいいのですが、ただの掛け算とします。勝率の定義から\[E_{AA} = \frac{1}{2}~~,~~~ E_{BA} = 1 - E_{AB}\]です。BとCをそれぞれAに置き換えると\[F(1 / 2) =F(1 / 2) \cdot F(1 / 2) = 1\]となり、CのみをAに置き換えると\[F(E_{AB}) \cdot F(E_{BA}) = 1\]となります。これは\[F(E_{AB}) = \frac{f(E_{AB})}{f(E_{BA})}\]とおけば自動的に満たされます。F(E)は単調増加関数なので値が分かれば、対応するEを一意に求めることができます。ここでは\[F(E_{AB})\]のことをBに対するAの「一般化オッズ」と呼ぶことにします。

交換則と結合則を満たせばいいのならば、掛け算でなくても足し算でもいいのではないかということになりますが、これは両辺の対数を取ると実現できます。\[G(E) = \log[F(E)]\]とすると、\[G(E_{AC}) = G(E_{AB}) + G(E_{BC})\]の形に書き直せるわけです。ここでは、\[G(E_{AB})\]のことをBに対するAの「一般化レート」と呼ぶことにします。

ここまでくると察しのいい読者の方はもう気付かれたと思いますが、これらの「一般化オッズ」や「一般化レート」は棋力の尺度に利用することができます。「Bに対する」の部分のBを平均的な選手に置き換えて省略すると、Aの「一般化オッズ」や「一般化レート」になります。後は値の原点と数字の単位(スケール)を定めればいいだけです。特に「一般化レート」は、差の値が意味を持つため、間隔尺度になります。つまり、上記の数学的な記述は強さの順序尺度を勝率間の関係式によって間隔尺度に直す作業だったわけです。イロレーティングでは、レートの原点を1500とし、スケールはレートが200違う時に勝率が約75%になるように調整します。これらは慣習的な決まりで、特に数学的に意味がある数字ではありません。

残る問題はF(E)やG(E)の関数形を決定することですが、これは数学的に普遍的に決まるものではなく、ゲームや選手の性質によって決まるものです。ですので、統計データから慎重に推定するというのが最も真面目なやり方でしょう。これは十分な量の棋譜があって、統計の専門家(※筆者は違います)が分析すれば、そんなに難しいことではないと思います。一度、floodgateの棋譜でデモンストレーションしてみても面白いかもしれません。筆者はこの辺の研究に詳しくないので、どの程度の先行研究があるのかは知りません。機会があれば、その辺も調べてご紹介できればと思います。

さて、ここで物理学者のイロ教授は、統計学的な推定に頼ることなく、一つの大胆でシンプルな仮説を導入しました。多少の粗らがあってもシンプルな方が実用的で普遍的であるというのは、よくあることです。そして、そういうモデル化は物理学者が最も得意とするところなのです。

(以下の記事に続く)

本題に入る前に今後よく使われることになる平均と標準偏差について統計学の授業風に解説します。「そんなの知ってるよ」って方は飛ばしてください。

まず、SF的な架空の話として、将棋のルールが変わらない程度に微妙に異なる多数の平行世界(パラレルワールド)を飛び回って膨大な数の棋譜を集めてきたとします。この棋譜には、この世界では実現されていない無数の対局が記述されており、ここから得られるデータが我々が真に知りたい情報ということになります。ここでは、その膨大な棋譜から取り出した膨大なN個の数値データの集団(母集団という)\[\{X_1, X_2, \dots, X_N\}\]を考えます。

母集団の平均(母平均)は\[\mu = \frac{1}{N} \sum_{i = 1}^{N} X_{i}\]で定義され、母集団の標準偏差(母標準偏差)は\[\sigma = \sqrt{\frac{1}{N} \sum_{i = 1}^{N} ( X_{i} - \mu )^{2}}\]で定義されます。また、母標準偏差の2乗である\[\sigma^{2}\]は母分散と呼ばれます。

平均は文字通り平均値のことであり、標準偏差は平均から分布がどのくらい広がっているのかを表している量です。例えば、平均4、標準偏差1ならば、こんな感じになります。
fig1
ただし、実際に分布がどんな形になっているのかは母集団によります。

さて、ここで問題になるのは、我々は実際にはパラレルワールドを行き来できないため、膨大な棋譜の中のごく一部(標本、サンプルと言う)しか持っていないということです。いかにして標本から母集団の統計情報を推定するのかということを考えなければなりません。

標本の数値データの集団(母集団の一部)を\[\{x_1, x_2, \dots, x_n\}\]とする時、母平均を推定するには、標本の平均\[m = \frac{1}{n} \sum_{i = 1}^{n} x_{i}\]を計算します。実際に、無数のパラレルワールドをランダムに巡って、各世界での標本の平均を集めて、それらの平均E[m](期待値と言う)をとると母平均と一致します。すなわち、\[E[m] = \mu\]となります。この計算は標本の集団が母集団の一部であることを考えると自明です。

では、母分散の場合はどうでしょうか?

平均と同様に標本の分散\[S^{2} = \frac{1}{n} \sum_{i = 1}^{n} ( x_{i} - m )^{2}\]を考えると変なことが起こります。例えば、n = 1の時、\[m = x_1\]ですので、\[S^{2} = 0\]となってしまい、どんなに多世界のn = 1の標本の分散を集めて平均を取って期待値を計算しても0は0で母分散にはなりません。これはn = 1だけに特有な現象ではなく、一般に標本の分散の期待値は\[E[S^{2}] = \frac{n - 1}{n} \sigma^{2}\]になってしまいます。ここの導出はそれなりに長いので省略します。このような食い違いが出てくるのは、平均が線形和であるのに対して、分散が2乗和で非線形だからです。一般に、非線形な統計量においては、特殊な母集団分布の場合を除いて、標本の統計量を多数集めた分布は、平均が元の母集団の統計量からズレており、偏った形になってしまいます。

ということで、母分散の推定には、不偏分散\[u^{2} = \frac{1}{n - 1} \sum_{i = 1}^{n} ( x_{i} - m )^{2}\]を使います。この不偏分散の期待値は母分散に一致します。

最後に母標準偏差の推定ですが、これも非線形なので標本の標準偏差というわけにはいきません。不偏分散の平方根をとるのも期待値が母標準偏差に一致しません。真面目に期待値が母標準偏差になるようにしたのが、不偏標準偏差\[D = \frac{\Gamma(n / 2 - 1 / 2)}{\Gamma(n / 2)} \sqrt{\frac{1}{2} \sum_{i = 1}^{n} ( x_{i} - m )^{2}}\]です。この導出もそれなりに大変なので省略します。ここで、\[\Gamma(z)\]というのは統計学によく出てくるガンマ関数という特殊関数です。このガンマ関数に対してスターリングの公式を適用して、nの大きいところで\[1 / n^{2}\]以下の項を無視すると、不偏標準偏差は\[D \approx \sqrt{\frac{1}{n - 3 / 2} \sum_{i = 1}^{n} ( x_{i} - m )^{2}}\]と近似できます。実際には、この近似式がよく用いられます。

このブログでは標準偏差として不偏標準偏差Dを用いています。

このような不偏推定値を用いるのは統計処理の一つの「作法」でありますが、「常にそうするべきか?」というのは論争のタネになります。分散や標準偏差のように簡単な関数で書ける場合にはいいのですのが、もっと複雑な処理の場合に不偏推定値がどうなるのかは大問題(ものによってはそれだけで学術論文になるレベル)ですし、「そこまでコストをかけてやることか?」「標本数が多ければ一緒でしょ?」「不偏推定値が上手く機能しないケースだってあるし」等ということにもなってきます。一方で「統計学的に正確に行うことが科学の普遍性だ」というような原理主義的な考え方の人もいて、研究者によって意見が対立してくることになるわけです。まぁ実際にはそこまで極端な人は少数だと思いますが。

2015年3月14日に行われた電王戦FINAL第1局において「投了の作法」が大きな話題となりました。棋士は通常、詰みの局面まで指すことはせず、その前に投了することが「作法」になっています。一方でコンピュータ将棋においては合法手がなくなるまで最後まで指しきるようにしていることが多いようです。

これらの「作法」については個々の美学が反映されているものですので、その是非についてここで論じることはありません。ここで取り上げたいのは、投了のやり方によって結果的に手数が変わってくるという点です。

棋士とソフトで平均手数はどれくらい違っているのか? また、投了条件に評価値閾値を設定した場合に値の設定によって手数はどれくらい変わるのか? 等を考えてみたいと思います。

棋士とソフトの手数の違いはデータを比較する際に補正のための情報として必要になることがあるかもしれません。また、投了条件の評価値設定を考える際には閾値と手数の関係性の情報が参考になることもあるでしょう。

目次


関連コラム

このページのトップヘ