daruma3940の日記

理解や文章に間違い等あればどんなことでもご指摘お願いします

Rotated Bitboardなのじぇ

f:id:daruma3940:20160520223745p:plain
Rotated Bitboardについての解説をしようじぇ?

Bitboardについての解説は以前の記事を見てくれだじぇ。
daruma3940.hatenablog.com



f:id:daruma3940:20160709192554j:plain
SquirrelはRotated Bitboardを使って効きのある升を計算しているよ!

f:id:daruma3940:20160521003616p:plain
最近はPEXTbitboardとかもあるらしいじゃない?どうしてRotated Bitboardを使うの?
f:id:daruma3940:20160520223745p:plain
twitter.com
mermoさん曰くPEXTよりも早いそうなのじぇ。
そしてまりちゃのPCはアルバイトして買った学習用i7-4770K以外のPCはAVX2に対応していなくてPEXTは使えないのでRotatedにせざるを得なかったのじぇ。

f:id:daruma3940:20160520223745p:plain
Bitboardによる効きの表現は効きのあるマスに対応するbitを1にすることである駒がどこに効きを作っているのかを表現するというものなのじぇ。
しかし長い効きを持つ駒の場合効きを遮る駒がどこにあるのかによってどこまで効きを伸ばすことができるかが変わってくるのじぇ。
そこで、(とびゴマの位置、邪魔ゴマの位置)全通りに対してどこに効きを発生させることができるかのTable集を作成し、どこに邪魔ゴマがあるかをindexにしてそのテーブルを引っ張ってくることで効きを表現しようという方法なのじぇ。


例えば
青いマスを邪魔ゴマがいるマス、赤いマスを効きを発生させている駒の升だとすると

f:id:daruma3940:20170813122054p:plain

この図で4の場所にいる飛車の縦方向のききを求めたければ
TateKikiTable[4(効きを発生させる駒の場所)][(bitboard>>1)&(7)] のようになるのじぇ
今のbitboardをシフトして必要なところだけマスクして取り出すことによって Tableのindexを作成できるのじぇ

f:id:daruma3940:20170813122635p:plain
この場合は
TateKikiTable[31(効きを発生させる駒の場所)][(bitboard>>28)&(7)]になるのじぇ


しかし横の効きを求めるためにはこのマスの番号のつけ方では
f:id:daruma3940:20170813122837p:plain
シフトとマスクではindexを作れないのじぇ。

そこでこのbitboardを90度回転させたboard(bitboard90とする)を作成すれば
f:id:daruma3940:20170813123015p:plain
これはさっきと同じようにシフトとマスクでindex作成できるのじぇ。

f:id:daruma3940:20160520223745p:plain
実際のbitboardは64bit整数2つ(ここではint64_t bb[2]とする)で作られるためbb[0]かbb[1]かどちらを参照するべきかも指定しないといけないためもうちっとふくざつになるのじぇ
斜め+45度斜め-45度についても似たような感じなのじぇ。
f:id:daruma3940:20160520223745p:plain

もし将棋の駒がすべて近接駒ならRotated Bitboardなんて技術は必要ないのじぇ。
Rotated Bitboardは長い効きを持つ駒の効きを考慮するために必要なのじぇ
f:id:daruma3940:20160520223745p:plain
ちなみにこれがSquirrelにおけるRotated Bitboardの設計図なのじぇ
f:id:daruma3940:20170813124340j:plain
f:id:daruma3940:20170813124350j:plain
f:id:daruma3940:20170813124412j:plain


あと駒のいる位置を表しているbitboard(occupied bitboad)は
回転無し,90度回転+45度回転,-45度回転の4つ保持しないといけないのだけれど

縦方向の効きは1段目9段目に邪魔ゴマがあっても1段目9段目に効きを作ることができるので縦方向occupiedbitboardは1段目9段目を表すbitを除いて7*9=63bitあればよく
横方向も1筋目9筋目のbitはいらないので7*9=63bit
斜めはそれぞれ7*7=49bitあればよいので
実はoccupiedbitboardはすべて256bitに収めることができ
これによって駒が動いた時のoccupiedbitboardのこうしんの処理はSIMD演算を使えば一気に処理できるのじぇ。
これを用いれば結構高速化できた記憶があるのじぇ