最善合議は最尤法によって与えられます。b(j)を真の最善手だと仮定した時に現在の状況になる確率P(j)が最も大きくなるb(j)を選択すればよいわけです。s(i)]\]の部分のみを比較すれば十分です。結果的に、合議は候補手の数nには依存しません。s]\]となる関数です。誤差関数erf(x)は、C++ならcmathをincludeすれば、そのまま使えますが、あまり速くはないようです。実際、筆者が適当に作った関数でも(g++で)5倍程度の速さが出ます。実際に模型の計算を超えて、現実に適用しようとすると、dとs(i)は調整変数として最適化する必要があります。V(i)\]として合議を行えば、結果に大きな違いは出ないようです。d\]の場合の最善手率を示します。棋力差も相関もない理想的な状況です。Aの予測に上の近似式を用いた予測最善合議の結果(青十字点)は最善合議の結果(黒点)とほぼ一致します。台数が多くなっても、最善合議が楽観合議(赤点)を大きく上回ることが分かります。2:調査手法」では、統計解析のためのデータを取得する方法を紹介しました。Ratings)を算出する方法を紹介します。ここで、「Intrinsic」を「固有」としたのは筆者の翻訳によるものであり、別の翻訳をされている方もいるようです。物理学では「Intrinsic」を「固有」と訳すことが多いため、反射的に「固有」としてしまいましたが、「内在」等の方が相応しいかもしれません。いずれにしても「潜在的に備わっている固有の」というような意味です。function)でよく目にするかもしれません。固有レーティングの前に、通常の“レーティング”について説明します。ここでの“レーティング”というのは、イロレーティングのことを意味しており、集団内での多数の勝敗の結果から、その集団内における相対的な棋力を推定した指標のことです。将棋倶楽部24のレートのことだと言うと、分かりやすいかもしれません。詳細は以下の記事で解説しています。2:あなたのレートは......ここで重要なのは、通常のレーティングは「勝敗の結果」のみで決まるという点です。「勝った者が強い」というわけですが、この理論は単純で頑強である一方で、それ故の弱点も有しています。通常のレーティングでは集団内の相対差しか推定することができず、時代や集団に依らない絶対的な棋力を推定することができません。棋譜の内容を一切見ていないため、本来の情報よりも遥かに少ない情報で棋力を判断することになってしまいます。極端な場合を除いては、不正解析に応用することもできません。素朴な直観としては、勝敗の結果よりも棋譜の内容の方が棋力についての豊潤な情報を含んでいるように感じられます。その直感をソフトと統計を用いて数値化しようという試みが固有レーティングです。固有レーティングにおいては、勝敗は考慮せず、棋譜の内容だけを見て、棋力を推定します。棋譜の情報を使うため、勝敗だけの情報よりも繊細な解析が可能であり、時代や集団に依らない絶対的な棋力が推定できたり、不正解析に応用できたり、トレーニングや棋譜解析に活用できたりという利点があります。一方で、ソフトに依存した手法であるため、ソフト自身の棋力を推定することができなかったり、ソフトが対象者に比べて十分に強くないと信用しづらかったりというような弱点もあります。具体的に、固有レーティングを算出する際に用いるのは、各局面におけるMLM(マルチPV)で算出された全ての合法手の評価値(実際には50手程度で十分)と実際の指し手のデータです。探索は十分な深さ(Regan教授らの論文では13)で固定して行います。評価値の符号は手番から見たものとして、例えば、先手番で+なら先手有利、後手番で+なら後手有利にして、常に最善手の評価値が最大になるようにします。i)と書くことにしましょう。データの解析は以下の2段階に分けられます。棋力を直接的に反映していると思われる統計量とイロレーティングとの相関関係を調べる。それらの統計量をモデルに基づいて推定する。第1段階は、言い換えると、勝敗に依らない「棋力」の再定義と言えます。再定義すること自体は自由なわけですが、新しく定義された「棋力」がイロレーティング(勝率)と強く相関していないと、指標として役に立ちません。「棋力」を表す統計量とイロレーティングとの相関関係を実際のデータに基づいて精査し、また、相互変換の関係式を推定しておく必要があります。この「棋力」を表す統計量から換算されるイロレーティングの推定値が固有レーティングです。具体的に、Regan教授らの論文では、「棋力」を表す統計量として、最善手との一致率と平均誤差が提案され、最終的には平均誤差が採用されています。j)の1手あたりの平均値のことです。u]}\]という関数が使われています(※後者の論文には違う式が載っていますが、前後の記述から、誤植だと思われます)。ここで、uは評価値の単位ですが、本来はきちんと調整した方がよいという注釈付きで、論文では歩兵単位(1歩兵=1ポイント)が使われています(※論文には歩兵の百分の一という記述もあるのですが、表の数字等を見る限り、センチ歩兵単位ではないと思われます)。この関数は、形勢が傾いた局面では人間は指し手の評価値の誤差に対して“鈍感”になるという傾向を反映しています。2:線形回帰と最小二乗法」)。使用する局面データは、定跡部分(論文では16手=先後8手ずつ)と大差の局面(論文では3歩兵以上)を除いた全ての局面です。この式だと、誤差がない場合のレートは3571となるはずですが、チェスの世界王者クラスが2700程度であることを考えると、妥当な数字だと考えられているようです。次に第2段階として、平均誤差の値を推定します。生の実測値をそのまま使えばいい」と感じられる方もいるかと思います。自然科学分野の人であれば、「どんな理論よりも観測値が正しい」ということが身に染みついていますので、そのような感覚が普通でしょう。実際に、実測値を用いても悪いということはありません。データが十分に多ければ、実測値も推定値も数値として大きな差はありませんので、どちらでも結果は大して変わりません。上記の手法を将棋に応用した山下宏氏の論文「将棋名人のレーティングと棋譜分析」では、実測値を用いて線形回帰を行っています(※この論文では、誤差は単純な差で定義されており、また、MLMではなくSLMのデータを用いているために誤差が必ずしも正にならず、負の誤差の平均を「平均好手」、正の誤差の平均を「平均悪手」と区別しています)。データの量が有限である情報科学においては、敢えて実測値を用いずに、モデルを仮定した推定値を用いることで様々な利点が生じます(※物理学で理論値を観測値で繰り込むのと逆方向の繰り込みに対応します)。実際、もしモデルが妥当であるのならば、推定値の方が実測値よりも多くの情報を反映していますので、データが少量の場合にも対応でき、また、データの雑音に対して頑強になります。モデルを活用することで、不正解析などの様々な応用も可能になります。これらのことは「モデルが妥当である」という前提に基づくものであることに注意してください(※この前提を受け入れられるかどうかは、主観確率論を認めるかどうかに近いと思われます:「役には立つが、信用はできない?」)。具体的には、以下のようにモデルを定めます。各々の指し手が独立した確率事象であるとし(相関は無視)、その先験的な実現確率が評価値のみに依存すると仮定する。i)の関数であるとして、関数モデルを設定する。関数モデル内の調整変数を実際のデータに基づいて推定する。i)\]と推定できます。0)は、もし1に近ければ、“この一手”という単純な局面に対応し、もし低ければ、他に有力な候補手がある複雑な局面に対応します。実現確率を帰無仮説に用いて、実際の指し手を統計的に検定することで、不正解析に応用することもできます。平均誤差が実現確率に依存していることから分かるように、実現確率は棋力や棋風に依存します。このため、推定に用いるデータは棋力や棋風を統一したものである必要があります。Regan教授らの論文では、棋風は特に考慮せず、イロレーティングで区分けされた棋譜データを用いています。s)^{c}}\]という関数モデルを用いています(※後者の論文では左辺の違った式が書かれていますが、誤植だと思われます)。sは評価値のスケールを決める逆感度変数であり、棋力が高い程、小さくなり、評価値の変化に対して敏感になります(※論文ではsを感度変数としていますが、意味としては逆なので、ここでは逆感度変数としました)。cは関数の形状を決める整合変数であり、棋力が高い程、大きくなり、最善手付近の手を整合的に選ぶようになります。右辺の関数の形は、連続した単調減少関数であればよいので、上記の逆指数関数の他に、逆多項式関数やロジスティック関数等も考えられますが、どれでやっても結果はさほど変わらないようです。ちなみに、上記のような関数モデルを用いると、実現確率が分かっている場合には、逆に解いて、評価値の方を求めることもできます。激指の場合には、ロジスティック回帰を用いて、実現確率を最大化するように機械学習を行っています(最尤法)。この手法は、一見すると評価値の差を用いて学習するボナンザ系統の機械学習とは全く別のものであるように思われますが、実現確率と評価値との間の関数モデルを適切に設定すると、両者は同等(もしくは類似)のものに帰着されます。残りの作業は、sとcの2つの変数を推定するだけですが、Regan教授らはこれに意外と苦戦しています。通常的な最小二乗法や最尤法では中々上手くいかないらしく(※この時点でモデルやデータの信頼性に疑問符をつける方も多いかと思われますが)、パーセンタイルを用いた特殊な推定法を用いています。詳細は省きますが、結果的に良好な結果が得られたようです(※ただし、モデルが信用できるかは別の話です)。以上、Regan教授らの論文に基づいて、固有チェスレーティングについて、簡単に解説しました。この考え方は、将棋にも直に応用可能なものであり、また、棋譜データを解析する上での基本知識になるかと思われます。モデルの信用性については様々な異論もあるかと思われますが、その辺の検証も含めて、“将棋メトリクス”の今後の重要な課題であると言えるでしょう。lfics81もう今年(2016年)も12月ですが、大晦日には電王戦合議制マッチが行われます。第3回将棋電王トーナメント(2015年)版のPonanza、nozomi、大樹の枝(多数決合議)と森下卓九段率いる3名の棋士が合議制マッチで対局するという企画です。合議によって棋士側がどれくらいの力を発揮するのかが最大の注目点ですが、多数決合議によってコンピュータ側の棋力(レート)がどうなるのかも気になるところです。単純に考えれば、上位(Ponanza)と下位(nozomi、大樹の枝)とでレート差の離れた組み合わせですので、中間のレートになりそうな気もしますが、実際には検証してみないと何とも言えません(※記事の最後に付記)。運営が実機で技巧辺りと100局くらいテスト対局してくれれば、それなりに推定できますが、手間がかかることですので、期待はできないでしょう。一方で、棋士側は、単純な多数決ではなく、話し合って指し手を決定します。大きく揉めない限りは、合議の効果が期待できそうです。視点を変えると、今回の合議制マッチは“直接民主制と熟議民主制の対決である”という見方もできるかもしれません。将棋における合議制には様々な先例があります。その中で個人的に最も印象に残っているのは、2013年6月22日のニコニコ超将棋会議で行われた投票将棋です。この対局は、西尾明六段に対して、ニコニコ生放送の視聴者が合議制で挑むというものであり、筆者も一視聴者として参加していました(足を引っ張っていただけですが)。生放送を利用した合議システムやフィッシャークロックルールの採用等、時代に先駆けた要素の多い企画であり、とても楽しいものでした。西尾六段の真剣な対局姿勢が深く印象に残っています。棋譜も観戦記の最後に載っています。対局内容も面白い将棋であり、(寄与は小さいですが)筆者自身が参加した対局だということもあって、新しいソフトを導入する際の検討テスト用の題材の一つとして使っています。前に激指14を購入した際にも同棋譜で検討を行い、先日、浮かむ瀬を導入した際にも検討を行いました。結果として、激指14と浮かむ瀬(並びに技巧20160606版)で大きく見解が分かれる局面が現れたので、今回は、コンピュータ将棋の“進化”を身近に感じた実例として、その話を書きたいと思います。課題局面は74手目△5三同飛の局面(下図)です。以下、評価値は末端で10億局面以上は読ませたものであり、符号は先手から見たもの(先手有利で+、後手有利で-)です。明六段ここで、先手▲3三角成は△同金で後手勝勢になります(以下、▲2二飛成△3一金▲4五桂△2二金▲5三桂成△3二玉で浮かむ瀬-2654、技巧-1875)が、先手には▲3五角という秘策があり、この手があるために、先手側はこの局面に誘導しようという作戦でした。この▲3五角が成立しているかどうかが、ここでの検討課題です。実戦では△5二飛と進み、ここで▲5三角成と角の押し売りをすれば、先手が分かりやすく勝勢だったというのが感想戦での結論でした(以下、△同飛▲2二飛成△5七桂▲同銀引△3二金▲1一龍△3一金▲3二金△5二玉▲3一龍△5七歩成▲同銀で浮かむ瀬+2550、技巧+2269)。実戦では▲5三角成とは踏み込めず、▲5三歩△8二飛▲5五銀△2六歩▲同飛△2五歩▲2三歩△3五歩と進みましたが、これも悪い進行ではなく、先手が優勢であるようです(以下、▲5二銀△3一玉▲2二歩成△同玉▲2三歩打△同玉▲2四歩打△同玉▲4三銀△2二桂▲1六飛△5七歩成▲1五金△2三玉▲5七銀△4五角▲2四金打△1二玉▲3三金△7八角成▲5九玉△5八歩で浮かむ瀬+2653、技巧+2061)。▲5五銀は、中央の銀を払って、同時にずっと懸案だった6六桂打を防いだ味のいい手であり、素人ながらに「これは行けるんじゃないか」と感じたことを覚えています。△3五歩に対して▲5二銀ではなく、▲2二歩成と行ったのが悪手だったようで、ここから一気に形勢が逆転して(以下、△同飛で浮かむ瀬-1331、技巧-1254)、後手の西尾六段の勝ちとなりました。なった局面は詰めろなので飛車を取ることができません。この局面の評価が難しく、激指14と浮かむ瀬等とで評価が分かれます。激指14の場合は、読みが浅い内は先手よりの互角を示し(PRO+で+273)、深く読ませても少し後手寄りになるものの互角の評価です(PRO+7で-83)。このため、過去に解析を行った際には、対応によっては難しくなるが、▲3五角は十分に成立している手であるという結論でした。浮かむ瀬や技巧で検討を行うと、激指14では成立していると考えられていた手順が否定され、深く読んでいくと、後手優勢の評価となります(浮かむ瀬は1421億局面35/72で-1232、技巧は1074億局面37/68で-738)。2六角で、浮かむ瀬-1363、技巧-1323となり、▲同銀なら、以下、△3五歩▲2二飛成△3一金▲6二龍△4五角▲7九歩△4四銀で、浮かむ瀬-1386、技巧-864となります。その他にも様々な変化が考えられますが(記事の最後に大まかな分岐図を付記します)、詳細に調べていくと、後手が大きく優勢になるものが多く、▲3五角は厳密には成立していなかったのではないかというのが、浮かむ瀬や技巧での検討結果です。筆者の目線から見れば、激指14も十分に強いソフトであり、浮かむ瀬や技巧がさらに強いと言っても、その差を実感することは余りないのではないかと以前は考えていました。実際に使って比較してみると、今回の検討のように、コンピュータ将棋の“進化”を体感することが意外とあることが分かってきました。言って、激指14が不要になったということではなく、普段の練習対局は棋力の微調整ができる激指を使っています。超将棋会議は、プロに近いレベルから筆者のような素人レベルまで、様々な棋力を持つ人々が熟議して、合意形成を行い、多数決で指し手を決めるという正に熟議民主制の雛型のようなシステムで行われました。棋力の低い人でも票数のバランスを取ることで“多数決の横暴”を防ぐことに貢献したり、票を取りまとめる中で様々なアイデアが出て検討が深まっていったりという良い面も見られた一方で、▲5三角成に踏み切れなかった一貫性の欠如や劣勢になって崩れた時の脆さ等、悪い面も見ることができました。大晦日の合議制マッチは、棋力が均質的に高い少数の棋士による合議ですので、ニコニコ超将棋会議とは全く違ったものになるかと思われます。将棋の内容のみならず、“合議”の進行がどうなるのかにも注目です。-------------------付記:多数決合議と楽観合議レート差の近いソフトの多数決合議については、伊藤毅志先生の研究があり(「コンピュータ将棋の進歩6」参照)、Bonanza、YSS、GPS将棋(当時のレート差150以内)の多数決合議によって有意に強くなることが示されています。多数決合議で強くなる機構は以下の簡単なモデルで示せます。ある局面における合法手が最善手(正確には参加ソフトよりも十分に強いソフトの最善手)とそれ以外の手に分類できるとしましょう。p_{3}\]とします。多数決合議による指し手は、2者以上の一致/バラけた場合には最強者の選択で決まります。p_{1}\]となった時に、多数決合議は最強者よりも強くなることが期待できます。a\]と書くことができ、aは正の値で、レートが高いほど大きくなる値だと考えられます。1})\]だと考えることができます。\frac{a}{2}\]となります。最強者とのレート差が小さければ、多数決合議は機能し、大きければ、機能しないということが分かるわけです。伊藤先生の研究では、レート差150以内の3者で上手く行ったわけですが、今回はそれ以上のレート差であること、また各ソフトのレートが当時よりも遥かに上がっていることから、実際にどうなるのかは未知数だと言えます。多数決合議は評価値の数値は参考にしておらず、「最善手」との一致率の向上を目指していました。一方で、評価値の情報を活かして、評価値の期待値を最大化するという方針の合議もあります。こちらの方が、ミニマックス法と相性がよく、実際に伊藤先生の研究等でも、多数決合議よりも良い結果を示しています。簡単なのは、類似ソフトの合議において最も評価値の高い指し手を選ぶという楽観合議です。評価が分かれた時、各ソフトの評価が対等であれば、最も評価値の高い指し手を選ぶことで、評価値の期待値を向上させることができます。評価値の低い指し手を選ぶ悲観合議だと、逆の結果となり、勝率も下がるようです。合議するソフトの性質が異なる場合には、評価値の規格化を揃えたり、期待値を計算する際のソフト毎の信頼性の重みを調整したり、次善手(他のソフトの最善手)の評価値の予測を調整したりすることが必要になるかと思われますが、伊藤先生の研究等では単純な楽観合議でも“経験的”に上手く行くようです(政治への応用はどうでしょう?)。ここで注意が必要なのは、これらの合議の比較対象が1台であり、多数台対1台の不平等な比較になってしまっているという点です。本来は同じ台数同士で比較する必要があります。多数台同士の比較をする場合には、各マシン間の情報のやり取りがどれくらい密/疎であるかが重要になります。メモリを共有しているような密な結合であれば、合議するよりも1つに力を結集する方が明確に強くなります。メモリを共有しておらず、マシン同士が離れた場所にある疎結合の場合でも、クラスタ化した方が強くなるようです(政治制度に例えると、軍隊/官僚化?)。システムの頑強性や作りやすさを勘案すると、合議制にも使い道はあり、実際に近年でも世界コンピュータ将棋選手権でPonanazaが活用しています。(追記:2016年12月25日)※「合議の効能:三人寄れば......」の記事でさらに詳細に考察しています。楽観合議については別の考え方を記しました。最新コメント「最新トラックバック」は提供を終了しました。