2009-11-06

■　Bonanzaの指し手生成は40%以上の高速化ができる

Bonanzaの評価関数はどのようなものか？【KKP編】
http://d.hatena.ne.jp/LS3600/20090928

のほうで保木さんからコメントを頂戴した。

> 先頭でbitwise ORをとって空なら抜けるように

Bonanza のソースファイルでもそうなっていると思います。
"while( BBToU(bb) )" の行です。

大きな違いはビットを 0 にセットする時、32ビットのシフ
トを使用しているところではないでしょうか。

Bonanza では "Xor( sq, bb )" マクロを使い、32x3 ビット
のテーブル参照しています。

LS3600 さんの方法がよさそうなので、将来参考にするかも
しれません。

私はbitboardをiterateするのに、foreach_bitboardなるマクロを使用しているのだが、その先頭でBBToU(bb) (これは、bitboardのdword 3つをORする)を行なったほうが良いのか行なわないほうが良いのかという問題がある。

出現頻度が高いものは、BBToUをしないほうが良い。すなわち、次のように先頭でのゼロチェックは行なわずに、bsr/bsf(bit scan reverse/bit scan forward)をしていくほうが速い。

// 先頭でのゼロチェックを行なわない版
#define foreach_bitboard_firstone_no_check(bb,sq,XXX) \
{\
  {\
		unsigned long _index_; \
		while ( _BitScanReverse( &_index_, bb.p[0] ) ) \
		{ \
			bb.p[0] ^= 1<< _index_; \
			sq = (BoardPos)(26 - _index_); \
			XXX; \
		} \
		while ( _BitScanReverse( &_index_, bb.p[1] ) ) \
		{ \
			bb.p[1] ^= 1<< _index_; \
			sq = (BoardPos)(53 - _index_); \
			XXX; \
		} \
		while( _BitScanReverse( &_index_, bb.p[2] ) ) \
		{ \
			bb.p[2] ^= 1<< _index_; \
			sq = (BoardPos)(80 - _index_); \
			XXX; \
		}	\
  }\
}

具体的には歩や銀、金(Bonanzaでは成り駒で金と同じ利きを持つものも含む)はそれなりに出現頻度が高いので↑のようなマクロで展開すると効果が絶大である。しかし、馬や龍などは出現頻度自体が低く、bsr/bsfを3回も行なうとそのレイテンシ自体が許容できないし、bitboardがemptyのときにループを抜けるために3回も条件分岐を経ないといけないのは遅くなるので、先頭でゼロチェックを行なったほうが良いと思う。

■　gennocapはどれくらい高速化できるか

さて、このようなマクロを用いて、gennocap.c (駒を捕獲しない指し手の生成) を高速化することを考える。次のコードはBonanzaの銀の移動による相手の駒を捕獲しない指し手生成部分である。

  foreach_bitboard_【lastone】_no_check(bb_piece,from,
  {
    // 1枚取り出す

    // 銀のmaskを作る。
    
    bb_desti = bb_p_empty & abb_【turn】_silver_attacks[from];
    foreach_bitboard_【lastone】(bb_desti,to,
    {
      utemp = To2Move( to ) | From2Move( from ) | Piece2Move( silver );
      if ( from 【<】【A6】 || to 【<】【A6】 ) { *pmove++ = utemp | FLAG_PROMO; }
      // 敵陣からの移動もしくは、敵陣への移動ならば成りの手も生成する必要がある。
      *pmove++ = utemp;
    });
  });

【　】の部分は、YaneLispというLisp系の言語(マクロプロセッサとして使用している)により先手用と後手用で自動的に置換されるようになっている。以下に、YaneLispで書いたgennocap.cのコードを示す。

//% (let x
//%   ('【b】' 'b' 'w')
//%   ('【w】' 'w' 'b')
//%   ('【B】' 'B' 'W')
//%   ('【W】' 'W' 'B')
//%   ('【firstone】' 'firstone' 'lastone')
//%   ('【lastone】' 'lastone' 'firstone')
//%   ('【0】' '0' '2')
//%   ('【1】' '1' '1')
//%   ('【2】' '2' '0')
//%   ('【＋】' '+' '-')
//%   ('【−】' '-' '+')
//%   ('【>】' '>' '<')
//%   ('【<】' '<' '>')
//%   ('【A6】' 'A6' 'I4')
//%   ('【A7】' 'A7' 'I3')
//%   ('【I4】' 'I4' 'A6')
//%   ('【I3】' 'I3' 'A7')
//%   ('【minus】' 'minus' 'plus')
//%   ('【plus】' 'plus' 'minus')
//%   ('【black】' 'black' 'white')
//%   ('【white】' 'white' 'black')
//%   ('【0x1ffU】' '0x1ffU' '0x7fc0000U')
//% )
//% (set z

Move* 【turn】_gen_nocaptures( const Tree * restrict ptree, Move * restrict pmove )
{

  // bb_p_empty = 先手の駒も後手の駒もないところ。!(A or B) = !A and !Bなので。
	bitboard bb_p_empty = ~(BB_BOCCUPY | BB_WOCCUPY);

	(中略)

}
//% )
//% (set w z)
//% (foreach e x (set w (replace w (array e 0) (array e 1) ) )) (write w)
	// 先手用コードの生成
//% (set w z)
//% (foreach e x (set w (replace w (array e 0) (array e 2) ) )) (write w)
	// 後手用コードの生成

なお、YaneLispについては以下のサイトからdownloadできる。
コンピュータ将棋プログラムをLISPで書く
http://labs.yaneu.com/20090905/

話をもどそう。銀の移動による駒を捕獲しない指し手生成は次のようにunrollできる。

  // 上段・下段だとdestiが隣の32bitに限定されるから、&をとる回数は1回減る。
  foreach_bitboard_【lastone】【0】_no_check(bb_piece,from,
  {
    bb_desti.p[【0】] = bb_p_empty.p[【0】] & abb_【b】_silver_attacks[from].p[【0】];
    bb_desti.p[【1】] = bb_p_empty.p[【1】] & abb_【b】_silver_attacks[from].p[【1】];

    u32 utemp = From2Move( from ) | Piece2Move( silver );
    foreach_bitboard_【lastone】【0】【1】_no_check(bb_desti,to,
    {
      u32 m = utemp | To2Move( to );

      *pmove++ = m | FLAG_PROMO;
      *pmove++ = m;
      // 逆順のほうがmをこのあと破壊できていいと思うがorderingに影響するかも知れないので放置
    });
  });
  foreach_bitboard_【lastone】【1】_no_check(bb_piece,from,
  {
    bb_desti = bb_p_empty & abb_【b】_silver_attacks[from];

    u32 utemp = From2Move( from ) | Piece2Move( silver );
    foreach_bitboard_【lastone】_no_check(bb_desti,to,
    {
      u32 m = utemp | To2Move( to );

      if ( to 【<】【A6】 ) { *pmove++ = m | FLAG_PROMO; }
      // 敵陣への移動ならば成りの手も生成する必要がある。

      *pmove++ = m;
    });
  });
  foreach_bitboard_【lastone】【2】_no_check(bb_piece,from,
  {
    bb_desti.p[【1】] = bb_p_empty.p[【1】] & abb_【b】_silver_attacks[from].p[【1】];
    bb_desti.p[【2】] = bb_p_empty.p[【2】] & abb_【b】_silver_attacks[from].p[【2】];

    u32 utemp =  From2Move( from ) | Piece2Move( silver );
    foreach_bitboard_【lastone】【1】【2】_no_check(bb_desti,to,
    {
      // 自陣からなのでこの銀が成れるということはありえない。
      *pmove++ = utemp | To2Move( to );
    });
  });

1,2,3段目にいる場合は、移動範囲は1,2,3,4段目に限られるのでbitboardの先頭二つのdwordだけを参照すれば良いのである。また、成る手の生成も楽になる。私は、以前bitboardは64bitレジスタを使ったほうがbsr/bsfが速くなっていいのではないかと書いたが、指し手生成を上のようにunrollするなら、いまのbitboardのbit layoutのほうが良いと思う。

さて、このように出現頻度の高い駒(歩・銀・金)や、前方にしか利かない駒(桂)は上のようにunrollしたほうが高速化が図れると思う。前方にしか利かない駒をunrollするのは、指し手生成のときに、移動先が限定されるからである。具体的には、上3段からなら上3段にしか移動できないし、4〜6段目からであっても、1〜4段目(すなわち、bitboardの先頭二つのdword)にしか移動しないからである。

このようにbitboardにアクセスを要する範囲が縮むので、前方にしか利かない駒もunrollしたほうが平均的には速度が向上すると思う。

■　指し手生成の速度はどれくらい向上したのか？

以上のように必要な部分にのみunrollを繰り返していくと、gennocap自体は本家のものより40%〜50%程度速くなった。

また、私は指し手生成自体はうまくやれば差分生成が出来て、数倍程度の高速化が出来ると見込んでいる。いずれ成果を発表したい。