Bonanzaが用いているbitboardの定数配列の意味【後編】
■ Bonanzaが用いているbitboardの定数配列の意味【後編】
前回記事 : Bonanzaが用いているbitboardの定数配列の意味【前編】
http://d.hatena.ne.jp/LS3600/20091102
の続き。
今回は、残りのbitboardの定数配列の意味を解説する。
これによりBonanzaのソースコードにある暗号めいたbitboardのビット演算関係の動作の大半が理解できるようになる。
■ abb_mask,abb_mask_rl90,abb_mask_rl45,abb_mask_rr45
まず、ini.cのini_tablesの残りabb_mask,abb_mask_rl90,abb_mask_rl45,abb_mask_rr45の意味から解説する。
変数名のabbのaはarray、bbはbitboardの略。rl90はrotation(回転) left 90度の意味。rlは45度左回転。rr45は45度右回転。
盤面の位置を表わす定数は、shogi.hで次のように定義されている。
// 各マスに対する文字列
// 上が後手側(A9 = 9一 , I1 = 1九)
enum { A9 = 0, B9, C9, D9, E9, F9, G9, H9, I9,
A8, B8, C8, D8, E8, F8, G8, H8, I8,
A7, B7, C7, D7, E7, F7, G7, H7, I7,
// x < A6の範囲が後手陣。先手にとって駒が成れるのはこの範囲。
A6, B6, C6, D6, E6, F6, G6, H6, I6,
A5, B5, C5, D5, E5, F5, G5, H5, I5,
A4, B4, C4, D4, E4, F4, G4, H4, I4,
// x > I4の範囲が先手陣。後手にとって駒が成れるのはこの範囲。
A3, B3, C3, D3, E3, F3, G3, H3, I3,
A2, B2, C2, D2, E2, F2, G2, H2, I2,
A1, B1, C1, D1, E1, F1, G1, H1, I1 };
// FirstOneは小さな値から探すので、この盤面で言えば左上からのスキャンになる。
// LastOneは大きな値から探すので、この盤面で言えば右上からのスキャンになる。本家Bonanzaのコードではこのenumは無名enumとなっているが、私はBoardPosという型名をつけている。ここは型名をつけたほうが圧倒的にわかりやすい。
今回出てくるabb_maskの配列のindexには、BoardPos型を指定する。つまり、例えばabb_mask[A9]ならば、将棋盤の9一の地点が1である(他の地点は0である)ようなbitboardである。このようにソース上で、配列のindexの型として単なるintを指定してあるように見えるのと、BoardPos型を指定してあるように見えるのとではまったくソースの可読性が異なる。
話を先に進めよう。
BoardPosの定数を用いて、ini.cのini_tablesでは、aini_rl90として次のように設定されている。これは90度回転させた盤面である。
const unsigned char aini_rl90[] = { A1, A2, A3, A4, A5, A6, A7, A8, A9,
B1, B2, B3, B4, B5, B6, B7, B8, B9,
C1, C2, C3, C4, C5, C6, C7, C8, C9,
D1, D2, D3, D4, D5, D6, D7, D8, D9,
E1, E2, E3, E4, E5, E6, E7, E8, E9,
F1, F2, F3, F4, F5, F6, F7, F8, F9,
G1, G2, G3, G4, G5, G6, G7, G8, G9,
H1, H2, H3, H4, H5, H6, H7, H8, H9,
I1, I2, I3, I4, I5, I6, I7, I8, I9 };この90度回転させた盤面で、BoardPosの部分を1にしたのがabb_mask_rl90である。具体的には初期化するコードは以下のようになっている。
for ( isquare = 0; isquare < nsquare; isquare++ )
{
isquare_rl90 = aini_rl90[isquare];
isquare_rl45 = aini_rl45[isquare];
isquare_rr45 = aini_rr45[isquare];
abb_mask[isquare] = bb_set_mask( isquare );
abb_mask_rl90[isquare] = bb_set_mask( isquare_rl90 );
abb_mask_rl45[isquare] = bb_set_mask( isquare_rl45 );
abb_mask_rr45[isquare] = bb_set_mask( isquare_rr45 );
}何故こんなものが必要かというと、縦に利く駒(香・飛)の利きを求めるときに、駒が存在する場所が1であるようなbitboardを90度回転させた盤面があれば、該当する筋に相当する9bitをスライド(bit shift)してくれば、その筋の9コのマスに駒が存在するのか/しないのかを表現する9bitが得られる。この9bitをもとにテーブルを引けば、利きがどこまで伸びているかが瞬時に確定するという仕組みである。(実際は9bitではなく7bitで済むのだが、それについては長くなるので利きに関するbitboardについて書くときに解説する。)
同様に角の利きを求めるためには斜め45度に回転させた盤面が必要になるということである。
■ 盤面はどうやって回転させるのか
90度回転はともかく、斜め45度回転させた盤面なんてものがビット演算の魔法で求まるのかなんて心配する人もいるだろうが、実際は探索中に都度45度回転させたりはしない。指し手を進めるときと戻すときにのみ、その移動元と移動先に該当するビットを反転させるだけである。
具体的には、make.c(指し手を進める)/unmake.c(指し手を戻す)にある次のコードになる。
SetClearFile( from, to, OCCUPIED_FILE );
SetClearDiag1( from, to, OCCUPIED_DIAG1 );
SetClearDiag2( from, to, OCCUPIED_DIAG2 );駒の移動元(from)と、駒の移動先(to)に該当する位置のbitを反転させる。OCCUPIED_FILEは、盤面を90度回転させたもので、OCCUPIED_DIAG1,2は盤面を45度回転させたものである。これらはマクロであり、shogi.hで次のように定義させている。
// 90度回転させたbitboardの、BoardPos i1,i2の位置をxorする。
#define SetClearFile(i1,i2,bb) \
(bb).p[0] ^= ((abb_mask_rl90[i1].p[0])|(abb_mask_rl90[i2].p[0])), \
(bb).p[1] ^= ((abb_mask_rl90[i1].p[1])|(abb_mask_rl90[i2].p[1])), \
(bb).p[2] ^= ((abb_mask_rl90[i1].p[2])|(abb_mask_rl90[i2].p[2]))
// 45度右回転させたbitboardの、BoardPos i1,i2の位置をxorする。
#define SetClearDiag1(i1,i2,bb) \
(bb).p[0] ^= ((abb_mask_rr45[i1].p[0])|(abb_mask_rr45[i2].p[0])), \
(bb).p[1] ^= ((abb_mask_rr45[i1].p[1])|(abb_mask_rr45[i2].p[1])), \
(bb).p[2] ^= ((abb_mask_rr45[i1].p[2])|(abb_mask_rr45[i2].p[2]))
// 45度左回転させたbitboardの、BoardPos i1,i2の位置をxorする。
#define SetClearDiag2(i1,i2,bb) \
(bb).p[0] ^= ((abb_mask_rl45[i1].p[0])|(abb_mask_rl45[i2].p[0])), \
(bb).p[1] ^= ((abb_mask_rl45[i1].p[1])|(abb_mask_rl45[i2].p[1])), \
(bb).p[2] ^= ((abb_mask_rl45[i1].p[2])|(abb_mask_rl45[i2].p[2]))ここまでくれば、abb_mask_rl90,abb_mask_rr45,abb_mask_rl45の意味は明瞭だろう。これらは、90度、45度回転させた盤面を、make/unmakeのときに差分更新するために必要なのだ。
■ まとめ
前回と今回の記事とで、ini.cのini_tablesで初期化しているbitboardの定数配列についてはすべて解説が終わった。
次回は、利きを計算するためのテーブルについて解説する。
