最新

Miyako Shogi System

コツコツ改良、へこたれない
2014| 1|
2013| 12|
2012| 01| 02| 04| 05| 06| 07| 08| 09| 10|
2011| 01| 02| 03| 04| 05| 07| 08| 10| 11| 12|
2010| 02| 03| 06| 07| 08| 09| 10| 12|

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でも動くようにしてきたが、プラットホーム決め打ちになりそうな予感。

リンクはご自由に (Miyako Shogi System Kyoto Japan)

ダウンロードのページ

Lighttpd

DreamPlug