2012/05/26
■ Bitboardの説明
いまさらながらこのような説明は不要かもしれないが、Bitboardの説明。
駒位置をビット位置であらわす(ここでは説明を簡単にするため81ビット演算が使えるとする)。
盤の座標値とビット番号 9 8 7 6 5 4 3 2 1 8 7 6 5 4 3 2 1 0 一 17 16 15 14 13 12 11 10 9 二 26 25 24 23 22 21 20 19 18 三 35 34 33 32 31 30 29 28 27 四 44 43 42 41 40 39 38 37 36 五 53 52 51 50 49 48 47 46 45 六 62 61 60 59 58 57 56 55 54 七 71 70 69 68 67 66 65 64 63 八 80 79 78 77 76 75 74 73 72 九
たとえば、先手歩の初期位置だと、
9 8 7 6 5 4 3 2 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 六 1 1 1 1 1 1 1 1 1 七 0 0 0 0 0 0 0 0 0 八 0 0 0 0 0 0 0 0 0 九
となる。
歩を突く手を生成してみよう。**に歩がいるときの利きのテンプレートを押し付ける方法もあるのだが、シフト命令でやってみよう。この81ビット列を9ビット右シフトすると、
9 8 7 6 5 4 3 2 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 五 1 1 1 1 1 1 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 九
演算1回で9個の歩を動かした(どうだすごいだろ)。あとは味方の駒位置ビット列とxorして、ビット位置を端から読んでいけば合法手となる。前に動く駒はすべてこの演算で動かすことができる(飛香の飛び駒の処理は別に行う)。
次に、9三と1三にいる銀を右上に動かしてみよう。
9 8 7 6 5 4 3 2 1 0 0 0 0 0 0 0 0 0 一 0 0 0 0 0 0 0 0 0 二 1 0 0 0 0 0 0 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 0 0 0 0 八 0 0 0 0 0 0 0 0 0 九
この81ビット列を10ビット右シフトすると、あれ、9一は変。
9 8 7 6 5 4 3 2 1 1 0 0 0 0 0 0 0 0 一 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 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 九
一番右端にいる駒を右に動かすと左に回ってしまうので、1筋を0にしたものとandしておく。
9 8 7 6 5 4 3 2 1 9 8 7 6 5 4 3 2 1 9 8 7 6 5 4 3 2 1 0 0 0 0 0 0 0 0 0 一 1 1 1 1 1 1 1 1 0 一 0 0 0 0 0 0 0 0 0 一 0 0 0 0 0 0 0 0 0 二 1 1 1 1 1 1 1 1 0 二 0 0 0 0 0 0 0 0 0 二 1 0 0 0 0 0 0 0 1 三 1 1 1 1 1 1 1 1 0 三 1 0 0 0 0 0 0 0 0 三 0 0 0 0 0 0 0 0 0 四 1 1 1 1 1 1 1 1 0 四 0 0 0 0 0 0 0 0 0 四 0 0 0 0 0 0 0 0 0 五 and 1 1 1 1 1 1 1 1 0 五 = 0 0 0 0 0 0 0 0 0 五 0 0 0 0 0 0 0 0 0 六 1 1 1 1 1 1 1 1 0 六 0 0 0 0 0 0 0 0 0 六 0 0 0 0 0 0 0 0 0 七 1 1 1 1 1 1 1 1 0 七 0 0 0 0 0 0 0 0 0 七 0 0 0 0 0 0 0 0 0 八 1 1 1 1 1 1 1 1 0 八 0 0 0 0 0 0 0 0 0 八 0 0 0 0 0 0 0 0 0 九 1 1 1 1 1 1 1 1 0 九 0 0 0 0 0 0 0 0 0 九
これを10ビット右シフトすればよい。
ここの説明が良い。
http://chessprogramming.wikispaces.com/Efficient+Generation+of+Sliding+Piece+Attacks#cite_note-1
■ げっ、_mm_slli_si128/_mm_srli_si128は8bitずつのシフトしかできない!
バレルシフタは回路を食うが、それは無いでしょ。
sse5では自由なシフトができるそうだが、幻の命令セットになったので、shld/shrdでちまちま書くか。Miyako Shogi SystemはWindowsでもLinuxでも32bitでも64bitでも動くようにしてきたが、プラットホーム決め打ちになりそうな予感。