Miyako Shogi System

■ 手生成ベンチマーク

ベンチマークができる程度になってきたので色々測ってみた。上記の後手番での手生成回数。

コンパイラ別

CPU:phenom II 3.2GHz

CPU別(コンパイラ gcc 4.6,4.7)

SIMD命令はまだうまく書けて無いようなので、参考までに。実はconroeを測定したときに古くて遅いCPUなのに、結構いいスコアをたたき出したので、急遽core i3を買ってきた次第。bfs/brs命令がAMDは遅いためbitboardでは不利と見た。

■ bitboardによる手生成の実装方法

bitboardによる銀の移動手のコード例としては、

org=p->bitboard[BLACK][P_GIN];  // 先手の銀のbitboard
while ( test128(org) ) {  // 駒がある
  from=bit_pop1st(&org);  // 駒位置
  and128(t,attack_gin_b[from],target);  // 先手銀の利きのbitboardを押し付ける
  while ( test128(t) ) {  // 利きのある数
    to=bit_pop1st(&t); // 移動先の位置
    pin_check()
    手の格納
  }
}

というふうになるであろう。上記コードにおいて、test128()はbitboardがゼロか非ゼロかをテストする関数である。

bit_pop1stはbitboardのLSBから立っているビット位置を返し、そのビットをクリアする関数である。32ビット版では次のようなコードとなっている。

bit_pop1st(BITBOARD *x)
{
int pos;
  if ( x->l ) {
    pos=__builtin_ctz(x->l);
    x->l&=(x->l-1);     // reset bit
    return pos;
  }
  else if ( x->m ) {
    pos=__builtin_ctz(x->m)+32;
    x->m&=(x->m-1);     // reset bit
    return pos;
  }
  pos=__builtin_ctz(x->h)+64;
  x->h&=(x->h-1);     // reset bit
  return pos;
}

_builtin_ctzはLSB側から'1'のビット位置を返す関数。x86ではbsf命令で展開される。

■ 駒を取らない移動手王手の生成

静止探索内では駒を取る手、駒を取らない王手を生成している。

bitboardによる隣接王手生成

たとえば52に王がいるとして銀の利きデータを貼り付ける
９ ８ ７ ６ ５ ４ ３ ２ １
 0  0  0  1  0  1  0  0  0 一
 0  0  0  0  K  0  0  0  0 二
 0  0  0  1  1  1  0  0  0 三
 0  0  0  0  0  0  0  0  0 四
 0  0  0  0  0  0  0  0  0 五
 0  0  0  0  0  0  0  0  0 六
 0  0  0  0  0  0  0  0  0 七
 0  0  0  0  0  0  0  0  0 八
 0  0  0  0  0  0  0  0  0 九

ビットの立った位置に銀の利きがあれば王手となる

74に地点に銀がいるとして、銀の利きは

９ ８ ７ ６ ５ ４ ３ ２ １
 0  0  0  0  0  0  0  0  0 一
 0  0  0  0  K  0  0  0  0 二
 0  1  1  1  0  0  0  0  0 三
 0  0  S  0  0  0  0  0  0 四
 0  1  0  1  0  0  0  0  0 五
 0  0  0  0  0  0  0  0  0 六
 0  0  0  0  0  0  0  0  0 七
 0  0  0  0  0  0  0  0  0 八
 0  0  0  0  0  0  0  0  0 九

上記のbitboardに銀の利きをandして

９ ８ ７ ６ ５ ４ ３ ２ １
 0  0  0  0  0  0  0  0  0 一
 0  0  0  0  K  0  0  0  0 二
 0  0  0  1  0  0  0  0  0 三
 0  0  S  0  0  0  0  0  0 四
 0  0  0  0  0  0  0  0  0 五
 0  0  0  0  0  0  0  0  0 六
 0  0  0  0  0  0  0  0  0 七
 0  0  0  0  0  0  0  0  0 八
 0  0  0  0  0  0  0  0  0 九

63の地点が王手の手となる

■ 駒打ち王手生成

たとえば52に王がいるとして銀の利きデータを貼り付ける
９ ８ ７ ６ ５ ４ ３ ２ １
 0  0  0  1  0  1  0  0  0 一
 0  0  0  0  K  0  0  0  0 二
 0  0  0  1  1  1  0  0  0 三
 0  0  0  0  0  0  0  0  0 四
 0  0  0  0  0  0  0  0  0 五
 0  0  0  0  0  0  0  0  0 六
 0  0  0  0  0  0  0  0  0 七
 0  0  0  0  0  0  0  0  0 八
 0  0  0  0  0  0  0  0  0 九

ビットの立った位置に銀を打てば王手となる