bitboard
最近、コンピュータ将棋やコンピュータオセロでbitboardという技法が注目を浴びている。特にコンピュータオセロでのbitboardのテクニックは凄まじく効果があるので、ここで概要だけ紹介しておく。*1
bitboardとは、1bpp(bit per pixel)のbitmapである。オセロであれば盤面は8×8 = 64マスなので、黒の駒が存在するbitを1,存在しないbitを0とすれば、黒の駒を表現するbitboardは64bit型整数で表現できる。同様に白の駒を表現するのも64bit型整数で表現できる。そうなると struct bitboard { u64 black,white; }; と、たったこれだけで盤面を表現できる。
このように表現すると、水平方向に駒が裏が返せるかの判定はテーブル処理で済む。さらに、盤面の90゜回転や45度回転はビット演算のテクニックで行なえることが知られている(このテクニックは名著『ハッカーのたのしみ』に載っている)ので、結局のところビット演算とテーブル処理を駆使すれば、条件分岐をほとんど用いずに駒の裏返し処理が出来る。
例えば探索時には盤面を頻繁に更新する必要があるが、bitboardを用いるなら次のようにやるだけである。
黒の着手位置を Bitboard m; それにより反転する位置を Bitboard rev; とすれば、
盤面の更新処理は以下のように記述できる。bitboard_black ^= m | rev;
bitboard_white ^= rev;
オセロの盤面はbitboardで表現すると64bit整数二つで表現できるので、64bitレジスタを持つCPUだとこの種の計算はかなり有利である。(探索結果を残すときにhash表に局面を登録するために)局面からhash値を計算するのも(テキトウな方法で良いなら)ビット演算でごねごねするだけで簡単に出来そうである。
一方、将棋のほうはどうかというと、駒の種類が多い(駒の数の分だけbitboardを用意して更新しようとすると大変である)ことや、9×9のマスが64bitに収まらないこともあって、bitboardの活用はそう容易ではない。盤面を表現するためのbitboardは64bitレジスタを
将棋ではbitboardは有名なところでは、Bonanzaが実装に用いているが、歩の利きを算出するのがメインで、それ以外は速度的には効果は乏しいのではないかと思う。ただ、コーディングがしやすくなるという意味はあるのかも知れない。
