コンピュータ将棋に関する基礎的な情報を収集し、分析し、発表する所です。lfics81通常、対局結果は時系列のデータリストとして記録されます。「いついつにAがBに勝った」というようなデータが逐次的に記録されていくわけです(※大会等では「第1回戦の記録」というような同時刻扱いのデータも出てきます)。この対局結果のデータリストから棋力を推測しようというのがイロレーティングの理論でした。イロレーティングについては以下の記事をご参照ください。2:あなたのレートは......イロレーティングの散歩道イロレーティングでは、逐次的に勝者のレートを上げ、敗者のレートを下げることで均衡点を探すということをします。対局数が少ない時にはレートを適切に測ることはできませんが、対局数が多ければ、レートは均衡点の周りを一定の標準偏差で揺れ動くことになります。この手法は簡単でありながら、時系列のデータにも自然に対応しており、棋力のなだらかな変化も均衡点の推移として反映することができるという優れた手法です。その一方で、均衡点をどのように見積もればいいのかが明確ではないこと、均衡点の見積もりに多数のデータが必要であり、また不確かさの評価が明確ではないこと、レート上限/下限の境界付近において偏りが発生すること等の問題点もあります。ベイズ統計を用いると、いくつかの仮定の下で、もう少し洗練された手法に改良することができますが、同時に、仕組みが複雑になってしまいます。この手法の洗練さ(信頼性とはまた別)と簡単さとのトレードオフは悩ましいところです。結局のところ、データの量が限られている以上は小手先で対処できることは限られており、よほど有力な仮説がなければ、データ量を増やす(つまり対局数を増やしたり、勝敗以外の棋譜データを活用したりする)のが一番ということになります。これらの問題は、全て時系列データの逐次処理に由来するものです。記録されている一定期間の対局結果を“時系列を無視して”処理する場合には、古典的な統計手法が有効になります(静的レーティングシステムという)。その一つが最尤法です。今回は、この手法について技術的に解説したいと思います。最初に、歴史的な背景と用語について少し触れておきます。今回の最尤法を用いたレート推定の方法は、Bradley-Terry模型(1952)が最初だと言われています。Bradley-Terry模型の勝率式は、書き換えると、イロレーティングの勝率仮定に一致します。「イロレーティング」という用語は厳密には時系列データを逐次的に処理する手順を含めた総括的なものであり、静的レーティングシステムにおける最尤法による推定模型は「Bradley-Terry模型」というのが正確です。この用語は専門的であり、一般には通じない可能性が極めて高いため、「イロレーティングを最尤法で」と言っても問題ないかと思います(専門家に怒られないという保証はありませんが)。最尤法はベイズ統計で定式化することもできるため、ベイズ統計による静的レーティング(静的ベイジアンELO)であると主張する人もいます。静的レーティングシステムにおいては、“時系列を無視する”ため、その期間内の全ての対局者のレートが一定であると仮定されており、その全てのレートを同時に推定することになります。これは期間内に大きくレートが変わった者がいる場合には誤差が発生するということを意味しており、特にfloodgateで中身が変わったという場合には注意が必要です(※このような仮定に由来する系統誤差は後述の不確かさの見積もりでは評価不能)。推定時にレート変更の情報があれば、対局者名を変更したり、外れデータとして弾いたりすることもできますが、実際には情報がないことがほとんどであり、対処は困難です。原理的にレートは相対値であるため、誰かを基準者としてレートの数値を固定し、そこからの相対値を推定します。平均を基準値にしたい場合には、最初に基準者を決めてレートを推定してから、最後に平均が基準値になる様に全体の値をシフトします。基準者は、なるべく中間的な実力で多数の対局者と多く対局している者が向いています。イロレーティングと同様に、最尤法においてもレートが求まらない対局者が発生することがあります。具体的には、「基準者と対局している者、また、その者と対局している者、また、その者と対局している者、......」という関係集団に含まれていない者、また、関係集団内でも集団内で全勝/全敗の者のレートは算出することができません。推定時には、事前にレート算出が可能であるかを確認して、算出可能者のみの対局に絞って計算する必要があります。ここでは時系列は考えないため、対局結果は「A対B:何勝何敗」という対局組み合わせ毎のデータリストにまとめることができます。ここでは簡単のために引き分けは考えません。引き分けは、取り除くか、0.5勝0.5敗に換算するかというような事前処理が行われているものとします。最尤法の原理は「データを再現する確率(尤もらしさ)が最大になるように変数(レート)を決める」ということです。ここで、確率を計算する際に仮定/模型が必要になります。仮定/模型の妥当性は、この手法の範囲内では分かりません(※データ量が多い場合には、無作為に選んだ一部のデータを推定に使わずに取っておき、推定結果とそのデータとの整合性から“予言性”を確かめるといった程度の確認なら可能です)。j)}\]のように与えられます。j)はiの負け数、R(i)はiのレートを表しています。j)」のように)、補正項のレート変数も含めて、同時に推定するようなこともできますが、変数を増やした分だけ、必要なデータの量も増えますので、豊潤にデータがない限りはお勧めできません。この確率Pは非常に小さな値になってしまうため、直接的に取り扱わずに自然対数にして取り扱います。\right]\]を最大化すればよいわけです。\right]\]がkに依らずに全て0となります。j)\]を使いました。多変数関数の最大化は、最急降下法や共役勾配法等で、簡単に数値計算することができます。解くよりも、最大化の方が簡単です。元の関数の符号を反転させれば、最大化は最小化になりますので、最大化と最小化は同じ問題になります。多変数関数の最小化は、拘束条件(ラグランジュ法による正則化)を除けば、ボナンザ式の機械学習と同じですので、結局、最尤法は機械学習と同じことをやればいいということになります。計算の際に必要な初期値は、基準者等に対する勝率から適当に与えれば、よほど変なデータでない限りは上手くいきます。j)の割合)は確率的にばらつきます。対局結果が異なれば、当然、最尤法によるレートの推定値も変わってきます。本来はレートの推定値というのは確率的にばらつくものであり、1つの推定値はサイコロを振って偶々出た値の1つに過ぎないと言えます。このような場合、ばらつきの大きさ(不確かさ)を評価して、誤差の目安とします。ばらつきの標準偏差は「標準不確かさ」と呼ばれ、推定値に付記されることが多いものです(※)。近年の測定論では、推定値(最確値)と標準不確かさを一揃えにして測定値として定義します。系統誤差が無視できる(と仮定する)場合には「標準不確かさ」は「標準誤差」と一致します。仮に、レートの真値が存在し、また、イロレーティングの勝率仮定が正しいとするならば、対局結果をシミュレートすることで、標準不確かさを見積もることができます。「レートの真値」は分からないものであるため、推定値に近い(誤差が小さい)と仮定して、真値の代わりに推定値で代用します。これは理論的には誤差の高次の項を無視することに対応しています。最尤法における標準不確かさの評価方法には、計算時に追加する仮定に応じて、いくつかの種類があります(ヘッセ行列の逆行列を用いた方法など)。一般的に、仮定を増やすほど、また、専門的な手法であるほど、計算量が少なくて済みます。今回の目的においては計算量はあまり重要ではないと思われますので、ここでは、最も仮定が少なく、最も汎用的な(最尤法以外でも使える)手法である「(不確かさ評価における)モンテカルロ法」を紹介します。この手法は、精密測定の分野でも最近よく用いられているものです(模型の造りは異なりますが)。方法は簡単であり、「レートの真値を推定値で近似して、疑似乱数を用いて対局をシミュレートし、その結果から対応する(平行世界の)推定値を計算することで推定値のばらつきを統計的に評価する」というだけです(つまり“力業”)。大体100~1000回くらい実行すれば、標準不確かさを大よそ見積もることができます。この方法では、単純計算では推定値の見積もりの100~1000倍の計算量が必要になりますが、実際には、初期値に推定値を与えれば大抵は収束が速いこと、推定値の計算時よりも最大化計算の許容精度をかなり大きく取ってよいこと、並列化が容易であること等から、そこまでの時間はかかりません。計算上の注意点としては、標準不確かさを評価する際に、元の推定値からの標準偏差ではなく、平均からの標準偏差を見積もるということがあります。一般的に、最尤法の推定値は、分布が偏っている可能性がある(不偏とは限らない)ため、平均とは一致しません。イロレーティングの場合には、レートの上限/下限の境界付近で偏りが生じやすくなっています。この偏りを考慮すると、この計算で知りたいのは不確かさ(ばらつきの大きさ)ですので、平均からの標準偏差を見積もる方が適切であるということになります。以上、今回は、最尤法を用いてレートの推定値と標準不確かさを見積もる方法を解説しました。時系列や逐次処理に拘らなければ、最尤法のような枯れた古典手法が有効になります。目の前の問題の前提を少し変えることで古典手法に落とし込むというのは、レート推定に限らす、一般的に有力な技法です。改」では、floodgate棋譜集における投了手数の詳細を解析し、平均手数(読みの類似度)とレートとの関係を論じました。ここでは、さらに詳細に対局者毎に関係を整理してみたいと思います。具体的には、floodgate棋譜集(2012~2016年版)から30手以上230手以下の投了決着棋譜に限定し、さらにレート差200以内で勝ち数と負け数が共に50以上ある対局者の組み合わせを選出しました。floodgate棋譜集については以下をご参照ください。M}{M}\]と定義します。130\]としています。平均手数Tは、勝ち棋譜と負け棋譜で別々に算出して、その算術平均を取ることで勝率補正を行っています(参照:「floodgateにおける手数とレート差:棋士との違いは?」)。この定義では、Yの値が正で大きい程、読みが類似しているということになり、負の値になると平均よりも読みが異なっているということになります。\]程度と見積もれます。100局なら0.023程度で、1000局なら0.007程度です。平均手数は投了設定に依存するため、読みの類似度としては投了設定が系統誤差を生むことがあり、注意が必要になります。該当する対局者の組み合わせ毎に、対局者の平均レートと読みの類似度Yとの関係を表示したのが下図です。棋譜集の年毎に点の色を変えています。オレンジ色の線と点は、それぞれレート500刻み区間の平均値を表しています。改」の記事の結果と同様の構造を示していることが分かります。詳細な対局者リストを記事の最後に付記します。リストを眺めると、2013年版の「amatyan」と「Titanda_L」の組み合わせは突出して類似度が高く、同じソフトを動かしていたのではないかと推測されます。その他の類似度の高い組み合わせは、名前を見る限り、別のソフト同士の組み合わせが多く、平均手数が長いからと言って必ずしも同一ソフトとは認定できないことが分かります。一方で、類似度の低い組み合わせを見ると、名前から同じソフトだと思われる組み合わせはほとんど見つからず、平均手数が短い場合には同一ソフトではないだろうということは言えるかもしれません。所々に解釈が難しい結果があります。(277)」は名前からしてgps同士の対局ですが、類似度は-0.072とやや低くなっています。対局数も多いので偶然とも考えづらく、「gps_」は従来のgpsとは異なる動作をしていたのではないかと考えられます。勝敗毎に類似度の内訳を見てみると、「gps_」が負けた時に-0.116と非常に低い値になっているため(※レート上位者が負ける時は本来は手数が伸びる傾向がある)、「gps_」の投了設定が低くなっていたか、予想外の進行で負けるような何かがプログラムにあったのだと思われます。(229)」は+0.058と正の類似度になっており、もしどちらも「gps_l」とBonanza6.0との対局だとすると、整合的ではありません。これも勝敗毎の内訳を見てみると、Bonanza6.0側が勝った場合には大きな差はなく、負けた場合にのみ平均40手程度の大きな差がついています。すると「bona6.0_norm」「bonanza6.0」の投了設定が非常に低く設定されていたのかもしれません。348)」は同じソフト同士の対局だと思われますが、類似度は+0.003と高くありません。こちらは勝敗毎の内訳を見ても不自然なところはないため、BlunderXX自体の自己対局における平均手数が短いか、両者共に投了設定を低くしていたかのどちらかだと思われます。この辺は、平均手数しか見ていないことの限界でしょう。以上、今回は、floodgate棋譜集(2012~2016年版)から、平均手数(読みの類似度)とレートとの関係を対局者毎に整理しました。結果として、投了設定等の系統誤差により機能していないと思われるデータも散見されるものの、全体的には平均手数から読みの類似度が推測できることが確認できました。lfics81ブログ開始時に最初に立ち上げた本シリーズですが、思いの外、長期連載になってしまいました。手数という簡単な情報も、調べていくと様々な将棋の性質と関係していることが分かり、話が拡がると同時に、少しずつ理解が深まってきた感じがします。2:棋士の投了手数」では、棋士棋譜集の手数分布について整理しました。外れデータや規格化について、注意深く議論を行いました。3:棋士の未投了率における長手数テールと冪乗則」では、棋士棋譜集の手数分布の長手数部分に冪乗則が現れることを示しました。この原因は未だに謎です。256手ルールだと長手数部分は消えてしまうため、コンピュータ将棋での検証も容易ではないと思われます。4:floodgateにおける投了手数」では、floodgate棋譜集の手数分布を整理して、棋士棋譜集との平均手数の違いを明らかにしました。floodgateの平均手数は今後も大きく変わりそうです。5:自己対局における投了手数」では、BonanzaとAperyの自己対局棋譜における平均手数を解析し、自己対局においては平均手数が大幅に上昇することを示しました。同時に、思考時間の増加により、平均手数が伸びるという傾向も示しました。6:様々な連続対局における投了手数」では、BonanzaとAperyの様々な連続対局における平均手数を解析し、平均手数が読みの類似性を反映していることを明らかにしました。改」では、改めてfloodgate棋譜集の平均手数の詳細を再解析し、平均手数とレートとの間の詳細な関係構造を明らかにしました。手数については、まだまだ他に論点もあるでしょうし、また、本シリーズから派生したコラム記事も多数ありますが、区切りもいいところですので、本シリーズは一旦ここで締めたいと思います。当初予定していた投了条件の評価値閾値の話は、評価値と勝率との関係から議論した方がよいと思い直しましたので、改めて別のところで論じたいと思います。最新コメント「最新トラックバック」は提供を終了しました。