2016年5月3日～5日に第26回世界コンピュータ将棋選手権（WCSC26）が開催されます。今回の選手権は、参加者も多く、また、出場ソフトの平均レベルも大きく向上していると見込まれることから、熾烈な争いになるのではないかと予想されています。とりわけ、一次予選は8つの勝ち抜け枠を39チーム（4月17日現在）が争うという構図になっており、また、その中には優勝候補も複数含まれることから、初日から全く息の抜けない状況になっています。
世界コンピュータ将棋選手権（WCSC）は基本的に「スイス式」競技会であり、今回も一次予選からスイス式で争われることになります。今回は、WCSC一次予選を例としながら、スイス式について改めて考えてみたいと思います。
競技大会において、どのような組み合わせで競技を行い、順位をつければよいのかというのは昔から運営者の頭を悩ませてきた問題です。順位付けというと反射的にソートのアルゴリズム（仕組み）が頭に浮かぶ方も多いかと思われますが、競技大会の場合には、会場の都合や参加者・関係者の意向、プログラム進行の流れ、アクシデントへの対応等の様々な制約条件があるため、そう簡単にはいきません。特に、関係者の意向等は数値化できるものでもありませんので、必ずしも数学的な最適解があるというわけでもなく、最後は運営責任者の判断ということになります。
競技会の方式は、大きく分けて、勝ち抜き（ノックアウト）方式と集団（グループ）方式の2つがあります。
「勝ち抜き方式」というのは、いわゆる日本語の“トーナメント”のことであり、基本的に負けたら終わりという方式です（※敗者復活戦がある場合もあります）。優勝者を決めるのに試合数が少なくて済んだり、段々と候補者が絞られることで盛り上がりを演出できたりといった利点があります。
「集団方式」というのは、いわゆる日本語の“リーグ戦”のことであり、各回ごとに様々な対戦組み合わせで競技を行い、その最終的な勝敗で順位を決定します。特に、全員が総当りで対戦する総当りリーグ戦（ラウンドロビン式）は、対戦組み合わせが各参加者にとって対称的になるため、公平性の高い方式になっています。
今回の話題である「スイス式」は、集団方式の一種であり、対戦組み合わせ時に勝敗数等で選別を行って、総当りよりも少ない回数で決着をつけるという方式です。総当り戦では実力差が離れた対戦が数多く含まれてしまいますが、スイス式では、勝敗数の選別により、なるべく実力が近いもの同士を戦わせて、無駄なく順位付けが行われます。言わば、総当り戦のダイジェストのような形です。また、最後に強者同士の対決が行われることで、勝ち抜き方式の良さも取り込んでいます。
こうして見ると、スイス式は“いいとこ取り”で文句のない方式に思えるのですが、問題点もあります。それは、対戦組み合わせを決めるのが複雑であるという点です。勝ち抜き式やラウンドロビン式の対戦組み合わせは誰もが一目で分かるくらいに単純であり、大会前にくじ引き等で決めてしまえば、それで終わりです。一方で、スイス式の場合には、複雑な取り決めに基づいて、対戦結果を随時的に反映させつつ、対戦組み合わせを順次的に決めていかなければなりません。この過程が複雑であり、また透明性に欠けるというのが、スイス式がそれほど広まっていない要因になっていると思われます。
スイス式の実施方法は実際に複雑です。日本チェス協会の解説ページには、次のように記されています。
スイス式は単純のようで実際に組合わせに当って見ると意外に難しく経験が必要である。
スイス式はいずれのシステムにしても人間のためのプログラムは完結している。しかし、コンピュータプログラム化となるとアルゴリズムの記述が難しく、単純なシステムでさえ完全なものがない。人間がフィージィブルな恣意で誤魔化してしまうところはコンピュータは”とんでもない”（結局はそれが正しいことが多い）組み合わせが出現し、誰も納得しない。
このことは、筆者も今回の記事のために実際にプログラムを書いてみて実感しました。WCSC26のルールに詳細まで書かれていないのは、きちんと細部まで記そうとすると大変だからだと思われます。
具体的に、スイス式の実施には、以下のようなことを決めなければなりません。
- どの時点の勝敗数を用いるか：前回まで（完全スイス式）／前々回まで（変形スイス式、対戦中に次の組み合わせを決定可能）／3回戦のみ初回で他は前回まで（WCSC方式）。
- レーティングや予選順位等の事前情報を使うかどうか：モンラート式／オランダ式／マクマホン式等。
- 同一勝敗数内の順位の決め方。
- 同一勝敗数内の組み合わせ法：順接／逆接（ネスト）／隣接／間接等。
- 同一勝敗数内の余り者の決定と処理の方法。
- 過去対戦済みの組み合わせを排除するかどうか、また排除する場合には組み直しの方法。
特に、最後の部分の説明は意外と大変です。
スイス式が複雑だというのは、言い換えると、それだけルールの自由度が大きいということになります。それらの詳細なルールの組み合わせにより、それぞれどのような有利／不利が生じるのかというのは、さらに複雑な話になります。この辺の話は、WCSCの運営側の方々が研究されています（参照：「世界コンピュータ将棋選手権における対戦組み合わせシステムの有効性（６）」「シミュレーションに基づくスイス式トーナメント組み合わせ方式の評価」等）。
さて、ここでは、そのような詳細はさておいて、WCSCの一次予選を具体例として、7回戦スイス式が大まかにどのような性質を持っているのかを調べてみたいと思います。
計算する量は「実力レート上位8位以内の参加者が実際に何人、8位以内で勝ち抜けるかの期待値」です。参加者の実力レートの分布は、あるレート差の範囲内で一様ランダムとします。スイス式の詳細は、上述のWCSC26のルールと瀧澤先生の論文の記述に基づいて決めました。ただし、順位付けの決定方法は、簡単化のため、勝ち点、ソルコフ（全ての対戦相手の勝ち点の合計）までとして、それでも同点の場合はランダムになっています。対局はイロレーティングに基づく確率過程であるとして、引き分けは考えずに計算を行い、それぞれ10万回の競技会のシミュレーションに基づいて期待値を算出しています。イロレーティングについては、以下の解説記事をご覧ください。
まずは、スイス式の結果の前に、総当りリーグ戦ではどうなるのかを抑えておきましょう。
下図は、横軸が回数、縦軸がその回数までで終了した場合の上位8名の勝ち抜け期待値です。対戦順序はランダムになっており、回数が「参加者数 - 1」に到達すると総当りになります。
全ての場合において、勝ち抜け期待値は、上限値である8に向かって、単調的に増加しています。
総当りの時の勝ち抜け期待値は、レート分布の抽出範囲のレート差が2000の場合、参加者が20名の時（青点）には約7.4であるのに対して、40名の時（黒点）には約7.1に下がっています。これは、参加者数が増えれば、その分だけ試合数を増やしたとしても、実力通りにいかないことが増えるということを意味しています。その主たる理由は、レート分布の抽出範囲が一定であるため、参加者数が増えると、参加者間の平均的なレート差が縮まるためだと考えられます。実際に、20名の参加者数に合わせてレート差を1000に調整した場合（水色点）には、総当りの時の勝ち抜け期待値は約7.1となって、黒点の場合とほぼ一致します。
WCSC26の一次予選の参加者数は約40名で、スイス式で7回戦を行います。この時の上位8名の勝ち抜け期待値を以下に示します。横軸は、レート分布の抽出範囲のレート差です。
総当りリーグ戦の結果（赤点）は、各参加者に対して対称的で回数も多いため、理論的な上限値を与えます。一方で、ランダムな順序で対戦する7回戦リーグ戦の結果（橙色点）は、それ以下の結果になってしまうとわざわざスイス式にする意味がないため、理論的な下限値を与えます。実際に、7回戦スイス式の結果（黒点）は、その中間に位置しており、7回戦リーグ戦を改善するものになっています。改善の度合いはレート差が大きいほど大きいようです。
この結果をWCSC26の一次予選に適用してみると、上位8名の内、6名程度が無事に予選を通過するだろうという予測になります。上位8名以外の参加者も2名程度が勝ち抜けるということになりますので、棋力的に多少不安があったとしても諦める必要はありません。「運も実力のうち」という言葉もあります。
最後に、設定ミス／遅刻／途中退場といったようなアクシデントによるノイズが加わった時にはどうなるかを示します。縦軸は40名、レート差2000の場合の勝ち抜け期待値であり、横軸はランダムで勝敗を反転させる確率（ノイズ）です。
全ての場合において、ほぼ線形に勝ち抜け期待値が減少していきます。この結果を見る限りは、方式によるノイズの影響の違いは少ないようです。
アクシデントは参加者当人にとってはしばしば深刻なものであり、特に強豪のアクシデントは印象的な結果をもたらすこともありますが、集団方式における統計的な期待値としては影響は大きくないと言えそうです。一般的に、アクシデントに対する頑強さは集団方式の特長とされています。
以上、WCSC一次予選を例としながら、スイス式について考えてみました。スイス式は複雑で手間のかかる方式ですが、同じ対戦回数のランダム順序のリーグ戦よりは優れています。スイス式競技会の裏には、少しでも大会をよくしようとする運営の方々の思いがあるのだと思われます。
- ------------------
追記（2016年5月2日）
「竜の卵」の欠場により、一次予選の通過枠が8枠から9枠に増えたようです。その他の欠場もあり、結局のところ、36名中、9名が二次予選に進むことになるとのことです。
以下に参加者数と通過枠を修正した場合の図を示します。
- ------------------
追記（2016年5月3日）
二次予選はスイス式9回戦で24名中、8名が通過します。この場合に対応する図は以下のようになります。
コメント