| bitboard反転パターン取得 | prev Page next Page |
オセロにて pos に着手した場合に反転するパターンを取得する処理：
着手箇所から8方向について、相手の石が連続し、自分の石が存在する というのが着手可能条件であり、
連続する相手の石が反転パターンとなる。
ループを用いる方法
Bitboard getRevPat(Bitboard m) // m は着手箇所、1ビットのみが1で他はすべて0{
Bitboard rev = 0;
Bitboard mask = transfer(m);
while( mask != 0 && (mask & bitborad_white) != 0 ) { // 白石が連続する間
rev |= mask;
mask = transfer(pos);
}
if( (mask & bitboard_black) == 0 ) // 黒石がなければ、着手できない
return 0;
else
return rev; // 反転パターン
}
CBitboard transfer(CBitboard m) は特定方向へ移動したパターンを返す。
右方向への移動であれば、
return (m>>1) & 0x7f7f7f7f7f7f7f7f;
と定義できる。
ループを用いない方法
uint64 wh = white & 0x7e7e7e7e7e7e7e7e; // 横移動のための番人
m1 = pos >> 1;
if( (m1 & wh) != 0 ) {
if( ((m2 = m1 >> 1) & wh) == 0 ) {
if( (m2 & black) != 0 ) rev |= m1;
} else if( ((m3 = m2 >> 1) & wh) == 0 ) {
if( (m3 & black) != 0 ) rev |= m1 | m2;
} else if( ((m4 = m3 >> 1) & wh) == 0 ) {
if( (m4 & black) != 0 ) rev |= m1 | m2 | m3;
} else if( ((m5 = m4 >> 1) & wh) == 0 ) {
if( (m5 & black) != 0 ) rev |= m1 | m2 | m3 | m4;
} else if( ((m6 = m5 >> 1) & wh) == 0 ) {
if( (m6 & black) != 0 ) rev |= m1 | m2 | m3 | m4 | m5;
} else {
if( ((m6 << 1) & black) != 0 ) rev |= m1 | m2 | m3 | m4 | m5 | m6;
}
}
条件分岐を用いない方法
1方向について返る石数は1〜6個であるので、それぞれに場合について計算し結果をorしてもよいuint64 wh = white & 0x7e7e7e7e7e7e7e7e; // 横移動のための番人
uint64 rev = 0;
uint64 e1, e2, e3, e4, e5, e6; // 空白から続く白石列
uint64 b1, b2, b3, b4, b5, b6; // 黒石から続く白石列
e1 = (m <<1) & wh;
e2 = (e1 << 1) & wh;
e3 = (e2 << 1) & wh;
e4 = (e3 << 1) & wh;
e5 = (e4 << 1) & wh;
e6 = (e5 << 1) & wh;
b1 = (black >> 1) & wh;
b2 = (b1 >> 1) & wh;
b3 = (b2 >> 1) & wh;
b4 = (b3 >> 1) & wh;
b5 = (b4 >> 1) & wh;
b6 = (b5 >> 1) & wh;
rev |= e1 & b1 |
e1 & b2 | e2 & b1 |
e1 & b3 | e2 & b2 | e3 & b1 |
e1 & b4 | e2 & b3 | e3 & b2 | e4 & b1 |
e1 & b5 | e2 & b4 | e3 & b3 | e4 & b2 | e5 & b1 |
e1 & b6 | e2 & b5 | e3 & b4 | e4 & b3 | e5 & b2 | e6 & b1;
他の方向についても同様
最後の行は以下のように書いた方が高速
rev |= e6 & b1;
rev |= e5 & (b1 |= b2);
rev |= e4 & (b1 |= b3);
rev |= e3 & (b1 |= b4);
rev |= e2 & (b1 |= b5);
rev |= e1 & (b1 | b6);
さらに以下のように記述すると、使用変数が減る
e1 = (m << 9) & wd;
e2 = (e1 << 9) & wd;
e3 = (e2 << 9) & wd;
e4 = (e3 << 9) & wd;
e5 = (e4 << 9) & wd;
e6 = (e5 << 9) & wd;
rev |= e6 & (b1 = (black >> 9) & wd);
rev |= e5 & (b1 |= (b1 >> 9) & wd);
rev |= e4 & (b1 |= (b1 >> 9) & wd);
rev |= e3 & (b1 |= (b1 >> 9) & wd);
rev |= e2 & (b1 |= (b1 >> 9) & wd);
rev |= e1 & (b1 | (b1 >> 9) & wd);
このページへのトラックバックURL： http://vivi.dyndns.org/wtb/257
2,387 page views,
page owner : びびすけ
2006/10/01 23:02 modified by びびすけ