Rotated Bitboardsは本当に高速なのか？ - Bonanzaソース完全解析ブログ

■　Rotated Bitboardsは本当に高速なのか？

rotateをやろうと思うと、90度、45度x2で、３つのbitboardをmakeMoveで更新しないといけない
unmakeMoveも同様。一つのbitboardは3個の32bitのint変数に演算を行うことになる。
これはけっこうばかにならないコスト。(駒を動かすと3x3x2=18回の演算がいる）

rotated bitboardは本当に速いのか？(小宮日記)
http://d.hatena.ne.jp/mkomiya/20090222

Rotated Bitboardで高速化されるかどうかは興味深いところですね。

#define AttackFile(i)  (abb_file_attacks[i]                               \
                         [((ptree->posi.occupied_rl90.p[aslide[i].irl90]) \
                            >> aslide[i].srl90) & 0x7f])

abb_file_attacksの求めたいbitboardが格納されているindexを確定させるために最低でも、テーブル参照3回(スライドテーブルの参照2回 + occupied_rl90への参照1回)、シフト演算1回、ビットAND 1回が必要です。

さて、本当にこんな演算が必要なのでしょうか？

■　64bit化でRotated Bitboardはどう高速化されるのか

まず知っておくべきことは、利きを求めるのに辺の情報は不要ということです。(→ Bonanzaの指し手生成ルーチン完全解読(5) http://d.hatena.ne.jp/LS3600/20091115#p1 )

例えば上下方向に飛車が利いているかを計算するには、1段目と9段目にある駒の状態はまったく関係がないということです。すなわち、2〜8段×9マス = 63マスの状態だけ保持してあれば良いので64bitに収まります。

同様に、角の利きならば、外周の状態には依存しないため、内周である7*7 = 49マスの状態だけ保持しておくだけで良くて、これまた64bitに収まります。( → bitboard の妄想ネタ
http://d.hatena.ne.jp/stonestonestone/20091108 )

このように、64bit環境で動作させるなら、64bitに収まるのは都合が良いです。64bit環境では、(常識的には)64bitレジスタへの代入、ビットシフト、ビットXOR/ANDなどは、32bitレジスタに対して行なうのと同じlatency / throughputだと考えられます。

それでは64bit環境でどう変わるか考えてみましょう。

OCCUPIED_FILEは64bitで持つとして、BoardPosに対応する箇所をbitwise xorをとるので、このときにテーブル参照1回、OCCUPIED_FILEとのxorに1命令。合計2命令で済みます。6命令が2命令になっているので、これはおおよそ3倍の高速化と言えます。

では、さきほどの縦方向の利きの到達するbitboardを計算するコードはどう変わるでしょうか？bitboard自体が64bitに収まっているのでp[ ]を指定する部分が不要になります。

おまけというわけではないですが occupied bitboard が64bitに収まったので、利きを取り出すときにレジスタを指定する必要がなくなります。

attacks_r???[sq][( occupied_r???.reg[select_r???[sq] ] >> shift_r???[sq] ) & 0x7F];
                      ↓
attacks_r???[sq][( occupied_r??? >> shift_r???[sq] ) & 0x7F];

Rotate Bitboards 一部64bit化 続(忘れた頃に、また忘れる)
http://d.hatena.ne.jp/stonestonestone/20091114

つまり、テーブル参照が1回減ります。個人的には、この最後の0x7fのマスクは、少し嫌なので0xffにしてみたい気もします。テーブルサイズは2倍になりますが、最下位バイトを取り出してテーブルを引くので、(常識的には、movzx命令が使われて)マスクの処理自体が省略できるからです。メモリ使用量が増えてかえって遅くなるかも知れませんがそれはそれとして。

■　Magic Bitboardで高速化できるのか？

Magic bitboardとは何ぞや？という方は、この記事をどうぞ。(→ Magic bitboardに関する記事 http://d.hatena.ne.jp/mclh46/20091108/1257683049 )

角の利きを求めるのに必要なoccupiedな盤面(駒があるところが1、無いところが0のbitboard)は7*7 = 49bitで、うまい定数を掛け算すれば、利きを計算するのに必要なbitが一箇所に集まるので角の利きが一発で求まるということです。(→ http://d.hatena.ne.jp/stonestonestone/20091110 )

残念ながら飛車のほうは、「Magic Bitboards で縦横同時を考えると最低でも隅を除く77マス分が必要で、64bitレジスタでは足りないのでマスによっては2回処理することになります。」(→ http://d.hatena.ne.jp/stonestonestone/20091111 )

・Magic Bitboardの利点
1) MakeMove/UnMakeMoveでdiag1,diag2の二つのbitboardを更新しなくとも1つだけで済む。
2) diag1とdiag2から利きのbitboardを求めて、そのあとbitwise orをとるコードが不要になる。

・Magic Bitboardの欠点
1) 64bit乗算のlatencyが気になる。(Corei7での値は公開されてませんが、32bit乗算のlatencyが3なのでそれよりは大きいと思います)
2) 数MB程度のテーブルが必要になる。

attacks_diag[sq][( occupied_rl45 >> shift_r???[sq] ) + ( occupied_rr45 >> shift_r???[sq] )];

↓ Magic Bitboardを使うと(疑似コードとしては)

attacks_diag[sq][ ((occupied_magic45 & magic_mask[sq])*magic_number[sq] >> magic_shift[sq]) & 0xfff ];

となるわけですかね。これ本当に速いのかな..。

さきほどと同じ理屈で0xfffでのmaskが嫌なので0xffffでマスクしたり..はしませんか。そうですか。

■　結論

今後の研究次第で今回の結論は容易に覆るので、今回の結論は保留とします！