コンピュータ将棋に関する基礎的な情報を収集し、分析し、発表する所です。今後の課題(TODO)今後、調べていきたい課題を書いておきます。「こんなことも知りたい」ということがありましたら、コメント欄やツイッターでお知らせください。この研究所は一人で細々とやっているものなので、研究や発表には非常に時間がかかります。Algorithm」(以下、Silver論文)が大きな話題となっています。Zeroを作り上げて、大きな衝撃を与えました。Zeroと同様の手法(以下、AlphaZero)をチェスと将棋に適用し、それぞれ“世界最強”ソフトを作成したということを報告しています。この“世界最強”の部分については、現在、様々な論議がなされているところでありますが、この論文で重要なのは「汎用的な枠組みによって専用系に匹敵する結果が得られた」という点であろうかと思われますので、この部分は論文の重要性には影響しないと思われます(正確性には影響するかもしれません)。今回は、取り急ぎ、Silver論文で個人的に衝撃を受けたことについて書いておきたいと思います。論文を読んで半ば衝動的に書いている記事ですので、いつも以上に“あわてんぼう”な内容を含んでいるかもしれませんが、ご容赦ください。深層学習による評価関数は多層のネットワークで表現されるような大量の計算を伴う関数(少し専門的な書き方では非線形関数)になっています。ここで、関数というのは変数(局面等の情報)を入力すると値(評価値)を返すもののことです。従来の将棋の評価関数も“大量の計算を伴う関数”という点では同じなのですが、こちらは線形和(係数をかけて足し合わせる計算、ネットワークでいうと1層に相当)が基本であり、深層学習によるものは非線形であることが特徴になります。このため、深層学習による評価関数は大量の並列的な計算を行わなければならず、コア数の多い特殊な計算機(GPU)で計算を行うわけですが、それでも従来の評価関数よりも計算に時間がかかります。計算機自体の作りが違うので単純な比較は難しいのですが、例えば、Silver論文の計算機環境では、1秒間に読める局面の数(NPS)はelmoが3500万程度であるのに対し、AlphaZeroは4万程度であり、千倍くらいの違いがあります。NPSが千倍も違うのに強さが互角(※細かいことは置いておいて大雑把に書きます)だというのは驚きの結果であり、深層学習の優秀さを示していると感じられる方が多いかと思われますが、筆者が衝撃を受けたのは実はその点ではありません。elmo等の従来の将棋ソフトはミニマックス探索(アルファベータ探索)を行って、評価値を改善しています。ミニマックス探索については、以下の解説記事をご参照ください。2:アルファベータ枝刈りここで見方を変えて、探索による改善までを含めて“評価関数”だとして再定義すると、実は従来の将棋ソフトの“評価関数”も膨大な計算の非線形関数であったと再解釈することができます。この定義なら、同じような規模の非線形関数として、AlphaZeroの評価関数との比較がしやすくなります。この観点から、Silver論文の結果を見ると(※AlphaZeroの探索部分がelmoの探索の一部と打ち消すようにelmoの“評価関数”の定義を調整したとして)、AlphaZeroの深層学習による評価関数と探索(の一部)を含めて再定義されたelmoの“評価関数”が、ものすごく大雑把に書いて、同程度の計算量で同程度の精度であったと解釈することができると思われます(※詳細には実物で検証しないと何とも言えませんが)。ここで注意しなければならないのは、深層学習のものは将棋専用の設計が行われていない一方で、従来の将棋ソフトのものは将棋専用に作られているという点です。通常、特化/専門化による最適化は改良する方に働くはずであり(そうでなければ最適化として機能していません)、大幅な改良になることもよくあります。このため、もし将棋においてミニマックス探索が十分に有効であるのならば、深層学習による汎用型評価関数はミニマックス探索による改善を含む従来型の“評価関数”には及ばないはずなのですが(※これまで筆者が将棋における深層学習の有効性にやや否定的であったのは、これが理由です)、Silver論文の結果はそうなっていません。Silver論文の結果は、将棋(やチェス)におけるミニマックス探索の有効性に疑問を投げかけるものであると解釈することができると思われます。従来、将棋ソフトにおいて、ミニマックス探索は経験的に優れた手法であると信じられていました。これは、先駆者であるチェスソフトでも同様です。実際に探索を深くしていく(思考時間を増やしていく)とレートが向上するということは、このブログでも紹介してきた通りです。この定説的な知見を見なさなければならないかもしれないというのは、個人的に非常に衝撃的であり、エキサイティングな結果であると感じています。Silver論文の5頁では、ミニマックス探索よりもモンテカルロ木探索(MCTS)が優れているとして、思考時間に対するレートの伸びを比較しています(図2)。これは評価関数の精度やNPSが全く異なるものの比較であり、探索部以外の条件が著しく異なってしまっているため、この主張は論理的に成立しないものと思われます。すると出版される際には消えているかもしれません。論文執筆側からすると、このように少し無理がある主張というのは、はっきりとは言えない(すぐにデータで証明できない)が研究過程での経験的に何らかの確からしい感覚があって主張しておきたいという場合があり、後で結果的に重要になることがあります。研究においては、科学的な正確性と重要性が異なることがあるわけです。ミニマックス探索の有効性について、DeepMindグループの疑問と筆者の私的解釈における疑問がどの程度、重なっているのかは分かりませんが、いずれにしても今後、この問題は大いに議論され、研究されることになるかと思われます。以上、今回は、取り急ぎ、Silver論文で個人的に衝撃を受けたことについて記しました。次回は、簡単な数理模型を使って、ミニマックス探索の有効性について改めて考え直してみたいと思います。lfics81二者で行う勝負事には相性というものがあります。二者間の勝率の期待値は必ずしも両者の実力差のみに依って決まるものではなく、相性にも依存するというわけです。極端な場合には、「AはBに勝ち越し、BはCに勝ち越すが、AはCに負け越す」といったような実力だけでは説明できない“じゃんけん”のような状態が出現することもあります。イロレーティングにおいては、相性という要素は考慮されていません。相性を調べるにはイロレーティングを超えた解析が必要になります。1:棋力ってなんだ?」「2:あなたのレートは......」の解説記事をご参照ください。R(B)\]とは異なっているはずです。B)\]を“相性によるレート補正”と定義しましょう。イロレーティングの立場から見ると、この相性による系統的なずれは系統誤差ということになります。今回は、floodgate棋譜集(2012~2016年版)において、この“相性によるレート補正”の大きさがどの程度であるのかを見積もりたいと思います。勝率の期待値や両者のレートが精確に分かっているのであれば、上の式をそのまま計算することで、補正値を精確に算出することができます。現実のfloodgate棋譜集においては勝率の期待値もレートもそれなりに大きな不確かさを有しており、補正値を精確に求めることはできません(※補正値の不確かさは、各々の不確かさの二乗和の平方根)。そこで、今回、考えるのは、個々の補正値ではなく、補正値の分布のばらつきの大きさです。個々の補正値の不確かさが大きくても、全体の分布のばらつきについてなら、ある程度は精度良く見積もることができます。b)]^{2}\]と書くことができます。ここで、aとbについての和はデータがある全ての組み合わせについての和です。1\]のように規格化されています。重み関数が定数であるならば、Dは標準偏差に該当します。b)を有しているため、不確かさの大きなデータと小さなデータを対等に取り扱うことは合理的ではありません。このような時、(古典的な)統計学では、Dの不確かさUを最小にするように重み関数を決定します(※詳細は記事の最後に付記)。結果的に、不確かさの大きなデータの重みは小さくなり、不確かさの小さなデータの重みは大きくなります。実際に用いるデータは、30手以上の投了決着棋譜に限定し、それぞれの組み合わせにおいて30勝以上かつ30敗以上のデータのみを採用します。計算に使用するレートの数値は最尤法によるものです。具体的には「floodgate棋譜集レートの最尤法との比較一覧(2012~2016年版)」をご覧ください。結果は以下の通りです。レート毎の分類は、各組合せの平均レートで行っています。39.5±4.0結果的に、相性によるレート補正値の分布のばらつきの大きさは大体33程度だということが分かります。レート3000以上に限定すると、やや不確かさは大きいですが、40程度に上昇しています。b)に依存してしまいます。これはあまり性質がよくないので、重み関数が補正値に依存しないように、重み関数内の補正値の二乗をDの二乗で置き換えるという方法も考えられます(※詳細は記事の最後に追記)。そのように重み関数を定数化した時の結果は以下の通りです。50.6±4.4この方法においては、補正値の大きなずれに対する抑制がかからないため、ばらつきの大きさが大きめに出る傾向があり、全体でも50弱の数値になっています。不確かさを最小にした場合に比べて、当然ですが、不確かさも大きくなっています。この2つの方法は、それぞれ別の量を測っていますので、どちらが正しいというわけではありません。ものすごく大雑把に捉えると、方法に依りますが、レート補正値の分布のばらつきの大きさは大体30~50程度であるということは言えるでしょう。以上、今回は、floodgate棋譜集(2012~2016年版)における“相性によるレート補正”の分布のばらつきの大きさを統計学的に見積もりました。結果として、方法に依りますが、大体30~50程度という数値が得られました。仮に分布が正規分布であるとするならば、ばらつきの大きさの2倍であるレート60~100以上の相性差となる相手は22人に1人となり、3倍のレート90~150以上の相性差となる相手は370人に1人となります。この結果は、あくまでもfloodgateの参加者に限定されたものであり、また、floodgate棋譜集のレート推定における理論誤差を含んだものであるという点には注意が必要です。b)の確率分布に従う確率的な量であると考えることができます。以下の計算では、この確率分布を正規分布であると仮定します(※元々、補正値は3つの量の和/差であるため、中心極限定理を鑑みると、この仮定はそんなには悪くはないはずです)。b)は補正値の確率変数を表し、アングルブラケットは期待値を表しています(※確率分布の重みを付けての積分)。b)]^{2}\]となっています。V(4)}}\]も得られます。]}\]を導入しました。]}\]と書くことができます。\frac{v(2)}{v(0)}\]をDについて解くことで求めることができます。適当な最尤法を用いると、大体はこの方法に近くなります。最新コメント「最新トラックバック」は提供を終了しました。