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

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

2016年04月

詳細な説明は、以下の解説記事をご覧ください。

javascriptにより、ブラウザから実行できるプログラムです。単一のhtmlファイルですので、何をしているのかはソースを見れば分かります。

一応、安全性は確認しておりますが、バグやファイル改ざん等のリスクまでは対応できません。利用する際には自己責任でお願い致します。このプログラムの使用に関して、当方は一切の責任を負いません。

古いブラウザだと動かないかもしれません。

対局数が多い場合には、処理に時間がかかることがあります。

英語版の表記は以下の意味です。

  • 「games」:対局数。
  • 「wins」:勝ち数。
  • 「draws」:引き分け数。
  • 「confidence interval」:信頼区間。
  • 「Calculate」:計算実行。
  • 「Select all」:全選択。
  • 「winning percentage」:勝率。
  • 「standard error」:標準誤差。
  • 「relative Elo rating」:相対イロレーティング。

「removed from games」は引き分けを対局数から取り除く場合、「transformed into (draws / 2) wins」は引き分け数の半分(端数は切り捨て)を勝ち数に加える場合に選択してください。

このプログラムは、パブリックドメイン(公有)扱いとします。ご自由にお使いください。

以下はc++版の関数です。やっていることは基本的にjavascript版と同じですが、コメントが付いています。

#include <algorithm> // std::minとstd::maxのため。windows.hの名前衝突に注意。
#include <cmath> // 数学関数のため。

// ----------------------------------------------
double log10_binomial(const int & n, const int & k)
// 二項係数 C(n, k) の常用対数。
// ----------------------------------------------
{
	const int m = std::min(k , (n - k));

	double s = 0.0;

	for (int i = 1; i <= m; i++)
	{
		s += std::log10((n - m + i) / double(i));
		// オーバーフロー対策で対数での計算。
		// 常識的な範囲の計算なら対数を取らずに掛け算のやり方でもよい。
		// javascript版では場合分けで少し高速化。
	}

	return(s);
}

// ----------------------------------------------
double binomial_distribution(const int & n, const int & k, const double & p)
// 二項分布 C(n, k) * p^{k} * (1 - p)^{n - k} の値。
// ----------------------------------------------
{
	return(std::pow(10.0, (log10_binomial(n, k) + k * std::log10(p) + (n - k) * std::log10(1.0 - p))));
	// オーバーフロー対策で対数での計算。
}

// ----------------------------------------------
void confidence_interval(const int & n, const int & k, const double & a, double & p, double & p_min, double & p_max, double & dr, double & dr_min, double & dr_max)
// 入力:対局数n、勝利数k、[100 * (1 - a)]%信頼区間のa。
// 出力:勝率推定値p、勝率下限値p_min、勝率上限値p_max、レート差推定値dr、レート差下限値dr_min、レート差上限値dr_max。
// ----------------------------------------------
{
	if ((n < 5) || (k <= 0) || (k >= n) || (a <= 0.0) || (a >= 1.0))
	{
		// 本来はエラー処理、ここでは省略。
		return;
	}

	// 勝率推定。
	p = k / double(n);

	// 挟み撃ちで区間を絞っていくための初期値。
	int k_min = 0;
	int k_max = n;

	// 区間境界での二項分布の値の初期値。
	double b_min = binomial_distribution(n, k_min, p);
	double b_max = binomial_distribution(n, k_max, p);

	// 確率の積算値。0から始めて、a越えを目指す。
	double s = 0.0;

	while (true) // a超えまでの無限ループ。
	{
		// 境界の分布値が小さい方を狭めていく。
		if (b_min < b_max)
		{
			s += b_min;
			if (s >= a) {break;} // 超えたら抜ける。越える前が信頼区間。
			k_min++;
			b_min = binomial_distribution(n, k_min, p);
		}
		else
		{
			s += b_max;
			if (s >= a) {break;} // 超えたら抜ける。越える前が信頼区間。
			k_max--;
			b_max = binomial_distribution(n, k_max, p);
		}
	}

	// 区間を勝率に直す。
	p_min = k_min / double(n);
	p_max = k_max / double(n);

	// レート差の計算。
	dr = 400.0 * std::log10(p / (1 - p));
	dr_min = (k_min == 0) ? -1.E308 : (400.0 * std::log10(p_min / (1 - p_min)));
	dr_max = (k_max == n) ?  1.E308 : (400.0 * std::log10(p_max / (1 - p_max)));
	// 念のために対数の発散を避けているが、普通の環境なら不要。

	return;
}

前回の記事「自己対戦及び連続対戦の誤差論 1:標準誤差と信頼区間」では、自己対戦/連続対戦の対局数が十分に大きい場合に誤差をどのように見積もればいいのかを整理しました。今回は、対局数の影響について解説します。

標準誤差は対局数nの平方根に逆比例していました。つまり、対局数が大きくなるほど、誤差は小さくなり、精度が高くなるということになります。

必要な精度というのは、実験者がどれくらいまで求めるのかということに依ってきますが、「実際に誤差を計算してみて、必要な精度が出ているかどうか」というのが「対局数が十分であるかどうか」の基本的な判断基準になります。ただし、誤差の計算には、いくつか注意しなければならないことがあります。それが今回の記事の主題です。

前回の記事で紹介した誤差論は、対局数が多くて標準誤差が小さい時に有効なものでした。そうでない場合には、誤差の見積もりを修正しなければならないことがあります。

例えば、標準誤差は、勝率の真値pに依存しており、p (1 - p)に比例していました。これは、pの関数として描くと、下図のようになります。

p_1-p

しかしながら、勝率の真値pは分からないため、勝率の推定値qを用いて、標準誤差を推定することになりました。pとqの値が近ければ、この標準誤差の推定は妥当なものとなりますが、もしそうでなければ、標準誤差の推定は的外れなものになってしまうかもしれません。特に、qが0や1に近い場合には、変化が大きいので、注意が必要です。

実際の標準誤差が推定よりも小さい場合には問題はないのですが、推定よりも大きい場合には、実際の精度よりも過剰に精度を見積もってしまうことになるため、問題が生じ得ます。該当する場合には、標準誤差を適度に上方修正して考える必要があるでしょう。

この話は、言い換えると、誤差の高次の項の問題の一種ということになります。誤差が小さければ現れなかった問題が、誤差が大きくなってくると無視できなくなってくるということです(※)。これらの問題をまとめて解決するには、結局のところ、対局数を増やして精度を上げるしかありません。

※(2016年5月31日追記) そもそも「誤差」は真値との差として定義されているわけですが、真値というのは値が分からないものであるため、「誤差」を計算するには真値について何らかの仮定を置く必要があります。これが、誤差論の根本的な問題の一つであり、高次の項の問題の根本もそこにあります。この問題を避けるため、「誤差」という概念は諦めて、「不確かさ」という概念を導入するというのが近年の主流です。「不確かさ」は平均からのばらつきとして定義され、その平均が真値に近いかどうかは問題を切り分けます。「誤差」と異なり、「不確かさ」についてならば、紛れのない国際基準を作ることも可能であり、その国際基準(GUM)は物理学や工学等の分野で広く採用されています。

一方で、誤差の大きさとは直接的に関係無しに、対局数の不足のみによって生じる問題もあります。具体的には、中心極限定理の適用の妥当性の問題です。こちらは理論的に対処することができます。

中心極限定理は、対局数が十分に大きい時に、確率分布が正規分布になることを示していました。しかしながら、実際には、n回連続対戦した時の勝率の推定値qの確率分布は離散確率分布になっており、正規分布のような連続確率分布にはなっていません。なぜなら、qは、自然数である勝ち数kを使って、“k / n”と計算されるからです。もちろん、nが十分に大きくなれば、“k / n”の有理数は実数に近いものとして取り扱うことができるわけですが、実際にそれがどれくらい良い近似であるのかというのは、誤差の評価とは別に、対局数によって決まってくる問題ということになります。

実際の確率分布は、勝率の真値pを用いると、\[\frac{n!}{k! (n - k)!} p^{k} (1 - p)^{n - k},~~ k = n q\]の二項分布として書き表すことができます。

この二項分布の標準偏差は、\[S = \sqrt{\frac{p (1 - p)}{n}}\]であり、前回の正規分布の標準偏差と同じになりますので、標準誤差については、実は対局数に依らずに厳密な値であったということが分かります。

対局数によって変わってくるのは、標準誤差と信頼区間との間の関係です。以下の図は、正規分布において95%信頼区間である「真値±1.96標準誤差」(上図)と99%信頼区間である「真値±2.58標準誤差」(下図)内の実際の確率を表しています。分布が正規分布であれば、それぞれ0.95と0.99になるはずのものですが、実際には二項分布であるために離散的に値が変わってきます。横軸は対局数nです。

s

二項分布はnが十分に大きければ、正規分布で近似することができます。これは中心極限定理に対応しています。ただし、nが大きくても、n p、もしくはn (1 - p)が小さければ、ポアソン分布になり、正規分布にはなりません。実際に、上記の図でも、pが0.5(黒点)と0.1(橙色点)の時には、正規分布に近い結果になっており、pが0.01(赤点)の時には、正規分布の結果からのズレが大きくなっています。

上の図で示した区間内の確率は大きい分には問題ないのですが、小さくなると、その分だけ信頼が落ちるということになります。また、これらの確率は勝率の真値pに依存しており、真値pは分からないものですので、対局数を調整して信頼を上げるというような操作を行うこともできません。結局のところ、確率の下限の方に着目して、その分だけ信頼区間の%を下方修正して考えるというのが、妥当な解釈ということになるでしょう。

勝率の真値pに対して推定値qを適用してよいということであるのならば、二項分布を用いて、最小の信頼区間を推定することができます。ただし、この信頼区間においても、上で記した「誤差の高次の項の問題」は変わらずに発生し得ます。この処方箋で対処できるのは、「中心極限定理の適用の妥当性の問題」のみです。

さて、前回の記事で、相対レートにおける標準誤差を推定する際に、勝率の標準誤差Sに対する展開を行いました。この展開は、Sがpや(1 - p)よりも十分に小さい時には有効なのですが、そうでない場合には使うことができません。特に、勝率に対してそれなりに広い信頼区間が与えられた時には、破綻してしまいます。

この問題も「誤差の高次の項の問題」の一種ですが、これは観測データの直接的な処理の問題ではなく、誤差伝播という間接的な処理の問題であるため、理論的な対処が可能です。

実際に、相対レートは勝率に対して単調増加関数ですので、信頼区間が与えられた時には、展開を用いなくても、上限値と下限値をそのまま放り込むことで、対応する相対レートの信頼区間を得ることができます。

これらの信頼区間の見積もりはコンピュータで簡単に計算することができます。「連続対戦における信頼区間の計算」の資料記事に計算プログラムを記しました。

以上、自己対戦/連続対戦の結果から勝率やレートを推定する際の誤差論について整理しました。結局のところ、実験の精度はデータの質と量で決まってきます。地道にデータを収集する基礎研究が華々しい成果の基盤になるのだと思います。

コンピュータ将棋の特長の一つに、誰でも簡単にソフト同士の対局実験ができるということがあります。人間の将棋の場合には、同じ人同士を100回、1000回と連続対局させて勝率を推定するというような実験は現実的に困難であるわけですが、コンピュータ同士なら黙々とやってくれます。実験ができるというのは技術開発にとって非常に大切なことです。

「同じソフト同士を戦わせたら毎回、同じ結果になるんじゃないか」と思われる方もいるかもしれませんが、多くの将棋ソフトは序盤に擬似的なランダム性が入っていますので、その範囲内で違った結果になります。逆に言えば、一局の結果というのは確率的なものですので、統計的に処理して、誤差も考えないと、適切な能力評価ができないと言えます。

今回は、自己対戦/連続対戦の結果から勝率やレートを推定する際の誤差の問題について整理してみたいと思います。以下、先手後手の手番については、常に割合を一定で揃えること(同数、もしくは常に先手/後手のみ等)として、誤差には影響しないものとします。また、引き分けもないものとしています。これは、引き分けの対局を取り除いていると考えることもできますし、互いに0.5勝分として2つの引き分けを1勝1敗に変換していると考えることもできます(※引き分けが奇数の場合は余りが出ますが、1つなら、どう処理しても以下の議論にほとんど影響を与えません)。

まずは、AとBがn回連続対戦して、Aがk回勝った時のAの勝率を推定してみましょう。

「そんなの勝率なんだから、“k / n”に決まってるだろ」と思われるかもしれませんが、そう思う根拠は何かということです。実際に、本当の勝率p(真値)というのは無限に多くの対局を行った時の勝ち数の割合の極限値であり、有限の対局数における“k / n”とは必ずしも一致しません。“k / n”というのは、pの推定値に過ぎないわけですから、何故それを推定値とするのかという根拠がいるわけです。

連続対戦のn回の結果は互いに独立であるとしましょう。人間同士の連続対戦であれば、前の結果を引きずる等の影響があるため、結果が独立であるとは限りませんが、コンピュータ同士の場合には、擬似乱数が機能していれば、互いに独立であるとみなすことができます。

今、勝率の真値pは分かりませんので、代わりに推定値qを用いるとすると、この時、Aがk回勝つ確率の推定値Qは、\[Q = \frac{n!}{k! (n - k)!} q^{k} (1 - q)^{n - k}\]となります。実際に「Aがk回勝つ」というのは実現されており、Qはできるだけ大きい値であった方が現実に近いだろうと考えられますので、Qを最大化するq、すなわち、\[\frac{d{Q}}{d{q}} \propto k - n q = 0\]を満たす\[q = \frac{k}{n}\]が最も尤もらしい推定値(最尤値)ということになります。

また、そもそも真の勝率pというのは、無数の対局結果における勝ち点のデータ集合(母集団)の平均(母平均)であるとも考えられます。この時、連続対戦のn回の結果というのは無作為の標本であると考えられますので、標本平均である“k / n” = qは、二乗誤差を最小化する「母平均の不偏推定値」にもなっています。平均と不偏推定値については、「平均と標準偏差:それって不偏推定値?」の解説記事をご覧ください。

つまり、この場合には、qというのは最尤値であり、かつ不偏推定値でもあるため、誰もが自然に受け入れていたということになります。以下、誤差論においては、「標本平均」という立場の方が分かりやすいので、そちらの立場から話を進めていきます。

さて、標本平均は、サンプル数nが同じでも、サンプルセットが異なれば値が変わり得ます。実際、n回の連続対戦を行う度に、毎回、標本平均である勝率の推定値qは異なる値になり得るわけです。つまり、標本平均自体が何らかの確率分布を持っているということになります。

サンプル数nの標本平均の確率分布については、中心極限定理が存在しており、nが十分に大きければ、平均p、標準偏差\[S = \frac{s}{\sqrt{n}}\]の正規分布になることが知られています(※記事の最後に直感的な証明を付記します)。ここで、pはサンプルを取る母集団の平均(すなわち、勝率の真値)であり、sは母集団の標準偏差、すなわち、\[s = \sqrt{p (1 - p)}\]です。標準偏差については、「平均と標準偏差:それって不偏推定値?」の解説記事をご覧ください。

n回の連続対戦を行った時に得られる勝率の推定値は、その確率分布に従って“サイコロ”を投げた時の1つの結果に過ぎません。それがどれくらい真値に近いのかは確率的にしか分からないということになります。

nが十分に大きいとして、確率分布が正規分布であるとすると、“サイコロ”を投げて「真値p±標準偏差S」の区間内の結果が得られる確率は約68.3%ということになります。この時の標準偏差Sは標準誤差とも言います(※慣習的に“シグマ”と呼ぶ人もいますが、記法の慣習は変わりやすいものですので、お勧めはしません)。

また、X%以上の確率で結果が得られるという区間を「X%信頼区間」と言います。つまり、「真値±標準誤差」は「68%信頼区間」です。また、「真値±1.96標準誤差」は「95%信頼区間」であり、「真値±2.58標準誤差」は「99%信頼区間」になります。「真値±(標準誤差×r)」と「[(1 - a)×100]%信頼区間」との関係を下図に示しました。

r-log10a

確率というものは、いくら確率が低くても当たる時には当たってしまうものですので、絶対ということはありません。「標準誤差の何倍まで」/「何%信頼区間」で良しとするのかは、そのデータの重要性を鑑みての人間の判断ということになります。とりあえずは標準誤差を推定しておけば、後は各人で判断が可能です。

ここで、「標準誤差を推定」と書いたのは、上述のSの式が母集団の標準偏差sに依存しているためです。母集団の標準偏差は、勝率の真値pが分からないと分からないため、これも推定する必要があります。ただし、こちらは真値の推定よりもゆるいものでよいため、式中の勝率の真値pを推定値q = k / nで置き換えて、\[s \approx \sqrt{q (1 - q)}\]としてもいいですし、標本の不偏標準偏差を用いて\[s \approx \sqrt{\frac{n}{n - (3 / 2)} q (1 - q)}\]と推定してもかまいません(※)。nが十分に大きければ、どちらでもほぼ同じ値になります。不偏推定値にこだわるかどうかの違いです。

※(2016年5月31日追記) 不偏分散の平方根(すなわち、分母が「n - (3 / 2)」ではなく、「n - 1」)を使うこともあり、これを実験誤差と呼びます。これは理論的には中途半端な取り扱いということになるのですが、慣習的には最もよく使われており、例えば、不確かさの国際基準(GUM)でも標準として採用されています。

さて、これでAとBとの間の勝率と標準誤差の推定ができるようになりましたので、次に両者の間の相対レートを求めてみましょう。

相対レートの推定値dRは、勝率の推定値qを用いて、\[dR = 400 \log_{10}(\frac{q}{1 - q}) + K\]で与えられます。ここで、Kは系統誤差を表していますが、これについては後で説明します。イロレーティングについては、以下の解説記事をご覧ください。

相対レートの標準誤差を求めるには、誤差伝播を考慮する必要があります。勝率の推定値qが、勝率の真値pと標準誤差Sから、q = p±Sで書かれる場合を想定して、上の相対レートの推定値の式をpの周りでSについて1次まで展開すると、\[dR \approx 400 \log_{10}(\frac{p}{1 - p}) + \frac{400}{\ln{(10)}} \frac{S}{p (1 - p)} + K\]となります。最初の項が相対レートの真値であり、次のSの1次の項が相対レートの標準誤差に当たります。相対レートの標準誤差を、Sの次数を変えないように推定値のみで書き換えると、\[\frac{400}{\ln{(10)}} \frac{S}{p (1 - p)} \approx 173.7 \frac{S}{q (1 - q)}\]となります。この誤差伝播における展開は、Sがpや(1 - p)よりも十分に小さくないと成立しませんので、適用する際にはご注意ください。

一般的に、誤差には偶然誤差と系統誤差があります(※設定ミスや計算ミス等の人為的な誤差も生じ得ますが、ここでは除きます)。今まで記してきた標準誤差というのは、偶然誤差を表す指標です。誤差には他に系統誤差が存在しており、これは統計処理で推定したり、取り除いたりすることはできません。

実は、勝率の推定の際にも系統誤差が生じる余地がありました。例えば、擬似乱数が偏っていたり、定期的に“何とかアップデート”が起動してマシンリソースが偏ったりするというようなことがあると、系統誤差が生じてしまい、それは統計処理で何とかなるものではありません。ただし、その時の系統誤差はあったとしても影響は少ないだろうと推測して省いていたわけです。

しかしながら、相対レートについては、相性の問題とイロレーティングの理論の問題があるために、系統誤差を無視することはできません。本来の相対レートというのは相性の問題を取り除いた上で評価されなければなりませんし、そもそもイロレーティングの理論で用いた仮定が妥当でなければ、有意義な値は出てきません。理論の部分については、そもそもイロレーティングを使うべきかという話になりますので、一先ず置いておくとしても、相性の問題は深刻です。

相性の問題については、今のところはデータが整理されておらず、各人の経験によって脳内補正するしかない状況であるようです。この問題については、機会がありましたら、改めて解析してみたいと考えています。

最後に、具体例で計算してみましょう。10000戦してAが8000勝したとします。すなわち、n = 10000、k = 8000です。この時の勝率の推定値は、\[q = \frac{8000}{10000} = 0.8\]となり、標準誤差は、\[S = \sqrt{\frac{10000}{10000 - 1.5}~ \times 0.8~ \times (1 - 0.8)}~~ \approx 0.004\]となります。相対レートの推定値は、\[dR = 400 \log_{10}(\frac{0.8}{1 - 0.8}) + K \approx 240.8 + K\]であり、その時の標準誤差は\[173.7 \times \frac{0.004}{0.8 (1 - 0.8)} \approx 4.3\]です。系統誤差Kについては、この情報からだけでは何も分かりません。

さて、以上の話は「nが十分に大きい」ということが前提になっていました。しかしながら、「十分に大きい」というのは具体的にどれくらいの大きさなのでしょうか? また、実験の都合により「十分ではないが、それなりに大きい」という場合には、何か別の処理方法があるのでしょうか? 次回は、その辺の話について書きたいと思います。

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

付記:中心極限定理の直感的な証明

以下の証明は直感的なもので厳密ではありません(※積率母関数を用いた弱収束の証明の簡易版です)。厳密な証明は統計学の教科書をご覧ください。

母集団の平均は0、標準偏差は1だとします。これは値の原点とスケールの取り方に対応しますので、一般性を失いません。

サンプル数nの無作為標本\[\{ x_{1}, x_{2}, \cdots, x_{n} \}\]の標本平均を\[M = \sum_{i = 1}^{n} \frac{x_{i}}{n}\]とします。

標本を何度も無作為に作り直す時、標本平均Mの期待値は、\[\big< M \big> = \sum_{i = 1}^{n} \frac{\big< x_{i} \big>}{n} = 0\]となります。ここで、母集団の平均が0であることを利用しました。

さらに、標本平均の2乗の期待値は、\[\big< M^{2} \big> = \sum_{i = 1}^{n} \sum_{j = 1}^{n} \frac{\big< x_{i} x_{j} \big>}{n^{2}} = \sum_{i = 1}^{n} \frac{\big< x_{i}^{2} \big>}{n^{2}} = \frac{1}{n}\]となります。ここで、無作為標本であることから、異なる2つの要素間の相関\[\big< x_{i} x_{j} \big>~~ (i \ne j)\]は0であるとしました。また、母集団の標準偏差が1であることを利用しました。

一般的に、同じ要素のペアだけが消えずに残ることから、m個の要素間の相関について、\[\sum_{i = 1}^{n} \sum_{j = 1}^{n} \sum_{k = 1}^{n} \cdots \sum_{l = 1}^{n} \big< x_{i} x_{j} x_{k} \cdots x_{l} \big>\]\[ = (m - 1) \sum_{i = 1}^{n} \big< x_{i}^{2} \big> \sum_{k = 1}^{n} \cdots \sum_{l = 1}^{n} \big< x_{k} \cdots x_{l} \big> (1 + O(1 / n))\]の分離定理が成立します。ここで、O(1 / n)は(1 / n)以下の項を表しており、具体的には、3つ以上の同じ要素の組み合わせから出てくる寄与のことを指しています。さらに、母集団の標準偏差が1であることから、\[(m - 1) \sum_{i = 1}^{n} \big< x_{i}^{2} \big> \sum_{k = 1}^{n} \cdots \sum_{l = 1}^{n} \big< x_{k} \cdots x_{l} \big> = (m - 1) n \sum_{k = 1}^{n} \cdots \sum_{l = 1}^{n} \big< x_{k} \cdots x_{l} \big>\]となります。

上の段落において、あらゆる異なる要素間の相関がゼロになるという「無作為」を仮定していること、並びに、m個の要素間の相関が発散せずに存在することを仮定していることに注意してください。これらの仮定は意外と自明ではありません。

nが十分に大きいとして、(1 / n)以下の寄与を無視すると、標本平均MのL次の積率\[\big< M^{L} \big>\]は、Lが奇数の時は0となり、Lが偶数の時には、L = 2 lとすると、\[\big< M^{2 l} \big> = \frac{1}{n^{l}} \prod_{j = 1}^{l} (2 j - 1)\]となります。

これらの積率は、確率分布が平均0、分散(1 / n)の正規分布であるとした場合のものと一致するため、nが十分に大きい時には、確率分布が正規分布となることが分かります。■

2016年5月3日~5日に第26回世界コンピュータ将棋選手権(WCSC26)が開催されます。今回の選手権は、参加者も多く、また、出場ソフトの平均レベルも大きく向上していると見込まれることから、熾烈な争いになるのではないかと予想されています。とりわけ、一次予選は8つの勝ち抜け枠を39チーム(4月17日現在)が争うという構図になっており、また、その中には優勝候補も複数含まれることから、初日から全く息の抜けない状況になっています。

世界コンピュータ将棋選手権(WCSC)は基本的に「スイス式」競技会であり、今回も一次予選からスイス式で争われることになります。今回は、WCSC一次予選を例としながら、スイス式について改めて考えてみたいと思います。

競技大会において、どのような組み合わせで競技を行い、順位をつければよいのかというのは昔から運営者の頭を悩ませてきた問題です。順位付けというと反射的にソートのアルゴリズム(仕組み)が頭に浮かぶ方も多いかと思われますが、競技大会の場合には、会場の都合や参加者・関係者の意向、プログラム進行の流れ、アクシデントへの対応等の様々な制約条件があるため、そう簡単にはいきません。特に、関係者の意向等は数値化できるものでもありませんので、必ずしも数学的な最適解があるというわけでもなく、最後は運営責任者の判断ということになります。

競技会の方式は、大きく分けて、勝ち抜き(ノックアウト)方式と集団(グループ)方式の2つがあります。

「勝ち抜き方式」というのは、いわゆる日本語の“トーナメント”のことであり、基本的に負けたら終わりという方式です(※敗者復活戦がある場合もあります)。優勝者を決めるのに試合数が少なくて済んだり、段々と候補者が絞られることで盛り上がりを演出できたりといった利点があります。

「集団方式」というのは、いわゆる日本語の“リーグ戦”のことであり、各回ごとに様々な対戦組み合わせで競技を行い、その最終的な勝敗で順位を決定します。特に、全員が総当りで対戦する総当りリーグ戦(ラウンドロビン式)は、対戦組み合わせが各参加者にとって対称的になるため、公平性の高い方式になっています。

今回の話題である「スイス式」は、集団方式の一種であり、対戦組み合わせ時に勝敗数等で選別を行って、総当りよりも少ない回数で決着をつけるという方式です。総当り戦では実力差が離れた対戦が数多く含まれてしまいますが、スイス式では、勝敗数の選別により、なるべく実力が近いもの同士を戦わせて、無駄なく順位付けが行われます。言わば、総当り戦のダイジェストのような形です。また、最後に強者同士の対決が行われることで、勝ち抜き方式の良さも取り込んでいます。

こうして見ると、スイス式は“いいとこ取り”で文句のない方式に思えるのですが、問題点もあります。それは、対戦組み合わせを決めるのが複雑であるという点です。勝ち抜き式やラウンドロビン式の対戦組み合わせは誰もが一目で分かるくらいに単純であり、大会前にくじ引き等で決めてしまえば、それで終わりです。一方で、スイス式の場合には、複雑な取り決めに基づいて、対戦結果を随時的に反映させつつ、対戦組み合わせを順次的に決めていかなければなりません。この過程が複雑であり、また透明性に欠けるというのが、スイス式がそれほど広まっていない要因になっていると思われます。

スイス式の実施方法は実際に複雑です。日本チェス協会の解説ページには、次のように記されています。

スイス式は単純のようで実際に組合わせに当って見ると意外に難しく経験が必要である。

スイス式はいずれのシステムにしても人間のためのプログラムは完結している。しかし、コンピュータプログラム化となるとアルゴリズムの記述が難しく、単純なシステムでさえ完全なものがない。人間がフィージィブルな恣意で誤魔化してしまうところはコンピュータは”とんでもない”(結局はそれが正しいことが多い)組み合わせが出現し、誰も納得しない。

このことは、筆者も今回の記事のために実際にプログラムを書いてみて実感しました。WCSC26のルールに詳細まで書かれていないのは、きちんと細部まで記そうとすると大変だからだと思われます。

具体的に、スイス式の実施には、以下のようなことを決めなければなりません。

  1. どの時点の勝敗数を用いるか:前回まで(完全スイス式)/前々回まで(変形スイス式、対戦中に次の組み合わせを決定可能)/3回戦のみ初回で他は前回まで(WCSC方式)。
  2. レーティングや予選順位等の事前情報を使うかどうか:モンラート式/オランダ式/マクマホン式等。
  3. 同一勝敗数内の順位の決め方。
  4. 同一勝敗数内の組み合わせ法:順接/逆接(ネスト)/隣接/間接等。
  5. 同一勝敗数内の余り者の決定と処理の方法。
  6. 過去対戦済みの組み合わせを排除するかどうか、また排除する場合には組み直しの方法。

特に、最後の部分の説明は意外と大変です。

スイス式が複雑だというのは、言い換えると、それだけルールの自由度が大きいということになります。それらの詳細なルールの組み合わせにより、それぞれどのような有利/不利が生じるのかというのは、さらに複雑な話になります。この辺の話は、WCSCの運営側の方々が研究されています(参照:「世界コンピュータ将棋選手権における対戦組み合わせシステムの有効性(6)」「シミュレーションに基づくスイス式トーナメント組み合わせ方式の評価」等)。

さて、ここでは、そのような詳細はさておいて、WCSCの一次予選を具体例として、7回戦スイス式が大まかにどのような性質を持っているのかを調べてみたいと思います。

計算する量は「実力レート上位8位以内の参加者が実際に何人、8位以内で勝ち抜けるかの期待値」です。参加者の実力レートの分布は、あるレート差の範囲内で一様ランダムとします。スイス式の詳細は、上述のWCSC26のルールと瀧澤先生の論文の記述に基づいて決めました。ただし、順位付けの決定方法は、簡単化のため、勝ち点、ソルコフ(全ての対戦相手の勝ち点の合計)までとして、それでも同点の場合はランダムになっています。対局はイロレーティングに基づく確率過程であるとして、引き分けは考えずに計算を行い、それぞれ10万回の競技会のシミュレーションに基づいて期待値を算出しています。イロレーティングについては、以下の解説記事をご覧ください。

まずは、スイス式の結果の前に、総当りリーグ戦ではどうなるのかを抑えておきましょう。

下図は、横軸が回数、縦軸がその回数までで終了した場合の上位8名の勝ち抜け期待値です。対戦順序はランダムになっており、回数が「参加者数 - 1」に到達すると総当りになります。

m-ev

全ての場合において、勝ち抜け期待値は、上限値である8に向かって、単調的に増加しています。

総当りの時の勝ち抜け期待値は、レート分布の抽出範囲のレート差が2000の場合、参加者が20名の時(青点)には約7.4であるのに対して、40名の時(黒点)には約7.1に下がっています。これは、参加者数が増えれば、その分だけ試合数を増やしたとしても、実力通りにいかないことが増えるということを意味しています。その主たる理由は、レート分布の抽出範囲が一定であるため、参加者数が増えると、参加者間の平均的なレート差が縮まるためだと考えられます。実際に、20名の参加者数に合わせてレート差を1000に調整した場合(水色点)には、総当りの時の勝ち抜け期待値は約7.1となって、黒点の場合とほぼ一致します。

WCSC26の一次予選の参加者数は約40名で、スイス式で7回戦を行います。この時の上位8名の勝ち抜け期待値を以下に示します。横軸は、レート分布の抽出範囲のレート差です。

dr-ev

総当りリーグ戦の結果(赤点)は、各参加者に対して対称的で回数も多いため、理論的な上限値を与えます。一方で、ランダムな順序で対戦する7回戦リーグ戦の結果(橙色点)は、それ以下の結果になってしまうとわざわざスイス式にする意味がないため、理論的な下限値を与えます。実際に、7回戦スイス式の結果(黒点)は、その中間に位置しており、7回戦リーグ戦を改善するものになっています。改善の度合いはレート差が大きいほど大きいようです。

この結果をWCSC26の一次予選に適用してみると、上位8名の内、6名程度が無事に予選を通過するだろうという予測になります。上位8名以外の参加者も2名程度が勝ち抜けるということになりますので、棋力的に多少不安があったとしても諦める必要はありません。「運も実力のうち」という言葉もあります。

最後に、設定ミス/遅刻/途中退場といったようなアクシデントによるノイズが加わった時にはどうなるかを示します。縦軸は40名、レート差2000の場合の勝ち抜け期待値であり、横軸はランダムで勝敗を反転させる確率(ノイズ)です。

pn-ev

全ての場合において、ほぼ線形に勝ち抜け期待値が減少していきます。この結果を見る限りは、方式によるノイズの影響の違いは少ないようです。

アクシデントは参加者当人にとってはしばしば深刻なものであり、特に強豪のアクシデントは印象的な結果をもたらすこともありますが、集団方式における統計的な期待値としては影響は大きくないと言えそうです。一般的に、アクシデントに対する頑強さは集団方式の特長とされています。

以上、WCSC一次予選を例としながら、スイス式について考えてみました。スイス式は複雑で手間のかかる方式ですが、同じ対戦回数のランダム順序のリーグ戦よりは優れています。スイス式競技会の裏には、少しでも大会をよくしようとする運営の方々の思いがあるのだと思われます。

  • ------------------

追記(2016年5月2日)

「竜の卵」の欠場により、一次予選の通過枠が8枠から9枠に増えたようです。その他の欠場もあり、結局のところ、36名中、9名が二次予選に進むことになるとのことです。

以下に参加者数と通過枠を修正した場合の図を示します。

dr-ev

  • ------------------

追記(2016年5月3日)

二次予選はスイス式9回戦で24名中、8名が通過します。この場合に対応する図は以下のようになります。

dr-ev

コンピュータ将棋の問題点としてよく挙げられるものに「水平線効果」(地平線効果とも言う)というものがあります。これは、「自らの探索の及ばない領域(水平線の先)に“落とし穴”がある時に、それに気付かずにその方向に進んでしまう」という問題のことであり、さらには、もっと意味を限定して、「長期的には損であるが無駄に手数がかかる手順によって“落とし穴”を探索領域外に押しやるような進行を選択してしまう」という問題のことを意味しています。コンピュータ将棋の探索については、以下の解説記事をご覧ください。

ここで注意が必要なのは、将棋ソフトが負けを読み切った際に行うことがある“王手ラッシュ”は、全て探索範囲内(水平線の手前)の読み筋ですので、厳密には水平線効果とは言わないということです。これは、単に手数を最大化するというプログラムがなされているというだけで、「問題」ではなくて「仕様」の話になります。ただし、将棋ソフトが負けを読み切って指しているのか、読み切れずに水平線効果が発動しているのかは、思考ログを見ないと傍からは分からないため(“即指し”等で推測はできますが)、判断が難しいということはあります。

さて、この水平線効果ですが、一体、何が問題なのでしょうか? この疑問は、一見すると自明に感じられますが、改めて考えてみると意外と複雑です。

元々、水平線効果が意味していたのは、深さを固定した探索の限界を表す問題だったと考えられます。深さ固定で頑張って探索しても、水平線の先は見えないのだから、長期的な大局観の不足を補うことはできないということであり、長期的な大局観を備えるためには、静的評価関数の精度向上や適切かつ十分な“探索延長”技術が不可欠であるというわけです。実際、コンピュータチェスにおいては、水平線効果への対策として、静止探索技術が発展したという経緯があります。

この意味に限定すると、問題点は技術的に明瞭であり、現代のコンピュータ将棋においては、既にほぼ克服済みの問題に思えます。現在の強豪ソフトの静的評価関数は、機械学習により、(例外的な局面はあるにせよ)十分な大局観を有していると考えられます。また、静止探索を含めて“探索延長”技術も大いに発展しており、有望そうな局面は倍近くの深さまで読むことも珍しくありません。もちろん、技術として更なる高みを目指すということはあるのでしょうが、水平線効果として当初、想定されていたレベルの問題としては、すでに十分に克服されているのではないかと思います。

しかしながら、水平線効果は別の問題としても解釈が可能です。

例えば、人工知能におけるフレーム問題の一種だという考え方もあります。「フレーム問題」というのは、「人工知能は自らの情報処理能力を超える情報は処理できないため、処理する情報を制限するフレームを外部から設定する必要がある」という問題のことです。人間の場合にはハードウエア(身体)が決まっているため、それによりフレームの限界は自動的に決まってくるわけですが、その制限がないコンピュータ将棋では持ち時間や探索範囲等のフレームを人間が設定する必要が出てきます。そして、設定されたフレーム(水平線)の外のことについては原理的に対応ができません。

このようにフレーム問題の一種として捉えると、水平線効果は、少なくても完全解析がなされるまでは、原理的に解決できない問題ということになり、また、この解釈においては、読み切りの局面を除き、ほとんどの将棋の指し手は水平線効果の産物ということになります。もしかすると、将棋は互いの水平線効果を楽しむゲームなのかもしれません。

また、将棋ソフトが勝負手を放てないのが水平線効果の問題の本質であるという考え方もあります。ミニマックス法では探索範囲内での最善手を目指すわけですが、この戦略こそが水平線効果が生じる根幹であるという考えです。自分が不利な状況であるのならば、もう負けるものと覚悟して、最善で粘りにいく戦略をやめて、紛れの多い局面に誘導するような戦略に切り替えるべきではないか、そうすれば結果的に水平線効果は出なくなるはずだというわけです。

この意見については、既存のコンピュータ将棋の戦略を大きく変えるものであるため、将来的に研究が進まないと何とも言えないところです。しかしながら、ミニマックス戦略が最善の戦略であるという保証はありませんので、将来的にもっと優れた戦略が開発される可能性はあります。その戦略においては、ここでの解釈における水平線効果は現れないかもしれません。

さらに、コンピュータが「長期的には損であるが無駄に手数がかかる手順」(以下、“無駄な手順”)を認識できないのが水平線効果の問題の本質であるという考え方もあります。この考え方に立つと、静的評価関数の精度向上や探索延長技術は対処療法的に問題を発現し難くしているだけにすぎず、本質的な解決にはなっていないということになり、また、“無駄な手順”をどのように定義して判定するのかという問題が解決されない限りは水平線効果は無くならないということになります。

この解釈を説明するための簡単な具体例として、“ただ捨て”の問題を考えてみましょう。

tadasute

上の部分図のように、歩を打って、そのまま成り捨てるという手順は、4手かけて歩を相手に渡すだけの進行になっています。盤面は同じで歩を相手に渡しているので明らかに損になる手順ですが、4手先延ばしすることで、水平線効果により、それ以上の損が見えなくなるのならば、結果的に“最善手”に選ばれてしまうことがありえます。実際、昔の弱い将棋ソフトではよく見られた手順です。

また、この手順の最中に必然手の応酬が挟まれる場合も同様です。この場合には、最初と最後で盤面も変わってくることになりますが、手順全体で見れば、“ただ捨て”の4手は無駄であると判断できます。

ある程度の棋力を有する人間ならば、このような“ただ捨て”の筋は“無駄な手順”だと判断して読みから切り捨てることができます。人間が“ただ捨て”の筋を考えるのは、持ち時間が足りなくて思考時間を稼ごうとする時くらいです。

コンピュータ将棋においては、「駒損を含む手順の探索を延長する」等の対策により、この問題を回避することができます。しかしながら、これらの探索延長の手法は、実践的には有効ではあるものの、人間とは異なり、“無駄な手順”を認識して対処しているわけではありません。

単に盤面が同じで持ち駒が異なる場合(「強度の水平線効果」と言う)を“無駄な手順”と判定して弾くだけであれば、簡単に実装することができます(参照:「強度の水平線効果を完全に防ぐ手法の提案」)。実際に、この手法(SHEK: Strong Horizon Effect Killer)では中盤以降で0.3~3%程度の局面の枝刈りができるようです。

しかしながら、「強度の水平線効果」を越えて、もっと広く“無駄な手順”を判定しようとすると処理が大変になります。手順を含めた情報が必要になるため、判定処理が複雑になってしまいますし、そもそも判定自体が難しいという状況も珍しくありません。例えば、中合いが、手数を伸ばすだけの無駄合いなのか、それとも駒を引き付けておくことで長手数後に本当に得をする合駒なのかというのは、簡単には分からないことがあります。また、追い詰められての王手や詰めろが、単に手数を伸ばすだけの暴発のなのか、それとも暴れることでどこかで相手の攻め駒を抜いたり、必要な持ち駒を減らしたりできるのかというのも同様です。しかも、判定処理の計算量が探索延長分の計算量を上回ってしまうようでは実用上の意味がないため、利用できる計算量にも制限があります。

“無駄な手順”を判定して弾くということは、「未来の挙動が、現在の局面情報のみで決まらず、過去の情報にも依存する」ということを意味しています。これを確率論では「非マルコフ性」と言います。現在のコンピュータ将棋は、千日手の処理やSHEK等を除いては、現在の局面情報に基づく処理が基本になっているため、“無駄な手順”の認識が難しいという状況になっているわけです。

そのように一般化して捉えると、水平線効果の本質は将棋の非マルコフ性にあるという考え方もできます。コンピュータ将棋の探索や機械学習において非マルコフ性を取り扱うというのは、一つの将来的な課題であり、この解釈における水平線効果はそのような研究の発展の中で解決されていくものなのかもしれません(※強度の水平線効果が終盤に多く現れるということから類推すると、もし実現すれば、終盤力の向上につながる可能性があります)。

以上、今回は、水平線効果の問題の所在について改めて考えてみました。何が問題なのかについては、

  • 当初の問題
  • フレームの問題
  • 戦略の問題
  • “無駄な手順”の問題(もしくは、将棋の非マルコフ性の問題)

というような複数の解釈が存在し、どの解釈に立つのかによって問題の性質が変わってきます。水平線効果について議論する際には、どのような問題について考えているのかを明確にした方がよいのかもしれません。

このページのトップヘ