【真実】 将棋 局面数 計算方法 【本当】
いったい合法な将棋の局面は本当は正確にいくつあるのかいくつあるのか気になって気になって眠れないorz
局面は羊のかわりにならない
完全解決するべく、改めて基本に立ち返ってみれり
基本手順
数え上げ対象の集合をΩとしたときに、重複も漏れもない数え上げは次のようにして行う。
- Ωを互いに背反な部分集合T_1, T_2, T_3, ..., T_nに分解できるときは、T_kそれぞれの元を数え上げ、結果を全て足し合わせる。
- Ωを集合F_1, F_2, F_3, ..., F_mの積集合に1対1対応できるときは、F_kそれぞれの元を数え上げ、結果を全て掛け合わせる。
- Ωについて上記のようなT_kやF_kを見出せないなら、（仕方なく）Ωの内容を具体的に列挙して数え上げる。
- 必要ならT_kやF_kを改めてΩとみなし、上記数え上げを再帰的に行う。
道具立て
いま、k種類の置駒がそれぞれr_1, r_2, ..., r_k個あるとして、これら全てをnマスに並べる方法の数g(n, k, { r_k })は次式で与えられる。
g(n, k, { r_k }) = CMB(n, r_1) * CMB(n - r_1, r_2) * ... * CMB(n - r_1 - r_2 - ... - r_(k-1), r_k)
= PRM(n, r_1 + r_2 + ... + r_k) / (r_1! * r_2 * ... * r_k)
ここでCMB(n, r)はn個のものから順序を区別せずにr個取り出す組み合わせ（コンビネーション）の数、PRM(n, r)はn個のものから順序を区別してr個取り出す方法（順列）の数。
一方、k種類の駒の個数の上限がそれぞれc_1, c_2, ..., c_kとして所与のとき、種類毎に可能な駒の個数(r_1, r_2, .., r_k)は、次のアルゴリズムで次々列挙できる（Perl風擬似コードで示す）。
use strict;
### { r_k }を初期化します。
sub init_cnt_vec(\@) {
our (@c, @r);
local (*c, *r) = @_;
$r[0] = undef;
}
### 可能な{ r_k }を列挙します。
sub move_next_cnt_vec(\@\@) {
our (@c, @r);
local (*c, *r) = @_;
if (!defined $r[0]) {
for (my $i = 0; $i < @c; ++$i) { $r[$i] = 0 }
return ($r[@c] = 1);
}
if (!$r[@c]) { return 0 }
my $i;
for ($i = 0; $i < @c; ++$i) {
if (++($r[$i]) < $c[$i]) { last }
$r[$i] = 0;
}
my $suc = ($i < @c);
return ($r[@c] = $suc);
}
my @c = (2, 3, 4); # テスト
my @r;
init_cnt_vec(@r);
while (move_next_cnt_vec(@c, @r)) { # ちょっとだけコルーチン風、
print "r[]=(@r)\n";
}なお配列@cが{ c_k }, @rが{ r_k }にそれぞれ対応する。
以下、上記手段を用いて順序だてて数え上げていく。
駒の区別
{ FU, KY, KE, GI, KI, KA, HI, OU } × { プレイヤーA, プレイヤーB }の16種類とする。
駒ごとの個数(c_1, c_2, ..., c_16)が決まる。
持駒、置駒の区別
目的の数え上げは＜持駒とする駒の組み合わせ＞毎の小問題に分解でき、分解後の個々の小問題において、数え上げ対象の集合は { 持駒を駒台A/Bに置く組み合わせ }×{ 置駒を盤に置く組み合わせ }と1対1でありる。（最後に掛け合わせれば良い。次に、小問題毎に足し合わせれば良い。）
なお、置駒と持駒の種類毎の個数の上限は(c_1, c_2, ..., c_16)という制約があるから、置駒とする個数(r_1, r_2, ..., r_16)を選んだとき、持駒の個数は自動的に(c_1 - r_1, c_2 - r_2, ..., c_16 - r_16)となることに注意。(r_1, r_2, ..., r_16)は上で述べた方法で列挙できる。
持駒を駒台A/Bに置く組み合わせの数え上げ
所与の持駒の個数(h_1, h_2, ..., h_16)=(c_1 - r_1, c_2 - r_2, ..., c_16 - r_16)の下で、持駒をAの駒台とBの駒台に割り振る組み合わせの数は
(h_1 + 1) * (h_2 + 1) * (h_3 + 1) * ... * (h_16 + 1)
である。（数え上げ完了。）
二歩の禁止（二歩以外の全てを正確に数える）
所与の置駒の個数(r_1, r_2, ..., r_16)の下で可能（合法）な置駒配置は、プレイヤーAの歩が筋1に1個だけ存在する/全く存在しない、筋2に1個だけ存在する/全く存在しない、....の2^9通りの場合に分解できる。さらにプレイヤーBの歩についても同様に分解を進めると、あわせて2^18通りの場合に分解できる。それぞれについて数え上げれば良い。（最後に足し合わせる。）
なお、プレイヤーAの歩が筋1に1個だけ存在する前提での数え上げは、(r_1, r_2, ..., r_16)から歩兵以外の最大8個の駒を選ぶ組み合わせ毎の小問題に分解できry
、、、
、、、
、、、
、、、まあこの伝でやっていけば、合法局面の全てを正確に数え上げられるのは明らかだが*1、なんつーか組み合わせ爆発で計算量的にこの時点ですでに駄目そうorz
もうちょっっっっっっっとブレイクスルーが要るっぽい、
基本手順は変わらないにしても、もっとうまい分解の仕方的な何かがががが、
