最新

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/06/24

Bitboardによる手の生成

地味な作業だが、手生成は速度に影響が大きいので大事な作業。

駒を取らない銀の手の生成には、次のような利きデータを用意しておく。

55の先手銀の利きデータ(attack_gin_b)
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  1  1  1  0  0  0 四
 0  0  0  0  S  0  0  0  0 五
 0  0  0  1  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 九

このような利きデータを盤のマス目だけ持つ。

andnot128(target,area_mask,occ);       // 駒の無い場所 (occは全部の駒位置)
org=p->bitboard[BLACK][P_GIN];
while ( test128(org) ) {  // 駒がある
  from=bit_fscan(&org);  // 駒位置
  bit_reset(org,from);   // 駒を消す
  and128(t,attack_gin_b[from],target);  // 先手銀の利きのbitboardを押し付ける
  while ( test128(t) ) {  // 利きのある数
    to=bit_pop1st(&t); // 移動先の位置
    pin_check()
    手の格納
  }
}

飛び駒の手生成には、次のような利きデータを用意しておく。

55の角の利きデータ(北東:slider_ne)
9 8 7 6 5 4 3 2 1
 0  0  0  0  0  0  0  0  1 一
 0  0  0  0  0  0  0  1  0 二
 0  0  0  0  0  0  1  0  0 三
 0  0  0  0  0  1  0  0  0 四
 0  0  0  0  B  0  0  0  0 五
 0  0  0  0  0  0  0  0  0 六
 0  0  0  0  0  0  0  0  0 七
 0  0  0  0  0  0  0  0  0 八
 0  0  0  0  0  0  0  0  0 九

55の角の利きデータ(北西:slider_nw)
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  1  0  0  0  0  0  0 三
 0  0  0  1  0  0  0  0  0 四
 0  0  0  0  B  0  0  0  0 五
 0  0  0  0  0  0  0  0  0 六
 0  0  0  0  0  0  0  0  0 七
 0  0  0  0  0  0  0  0  0 八
 0  0  0  0  0  0  0  0  0 九

55の角の利きデータ(南東:slider_se)
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  B  0  0  0  0 五
 0  0  0  0  0  1  0  0  0 六
 0  0  0  0  0  0  1  0  0 七
 0  0  0  0  0  0  0  1  0 八
 0  0  0  0  0  0  0  0  1 九

55の角の利きデータ(南西:slider_sw)
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  B  0  0  0  0 五
 0  0  0  1  0  0  0  0  0 六
 0  0  1  0  0  0  0  0  0 七
 0  1  0  0  0  0  0  0  0 八
 1  0  0  0  0  0  0  0  0 九

方角は先手側から見たもの。

org=p->bitboard[BLACK][P_KAKU];  // 角
while ( test128(org) ) {
  from=bit_fscan(org);
  bit_reset(org,from);
  t=AttackKaku(from,occ);     // 角筋のビットボードを返す
  if ( from <= 26 ) {         // 引き成り
    while ( test128(t) ) {
      to=bit_pop1st(&t);
      pin_check()
      成る手の格納
    }
  }
  else {
    while ( test128(t) ) {
      to=bit_pop1st(&t);
      pin_check()
      手の格納
    }
  }
}

角筋を返す関数は

ne=slider_ne[pos];      // 利きデータ (NE)
nw=slider_nw[pos];      // (NW)
se=slider_se[pos];      // (SE)
sw=slider_sw[pos];      // (SW)

and128(t,ne,occ);       // 利きデータと駒のある位置のand
if ( test128(t) ) {     // 邪魔駒があった
  to=bit_rscan(t);    // 邪魔駒の位置
  and128(ne,ne,slider_sw[to]);    // 間の枡を抽出
}

and128(t,nw,occ);
if ( test128(t) ) {
  to=bit_rscan(t);
  and128(nw,nw,slider_se[to]);
}

and128(t,se,occ);
if ( test128(t) ) {
  to=bit_fscan(t);
  and128(se,se,slider_nw[to]);
}

and128(t,sw,occ);
if ( test128(t) ) {
  to=bit_fscan(t);
  and128(sw,sw,slider_ne[to]);
}

or128(ne,ne,nw);    // 移動先のビットボード
or128(se,se,sw);
or128(t,ne,se);

return t;

角のいる場所から斜めに利きを延ばし、全駒データとANDを取る。もし間に駒があればビットが立つので角に一番近い邪魔駒の位置まで利きデータとANDを取る。得られた4本の斜めデータをORしたものを返す。

2012/06/06

Bitboard(続)

歩の手は9bitシフトで生成するのが効率が良いが、

その他の手の時はシフト演算より利きの型紙を押し付ける方が良さそうなので、

桂銀金馬竜王による隣接手は利きの型紙を生成し、押し付ける方式に変更する。

利きの型紙データが思ったより小さくて済むからである(1次キャッシュに十分入る)。

2012/06/05

書き換えなければならないモジュール

利きのデータがなくなることにより、

・ピン駒を探す

・王手をかけている判定

・利きのあるところに王移動はしない

・交換値計算(あるマスに利きを付けている駒を捜す)

・取れる駒を探す

・開き王手生成(逆ピン駒を探す)

は作り直す必要がある。

・評価関数で王の周りの利きの数の計算

評価関数の書き換えは評価項目の見直しもあるので先に延ばす。

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

ダウンロードのページ

Lighttpd

DreamPlug