今年（2016年）の大晦日は電王戦合議制マッチが行われます。第3回将棋電王トーナメント（2015年）版のPonanza、nozomi、大樹の枝（多数決合議）と森下卓九段、稲葉陽八段、斎藤慎太郎六段の3名の棋士が合議制マッチで対局するという企画です。
この企画については、「ニコニコ超将棋会議３五角は成立していたか？：合議と熟議」の記事でも触れ、また、「多数決合議と楽観合議」についても付記しています。
付記の内容は、簡単にまとめると、以下のようになります。
- 棋力差の少ないソフトの合議については伊藤毅志先生等の研究があり、例えば、「コンピュータ将棋の進歩6」では、Bonanza、YSS、GPS将棋（当時のレート差150以内）の多数決合議が有意に強くなり、また、楽観合議はそれ以上に強くなるとの報告がある。
- 多数決合議の有効性は簡単な数理モデルで示すことができ、ソフト間の相関を無視すれば、ソフト間の棋力差が小さければ、最善手率が最強参加者を上回り、また、棋力差が大きくなると有効に機能しなくなるということが分かる。
- 楽観合議は評価値期待値の最大化の簡易版と解釈できる（※楽観合議については、さらに別の解釈が可能であることを今回の記事で示します）。
- 合議と最強参加者との比較は、多数台と1台との比較になるので、注意が必要。
今回は、もう少し詳細な模型を用いて、合議の効能について改めて考えてみたいと思います。
模型の詳細は以下の通りです。
- ある局面において、参加ソフトよりも十分に強いソフトが示す有効な候補手の数をnとして、残りの合法手は無視する。最善手（以下、真の最善手）の評価値をA、残りの候補手の評価値を一定のBであると仮定し（※Bは平均値に相当）、その差をd = A - Bとする。
- 各々の候補手に対する各ソフトの評価値は正規分布に従って確率的にばらつくものとする。また、各ソフトの評価値の規格化は揃えられており、確率分布に偏りはないものとする。
- 各ソフト毎に各々の評価値における最善手と最大評価値のみが合議のために利用可能。
- 各ソフト間の相関は基本的には考えないが、後で簡易的に検討する。
- 合議の結果が真の最善手とどれだけ一致するかという“最善手率”を測定する。
さらに、電王戦合議制マッチを意識し、具体的に3者の合議を考えて、3者の正規分布の標準偏差をそれぞれ
\[s_{1} < s_{2} = s_{3}\]
と仮定します。ここで、「1」が最強者であるPonanza、「2」と「3」がnozomiと大樹の枝を想定しています。結果的に、模型は、局面の情報である候補手nの他に、
\[\frac{s_{1}}{d}~,~ \frac{s_{2}}{d}\]
の2つの変数で決まることになります。
下図に、候補手n = 2と3の局面における様々な合議の最善手率を示します。最強者の標準偏差は一定にして、横軸は下位ソフトの標準偏差を取り、横軸が大きい程、ソフト間の棋力差が大きくなるようにしています。変数の値は、一致率や有効分岐数のデータの整合性から、それなりに適当な範囲になっていることを期待しています。各点はそれぞれ1千万回のシミュレーションの結果です。
まずは、合議せずに各ソフト単独で指した場合の最善手率を黒線で示します。上の線が最強ソフトの最善手率で、下の線が下位ソフトの最善手率です。両者が乖離するほど、棋力差が大きいことを表しています。また、合議の最善手率が最強ソフトの最善手率（上線）を下回ってしまうと、最強ソフト単独で指した方が強いということになってしまいますので、合議の意義が失われます。
電王戦合議制マッチで採用されている多数決合議の最善手率を緑点で示します。ソフト間の棋力差が小さい内は有効に機能しますが、大きくなると機能しなくなる様子がグラフから読み取れます。
今回は、模型が簡単ですので、最善の結果を期待できる合議システム（以下、最善合議）も簡単に計算することができます（※記事の最後に詳細を付記）。その結果が黒点であり、合議の仕組みを頑張って調整した時の最大値を与えるものです。こちらも多数決合議と同様に、ソフト間の棋力差が大きくなるほど、合議の効果は薄れていきますが、多数決合議とは違い、合議の機能が失われることはありません。
評価値が最大の指し手を選ぶ楽観合議の結果を赤点、最小の指し手を選ぶ悲観合議の結果を青点で示します。悲観合議は全く機能しませんが、楽観合議はソフト間の棋力差が小さければ有効です。この機構の詳細な解説は長くなるので省略しますが、大まかには、正規分布（もしくは類似の分布）型の確率分布であれば、評価値が高い指し手が真の最善手である確率が高いため、下位ソフトによるノイズが小さければ、楽観合議は機能すると説明できます。
グラフ全体を眺めると、多数決合議がかなり優秀で、楽観合議は多数決合議に劣るという結果になっています。この結果を見る限りは、電王戦合議制マッチにおける多数決合議も効果的である可能性が高いように思えてきます。
しかしながら、果たして、この結果は現実的に妥当なものだと言えるでしょうか？ 実際、伊藤先生等の研究では、多数決合議は楽観合議を下回る結果となっており、今回の結果とは矛盾しています。
この矛盾を追及し、現実的な合議の効能を考えるには、今まで無視してきたソフト間の相関を考えなければなりません。実際に、将棋ソフトには共通の特徴があることも考えられますし、特に今回の電王戦合議制マッチに使われるnozomiと大樹の枝は同系統のソフトであるため、相関を無視することは現実的ではないでしょう。極端な例として、仮にnozomiと大樹の枝が完全にシンクロすることがあるとすれば、多数決合議の結果はそれらの単独の指し手と一致してしまい、合議は確実に機能しません。
一例として、下位ソフト間のシンクロ率を50％にした時（※50％の確率で指し手と評価値が一致）、各ソフトの指し手の一致率は下図のようになります。相関がない時の下位ソフト間の一致率が青点であり（最強者との一致率は赤点）、シンクロ率50％の時の一致率が黒点です。
無相関時の青点は、完全にランダムな場合の1/2（上図）と1/3（下図）を少し上回る程度であり、同系統ソフト間の一致率を再現できていません。シンクロ率による相関を入れることで、黒点のように、一致率を大きく向上させ、現実に近づけることができます。
シンクロ率50％の相関がある時の多数決合議と楽観合議の結果を下図に十字点で示します。無相関時の結果の丸点は上図と同じです。
楽観合議の方は相関に対して頑強であり、結果は大きく変わりませんが、一方で、多数決合議の方は相関の影響が大きく、最善手率が大きく低下します。結果的に、楽観合議と多数決合議が逆転して、楽観合議の方が優位となり、実際の報告に近い結果が得られます。
まとめると、合議において重要なのは、棋力の均質性（棋力差を少なく）と棋風の異質性（同調を少なく）ということになります。特に、多数決合議は同調による相関の影響が大きく、現実に楽観合議に劣ることがあるというのは、相関効果のためではないかと考えられます。楽観合議も棋力差の影響を受けやすく、最善合議には劣りますが、実装が簡単であり、また、相関効果に対して頑強である点が優れていると言えます。
また、今回の多数決合議の話は、政治の民主制の話ともリンクしているかもしれません。合議を上手く機能させるためには、情報格差が少ない方が望ましく、そのためには教育や報道の役割が重要になります。また、熟議したり、間接民主制で段階的に均らしたりすることも意味があると考えられます。さらに、相関効果を減らすために、各自が様々な視点の情報に幅広く触れ、同調的にならないことも大切になるでしょう。この辺は、メディアのあり方とも大きく関係している気がします。
以上、今回は、合議の効能について少し詳しく考えました。実際に電王戦合議制マッチの多数決合議がどれくらい機能するのかについては、実機で検証してみないと何とも言えませんが、同系統ソフトによる相関が小さくないこと、上位と下位の棋力差が大きいことを鑑みると、上手く機能しない可能性も少なくないと考えられます。
-------------------
付記：最善合議について（2016年12月31日）
一般的にN台の多数台合議を考えましょう。各台の最善手をB(i)、評価値をV(i)、確率分布の標準偏差をs(i)とします（i = 1, 2, ..., N）。B(i)の中に出てくる最善手がk種類だとして、それぞれの手をb(j)と書くことにします（j = 1, 2, ..., k）。k = 1の場合には、その手を選択する以外にはありませんので、k > 1の場合を考えます。
最善合議は最尤法によって与えられます。すなわち、b(j)を真の最善手だと仮定した時に現在の状況になる確率P(j)が最も大きくなるb(j)を選択すればよいわけです。
候補手の数がnの局面において、確率P(j)は、
\[P(j) = C \prod_{i = 1}^{N} F[b(j), B(i), V(i), s(i)] [E_{y}[V(i), s(i)]]^{n - 1}\]
となりますが、規格化係数C等、b(j)に依らない部分は比較の際には無視できますので、
\[\prod_{i = 1}^{N} F[b(j), B(i), V(i), s(i)]\]
の部分のみを比較すれば十分です。結果的に、合議は候補手の数nには依存しません。
ここで、式中のF[b, B, V, s]というのは、b = Bの時には、
\[G_{x}[V, s] E_{y}[V, s]\]
となり、そうでなければ、
\[G_{y}[V, s] E_{x}[V, s]\]
となる関数です。また、真の最善手の真の評価値をA、残りの候補手の真の評価値をA - dとして、
\[x = \frac{V - A}{s},~ y = x + \frac{d}{s}\]
とすると、ガウス関数部分は、
\[G_{x}[V, s] = e^{- x^{2} / 2}\]
と
\[G_{y}[V, s] = e^{- y^{2} / 2}\]
になり、誤差関数部分は、
\[E_{x}[V, s] =\text{erf}(\frac{x}{\sqrt{2}}) + 1\]
と
\[E_{y}[V, s] = \text{erf}(\frac{y}{\sqrt{2}}) + 1\]
になります。
誤差関数erf(x)は、C++ならcmathをincludeすれば、そのまま使えますが、あまり速くはないようです。実際、筆者が適当に作った関数でも（g++で）5倍程度の速さが出ます。
さて、実際に模型の計算を超えて、現実に適用しようとすると、dとs(i)は調整変数として最適化する必要があります。また、それとは別にAを予測しなければならないわけですが、こちらは、最善手とそれ以外とを等確率だと荒く近似し、
\[A \approx \frac{k - 1}{k} d + \frac{1}{N} \sum_{i = 1}^{N} V(i)\]
として合議を行えば、結果に大きな違いは出ないようです。
下図に、
\[s(1) = s(2) = ... = s(N) = 2 d\]
の場合の最善手率を示します。棋力差も相関もない理想的な状況です。
Aの予測に上の近似式を用いた予測最善合議の結果（青十字点）は最善合議の結果（黒点）とほぼ一致します。また、台数が多くなっても、最善合議が楽観合議（赤点）を大きく上回ることが分かります。
