コンピュータ将棋に関する基礎的な情報を収集し、分析し、発表する所です。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について解くことで求めることができます。適当な最尤法を用いると、大体はこの方法に近くなります。lfics81将棋のような二人で行う順番制のゲームでは、最初の手番をどちらにするかで“先手”と“後手”とに分かれます。一般的に、先手と後手では初期条件が違いますので、ゲームの結果にも影響があります。通常は、先に行動して利益が得られる先手が有利だとされていますが、例外もあります。リバーシ(オセロ)では、初期局面での先手の合法手は対称性を考慮すると実質的に1つだけですが、その手が得かどうかは定かではありません。6×6では後手必勝が確定していますが、8×8以降は不明であり、棋譜集に依りますが、勝率的にも互角に近いようです(例えば、「オセまにあ」では、10000局で先手の勝率49.8%)。advantage」という)。Games」では、先手勝率38.8%、後手勝率29.8%、引き分け31.4%であり、引き分けを除くと、先手勝率56.6%、後手勝率43.4%になります(※チェスでは引き分けを0.5勝0.5敗として勝ち点率を計算するのが通例ですが、ここでは他と合わせるために引き分けを無視した場合の数値を記しています)。他の棋譜集でも似たような数字ですが、コンピュータチェスでは引き分けと先手勝率が少し上がるようです。40/40」では、執筆時点(2017年1月)で先手勝率34.5%、後手勝率25.6%、引き分け39.9%であり、引き分けを除くと、先手勝率57.4%、後手勝率42.6%(レート差51.8)となっています。この有利/不利が存在するため、チェスの公式戦等では、両者が先手・後手を交互にもち、2局をセットにして偶数回の対局を行うのが通例です。互いに機会を平等にすれば、乱数を入れずに公平性が確保できます。数回の対局では五分五分の結果が出ることがあり、状況によっては大会運営を悩ませることにもなります。囲碁でも先手が有利だと言われており、先手と後手を公平にするために「コミ」と呼ばれるハンデをつけています(日本ルールでは6目半)。コミの大きさが適切であるかは議論の余地のあるところであり、特にコンピュータ囲碁においては技術の進化と共に今後、変わっていくかもしれません。将棋では、やや先手有利というのが定説であり、入玉等の一部のルールにおいては先手有利を前提としているかのような取り決めも見られます。ほとんどのルールにおいては先手と後手を平等なものとして取り扱っており、大会の運営においても先手と後手の差が考慮されることは通常はありません。この辺りは、コンピュータ将棋の大会等においても議論になることがあり、現在のルールには“本音と建前”の乖離があるのかもしれません(※)。将棋でも先手と後手を公平にしようとするのであれば、チェスのように偶数局にしたり、入玉宣言の点数に「コミ」を出したりするというようなことも考えられますが、副作用もありますので熟慮が必要になります。乱数を含めた公平性ということであれば、「振り駒」で確保できているとも言えますが(記事の最後に付記)、“運”の要素をどのように認めるのかについても議論の余地がありそうです。今回は、この点を検証してみたいと思います。単純に勝率を見てみましょう。棋士棋譜集(2015年11月版)では、先手の22256勝19634敗であり、勝率53.13%(標準誤差0.24%)となっています。これをイロレーティングのレート差に換算すると、21.8(標準誤差1.7)となります。棋士における先手勝率は、棋譜集に依りますが、大体この程度の数値になります。floodgate棋譜集(2012~2016年版)における結果は以下の通りです。全体:57900勝51931敗、勝率52.72%±0.15%、レート差18.9±1.0。2012:14611勝13311敗、勝率52.33%±0.30%、レート差16.2±2.1。2013:19241勝17333敗、勝率52.61%±0.26%、レート差18.1±1.8。2014:11729勝10260敗、勝率53.34%±0.34%、レート差23.2±2.3。6544敗、勝率51.99%±0.43%、レート差13.8±3.0。4483敗、勝率53.85%±0.51%、レート差26.8±3.5。対局者の平均レートを3000以上の対局に絞ると、以下のようになります。ここで、レートの数値は最尤法による推定値を用いています。2012年は数が少ないので(29勝20敗)、ここには記載していません。全体:13633勝11876敗、勝率53.44%±0.31%、レート差24.0±2.2。4157敗、勝率53.97%±0.52%、レート差27.7±3.7。2564敗、勝率54.71%±0.66%、レート差32.8±4.6。2564敗、勝率51.47%±0.69%、レート差10.2±4.8。2571敗、勝率53.12%±0.67%、レート差21.7±4.7。これらの結果をまとめると、先手の有利はレート差でおおよそ20程度、強豪同士では更にわずかに有利になるということが分かります。次に、自己対局での勝率を見てみましょう。探索深さ6の2015年のPonanzaでは、1700局で先手勝率51.82%(標準誤差1.21%)となるようです(参考:山本一成氏のツイッター)。これはレート差では、12.7(標準誤差8.4)となります。手元にあるBonanza(6.0)、Apery(wcsc25_bmi2)、技巧(20160606)による結果では以下のようになっています。5:自己対局における投了手数」をご参照ください。持ち時間は、1秒1000局、2秒1000局、4秒1000局、8秒1000局(技巧のみ無し)です。Bonanzaについては通常の定跡ファイルによる結果と宮本定跡を用いた結果があります。Bonanza(通常定跡):2057勝1794敗、勝率53.41%±0.80%、レート差23.8±5.6。Bonanza(宮本定跡):2091勝1795敗、勝率53.81%±0.80%、レート差26.5±5.6。Apery:1873勝1852敗、勝率50.28%±0.82%、レート差2.0±5.7。技巧:1428勝1160敗、勝率55.18%±0.98%、レート差36.1±6.9。上記合計:7449勝6601敗、勝率53.02%±0.42%、レート差21.0±2.9。結果を見ると、対局数があまり多くないこともありますが、レート差20の付近から大きくばらついています。自己対局の先手勝率はソフト毎にばらつきが大きいのかもしれません。最後に、floodgate棋譜集(2012~2016年版)における先手と後手のレート差を最尤法で見積もってみましょう。手法は以下の通りです。各々の先手と後手を別者として、年度ごとにfloodgate棋譜集におけるレートを最尤法で推定する(棋譜数100、勝ち数5、負け数5以上の者に限定、手法の詳細は「最尤法によるレート推定と不確かさ」を参照)。求めた推定値と標準不確かさから、さらに最尤法(最小二乗法)を用いて、先手と後手のレート差を推定する(詳細は記事の最後に付記)。結果は以下の通りです。ここで、レートの分類は先手と後手の平均レートで行っており、標準不確かさは1000回のシミュレーション(モンテカルロ法)によって見積もっています。全体:レート差19.9±1.8。レート2000~2500:レート差11.7±2.9。レート2500~3000:レート差24.6±2.7。レート3000~3500:レート差25.7±4.3。この結果は勝率による結果と整合的になっています。勝率による結果と比べて不確かさが大きくなっているのは、棋譜採択の条件を絞っているためです。この結果から、勝率による単純な見積もりでも悪くないことが分かります。詳細を眺めると、レート2500以下のソフトでは先手と後手のレート差が小さくなっており、これが全体のレート差を押し下げていることが見てとれます。レート2500以上のソフトに限ると、レート差はおおよそ25程度であるようです。以上、今回は、コンピュータ将棋における先手の有利さを検証しました。勝率による見積もりにおいても、レート差による見積もりにおいても、レート2500以上のソフトにおいては先手と後手のレート差はおおよそ25程度であるということが分かりました。この数値はコンピュータチェスにおけるレート差50程度の約半分ということになります。-------------------付記:振り駒について先手/後手を決める方法は各競技で様々なやり方があります。リバーシでは、片方が手で隠した石の表の色をもう片方が当てる「伏石」という方法が使われます。チェスでは、片方が両手にそれぞれ隠した白と黒のポーンをもう片方が選んで色を決める「トス」という方法が使われ、囲碁では、片方が握った石の数が偶数か奇数かをもう片方が当てる「ニギリ」という方法が使われます。将棋では、5枚の歩を落として表裏の枚数で先後を決める「振り駒」という方法が使われます。将棋の駒は落としても割れにくい素材でできているため、他のゲームよりも少し“荒っぽい”やり方になっており、この辺りも将棋の文化的な特徴の一つだと言えるでしょう。「振り駒」が確率的に公平であるかどうかは難しい問題です。駒の表と裏とが対称であることを仮定するならば、五分五分になることが期待されるわけですが(先験的確率という)、これはあくまでも仮定の話であって現実ではありません。実際、例えば、コイン落としでは、コインの表と裏の重さが違うため、落とし方によっては大きく結果を偏らせることもできます。プロの公式戦においては、真部一男九段の提案による調査により、1541局(2005年7月12日~2006年7月11日)で「歩」が50.36%(776局)であることが分かっています(※公式戦で振るのは記録係等の第三者)。この場合の標準誤差は1.27%ですので、結果は標準誤差の範囲内に収まっています。数%以上の大きな偏りがある可能性は少ないという結果です。この結果は「公式戦の振り駒の結果に大きな偏りが見られなかった」というだけのことであり、「大きな偏りの出る振り方が存在しない」ということまでは意味しません。現実の駒が表裏非対称であり、また、持ち方や振り方の自由度がある以上は、何かしら大きな偏りを出す方法はあるのではないかという気はします。この辺のことは「振り駒」の研究よりも「まわり将棋」の研究の方が相応しいかもしれません。\right]\]となります。0\]を解けばよいことになります。S(i)^{2}}\]という結果が得られます。この結果は、特に、先手と後手のレート差dについて、不確かさによる重みを付けた先手と後手のレート推定値の差の平均となっていることから、妥当なものであると考えられます。相対差を取っていますので、レート推定値の絶対値に対する誤差はdには直接的に影響しないようになっています。-------------------追記:先手と後手のレート差の分布のばらつきの大きさ(2017年2月16日)上述の付記の最尤法(最小二乗法)による推定手法は、重み関数を不確かさについて最小化する統計学的手法と結果的に一致しています。同様の手法により、先手と後手のレート差の分布のばらつきの大きさも見積もってみましょう。手法の詳細は「ソフトの相性:ふたりの距離の統計的概算」の記事と同じです。結果は以下の通りです。レート毎に分類した結果も示します。全体:23.6±1.8(最小不確かさ)、28.4±2.0(重み関数定数化)レート2000~2500:20.9±2.7(最小不確かさ)、26.7±3.1(重み関数定数化)レート2500~3000:23.0±2.8(最小不確かさ)、26.3±3.0(重み関数定数化)レート3000~3500:29.4±4.7(最小不確かさ)、32.3±4.9(重み関数定数化)結果を見る限り、どうやら先手の有利さはソフトによってばらつきが大きいようです。改」では、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年版)から、平均手数(読みの類似度)とレートとの関係を対局者毎に整理しました。結果として、投了設定等の系統誤差により機能していないと思われるデータも散見されるものの、全体的には平均手数から読みの類似度が推測できることが確認できました。1:一歩百点?」では、評価値が本来は順序尺度であることを指摘し、なぜ将棋の評価値が比率尺度として取り扱われているのかを説明しました。今回は、将棋の評価値を別の形で表現する方法について考えてみたいと思います。コンピュータ囲碁においては、評価値は0~100%までの“勝率”で表現されます。囲碁では「駒得/駒損」のような分かりやすい指標がなく、また、目数の期待値を用いた従来的な形勢判断もコンピュータ囲碁では有効ではなかったため、勝率の予測値がそのまま評価値となりました。“勝率”は「ゲームの特性」や「評価関数の設計」に依存しない表現であるため、評価値の普遍的な表現方法の一つだと言えます。コンピュータ将棋においても、評価値を“勝率”に換算して表そうという考え方があります。f(V)\]と変換することで、“勝率”Pに換算することができます。この定義がはっきりしないと、関数fを具体的に定めることができません。“勝率”の定義については、おおよそ以下のような考え方があります。シミュレーションによる勝率。