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

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

コラム記事

  1. 将棋倶楽部24におけるponanzaの69連勝をどう見るか
  2. 将棋のルールは完璧か?:「最後の審判」が提起したこと
  3. 棋士の粘りと棋力:強い人は粘らせない?
  4. 棋士の手数とレート差:平均手数から棋力が分かる?
  5. “将棋の神様”ってなんだろう? 1:本居宣長と小林秀雄 2:完全解析と予知
  6. floodgateにおける手数とレート差:棋士との違いは?
  7. 手数分布はガンマ分布で近似できるか?
  8. 手数と進行度:あと何手?
  9. 一局面の合法手の最大数が593手であることの証明
  10. フィッシャークロックルールについて:規則に優劣はあるか?
  11. 将棋の消費カロリーは何ワット?
  12. 将棋の局面数 1:局面数は無量大数 2:分岐の迷宮
  13. 将棋の棋譜数:“10の220乗”説の真相!?
  14. 序盤の局面数:駒組みは宇宙の星々より多い?
  15. アルファベータ法の筆算:これであなたもコンピュータ!?
  16. 水平線効果は何が問題なのか?
  17. スイス式競技会:WCSC一次予選を例として
  18. 羽生名人が第2期電王戦に出場する確率は?
  19. 人間の値打ち 1:不正判定における許容リスク 2:統計的判定基準
  20. チェスの不正解析 1:Regan教授曰く 2:調査手法 3:固有レーティングとは?
  21. ニコニコ超将棋会議3五角は成立していたか?:合議と熟議
  22. 合議の効能:三人寄れば……
  23. 将棋は酔歩ではない?:酔歩模型と手数分布
  24. 評価値という数値 1:一歩百点? 2:勝率と酔歩模型
  25. 平均手数で分かる読みの類似度:floodgate棋譜集の分析
  26. 先手と後手:どちらが有利?
  27. ソフトの相性:ふたりの距離の統計的概算
  28. ミニマックス法の有効性 1:Silver論文の私的解釈

今後の課題(TODO)

今後、調べていきたい課題を書いておきます。もし「こんなことも知りたい」ということがありましたら、コメント欄やツイッターでお知らせください。ただし、この研究所は一人で細々とやっているものなので、研究や発表には非常に時間がかかります。

  • 棋風について
  • コンピュータ将棋のモデル化について
  • 戦法・戦型の分類方法について

2017年12月5日に投稿されたGoogle DeepMind社のグループによるプレプリント論文「Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm」(以下、Silver論文)が大きな話題となっています。DeepMind社は、以前、深層学習と強化学習により、囲碁の専門知識を使わずに最強の囲碁ソフトAlphaGo Zeroを作り上げて、大きな衝撃を与えました。今回の論文では、AlphaGo Zeroと同様の手法(以下、AlphaZero)をチェスと将棋に適用し、それぞれ“世界最強”ソフトを作成したということを報告しています。この“世界最強”の部分については、現在、様々な論議がなされているところでありますが、この論文で重要なのは「汎用的な枠組みによって専用系に匹敵する結果が得られた」という点であろうかと思われますので、この部分は論文の重要性には影響しないと思われます(正確性には影響するかもしれません)。

今回は、取り急ぎ、Silver論文で個人的に衝撃を受けたことについて書いておきたいと思います。論文を読んで半ば衝動的に書いている記事ですので、いつも以上に“あわてんぼう”な内容を含んでいるかもしれませんが、ご容赦ください。

深層学習による評価関数は多層のネットワークで表現されるような大量の計算を伴う関数(少し専門的な書き方では非線形関数)になっています。ここで、関数というのは変数(局面等の情報)を入力すると値(評価値)を返すもののことです。従来の将棋の評価関数も“大量の計算を伴う関数”という点では同じなのですが、こちらは線形和(係数をかけて足し合わせる計算、ネットワークでいうと1層に相当)が基本であり、深層学習によるものは非線形であることが特徴になります。

このため、深層学習による評価関数は大量の並列的な計算を行わなければならず、コア数の多い特殊な計算機(GPU)で計算を行うわけですが、それでも従来の評価関数よりも計算に時間がかかります。計算機自体の作りが違うので単純な比較は難しいのですが、例えば、Silver論文の計算機環境では、1秒間に読める局面の数(NPS)はelmoが3500万程度であるのに対し、AlphaZeroは4万程度であり、千倍くらいの違いがあります。

NPSが千倍も違うのに強さが互角(※細かいことは置いておいて大雑把に書きます)だというのは驚きの結果であり、深層学習の優秀さを示していると感じられる方が多いかと思われますが、筆者が衝撃を受けたのは実はその点ではありません。

elmo等の従来の将棋ソフトはミニマックス探索(アルファベータ探索)を行って、評価値を改善しています。ミニマックス探索については、以下の解説記事をご参照ください。

ここで見方を変えて、探索による改善までを含めて“評価関数”だとして再定義すると、実は従来の将棋ソフトの“評価関数”も膨大な計算の非線形関数であったと再解釈することができます。この定義なら、同じような規模の非線形関数として、AlphaZeroの評価関数との比較がしやすくなります。

この観点から、Silver論文の結果を見ると(※AlphaZeroの探索部分がelmoの探索の一部と打ち消すようにelmoの“評価関数”の定義を調整したとして)、AlphaZeroの深層学習による評価関数と探索(の一部)を含めて再定義されたelmoの“評価関数”が、ものすごく大雑把に書いて、同程度の計算量で同程度の精度であったと解釈することができると思われます(※詳細には実物で検証しないと何とも言えませんが)。

ここで注意しなければならないのは、深層学習のものは将棋専用の設計が行われていない一方で、従来の将棋ソフトのものは将棋専用に作られているという点です。通常、特化/専門化による最適化は改良する方に働くはずであり(そうでなければ最適化として機能していません)、大幅な改良になることもよくあります。

このため、もし将棋においてミニマックス探索が十分に有効であるのならば、深層学習による汎用型評価関数はミニマックス探索による改善を含む従来型の“評価関数”には及ばないはずなのですが(※これまで筆者が将棋における深層学習の有効性にやや否定的であったのは、これが理由です)、Silver論文の結果はそうなっていません。

すなわち、Silver論文の結果は、将棋(やチェス)におけるミニマックス探索の有効性に疑問を投げかけるものであると解釈することができると思われます。

従来、将棋ソフトにおいて、ミニマックス探索は経験的に優れた手法であると信じられていました。これは、先駆者であるチェスソフトでも同様です。実際に探索を深くしていく(思考時間を増やしていく)とレートが向上するということは、このブログでも紹介してきた通りです。

この定説的な知見を見なさなければならないかもしれないというのは、個人的に非常に衝撃的であり、エキサイティングな結果であると感じています。

さて、Silver論文の5頁では、ミニマックス探索よりもモンテカルロ木探索(MCTS)が優れているとして、思考時間に対するレートの伸びを比較しています(図2)。ただ、これは評価関数の精度やNPSが全く異なるものの比較であり、探索部以外の条件が著しく異なってしまっているため、この主張は論理的に成立しないものと思われます。もしかすると出版される際には消えているかもしれません。

ただ、論文執筆側からすると、このように少し無理がある主張というのは、はっきりとは言えない(すぐにデータで証明できない)が研究過程での経験的に何らかの確からしい感覚があって主張しておきたいという場合があり、後で結果的に重要になることがあります。研究においては、科学的な正確性と重要性が異なることがあるわけです。

ミニマックス探索の有効性について、DeepMindグループの疑問と筆者の私的解釈における疑問がどの程度、重なっているのかは分かりませんが、いずれにしても今後、この問題は大いに議論され、研究されることになるかと思われます。

以上、今回は、取り急ぎ、Silver論文で個人的に衝撃を受けたことについて記しました。

次回は、簡単な数理模型を使って、ミニマックス探索の有効性について改めて考え直してみたいと思います。

  • 次の記事:「ミニマックス法の有効性 2:誤差を含む模型解析例」

二者で行う勝負事には相性というものがあります。二者間の勝率の期待値は必ずしも両者の実力差のみに依って決まるものではなく、相性にも依存するというわけです。極端な場合には、「AはBに勝ち越し、BはCに勝ち越すが、AはCに負け越す」といったような実力だけでは説明できない“じゃんけん”のような状態が出現することもあります。

イロレーティングにおいては、相性という要素は考慮されていません。相性を調べるにはイロレーティングを超えた解析が必要になります。イロレーティングについては「イロレーティング 1:棋力ってなんだ?」「2:あなたのレートは……」の解説記事をご参照ください。

相性を考慮すると、AのBに対する勝率の期待値P(A, B)から計算されるレート差

\[dr(A, B) = 400 \log_{10}(\frac{P(A, B)}{1 - P(A, B)})\]

は、両者のレートR(A)、R(B)のレート差

\[dR(A, B) = R(A) - R(B)\]

とは異なっているはずです。その差

\[x(A, B) = dR(A, B) - dr(A, B)\]

を“相性によるレート補正”と定義しましょう。イロレーティングの立場から見ると、この相性による系統的なずれは系統誤差ということになります。

今回は、floodgate棋譜集(2012~2016年版)において、この“相性によるレート補正”の大きさがどの程度であるのかを見積もりたいと思います。

もし勝率の期待値や両者のレートが精確に分かっているのであれば、上の式をそのまま計算することで、補正値を精確に算出することができます。しかしながら、現実のfloodgate棋譜集においては勝率の期待値もレートもそれなりに大きな不確かさを有しており、補正値を精確に求めることはできません(※補正値の不確かさは、各々の不確かさの二乗和の平方根)。

そこで、今回、考えるのは、個々の補正値ではなく、補正値の分布のばらつきの大きさです。個々の補正値の不確かさが大きくても、全体の分布のばらつきについてなら、ある程度は精度良く見積もることができます。

一般的に分布のばらつきの大きさDの二乗は、

\[D^{2} = \sum_{a, b} w(a, b) [x(a, b)]^{2}\]

と書くことができます。ここで、aとbについての和はデータがある全ての組み合わせについての和です。また、重み関数w(a, b)は

\[\sum_{a, b} w(a, b) = 1\]

のように規格化されています。

もし重み関数が定数であるならば、Dは標準偏差に該当します。しかしながら、x(a, b)は、aとbの組み合わせ毎に異なる不確かさs(a, b)を有しているため、不確かさの大きなデータと小さなデータを対等に取り扱うことは合理的ではありません。

このような時、(古典的な)統計学では、Dの不確かさUを最小にするように重み関数を決定します(※詳細は記事の最後に付記)。結果的に、不確かさの大きなデータの重みは小さくなり、不確かさの小さなデータの重みは大きくなります。

実際に用いるデータは、30手以上の投了決着棋譜に限定し、それぞれの組み合わせにおいて30勝以上かつ30敗以上のデータのみを採用します。また、計算に使用するレートの数値は最尤法によるものです。具体的には「floodgate棋譜集レートの最尤法との比較一覧(2012~2016年版)」をご覧ください。

結果は以下の通りです。レート毎の分類は、各組合せの平均レートで行っています。

  • 全体:D±U = 33.2±1.4
  • レート2000~2500:D±U = 33.5±2.0
  • レート2500~3000:D±U = 31.3±2.2
  • レート3000~3500:D±U = 39.5±4.0

結果的に、相性によるレート補正値の分布のばらつきの大きさは大体33程度だということが分かります。また、レート3000以上に限定すると、やや不確かさは大きいですが、40程度に上昇しています。

(以下、加筆と修正[2017年2月16日])

さて、上記のように単純に不確かさUを最小化してしまうと、重み関数w(a, b)が補正値x(a, b)に依存してしまいます。これはあまり性質がよくないので、重み関数が補正値に依存しないように、重み関数内の補正値の二乗をDの二乗で置き換えるという方法も考えられます(※詳細は記事の最後に追記)。

そのように重み関数を定数化した時の結果は以下の通りです。

  • 全体:D±U = 47.3±1.6
  • レート2000~2500:D±U = 50.0±2.5
  • レート2500~3000:D±U = 43.1±2.5
  • レート3000~3500:D±U = 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棋譜集のレート推定における理論誤差を含んだものであるという点には注意が必要です。

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

付記:重み関数の計算

補正値x(a, b)が不確かさs(a, b)を有するということは、補正値は平均x(a, b)、標準偏差s(a, b)の確率分布に従う確率的な量であると考えることができます。以下の計算では、この確率分布を正規分布であると仮定します(※元々、補正値は3つの量の和/差であるため、中心極限定理を鑑みると、この仮定はそんなには悪くはないはずです)。

確率的な期待値として、Dの二乗を書き直すと、

\[D^{2} = \sum_{a, b} w(a, b) < [X(a, b)]^{2} - [s(a, b)]^{2} >\]

となります。ここで、X(a, b)は補正値の確率変数を表し、アングルブラケットは期待値を表しています(※確率分布の重みを付けての積分)。実際に、期待値を計算してみると、

\[D^{2} = \sum_{a, b} w(a, b) [x(a, b)]^{2}\]

となっています。

Dの不確かさUの二乗は、Dの二乗の不確かさを

\[u^{2} = < [ \sum_{a, b} w(a, b) [ [X(a, b)]^{2} - [s(a, b)]^{2} - D^{2} ] ]^{2} >\]

とすると、

\[D + U \approx \sqrt{D^{2} + u^{2}} \approx D + \frac{u}{2 D}\]

ですので、

\[U^{2} = \frac{u^{2}}{4 D^{2}}\]

となり、この期待値を注意深く計算すると、

\[U^{2} = \frac{1}{2 D^{2}} \sum_{a, b} [w(a, b)]^{2} [s(a, b)]^{2} [ 2 [x(a, b)]^{2} + [s(a, b)]^{2} ]\]

となります。

これを、規格化条件の下、重み関数w(a, b)について最小化すると(※ラグランジュの未定乗数法)、

\[D^{2} = \sqrt{\frac{V(4)}{V(0)}}\]

が得られ、また、

\[U^{2} = \frac{1}{V(2) + \sqrt{V(0) V(4)}}\]

も得られます。ここで、

\[V(n) = \sum_{a, b} \frac{[x(a, b)]^{n}}{[s(a, b)]^{2} [ 2 [x(a, b)]^{2} + [s(a, b)]^{2} ]}\]

を導入しました。

この時、重み関数w(a, b)は、

\[w(a, b) = \frac{(1 - U^{2} V(2)) / V(0) + U^{2} [x(a, b)]^{2}}{[s(a, b)]^{2} [ 2 [x(a, b)]^{2} + [s(a, b)]^{2} ]}\]

となります。

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

追記:重み関数の定数化(2017年2月16日)

重み関数が補正値に依存しないように、重み関数内の補正値の二乗をDの二乗で置き換えると、

\[w(a, b) = \frac{1}{v(0) [s(a, b)]^{2} [ 2 D^{2} + [s(a, b)]^{2} ]}\]

と書くことができます。ここで、

\[v(n) = \sum_{a, b} \frac{[x(a, b)]^{n}}{[s(a, b)]^{2} [ 2 D^{2} + [s(a, b)]^{2} ]}\]

です。

この重み関数を用いると、Dの大きさは、

\[D^{2} = \sum_{a, b} w(a, b) [x(a, b)]^{2} = \frac{v(2)}{v(0)}\]

をDについて解くことで求めることができます。

適当な最尤法を用いると、大体はこの方法に近くなります。

このページのトップヘ