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

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

カテゴリ: 解説

通常、対局結果は時系列のデータリストとして記録されます。「いついつにAがBに勝った」というようなデータが逐次的に記録されていくわけです(※大会等では「第1回戦の記録」というような同時刻扱いのデータも出てきます)。

この対局結果のデータリストから棋力を推測しようというのがイロレーティングの理論でした。イロレーティングについては以下の記事をご参照ください。

イロレーティングでは、逐次的に勝者のレートを上げ、敗者のレートを下げることで均衡点を探すということをします。対局数が少ない時にはレートを適切に測ることはできませんが、対局数が多ければ、レートは均衡点の周りを一定の標準偏差で揺れ動くことになります。

この手法は簡単でありながら、時系列のデータにも自然に対応しており、棋力のなだらかな変化も均衡点の推移として反映することができるという優れた手法です。その一方で、均衡点をどのように見積もればいいのかが明確ではないこと、均衡点の見積もりに多数のデータが必要であり、また不確かさの評価が明確ではないこと、レート上限/下限の境界付近において偏りが発生すること等の問題点もあります。

ベイズ統計を用いると、いくつかの仮定の下で、もう少し洗練された手法に改良することができますが、同時に、仕組みが複雑になってしまいます。この手法の洗練さ(信頼性とはまた別)と簡単さとのトレードオフは悩ましいところです。結局のところ、データの量が限られている以上は小手先で対処できることは限られており、よほど有力な仮説がなければ、データ量を増やす(つまり対局数を増やしたり、勝敗以外の棋譜データを活用したりする)のが一番ということになります。

これらの問題は、全て時系列データの逐次処理に由来するものです。すでに記録されている一定期間の対局結果を“時系列を無視して”処理する場合には、古典的な統計手法が有効になります(静的レーティングシステムという)。その一つが最尤法です。今回は、この手法について技術的に解説したいと思います。

最初に、歴史的な背景と用語について少し触れておきます。今回の最尤法を用いたレート推定の方法は、Bradley-Terry模型(1952)が最初だと言われています。Bradley-Terry模型の勝率式は、書き換えると、イロレーティングの勝率仮定に一致します。「イロレーティング」という用語は厳密には時系列データを逐次的に処理する手順を含めた総括的なものであり、静的レーティングシステムにおける最尤法による推定模型は「Bradley-Terry模型」というのが正確です。ただし、この用語は専門的であり、一般には通じない可能性が極めて高いため、「イロレーティングを最尤法で」と言っても問題ないかと思います(専門家に怒られないという保証はありませんが)。また、最尤法はベイズ統計で定式化することもできるため、ベイズ統計による静的レーティング(静的ベイジアンELO)であると主張する人もいます。

静的レーティングシステムにおいては、“時系列を無視する”ため、その期間内の全ての対局者のレートが一定であると仮定されており、その全てのレートを同時に推定することになります。これは期間内に大きくレートが変わった者がいる場合には誤差が発生するということを意味しており、特にfloodgateで中身が変わったという場合には注意が必要です(※このような仮定に由来する系統誤差は後述の不確かさの見積もりでは評価不能)。推定時にレート変更の情報があれば、対局者名を変更したり、外れデータとして弾いたりすることもできますが、実際には情報がないことがほとんどであり、対処は困難です。

原理的にレートは相対値であるため、誰かを基準者としてレートの数値を固定し、そこからの相対値を推定します。平均を基準値にしたい場合には、最初に基準者を決めてレートを推定してから、最後に平均が基準値になる様に全体の値をシフトします。基準者は、なるべく中間的な実力で多数の対局者と多く対局している者が向いています。

イロレーティングと同様に、最尤法においてもレートが求まらない対局者が発生することがあります。具体的には、「基準者と対局している者、また、その者と対局している者、また、その者と対局している者、……」という関係集団に含まれていない者、また、関係集団内でも集団内で全勝/全敗の者のレートは算出することができません。推定時には、事前にレート算出が可能であるかを確認して、算出可能者のみの対局に絞って計算する必要があります。

ここでは時系列は考えないため、対局結果は「A対B:何勝何敗」という対局組み合わせ毎のデータリストにまとめることができます。また、ここでは簡単のために引き分けは考えません。引き分けは、取り除くか、0.5勝0.5敗に換算するかというような事前処理が行われているものとします。

最尤法の原理は「データを再現する確率(尤もらしさ)が最大になるように変数(レート)を決める」ということです。ここで、確率を計算する際に仮定/模型が必要になります。仮定/模型の妥当性は、この手法の範囲内では分かりません(※データ量が多い場合には、無作為に選んだ一部のデータを推定に使わずに取っておき、推定結果とそのデータとの整合性から“予言性”を確かめるといった程度の確認なら可能です)。

イロレーティングの勝率仮定(Bradley-Terry模型)においては、確率Pは、

\[P = \prod_{(i, j)} \left[ \frac{1}{1 + 10^{- (R(i) - R(j)) / 400}} \right]^{w(i, j)} \left[ \frac{1}{1 + 10^{- (R(j) - R(i)) / 400}} \right]^{l(i, j)}\]

のように与えられます。ここで、(i, j)は対局組み合わせ、w(i, j)はその対局組み合わせにおけるiの勝ち数、l(i, j)はiの負け数、R(i)はiのレートを表しています。レートの差の部分にさらに相性のレート補正項を入れて(例えば、「R(i) - R(j) + A(i, j)」のように)、補正項のレート変数も含めて、同時に推定するようなこともできますが、変数を増やした分だけ、必要なデータの量も増えますので、豊潤にデータがない限りはお勧めできません。

この確率Pは非常に小さな値になってしまうため、直接的に取り扱わずに自然対数にして取り扱います。すなわち、

\[\ln{P} = - \sum_{(i, j)} \left[ w(i, j) \ln[1 + 10^{- (R(i) - R(j)) / 400}] + l(i, j) \ln[1 + 10^{- (R(j) - R(i)) / 400}] \right]\]

を最大化すればよいわけです。最大値では、変数(レート)に対する偏微分である

\[\frac{\partial{\ln{P}}}{\partial{R(k)}} = \frac{\ln{10}}{400} \sum_{(i, j)} (\delta_{k, i} - \delta_{k, j}) \left[ \frac{w(i, j)}{1 + 10^{(R(i) - R(j)) / 400}} - \frac{l(i, j)}{1 + 10^{(R(j) - R(i)) / 400}} \right]\]

がkに依らずに全て0となります。ここで、クロネッカーのデルタ記号

\[\delta_{i, j} = 0 ~(i = j) ~~\text{or}~~ 1 ~(i \ne j)\]

を使いました。

多変数関数の最大化は、最急降下法や共役勾配法等で、簡単に数値計算することができます。一般的には、非線形連立方程式を解くよりも、最大化の方が簡単です。また、元の関数の符号を反転させれば、最大化は最小化になりますので、最大化と最小化は同じ問題になります。多変数関数の最小化は、拘束条件(ラグランジュ法による正則化)を除けば、ボナンザ式の機械学習と同じですので、結局、最尤法は機械学習と同じことをやればいいということになります。計算の際に必要な初期値は、基準者等に対する勝率から適当に与えれば、よほど変なデータでない限りは上手くいきます。

さて、これで最尤法を用いてレート推定ができるようになったわけですが、推定の結果はどれくらい確か/不確かなのでしょうか?

SF的に微妙に異なる平行世界を考えると、棋力(レートの真の値)や対局組み合わせ、対局数が同じであっても、対局結果(w(i, j)とl(i, j)の割合)は確率的にばらつきます。対局結果が異なれば、当然、最尤法によるレートの推定値も変わってきます。つまり、本来はレートの推定値というのは確率的にばらつくものであり、1つの推定値はサイコロを振って偶々出た値の1つに過ぎないと言えます。このような場合、ばらつきの大きさ(不確かさ)を評価して、誤差の目安とします。特に、ばらつきの標準偏差は「標準不確かさ」と呼ばれ、推定値に付記されることが多いものです(※)。

※ 近年の測定論では、推定値(最確値)と標準不確かさを一揃えにして測定値として定義します。系統誤差が無視できる(と仮定する)場合には「標準不確かさ」は「標準誤差」と一致します。

もし仮に、レートの真値が存在し、また、イロレーティングの勝率仮定が正しいとするならば、対局結果をシミュレートすることで、標準不確かさを見積もることができます。ただし、「レートの真値」は分からないものであるため、推定値に近い(誤差が小さい)と仮定して、真値の代わりに推定値で代用します。これは理論的には誤差の高次の項を無視することに対応しています。

最尤法における標準不確かさの評価方法には、計算時に追加する仮定に応じて、いくつかの種類があります(ヘッセ行列の逆行列を用いた方法など)。一般的に、仮定を増やすほど、また、専門的な手法であるほど、計算量が少なくて済みます。

今回の目的においては計算量はあまり重要ではないと思われますので、ここでは、最も仮定が少なく、最も汎用的な(最尤法以外でも使える)手法である「(不確かさ評価における)モンテカルロ法」を紹介します。この手法は、精密測定の分野でも最近よく用いられているものです(模型の造りは異なりますが)。

方法は簡単であり、「レートの真値を推定値で近似して、疑似乱数を用いて対局をシミュレートし、その結果から対応する(平行世界の)推定値を計算することで推定値のばらつきを統計的に評価する」というだけです(つまり“力業”)。大体100~1000回くらい実行すれば、標準不確かさを大よそ見積もることができます。

この方法では、単純計算では推定値の見積もりの100~1000倍の計算量が必要になりますが、実際には、初期値に推定値を与えれば大抵は収束が速いこと、推定値の計算時よりも最大化計算の許容精度をかなり大きく取ってよいこと、並列化が容易であること等から、そこまでの時間はかかりません。

計算上の注意点としては、標準不確かさを評価する際に、元の推定値からの標準偏差ではなく、平均からの標準偏差を見積もるということがあります。一般的に、最尤法の推定値は、分布が偏っている可能性がある(不偏とは限らない)ため、平均とは一致しません。特にイロレーティングの場合には、レートの上限/下限の境界付近で偏りが生じやすくなっています。この偏りを考慮すると、この計算で知りたいのは不確かさ(ばらつきの大きさ)ですので、平均からの標準偏差を見積もる方が適切であるということになります。

以上、今回は、最尤法を用いてレートの推定値と標準不確かさを見積もる方法を解説しました。時系列や逐次処理に拘らなければ、最尤法のような枯れた古典手法が有効になります。目の前の問題の前提を少し変えることで古典手法に落とし込むというのは、レート推定に限らす、一般的に有力な技法です。

前回の記事「自己対戦及び連続対戦の誤差論 1:標準誤差と信頼区間」では、自己対戦/連続対戦の対局数が十分に大きい場合に誤差をどのように見積もればいいのかを整理しました。今回は、対局数の影響について解説します。

標準誤差は対局数nの平方根に逆比例していました。つまり、対局数が大きくなるほど、誤差は小さくなり、精度が高くなるということになります。

必要な精度というのは、実験者がどれくらいまで求めるのかということに依ってきますが、「実際に誤差を計算してみて、必要な精度が出ているかどうか」というのが「対局数が十分であるかどうか」の基本的な判断基準になります。ただし、誤差の計算には、いくつか注意しなければならないことがあります。それが今回の記事の主題です。

前回の記事で紹介した誤差論は、対局数が多くて標準誤差が小さい時に有効なものでした。そうでない場合には、誤差の見積もりを修正しなければならないことがあります。

例えば、標準誤差は、勝率の真値pに依存しており、p (1 - p)に比例していました。これは、pの関数として描くと、下図のようになります。

p_1-p

しかしながら、勝率の真値pは分からないため、勝率の推定値qを用いて、標準誤差を推定することになりました。pとqの値が近ければ、この標準誤差の推定は妥当なものとなりますが、もしそうでなければ、標準誤差の推定は的外れなものになってしまうかもしれません。特に、qが0や1に近い場合には、変化が大きいので、注意が必要です。

実際の標準誤差が推定よりも小さい場合には問題はないのですが、推定よりも大きい場合には、実際の精度よりも過剰に精度を見積もってしまうことになるため、問題が生じ得ます。該当する場合には、標準誤差を適度に上方修正して考える必要があるでしょう。

この話は、言い換えると、誤差の高次の項の問題の一種ということになります。誤差が小さければ現れなかった問題が、誤差が大きくなってくると無視できなくなってくるということです(※)。これらの問題をまとめて解決するには、結局のところ、対局数を増やして精度を上げるしかありません。

※(2016年5月31日追記) そもそも「誤差」は真値との差として定義されているわけですが、真値というのは値が分からないものであるため、「誤差」を計算するには真値について何らかの仮定を置く必要があります。これが、誤差論の根本的な問題の一つであり、高次の項の問題の根本もそこにあります。この問題を避けるため、「誤差」という概念は諦めて、「不確かさ」という概念を導入するというのが近年の主流です。「不確かさ」は平均からのばらつきとして定義され、その平均が真値に近いかどうかは問題を切り分けます。「誤差」と異なり、「不確かさ」についてならば、紛れのない国際基準を作ることも可能であり、その国際基準(GUM)は物理学や工学等の分野で広く採用されています。

一方で、誤差の大きさとは直接的に関係無しに、対局数の不足のみによって生じる問題もあります。具体的には、中心極限定理の適用の妥当性の問題です。こちらは理論的に対処することができます。

中心極限定理は、対局数が十分に大きい時に、確率分布が正規分布になることを示していました。しかしながら、実際には、n回連続対戦した時の勝率の推定値qの確率分布は離散確率分布になっており、正規分布のような連続確率分布にはなっていません。なぜなら、qは、自然数である勝ち数kを使って、“k / n”と計算されるからです。もちろん、nが十分に大きくなれば、“k / n”の有理数は実数に近いものとして取り扱うことができるわけですが、実際にそれがどれくらい良い近似であるのかというのは、誤差の評価とは別に、対局数によって決まってくる問題ということになります。

実際の確率分布は、勝率の真値pを用いると、\[\frac{n!}{k! (n - k)!} p^{k} (1 - p)^{n - k},~~ k = n q\]の二項分布として書き表すことができます。

この二項分布の標準偏差は、\[S = \sqrt{\frac{p (1 - p)}{n}}\]であり、前回の正規分布の標準偏差と同じになりますので、標準誤差については、実は対局数に依らずに厳密な値であったということが分かります。

対局数によって変わってくるのは、標準誤差と信頼区間との間の関係です。以下の図は、正規分布において95%信頼区間である「真値±1.96標準誤差」(上図)と99%信頼区間である「真値±2.58標準誤差」(下図)内の実際の確率を表しています。分布が正規分布であれば、それぞれ0.95と0.99になるはずのものですが、実際には二項分布であるために離散的に値が変わってきます。横軸は対局数nです。

s

二項分布はnが十分に大きければ、正規分布で近似することができます。これは中心極限定理に対応しています。ただし、nが大きくても、n p、もしくはn (1 - p)が小さければ、ポアソン分布になり、正規分布にはなりません。実際に、上記の図でも、pが0.5(黒点)と0.1(橙色点)の時には、正規分布に近い結果になっており、pが0.01(赤点)の時には、正規分布の結果からのズレが大きくなっています。

上の図で示した区間内の確率は大きい分には問題ないのですが、小さくなると、その分だけ信頼が落ちるということになります。また、これらの確率は勝率の真値pに依存しており、真値pは分からないものですので、対局数を調整して信頼を上げるというような操作を行うこともできません。結局のところ、確率の下限の方に着目して、その分だけ信頼区間の%を下方修正して考えるというのが、妥当な解釈ということになるでしょう。

勝率の真値pに対して推定値qを適用してよいということであるのならば、二項分布を用いて、最小の信頼区間を推定することができます。ただし、この信頼区間においても、上で記した「誤差の高次の項の問題」は変わらずに発生し得ます。この処方箋で対処できるのは、「中心極限定理の適用の妥当性の問題」のみです。

さて、前回の記事で、相対レートにおける標準誤差を推定する際に、勝率の標準誤差Sに対する展開を行いました。この展開は、Sがpや(1 - p)よりも十分に小さい時には有効なのですが、そうでない場合には使うことができません。特に、勝率に対してそれなりに広い信頼区間が与えられた時には、破綻してしまいます。

この問題も「誤差の高次の項の問題」の一種ですが、これは観測データの直接的な処理の問題ではなく、誤差伝播という間接的な処理の問題であるため、理論的な対処が可能です。

実際に、相対レートは勝率に対して単調増加関数ですので、信頼区間が与えられた時には、展開を用いなくても、上限値と下限値をそのまま放り込むことで、対応する相対レートの信頼区間を得ることができます。

これらの信頼区間の見積もりはコンピュータで簡単に計算することができます。「連続対戦における信頼区間の計算」の資料記事に計算プログラムを記しました。

以上、自己対戦/連続対戦の結果から勝率やレートを推定する際の誤差論について整理しました。結局のところ、実験の精度はデータの質と量で決まってきます。地道にデータを収集する基礎研究が華々しい成果の基盤になるのだと思います。

コンピュータ将棋の特長の一つに、誰でも簡単にソフト同士の対局実験ができるということがあります。人間の将棋の場合には、同じ人同士を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が十分に大きい時には、確率分布が正規分布となることが分かります。■

前回の記事「ミニマックス法とは何か? 1:コンピュータ将棋の基本戦略」では、ミニマックス法の戦略について解説しました。今回は、ミニマックス法における枝刈りについて解説します。

枝刈りには大きく分けて2つの種類があります。「前向き枝刈り」と「後ろ向き枝刈り」です。

「前向き枝刈り」とは、探索を行わずに何かしらの人為的な基準によって枝刈りを行うことです。探索に“先入観”を取り入れることになりますので、上手くいくかどうかはやり方に依ってきます。

「後ろ向き枝刈り」とは、探索時の情報を活用することでミニマックス法の結果ができるだけ変わらないように行われる枝刈りのことです。副題の「アルファベータ枝刈り」(アルファベータ法とも言う)が代表例であり、これはミニマックス法の結果を確実に再現することができます。後ろ向き枝刈りは基本的にはやった方が得になります。

今回の記事では、主として、後ろ向き枝刈りの最も基本的な手法であるアルファベータ法について解説します。この手法は、コンピュータ将棋の探索技術の基盤となるものです。

まずは、前回のミニマックス法の探索例を再掲します。

minimax_1

この例は、以下の図のように書き換え、「?」部分を任意の数字に置き換えても、初期局面の評価値や最善手の結果は変わりません。実際に色々と数字を入れて確認してみてください。ただし、探索途中の局面の評価値は変わりうるので、「+700↑」「+200↓」のように範囲で表現しています。ここで、数字末尾の「↑」は「以上」を、「↓」は「以下」を表しています。

ab_0

このことは、言い換えると、「?」部分は実は探索する必要がなかったということを意味しています。必ずしも全局面を探索しなくても、正確な初期局面の評価値や最善手を得ることができるというわけです。

それでは、実際にどのように探索をすれば無駄を減らすことができるのでしょうか?

探索量を減らすという事は、その分だけ情報量を減らすということを意味していますので、上の例で途中の評価値を確定値から範囲値に変えたように、情報量削減の工夫が必要になってきます。

探索の際に下限と上限の範囲を決めることで情報量を減らし、探索の無駄を省く手法のことをアルファベータ法と言います。名前は、下限値をα、上限値をβと書いたことに由来しており、現在でも探索の下限値と上限値は慣習的にαとβで書き表されます。

実際にやってみましょう。

ab_1

上の図でそれぞれの局面の左下に書いてあるのが探索範囲です。初期局面の探索範囲は負の無限から正の無限までの全ての範囲にしてあります(※図中の「INF」は無限の意味)。初期局面からスタートして、局面を展開し、上から下へと順番に探索していきます。探索範囲は、探索で得られた情報を用いて、随時更新されていきます。

まず、一番上に位置している4つの局面は、まだ何も情報がありませんので、初期局面の探索範囲のままです。右上の末端で「+500」という値が得られます。この分岐では最大値を探しているので、2番目の末端局面の探索範囲の下限が「+500」に更新されます。2番目の末端局面の値は「-200」であり、下限以下ですので、これは無視されて、最終更新値である「+500」が一つ前の局面の評価値として返されます。

一つ前の局面の分岐においては、最小値を探しているので、ここでは探索範囲の上限が更新されます。結果、探索の上限は「+500」となるのですが、3番目の末端局面の値は「+700」であるため、これで下限値を更新すると、それ以降の探索範囲は「+700」以上「+500」以下となって探索範囲が消失します。探索範囲が消失するということは、それ以降は探索しなくてもよいということです。

以下同様の操作で、無駄な探索を省いて正確な結果を得ることができます。この手順はプログラムで書くと簡単なのですが、人間が理解しようとすると中々に大変です。アルファベータ法の筆算方法の詳細については「アルファベータ法の筆算:これであなたもコンピュータ!?」の記事にまとめました。

さて、ここで注意しなければならないのは、上記の手法に際して、「上から下へ」という探索の順序を指定していたことです。前の記事で全局面を探索していた時には探索順序は関係ありませんでした。

実は、アルファベータ法の場合には探索順序が重要であり、探索順序によって省略できる探索量が変わってきます。例えば、上の例では末端の8局面の内の3局面の省略に成功していますが、記事冒頭の図に戻って、順序を「下から上へ」と逆にしてアルファベータ法をやってみると、ただの1局面も省略できないことが分かります。種を明かすと、上の例は「上から下へ」と探索した時に最も効率がよくなるような順序(各分岐で最善手を最初に探索)になっていたのです。

それでは、実際に探索順序によって探索量はどれくらい変わってくるのでしょうか?

分岐数を3に固定した時の探索局面数を以下に示します。横軸は探索の深さdです。青点が最善順序の時の結果(評価値は各分岐に対して等間隔)、赤点が最善順序の逆順の時の結果、黒点がランダムの時の結果(1000回の平均)になります。縦軸は常用対数ですので、10の何乗であるのかを表しています。

minimax_count

全局面を探索する場合には、3のd乗ですので、赤線になります。最善順序の逆順の場合の結果(赤点)は、これに近くなります。一方で、最善順序の場合の結果(青点)は、\[2 \times 3^{d / 2}\]の線(青線)によく一致しています。この式は、3を分岐数で置き換えると、固定分岐数におけるアルファベータ法の理想値として知られているものです。ランダムの場合の結果(黒点)は両者の中間くらいに位置しています。

つまり、アルファベータ法は、順序が最善ならば、探索量を平方根で減らすことができます。平方根の違いは意外と大きく、例えば、上図で20手のところを見てみると、最善順序なら10万局面程度の探索で済むところが、ランダムならその100倍以上の計算量が必要になり、全局面なら1万倍以上の計算量が必要になります。最善順序なら1秒で済む思考時間が、2分とか、3時間とかになってきてしまうわけです。局面数が増えると、違いはより顕著になります。

アルファベータ法が最もよく機能するのは、各分岐で最善手を最初に探索する場合であり、有望そうな手から順番に探索していくことが大切になります(指し手の順序付けの問題と言う)。一般には、浅い探索の結果を活用したり、別の枝(兄弟ノード)での突出した最善手(「killer move」と言う)を優先して探索したりというような工夫がなされています。

さて、上の例では、初期局面の探索範囲を負の無限から正の無限までの全範囲に設定していたわけですが、最初の段階から探索範囲に制限を加えてしまうことも可能です。ただし、その場合には、下限以下に正解がある場合には下限以下という情報しか得られませんし(「fail low」と言う)、逆に上限以上に正解がある場合には上限以上という情報しか得られません(「fail high」と言う)。設定範囲内に正解があるかどうかという賭けの要素が出てきます。

また、下限値(α)と上限値(β)を利用して、さらに枝刈りを行う手法もあります。例えば、「null move枝刈り」や「futility枝刈り」等が有名です。

「null move枝刈り」というのは、パス(null move)によって相手に手番を渡した時に、それでも上限値以上なら、その局面は上限値以上と決め付けるという手法のことです。将棋の場合には、パスより酷い手しかないという局面(チェス由来のドイツ語でツークツワンクと言う)は滅多にありませんから、非常に高確率で有効な手法です。

「futility枝刈り」というのは、末端まで残り1手の局面で評価値の簡易見積もりが下限値を大きく下回っている/上限値を大きく上回っているのならば、無駄(futility)になる可能性が高いので、その局面の探索を打ち切るという手法のことです。残り数手に拡張されることもあります。

これらの手法は、アルファベータ法とは異なり、確実な結果を保証するものではありませんが、コンピュータ将棋においては有効な運用が可能であることが知られています。

ちなみに、各々の枝刈り手法が「前向き」なのか、「後ろ向き」なのかについては文献によって記述に差があるようです。例えば、「futility枝刈り」は、評価値の簡易見積もりと人為的な基準によって探索を行わずに枝刈りをしているわけですから、厳密には「前向き」だと思われますが、一方で、アルファベータ法の近似手法の一つだと捉えると、「後ろ向き」であるとも解釈が可能です。「前向き」/「後ろ向き」の分類は、数学的な定義の問題というよりは、その手法をどういうものだと位置づけているかという解釈の問題なのかもしれません。

また、「全幅探索」という言葉についても様々に解釈の余地があるようです。本来は「その深さの全ての局面の探索」を意味する言葉ですが、それと同じ結果が得られるアルファベータ法も「全幅探索」に含めることがあります。また、「null move枝刈り」や「futility枝刈り」等も、近似的に同じ結果を得ていると考えて、「全幅探索」に含めることがあります(例えば、Bonanza等)。

この辺のことは定義に拘る人が見ると頭が痛くなるかもしれませんが、急速に発展する分野において言葉の整理が追いつかないというのは、とてもよくあることです。言葉を整理するのは、全てが終わった後に学問としてまとめる学者の仕事なのです。

最後に、ハードウエアに関することを少し補足しておきます。

上記の例では、1つのスレッド(一連の命令の流れ)で処理することが暗黙の前提になっていました。しかしながら、最近のCPUはマルチコアが基本になっています。例えば、第1期電王戦に使用されるIntel Core i7-6700Kであれば、4つの物理コアを有しており、一度に4つのスレッドを処理することが可能です。さらに、ハイパースレッディング(HT)技術を用いると、4つの物理コアを8つの仮想コア(論理コアとも言う)に分けて利用することもでき、同時に8つのスレッドを処理することも可能になります。ただし、その場合には、1スレッドの性能は0.65倍程度に落ちてしまうようです(参照:「30分でBonanzaの評価関数の要点を話します!」)。また、1台のPCに限らず、多数のPCをつなげてクラスタとして使用する場合には、もっと大量のスレッドを同時に処理することになります。

上述のアルファベータ法等の枝刈りは、探索時に得た情報を随時的に活用していました。これをマルチスレッドでどのように処理すればいいのかというのは技術的に簡単な話ではありません(並列化の問題と言う)。スレッド数が倍になっても自動的に探索速度が倍になるわけではないということです(※一説には、実効的な探索速度はスレッド数の平方根以上程度と言われています)。この問題については、ここではこれ以上は深入りしません。

以上、今回はミニマックス法における枝刈りについて解説しました。ここで記したのは、本当に基礎的な部分ですが、コンピュータがどのように“考えている”のかを知るための一つのきっかけとなってくれれば幸いです。

電王戦で一躍有名になったものの一つに「評価値」というものがあります。これはコンピュータが考える局面の形勢を数値化したものであり、歩一枚が100点程度になるように規格化されています。ちなみに、歩が100点というのは、コンピュータチェスのセンチポーン(1点=歩兵の100分の1)に由来しています。

機械が計算する値なら、電卓のように、局面を入れればポンと決まった値が出てきそうな気がしますが、実際の評価値は時間が経つと共に数値が更新されていきます。これはコンピュータが“考えている”からなのですが、一体、何をどうやって“考えている”のでしょうか?

実は、局面を入れればポンと出てくる値というのはちゃんと存在していて、「静的評価値」と言います。機械学習等で作るのは、この値を計算する関数(静的評価関数)です。コンピュータは、この静的評価値に基づいて、先の手を読んで(探索と言う)、評価値を更新していきます。いわゆる「評価値」というのは、読んだ先の局面の静的評価値のことであり、それ故に、探索が進むにつれて値が変わってくるわけです。

この辺の手法というのは、意外と人間に近い感じがします。「静的評価値」が“一目の判断”に対応していると考えると、それに基づいて先の展開を読んで、形勢を判断したり、指し手を決めたりするということ自体は人間のやり方と同じです。

それでは、実際にコンピュータはどのように探索を行っているのでしょうか?

もちろん、技術の詳細は複雑であり、また、ソフトによっても違うわけですが、今回は最も基本となる仕組みである「ミニマックス法」について解説します。

まず、先の展開を読むためには、自分の指し手の方針を決め、また、相手の指し手を予測しなければなりません。いわゆる戦略が必要になります。

自分の指し手については、最も評価値の高い局面(“最善手”と言う、本当に最善であるかは神のみぞ知る)を選択することにします。序盤では定跡ファイルの登録手を用いたり、対人ゲームでは擬似乱数によって手をばらけさせたりというようなこともありますが、ここでは最善手のみを考えます。

相手の指し手については、相手が自分であると想定して、相手にとっての最善手(こちらの評価値を最も下げる手)を指し手として予測します。「なぜベストを尽くさないのか」というわけです。

このように両者が最善手で応じると考えると、先の展開を読むことが可能になります。この戦略を「ミニマックス法」と言います。「ミニマックス」とは「最小(min)となる最大損害(max)」という意味であり、将棋は2人で指すものですから、こちらのミスをなくしてひたすら耐えていれば、その内に相手がミスをして有利を築けるだろうと考えていることになります(※ここでの「耐える」というのは将棋の攻め/受けとは別の概念であり、攻めでも受けでも、得をするためにやるのではなく、損をしないためにやっているということです)。

ちなみに、将棋の場合には「自分の損害」=「相手の利益」ですので(零和と言う)、「最小となる相手の最大利益」と言い換えることもできます。ただの言い換えですが、受ける印象は変わります。また、「損害」と「利益」というのは、原点と符号だけの違いですので、「最大(max)となる最小利益(min)」と言い換えることもでき、この場合は「マクシミン」戦略と呼ばれます。この辺は様々な書き方ができるので混乱の元になるのですが、本質は同じことです。

それでは、具体的にやってみましょう。

簡単のために深さを3に固定して、以下の図のゲーム展開(ゲーム木と言う)における3手の読みを考えてみます。

minimax_0

一番左が出発局面(根ノード)で自分の手番(青色)とします。そこから、指し手の候補が2つに分かれて、右側の相手の手番(赤色)の局面となり、さらに分岐して右へ右へと展開していきます。右端の末端局面(葉ノード)にある数字が、その局面の静的評価値です。静的評価値の数値は、こちらが優勢となる正の値が多いですが、中には負の値となってしまう変化も含まれています。

両者最善の変化を探すには、以下の図のように、右端の末端局面から順番に遡っていきます。こちらの手番では最大値を選び、相手の手番では最小値を選びます。

minimax_1

結果的に、一番上の変化が両者最善であったということが分かり(※後の説明のために、意図的にそういう順序にしています)、出発局面の評価値が+500点であるということも分かりました。

ここで、「何で探索なんて行っているんだろう?」「探索なんてせずに静的評価値をそのまま使えばいいじゃないか」という疑問をもたれる方もいるかもしれません。確かに、探索を行っても最終的に使うのは末端局面の静的評価値なわけですから、静的評価値の確からしさが現局面においても末端局面においてもそんなに変わらないとすると、無駄に仮定をおいて現局面から離れていく分だけ、探索は評価値の精度を落としているだけという可能性もあるわけです。もしそうなら、読み切りができる最終盤を除けば、探索をしない方がよいということも考えられます。

実は、ここのところがミニマックス法が「戦略」である所以であり、仮に評価値の精度が向上していないとしても、少なくとも探索の範囲内においてミスをしないことが勝率に結び付くだろうという考え方なのです(※評価値の精度自体は変わらなくても、探索を行えば、探索範囲分の下限保証が付いた値になります)。

ミニマックス法がどういう状況ならば「戦略」として正しいのかというのは非常に難しい問題なのですが、理論の話はさておき、現実のコンピュータ将棋においては探索の深さと勝率には強い正の相関があります。コンピュータ将棋におけるミニマックス法の有効性は実証的に示されていると言えます。

また、ミニマックス法に基づくと、静的評価関数の良し悪しについても一つの指針が立てられます。それは「両者最善で指し手が進んだ時に静的評価値の変動が少ないものが良い」ということです。もし静的評価値の変動が少なければ、末端局面からさらに探索を進めたのと同様の結果をその分の探索をせずに得られることになりますし、また、次回に説明するように、探索自体もより効率的に行えるようになります。

Bonanza式の機械学習においては、教師となる棋譜に基づいて、指し手がなるべく一致するように(かつ過剰に一致しすぎないように)静的評価関数を作成するわけですが、このやり方では、手に入る良質な教師棋譜の数に制限があるために、どうしても限界が出てきてしまいます。そこで、上記の方針を採用すれば、自らの探索結果を教師とすることで、Bonanza式の静的評価関数をさらに強化していく学習が可能になるわけです。この手法を確立したのは、筆者の理解では、NineDayFever(NDF)だと思います。

さて、上の例では深さを固定しているわけですが、これでは持ち時間のある対局には対応できません。ですので、最初は浅い深さで読んで、そこから徐々に深く読んでいくという反復深化の手法が採られます。また、末端局面で王手や駒取り等に手を絞った少量の探索(静止探索と言う)を行ったり、有望そうな局面について探索を延長したりというようなことも行われます。これらの技術についての説明は、ここでは省略します。

また、上の例では、全ての局面を全幅的に探索して答えを出しているのですが、これは明らかに非効率的であり、平均分岐数が約80と言われる将棋においては、このやり方では深く読むことはできません。読む必要のない変化を切り捨てる「枝刈り」と呼ばれる手法が必須になってきます。

次回は、この「枝刈り」について解説します。

このページのトップヘ