Miyako Shogi System

■ Stockfishの探索

PV search

ハッシュを見る スコアが使えるなら使う(真値のみ)
ハッシュの手があり,王手がかかっていないなら現局面の評価値を求め,ハッシュに登録する...(1)
Internal iterative deepening
手生成
for 手の数
  Singular extension
  手で局面更新
  LMR判定...(2)
  探索
  局面戻す
  betaカット判定
ハッシュ登録

非PV search

ハッシュを見る スコアが使えるなら使う
ハッシュの手があり,王手がかかっていないなら現局面の評価値を求め,ハッシュに登録する
Razoring
Reverse Futility Pruning
Null move search
  if (nullValue >= beta)
    再探索してbetaを上回るならその値を返す
ProbCut
Internal iterative deepening
手生成
for 手の数
  Singular extension
  枝刈...(3)
    Move count based pruning...(4)
    Futility Pruning...(5)
    残り深さが少なくSEEが負なら刈る
  手で局面更新
  LMR判定
  探索
  局面戻す
  betaカット判定
ハッシュ登録

qsearch

ハッシュを見る スコアが使えるなら使う
ハッシュの手があり,王手がかかっていないなら現局面の評価値を求め,ハッシュに登録する
Stand pat Return
手生成
for 手の数
  Futility Pruning
    futilityBase+取った駒の価値 < beta なら刈る
    futilityBase < beta かつ SEEが負なら刈る
  王手を受けていない または 王手を受けていて駒を取らない手 ハッシュの手でなく SEE負なら枝刈
  手で局面更新
  qsearch
  局面戻す
  betaカット判定
ハッシュ登録

(1)ハッシュの手があるということはすでに探索済なのでこれはうまい工夫

(2)残り深さ,PV/非PV,improving,オーダリング順位で縮退する深さを変えている.improvingは3手前の局面より評価値が上がっている状態.

(3)王手がかかっている局面,重大な手,成る手取る手,threatMove,refutesは刈らない.

重大な手...王手,次にPAWNが成る手,キャスリング

threatMove...1手先のcurrentMoveがある...Null move searchで相手に有効な手があった

refutes...刈ってはならない手の判定.threatMoveですぐ取られる手.threatMoveで駒損.自分が動いた後に相手の駒が来る.利き変化.影利き変化.safe moves which block the threat path.

(4)残り深さ,PV/非PV,improving,オーダリング順で刈る数を変えている.

(5)残り深さでマージンを変えている.

■ SSEによるbitboardの実装の検討

bitboardによる先手銀の駒を取らない移動手のコードは、

org=p->bitboard[BLACK][P_GIN];                  // 銀
while ( (from=bit_pop1st(&org)) >= 0 ) {
  and128(t,attack_gin_b[from],target);
  mt=from+(P_GIN<<14);
  while ( (to=bit_pop1st(&t)) >= 0 ) {
    pin_check()
    *p_move++=mt+(to<<7);
    if ( (to <= 26) || (from <= 26) ) *p_move++=mt+(to<<7)+PROMOTE_BIT;
  }
}

bit_pop1stはbitboardのLSBから立っているビット位置を返し、そのビットをクリアする関数である。bitboardが全てゼロのときは-1を返すようにした。

static inline int
bit_pop1st(BITBOARD *x)
{
int pos=-1;
#ifdef  __x86_64__
  if ( x->l64 ) {
    pos=__builtin_ctzll(x->l64);
    x->l64&=(x->l64-1); // reset bit
  }
  else if ( x->h64 ) {
    pos=__builtin_ctzll(x->h64)+64;
    x->h64&=(x->h64-1); // reset bit
  }
#else
  if ( x->l ) {
    pos=__builtin_ctz(x->l);
    x->l&=(x->l-1);     // reset bit
  }
  else if ( x->m ) {
    pos=__builtin_ctz(x->m)+32;
    x->m&=(x->m-1);     // reset bit
  }
  else if ( x->h ) {
    pos=__builtin_ctz(x->h)+64;
    x->h&=(x->h-1);     // reset bit
  }
#endif
  return pos;
}

SSE2ではand128などの128bit論理演算が可能である。

#define zero128(r)       (r).x=_mm_xor_si128((r).x,(r).x)
#define and128(r,a,b)    (r).x=_mm_and_si128((a).x,(b).x)
#define or128(r,a,b)     (r).x=_mm_or_si128((a).x,(b).x)
#define xor128(r,a,b)    (r).x=_mm_xor_si128((a).x,(b).x)
#define andnot128(r,a,b) (r).x=_mm_andnot_si128((b).x,(a).x)
#define andor128(r,a,b)  (r).x=_mm_or_si128((r).x,_mm_and_si128((a).x,(b).x))

SSE4では次の比較関数も使える。Zフラグに結果が入る。

#define test128(a)       (!_mm_testz_si128((a).x,(a).x))
#define andtest128(a,b)  (!_mm_testz_si128((a).x,(b).x))

上記手生成コードでSIMD命令が有効となるのはand128であろう。後の命令は非SIMD命令であり、SIMDレジスタと通常レジスタの移動のオーバーヘッドがあるだろう。

■ 手生成ベンチマーク

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

コンパイラ別

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 九

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

■ 交換値計算

ある位置に来ることが可能な駒のビットボードを求める(AttackPieces関数)

// 隣接の利き(先手)
and128(attack,p->bitboard[BLACK][P_FU],pos2bb[pos+9]);          // 歩
andor128(attack,p->bitboard[BLACK][P_KEI],attack_kei_w[pos]);   // 桂
andor128(attack,p->bitboard[BLACK][P_GIN],attack_gin_w[pos]);   // 銀
andor128(attack,p->bitboard[BLACK][P_N_FU],attack_kin_w[pos]);  // と
andor128(attack,p->bitboard[BLACK][P_N_KYO],attack_kin_w[pos]); // 杏
andor128(attack,p->bitboard[BLACK][P_N_KEI],attack_kin_w[pos]); // 圭
andor128(attack,p->bitboard[BLACK][P_N_GIN],attack_kin_w[pos]); // 全
andor128(attack,p->bitboard[BLACK][P_KIN],attack_kin_w[pos]);   // 金
andor128(attack,p->bitboard[BLACK][P_OU],attack_ou[pos]);       // 王
andor128(attack,p->bitboard[BLACK][P_N_KAKU],attack_uma[pos]);  // 馬
andor128(attack,p->bitboard[BLACK][P_N_HISH],attack_ryu[pos]);  // 竜

// 隣接の利き(後手)
andor128(attack,p->bitboard[WHITE][P_FU],pos2bb[pos-9]);        // 歩
andor128(attack,p->bitboard[WHITE][P_KEI],attack_kei_b[pos]);   // 桂
andor128(attack,p->bitboard[WHITE][P_GIN],attack_gin_b[pos]);   // 銀
andor128(attack,p->bitboard[WHITE][P_N_FU],attack_kin_b[pos]);  // と
andor128(attack,p->bitboard[WHITE][P_N_KYO],attack_kin_b[pos]); // 杏
andor128(attack,p->bitboard[WHITE][P_N_KEI],attack_kin_b[pos]); // 圭
andor128(attack,p->bitboard[WHITE][P_N_GIN],attack_kin_b[pos]); // 全
andor128(attack,p->bitboard[WHITE][P_KIN],attack_kin_b[pos]);   // 金
andor128(attack,p->bitboard[WHITE][P_OU],attack_ou[pos]);       // 王
andor128(attack,p->bitboard[WHITE][P_N_KAKU],attack_uma[pos]);  // 馬
andor128(attack,p->bitboard[WHITE][P_N_HISH],attack_ryu[pos]);  // 竜

// 飛び利きについて調べる(先手)
or128(hish,p->bitboard[BLACK][P_HISH],p->bitboard[BLACK][P_N_HISH]);  // 飛&竜
or128(hish_kyo,hish,p->bitboard[BLACK][P_KYO]);  // 飛&竜&香
or128(kaku,p->bitboard[BLACK][P_KAKU],p->bitboard[BLACK][P_N_KAKU]);  // 角&馬

slider_r(slider_n,slider_s,hish)        // 飛び利き(N)
slider_f(slider_s,slider_n,hish_kyo)    // 飛び利き(S)
slider_r(slider_e,slider_w,hish)        // 飛び利き(E)
slider_f(slider_w,slider_e,hish)        // 飛び利き(W)
slider_r(slider_ne,slider_sw,kaku)      // 飛び利き(NE)
slider_r(slider_nw,slider_se,kaku)      // 飛び利き(NW)
slider_f(slider_se,slider_nw,kaku)      // 飛び利き(SE)
slider_f(slider_sw,slider_ne,kaku)      // 飛び利き(SW)
 
// 飛び利きについて調べる(後手)
or128(hish,p->bitboard[WHITE][P_HISH],p->bitboard[WHITE][P_N_HISH]);  // 飛&竜
or128(hish_kyo,hish,p->bitboard[WHITE][P_KYO]); // 飛&竜&香
or128(kaku,p->bitboard[WHITE][P_KAKU],p->bitboard[WHITE][P_N_KAKU]);  // 角&馬

slider_r(slider_n,slider_s,hish_kyo)    // 飛び利き(N)
slider_f(slider_s,slider_n,hish)        // 飛び利き(S)
slider_r(slider_e,slider_w,hish)        // 飛び利き(E)
slider_f(slider_w,slider_e,hish)        // 飛び利き(W)
slider_r(slider_ne,slider_sw,kaku)      // 飛び利き(NE)
slider_r(slider_nw,slider_se,kaku)      // 飛び利き(NW)
slider_f(slider_se,slider_nw,kaku)      // 飛び利き(SE)
slider_f(slider_sw,slider_ne,kaku)      // 飛び利き(SW)

return attack;

交換値を求める

attacker=AttackPieces(to);          // toに来る駒のリスト
if ( !test128(attacker) ) return 0;     // 来る駒がないなら終了

turn=( piece & B_BIT ) ? WHITE : BLACK;     // toにいる駒の反対の手番
piece=PIECE_TYPE(piece);
v=piece_value[piece];
list[0]=0;
from=to;

for ( depth=0; depth < 18; ) {  // 八方+角2枚+飛2枚+香4枚+桂2枚+=18
  from=SQUARES;
  toに来れるもっとも価値の低い駒(from)を探す
  駒がなくなったら打ち切り
  王を取られる手なら打ち切り
  list[depth+1]=-list[depth]+v;       // 交換値のリスト
  v=toにいる駒の価値
  depth++;
  成れる駒は成っておく
  動いた駒があるときはその方向に飛び利きを伸ばしtoに来る駒のリストに追加
  turn^=1;  // 手番変更
}

listから最大の値を返す

■ 王手とピン駒の求め方

隣接による王手は王の位置に相手駒の利きをorすれば良い

pos=bit_fscan(p->bitboard[BLACK][P_OU]);        // 王の位置

and128(stack->check,p->bitboard[WHITE][P_FU],pos2bb[pos-9]);          // 歩
andor128(stack->check,p->bitboard[WHITE][P_KEI],attack_kei_b[pos]);     // 桂
andor128(stack->check,p->bitboard[WHITE][P_GIN],attack_gin_b[pos]);     // 銀
andor128(stack->check,p->zenkin[WHITE],attack_kin_b[pos]);              // 金・成金
andor128(stack->check,p->bitboard[WHITE][P_N_KAKU],attack_uma[pos]);    // 馬
andor128(stack->check,p->bitboard[WHITE][P_N_HISH],attack_ryu[pos]);    // 竜

stack->checkには王への利きが入っている。

飛び利き王手は、たとえば飛車の横利きで王手されている時、

K0000000R

王からの利きデータで飛車の位置を出す(to)

王の位置からと飛車の位置までの間の枡を求める

011111110

これと全駒位置とandをとる(between)

もし立っているビット数が0なら間に駒が無いので、飛び利き王手である

もし立っているビット数が1ならピン駒である(自分の駒か相手の駒かの判定は不必要、手生成の時相手の駒は動かせない)

betweenは王手を受けるとき使うので保存しておく(合駒位置である)

and128(t,slider_attack[pos],piece);   // 飛び利きをしている駒を探す
if ( test128(t) ) { // 飛び利きをしている駒があった
BITBOARD    between, pin;
  to=bit_rscan(t); // 飛び利きをしている駒の位置
  and128(between,slider_attack[pos],slider_opposite[to]);   // 間のマスを抽出
  and128(pin,between,p->occ);   // 間の駒を抽出
  n=bit_popcount(pin);    // 間の駒の数
  if ( n == 0 ) { // 飛び利き王手
    or128(stack->check,stack->check,t);   // 王手している駒
    stack->between=between;               // 合い駒生成で使う
  }
  else if ( n == 1 ) {   // ピン駒である
    to=bit_fscan(pin);   // ピン駒の位置
    stack->pin_dir[to]=dir;  // ピンされている方向
  }

■ Bitboardによる手の生成(駒を取る手)

駒を取る銀の手の生成。隣接手は簡単。

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

飛び駒の取る手生成には、邪魔駒の判定が必要(相手駒へ利きがあるか)。

target=p->bitboard[WHITE][P_OCCUPY];  // 相手駒の位置
t.x=and128(slider_attack[from],target);  // 先手飛び駒の利きのbitboardを押し付ける
while ( test128(t) ) {  // 利きのある数
  to=bit_fscan(&t); // 移動先の位置
  bit_reset(t,to);  // 移動先を消す
  t.x=and128(slider_attack[from],slider_opposite[to]);	// 間の枡を抽出
   if ( !andtest128(t,p->occ) ) {  // 邪魔駒が無い
     pin_check()
     手の格納
   }
 }