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

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

2017年02月

コラム記事

  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. ソフトの相性:ふたりの距離の統計的概算

今後の課題(TODO)

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

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

二者で行う勝負事には相性というものがあります。二者間の勝率の期待値は必ずしも両者の実力差のみに依って決まるものではなく、相性にも依存するというわけです。極端な場合には、「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について解くことで求めることができます。

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

将棋のような二人で行う順番制のゲームでは、最初の手番をどちらにするかで“先手”と“後手”とに分かれます。一般的に、先手と後手では初期条件が違いますので、ゲームの結果にも影響があります。

通常は、先に行動して利益が得られる先手が有利だとされていますが、例外もあります。例えば、どうぶつしょうぎは後手必勝であり、初期局面がzugzwang(できればパスしたい局面)になっています(参照:『「どうぶつしょうぎ」 の完全解析』)。また、リバーシ(オセロ)では、初期局面での先手の合法手は対称性を考慮すると実質的に1つだけですが、その手が得かどうかは定かではありません。6×6では後手必勝が確定していますが、8×8以降は不明であり、棋譜集に依りますが、勝率的にも互角に近いようです(例えば、「オセまにあ」では、10000局で先手の勝率49.8%)。

チェスでは先手の勝率が高く、先手有利と言われています(「first-move advantage」という)。例えば、「A Visual Look at 2 Million Chess Games」では、先手勝率38.8%、後手勝率29.8%、引き分け31.4%であり、引き分けを除くと、先手勝率56.6%、後手勝率43.4%になります(※チェスでは引き分けを0.5勝0.5敗として勝ち点率を計算するのが通例ですが、ここでは他と合わせるために引き分けを無視した場合の数値を記しています)。他の棋譜集でも似たような数字ですが、コンピュータチェスでは引き分けと先手勝率が少し上がるようです。例えば、「CCRL 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。
  • 2015: 7087勝 6544敗、勝率51.99%±0.43%、レート差13.8±3.0。
  • 2016: 5232勝 4483敗、勝率53.85%±0.51%、レート差26.8±3.5。

また、対局者の平均レートを3000以上の対局に絞ると、以下のようになります。ここで、レートの数値は最尤法による推定値を用いています。また、2012年は数が少ないので(29勝20敗)、ここには記載していません。

  • 全体:13633勝11876敗、勝率53.44%±0.31%、レート差24.0±2.2。
  • 2013: 4875勝 4157敗、勝率53.97%±0.52%、レート差27.7±3.7。
  • 2014: 3097勝 2564敗、勝率54.71%±0.66%、レート差32.8±4.6。
  • 2015: 2719勝 2564敗、勝率51.47%±0.69%、レート差10.2±4.8。
  • 2016: 2913勝 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年版)における先手と後手のレート差を最尤法で見積もってみましょう。

手法は以下の通りです。

  1. 各々の先手と後手を別者として、年度ごとにfloodgate棋譜集におけるレートを最尤法で推定する(棋譜数100、勝ち数5、負け数5以上の者に限定、手法の詳細は「最尤法によるレート推定と不確かさ」を参照)。
  2. 求めた推定値と標準不確かさから、さらに最尤法(最小二乗法)を用いて、先手と後手のレート差を推定する(詳細は記事の最後に付記)。

結果は以下の通りです。ここで、レートの分類は先手と後手の平均レートで行っており、標準不確かさは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%ですので、結果は標準誤差の範囲内に収まっています。つまり、数%以上の大きな偏りがある可能性は少ないという結果です。ただし、この結果は「公式戦の振り駒の結果に大きな偏りが見られなかった」というだけのことであり、「大きな偏りの出る振り方が存在しない」ということまでは意味しません。

現実の駒が表裏非対称であり、また、持ち方や振り方の自由度がある以上は、何かしら大きな偏りを出す方法はあるのではないかという気はします。この辺のことは「振り駒」の研究よりも「まわり将棋」の研究の方が相応しいかもしれません。

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

付記:先手と後手のレート差の最尤法(最小二乗法)による推定

参加者iの先手におけるレート推定値をr(i)、標準不確かさをs(i)とし、後手におけるレート推定値をR(i)、標準不確かさをS(i)とする時、参加者iの平均レート推定値がm(i)、先手と後手のレート差がdとなる確率Pの自然対数は、確率分布を正規分布と仮定すると、

\[\ln{P} = - \sum_{i} \left[ \frac{[ m(i) + d / 2 - r(i) ]^{2}}{2 s(i)^{2}} + \frac{[ m(i) - d / 2 - R(i) ]^{2}}{2 S(i)^{2}} \right]\]

となります。

最尤法(最小二乗法)では、この確率Pをm(i)とdについて最大化(最小二乗誤差を最小化)すればよいので、

\[\frac{\partial{\ln{P}}}{\partial{m(i)}} = 0\]

\[\frac{\partial{\ln{P}}}{\partial{d}} = 0\]

を解けばよいことになります。

実際に偏微分を計算して、解を求めると、

\[m(i) = \frac{S(i)^{2} r(i) + s(i)^{2} R(i)}{s(i)^{2} + S(i)^{2}} + \frac{s(i)^{2} - S(i)^{2}}{s(i)^{2} + S(i)^{2}} \frac{d}{2}\]

\[d = \left[ \sum_{i} \frac{1}{s(i)^{2} + S(i)^{2}} \right]^{-1} \sum_{i} \frac{r(i) - R(i)}{s(i)^{2} + 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(重み関数定数化)

結果を見る限り、どうやら先手の有利さはソフトによってばらつきが大きいようです。

このページのトップヘ