思うだけで学ばない日記 2.0

思うだけで学ばない日記から移転しました☆！よろしくお願いします。

将棋 局面数 計算方法

AI

エデンの園配置の除外とか考えずに、単純に可能な駒の配置を重複無く数え上げるには、次のように考えれば良い*1
【追記】ｺｿｰﾘ直させていただきましたorz　そして補足が有ります（末尾の追記参照）。
【追記2】置駒の配置の数え上げの式がまちｶﾞｯﾁｮﾙorz
修正範囲甚大のためこのエントリは無かったことになりました。→誘導】

駒の分類

駒の種類（駒タイプ）は歩兵(FU)、香車(KY)、桂馬(KE)、銀将(GI)、金将(KI)、角行(KA)、飛車(HI)、王将(OU)の8種類。
これらは、次の2項で分類できる。

  1. 成る可能性の有無（KIとOUのみ成り得ない）
  2. 持駒の可能性の有無（OUのみ持駒になり得ない）

盤上の駒配置

盤にr個の駒を並べる方法の数は、そのr個の内訳によらずPMT(81,r)。ここでPMT(n,r)は順列。・・・(1)
ただし成れる駒については生駒と成駒の区別が要るから、それらが含まれる状況ではP(81,r)だけでは済まない。これは再帰などして分割して計算する必要がある。・・・(1')

持駒の扱い

駒タイプtのうち、持駒であるものの個数をj[t]と書くとして、j[t]個を対局者A/Bの駒台に割り振る方法はj[t]+1通り。
駒タイプtがFU〜OUの8種類なら、割り振る方法はトータルで(j[FU]+1)*(j[KY]+1)*...*(j[OU]+1)通り*2。・・・(2)

で、合わせるとどうなるのよ？

駒タイプ毎の持駒の個数j[]が決まれば、駒タイプ毎の置駒の個数も決まる。よってそれぞれのケースについて、盤に置駒を並べる方法の数(1')を計算して求め、さらに持駒の割り振り方法の数(2)を掛け、それらを全部足し合わせれば良い。
プログラムにすると約こんあ感じ（Ver.1→Ver.2修正済）

use strict;
use bigrat;
local $[ = 0;

# マス数
sub ncells() { 81 }

# 駒の個数
my %num_dic = (
    FU  => 2 * 9,
    KY  => 2 * 2,
    KE  => 2 * 2,
    GI  => 2 * 2,
    KI  => 2 * 2,
    KA  => 2 * 1,
    HI  => 2 * 1,
    OU  => 2 * 1,
);

# フラグ
sub pr()  { 1 << 0 }    # 盤上に成駒として存在可能
sub ha()  { 1 << 1 }    # 駒台上に存在可能

# 駒の属性辞書
my %attr_dic = (
    FU  => ha | pr,
    KY  => ha | pr,
    KE  => ha | pr,
    GI  => ha | pr,
    KI  => ha,
    KA  => ha | pr,
    HI  => ha | pr,
    OU  => 0,
);

# 駒の種類の一覧表
my @ktyps = sort keys %attr_dic;

# 駒の一覧表
my @ktab;

# %num_dicから@ktabを構築します。
sub reconfig_ktab() {
    my $kid = 0;
    foreach my $typ (keys %num_dic) {
        for (my $n = $num_dic{$typ}; $n > 0; --$n) {
            $ktab[$kid++] = $typ;
        }
    }
}

### 盤に置く組み合わせの数を返します。
### 第1引数: 駒ID
### 第2引数: 盤の占有済みマス数
sub count_on_board($$) {
    my ($kid, $used) = @_;

    if ($kid > $#ktab) { return 1 }

    my $typ = $ktab[$kid];

    my $n = ncells - $used;
    if (($attr_dic{$typ} & pr) != 0) { $n *= 2 }
    return ($n * count_on_board($kid + 1, $used + 1));
}

### 持駒の可能性も含めた全ての組み合わせの数を返します。
sub count_total($) {
    my $typidx = $_[0];

    if ($typidx > $#ktyps) {
        reconfig_ktab();
        my $k = count_on_board(0, 0);
        #print "*** ktab[]=(@ktab), k=$k\n";
        return $k;
    }

    my $cnt = 0;

    my $typ = $ktyps[$typidx];
    my $max = $num_dic{$typ};
    if ($max == 0) {                            # (非使用の駒(駒箱内))
        return count_total($typidx + 1);
    } elsif (($attr_dic{$typ} & ha) != 0) {     # (持駒になり得る)
        for (my $i = 0; $i <= $max; ++$i) {
            $num_dic{$typ} = $i;                # $i := 盤上にある駒タイプ$typの個数
            my $j =$max - $i;                   # $j := AかBの駒台上にある駒タイプ$typの個数
            my $k = count_total($typidx + 1);
            my $m = $j + 1;                     # 持駒のA/B分配の組み合わせの数
            my $n = $m * $k;                    # 駒台と盤を合わせた組み合わせの数
            #print " " x $typidx, "$typ($i:$j) : n=$m*$k=$n\n";
            $cnt += $n;
        }
    } else {
        $cnt = count_total($typidx + 1);
    }

    return $cnt;
}

my $cnt = count_total(0);
print "\n";

reconfig_ktab();
print "ktab[]=(@ktab)\n";
print "count=$cnt\n";

結果（Ver.1→Ver.2修正に伴い変更）

ktab[]=(KA KA HI HI OU OU KY KY KY KY KI KI KI KI GI GI GI GI FU FU FU FU FU FU FU FU FU FU FU FU FU FU FU FU FU FU KE KE KE KE)
count=568653387724571072712889502009589997851755039888069797880015921288706902252988007494000

検算（Ver.1→Ver.2修正では変化無し）

下記結果ではテスト用のメッセージをONにしている。例：KI(0:2)とは、KIの置駒0個、持駒2個の意。
(1) OU 2個のとき:

*** ktab[]=(OU OU), k=6480

ktab[]=(OU OU)
count=6480

(2) KI 2個のとき:

     KI(0:2) : n=3*1=3
*** ktab[]=(KI), k=81
     KI(1:1) : n=2*81=162
*** ktab[]=(KI KI), k=6480
     KI(2:0) : n=1*6480=6480

ktab[]=(KI KI)
count=6645

(3) GI 2個のとき:

 GI(0:2) : n=3*1=3
*** ktab[]=(GI), k=162
 GI(1:1) : n=2*162=324
*** ktab[]=(GI GI), k=25920
 GI(2:0) : n=1*25920=25920

ktab[]=(GI GI)
count=26247

まあとりあえず無問題っぽい。

追記（2010-10-17 15時頃）

count_total()内に余計な条件分岐が放置されてたorz；

           my $k = ($i > 0) ? count_total($typidx + 1) : 1;

は、

           my $k = count_total($typidx + 1);

でないとおかしい。上述のコードと結果は差し替え済み。駒1種類の検算結果は変更無し。

あと、修正前コードも修正後コードも、生駒の移動禁止マスを考慮しない。（例えば歩兵が敵陣最奧にいるという反則局面も1局面として数えている。）これの除外は…ちょっと場合分けがめんどくさげなので今回は堪忍ということで仕様とさせていただきます。
なんで難しいかというと、歩兵xを盤に置く前にすでに盤上に存在するn個の駒のうち、敵陣最奧部の駒の個数をn1、そうでない駒の個数をn2として、

  • 上記反則局面も含めて数えて良いなら、xを置く可能性は81-(n1 + n2)通りでn1とn2の組み合わせとは非依存に求められるので簡単
  • 上記反則局面を含めないなら、xを置く可能性は81-8-n2通りであり、n1とn2の組み合わせに依存するので難しい、

というしくみ。
いやよく考えたら、上記反則局面を除外しない数え上げ結果から系統立った方法で上記反則局面を差し引くことができるかもしれないけども、何か間違いそうなのでパス。
いやさらによく考えたら、二歩を含む局面も同様に数えてしまっていますなorz

検算（駒2種類）

(1) GI 1個、KI 1個

*** ktab[]=(), k=1
     KI(0:1) : n=2*1=2
*** ktab[]=(KI), k=81
     KI(1:0) : n=1*81=81
 GI(0:1) : n=2*83=166
*** ktab[]=(GI), k=162
     KI(0:1) : n=2*162=324
*** ktab[]=(KI GI), k=12960
     KI(1:0) : n=1*12960=12960
 GI(1:0) : n=1*13284=13284

ktab[]=(KI GI)
count=13450

多分問題なさげ。

*1:いや知らんけど。

*2:もっとも、OUは持駒になり得ないから常にj[OU]=0だが。