コンピュータ将棋の特長の一つに、誰でも簡単にソフト同士の対局実験ができるということがあります。人間の将棋の場合には、同じ人同士を100回、1000回と連続対局させて勝率を推定するというような実験は現実的に困難であるわけですが、コンピュータ同士なら黙々とやってくれます。実験ができるというのは技術開発にとって非常に大切なことです。

「同じソフト同士を戦わせたら毎回、同じ結果になるんじゃないか」と思われる方もいるかもしれませんが、多くの将棋ソフトは序盤に擬似的なランダム性が入っていますので、その範囲内で違った結果になります。逆に言えば、一局の結果というのは確率的なものですので、統計的に処理して、誤差も考えないと、適切な能力評価ができないと言えます。

今回は、自己対戦/連続対戦の結果から勝率やレートを推定する際の誤差の問題について整理してみたいと思います。以下、先手後手の手番については、常に割合を一定で揃えること(同数、もしくは常に先手/後手のみ等)として、誤差には影響しないものとします。また、引き分けもないものとしています。これは、引き分けの対局を取り除いていると考えることもできますし、互いに0.5勝分として2つの引き分けを1勝1敗に変換していると考えることもできます(※引き分けが奇数の場合は余りが出ますが、1つなら、どう処理しても以下の議論にほとんど影響を与えません)。

まずは、AとBがn回連続対戦して、Aがk回勝った時のAの勝率を推定してみましょう。

「そんなの勝率なんだから、“k / n”に決まってるだろ」と思われるかもしれませんが、そう思う根拠は何かということです。実際に、本当の勝率p(真値)というのは無限に多くの対局を行った時の勝ち数の割合の極限値であり、有限の対局数における“k / n”とは必ずしも一致しません。“k / n”というのは、pの推定値に過ぎないわけですから、何故それを推定値とするのかという根拠がいるわけです。

連続対戦のn回の結果は互いに独立であるとしましょう。人間同士の連続対戦であれば、前の結果を引きずる等の影響があるため、結果が独立であるとは限りませんが、コンピュータ同士の場合には、擬似乱数が機能していれば、互いに独立であるとみなすことができます。

今、勝率の真値pは分かりませんので、代わりに推定値qを用いるとすると、この時、Aがk回勝つ確率の推定値Qは、\[Q = \frac{n!}{k! (n - k)!} q^{k} (1 - q)^{n - k}\]となります。実際に「Aがk回勝つ」というのは実現されており、Qはできるだけ大きい値であった方が現実に近いだろうと考えられますので、Qを最大化するq、すなわち、\[\frac{d{Q}}{d{q}} \propto k - n q = 0\]を満たす\[q = \frac{k}{n}\]が最も尤もらしい推定値(最尤値)ということになります。

また、そもそも真の勝率pというのは、無数の対局結果における勝ち点のデータ集合(母集団)の平均(母平均)であるとも考えられます。この時、連続対戦のn回の結果というのは無作為の標本であると考えられますので、標本平均である“k / n” = qは、二乗誤差を最小化する「母平均の不偏推定値」にもなっています。平均と不偏推定値については、「平均と標準偏差:それって不偏推定値?」の解説記事をご覧ください。

つまり、この場合には、qというのは最尤値であり、かつ不偏推定値でもあるため、誰もが自然に受け入れていたということになります。以下、誤差論においては、「標本平均」という立場の方が分かりやすいので、そちらの立場から話を進めていきます。

さて、標本平均は、サンプル数nが同じでも、サンプルセットが異なれば値が変わり得ます。実際、n回の連続対戦を行う度に、毎回、標本平均である勝率の推定値qは異なる値になり得るわけです。つまり、標本平均自体が何らかの確率分布を持っているということになります。

サンプル数nの標本平均の確率分布については、中心極限定理が存在しており、nが十分に大きければ、平均p、標準偏差\[S = \frac{s}{\sqrt{n}}\]の正規分布になることが知られています(※記事の最後に直感的な証明を付記します)。ここで、pはサンプルを取る母集団の平均(すなわち、勝率の真値)であり、sは母集団の標準偏差、すなわち、\[s = \sqrt{p (1 - p)}\]です。標準偏差については、「平均と標準偏差:それって不偏推定値?」の解説記事をご覧ください。

n回の連続対戦を行った時に得られる勝率の推定値は、その確率分布に従って“サイコロ”を投げた時の1つの結果に過ぎません。それがどれくらい真値に近いのかは確率的にしか分からないということになります。

nが十分に大きいとして、確率分布が正規分布であるとすると、“サイコロ”を投げて「真値p±標準偏差S」の区間内の結果が得られる確率は約68.3%ということになります。この時の標準偏差Sは標準誤差とも言います(※慣習的に“シグマ”と呼ぶ人もいますが、記法の慣習は変わりやすいものですので、お勧めはしません)。

また、X%以上の確率で結果が得られるという区間を「X%信頼区間」と言います。つまり、「真値±標準誤差」は「68%信頼区間」です。また、「真値±1.96標準誤差」は「95%信頼区間」であり、「真値±2.58標準誤差」は「99%信頼区間」になります。「真値±(標準誤差×r)」と「[(1 - a)×100]%信頼区間」との関係を下図に示しました。

r-log10a

確率というものは、いくら確率が低くても当たる時には当たってしまうものですので、絶対ということはありません。「標準誤差の何倍まで」/「何%信頼区間」で良しとするのかは、そのデータの重要性を鑑みての人間の判断ということになります。とりあえずは標準誤差を推定しておけば、後は各人で判断が可能です。

ここで、「標準誤差を推定」と書いたのは、上述のSの式が母集団の標準偏差sに依存しているためです。母集団の標準偏差は、勝率の真値pが分からないと分からないため、これも推定する必要があります。ただし、こちらは真値の推定よりもゆるいものでよいため、式中の勝率の真値pを推定値q = k / nで置き換えて、\[s \approx \sqrt{q (1 - q)}\]としてもいいですし、標本の不偏標準偏差を用いて\[s \approx \sqrt{\frac{n}{n - (3 / 2)} q (1 - q)}\]と推定してもかまいません(※)。nが十分に大きければ、どちらでもほぼ同じ値になります。不偏推定値にこだわるかどうかの違いです。

※(2016年5月31日追記) 不偏分散の平方根(すなわち、分母が「n - (3 / 2)」ではなく、「n - 1」)を使うこともあり、これを実験誤差と呼びます。これは理論的には中途半端な取り扱いということになるのですが、慣習的には最もよく使われており、例えば、不確かさの国際基準(GUM)でも標準として採用されています。

さて、これでAとBとの間の勝率と標準誤差の推定ができるようになりましたので、次に両者の間の相対レートを求めてみましょう。

相対レートの推定値dRは、勝率の推定値qを用いて、\[dR = 400 \log_{10}(\frac{q}{1 - q}) + K\]で与えられます。ここで、Kは系統誤差を表していますが、これについては後で説明します。イロレーティングについては、以下の解説記事をご覧ください。

相対レートの標準誤差を求めるには、誤差伝播を考慮する必要があります。勝率の推定値qが、勝率の真値pと標準誤差Sから、q = p±Sで書かれる場合を想定して、上の相対レートの推定値の式をpの周りでSについて1次まで展開すると、\[dR \approx 400 \log_{10}(\frac{p}{1 - p}) + \frac{400}{\ln{(10)}} \frac{S}{p (1 - p)} + K\]となります。最初の項が相対レートの真値であり、次のSの1次の項が相対レートの標準誤差に当たります。相対レートの標準誤差を、Sの次数を変えないように推定値のみで書き換えると、\[\frac{400}{\ln{(10)}} \frac{S}{p (1 - p)} \approx 173.7 \frac{S}{q (1 - q)}\]となります。この誤差伝播における展開は、Sがpや(1 - p)よりも十分に小さくないと成立しませんので、適用する際にはご注意ください。

一般的に、誤差には偶然誤差と系統誤差があります(※設定ミスや計算ミス等の人為的な誤差も生じ得ますが、ここでは除きます)。今まで記してきた標準誤差というのは、偶然誤差を表す指標です。誤差には他に系統誤差が存在しており、これは統計処理で推定したり、取り除いたりすることはできません。

実は、勝率の推定の際にも系統誤差が生じる余地がありました。例えば、擬似乱数が偏っていたり、定期的に“何とかアップデート”が起動してマシンリソースが偏ったりするというようなことがあると、系統誤差が生じてしまい、それは統計処理で何とかなるものではありません。ただし、その時の系統誤差はあったとしても影響は少ないだろうと推測して省いていたわけです。

しかしながら、相対レートについては、相性の問題とイロレーティングの理論の問題があるために、系統誤差を無視することはできません。本来の相対レートというのは相性の問題を取り除いた上で評価されなければなりませんし、そもそもイロレーティングの理論で用いた仮定が妥当でなければ、有意義な値は出てきません。理論の部分については、そもそもイロレーティングを使うべきかという話になりますので、一先ず置いておくとしても、相性の問題は深刻です。

相性の問題については、今のところはデータが整理されておらず、各人の経験によって脳内補正するしかない状況であるようです。この問題については、機会がありましたら、改めて解析してみたいと考えています。

最後に、具体例で計算してみましょう。10000戦してAが8000勝したとします。すなわち、n = 10000、k = 8000です。この時の勝率の推定値は、\[q = \frac{8000}{10000} = 0.8\]となり、標準誤差は、\[S = \sqrt{\frac{10000}{10000 - 1.5}~ \times 0.8~ \times (1 - 0.8)}~~ \approx 0.004\]となります。相対レートの推定値は、\[dR = 400 \log_{10}(\frac{0.8}{1 - 0.8}) + K \approx 240.8 + K\]であり、その時の標準誤差は\[173.7 \times \frac{0.004}{0.8 (1 - 0.8)} \approx 4.3\]です。系統誤差Kについては、この情報からだけでは何も分かりません。

さて、以上の話は「nが十分に大きい」ということが前提になっていました。しかしながら、「十分に大きい」というのは具体的にどれくらいの大きさなのでしょうか? また、実験の都合により「十分ではないが、それなりに大きい」という場合には、何か別の処理方法があるのでしょうか? 次回は、その辺の話について書きたいと思います。

-------------------

付記:中心極限定理の直感的な証明

以下の証明は直感的なもので厳密ではありません(※積率母関数を用いた弱収束の証明の簡易版です)。厳密な証明は統計学の教科書をご覧ください。

母集団の平均は0、標準偏差は1だとします。これは値の原点とスケールの取り方に対応しますので、一般性を失いません。

サンプル数nの無作為標本\[\{ x_{1}, x_{2}, \cdots, x_{n} \}\]の標本平均を\[M = \sum_{i = 1}^{n} \frac{x_{i}}{n}\]とします。

標本を何度も無作為に作り直す時、標本平均Mの期待値は、\[\big< M \big> = \sum_{i = 1}^{n} \frac{\big< x_{i} \big>}{n} = 0\]となります。ここで、母集団の平均が0であることを利用しました。

さらに、標本平均の2乗の期待値は、\[\big< M^{2} \big> = \sum_{i = 1}^{n} \sum_{j = 1}^{n} \frac{\big< x_{i} x_{j} \big>}{n^{2}} = \sum_{i = 1}^{n} \frac{\big< x_{i}^{2} \big>}{n^{2}} = \frac{1}{n}\]となります。ここで、無作為標本であることから、異なる2つの要素間の相関\[\big< x_{i} x_{j} \big>~~ (i \ne j)\]は0であるとしました。また、母集団の標準偏差が1であることを利用しました。

一般的に、同じ要素のペアだけが消えずに残ることから、m個の要素間の相関について、\[\sum_{i = 1}^{n} \sum_{j = 1}^{n} \sum_{k = 1}^{n} \cdots \sum_{l = 1}^{n} \big< x_{i} x_{j} x_{k} \cdots x_{l} \big>\]\[ = (m - 1) \sum_{i = 1}^{n} \big< x_{i}^{2} \big> \sum_{k = 1}^{n} \cdots \sum_{l = 1}^{n} \big< x_{k} \cdots x_{l} \big> (1 + O(1 / n))\]の分離定理が成立します。ここで、O(1 / n)は(1 / n)以下の項を表しており、具体的には、3つ以上の同じ要素の組み合わせから出てくる寄与のことを指しています。さらに、母集団の標準偏差が1であることから、\[(m - 1) \sum_{i = 1}^{n} \big< x_{i}^{2} \big> \sum_{k = 1}^{n} \cdots \sum_{l = 1}^{n} \big< x_{k} \cdots x_{l} \big> = (m - 1) n \sum_{k = 1}^{n} \cdots \sum_{l = 1}^{n} \big< x_{k} \cdots x_{l} \big>\]となります。

上の段落において、あらゆる異なる要素間の相関がゼロになるという「無作為」を仮定していること、並びに、m個の要素間の相関が発散せずに存在することを仮定していることに注意してください。これらの仮定は意外と自明ではありません。

nが十分に大きいとして、(1 / n)以下の寄与を無視すると、標本平均MのL次の積率\[\big< M^{L} \big>\]は、Lが奇数の時は0となり、Lが偶数の時には、L = 2 lとすると、\[\big< M^{2 l} \big> = \frac{1}{n^{l}} \prod_{j = 1}^{l} (2 j - 1)\]となります。

これらの積率は、確率分布が平均0、分散(1 / n)の正規分布であるとした場合のものと一致するため、nが十分に大きい時には、確率分布が正規分布となることが分かります。■