Miyako Shogi System

■ 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命令で展開される。