ビットボードなのじぇ２
今回もbitboardについての記事を書いていくのじぇ
今回はbitboardの初期化編なのじぇ
なかなか難しかったのじぇ。
これのせいで今日の2限の授業はいつの間にか終わってたのじぇ
ちゃんと授業ききなさいよ...
まあいいのじぇ。
ここで一つ断っておくべきことがあるのじぇ
この初期化はかなり理解が難しくてこの記事の内容があっている保証さんはないのじぇ
あと自分でコードを読んでみて1点分からなかったところがあるので誰か教えて欲しいのじぇ
「なぜ飛車は無条件全域から王に王手をかけれるのか」
これは解決した。飛車は邪魔ゴマがいないとき盤面の任意の升に2回移動でいけるから、どこからでも王手をかけれる
ということなのじぇ。
詳しい人いればコメント欄にでもおねがいするのじぇ。
Bitboard::init()における初期化には簡単で読めばすぐわかるような内容と
読んでもすぐには分からないような内容があるのじぇ
ここではそのわかりにくい個所のみ解説していくつもりなのじぇ。
具体的には
4) 遠方利きのテーブルの初期化
7) 二歩用のテーブル初期化
9) 王手となる候補の駒のテーブル初期化
のことなのじぇ。もしかしたら他にも本質的に難しい個所はあるかもしれないけれど
まいちゃはそれすら気が付いていないのかもしれないのじぇ
まあとりあえず（４）の解説を始めるのじぇ正直(4)が一番鬼門なのじぇ
これを考え付いたAperyの平岡さんはすごい人なのじぇ
ここでは飛車と角の邪魔ゴマの位置を考慮した利きを算出しているのじぇ
ここではfor (Piece pc : {BISHOP, ROOK})というループ文で角の利きと飛車の利きを計算する部分のコードをひとつにまとめてるけどそれだと多少複雑でわかりにくくなってしまうのでここでは飛車についてのみ考えるのじぇ
飛車についてのみ考えた（４）の部分のコードはこうなるのじぇ
（まあコードにコメントもつけてるので解説なくてもわかる人はコードを見るだけでもわかるかもしれないのじぇ）
// 角と飛車の利きテーブルの初期化 // 使用されている箇所を見るとここですでに障害物の位置が考慮されている.... // 邪魔ゴマを考慮した大ゴマの利きを格納するテーブルのアドレス //RookEffect[495616+1] //495626=(1<<12)*49+(1<<14)*4+(1<<13)*28 Bitboard* effects = RookEffect; // sqの升に対してテーブルのどこを引くかのindex int* effectIndex = RookEffectIndex; //邪魔ゴマを無視した飛車の利きがきいてる部分が１になってるbitboard Bitboard* masks = RookEffectMask; int index = 0; //飛車の利きのある場所は先手後手に対して同じである for (auto sq : SQ) { effectIndex[sq] = index;//sqに飛車を置いた時の邪魔ゴマを考慮した周りへの利きは一次元配列のindex番目から始まる。 // sqの地点にpieceがあるときにその利きを得るのに関係する升を取得する masks[sq] = calcEffectMask(sq, pc);//ここでsqに駒を置いた時の周りへの利きのbitboardが出来上がる。 //p[0]とp[1]に被っているところはない ASSERT_LV3(!(masks[sq].p[0] & masks[sq].p[1])); // sqの利きはのある場所bit立っているのか const int bits = masks[sq].pop_count(); //ocuppied bitboardは利きを遮る邪魔ゴマの位置 //つまり利きのある場所の数をnとすると2^n乗だけ邪魔ゴマの位置としては通りがある const int num = 1 << bits; //iを1ずつnumまで増やしていくことですべての邪魔ゴマの通りを考えることができる for (int i = 0; i < num; ++i) { Bitboard occupied = indexToOccupied(i, bits, masks[sq]);//index(iのこと)からoccupied_bitboardを作る //利きのある場所における障害物の位置はnum（1 << bits）通りある //障害物の位置を考慮した利きをここで計算する。 //index どこに利きの原因となる駒があるかによるインデックス occupiedToindex 障害物の位置の組み合わせによるインデックス effects[index + occupiedToIndex(occupied & masks[sq], masks[sq])] = effectCalc(sq, occupied, pc); } index += num; } // 盤外(SQ_NB)に駒を配置したときに利きがZERO_BBとなるときのための処理 effectIndex[SQ_NB] = index;
// 飛車をsqにおいたときに発生する利き（邪魔ゴマは考慮しない） auto calcEffectMask = [](Square sq, Piece piece) { Bitboard result; ASSERT_LV3(piece == ROOK); result = RANK_BB[rank_of(sq)] ^ FILE_BB[file_of(sq)];//XOR sqの地点で利きは交わるがそこは関係ないのでXORでいい // 飛車が外周に居ない限り、その外周升は利きの計算には関係ない。 if (file_of(sq) != FILE_1) { result &= ~FILE1_BB; } if (file_of(sq) != FILE_9) { result &= ~FILE9_BB; } if (rank_of(sq) != RANK_1) { result &= ~RANK1_BB; } if (rank_of(sq) != RANK_9) { result &= ~RANK9_BB; } // sqの地点は関係ないのでクリアしておく。 result &= ~Bitboard(sq); return result; };
//indexの0と1の位置でどこに邪魔ゴマを置くか決めてresultのそのマスのbitを立てていくための関数 //indexのループは子の関数の外側にある auto indexToOccupied = [](const int index, const int bits, const Bitboard& mask_) { auto mask = mask_; auto result = ZERO_BB;//何も入っていないbitboard for (int i = 0; i < bits; ++i)//bitsは邪魔ゴマを考慮しない利き中の立っているbit数 { const Square sq = mask.pop();//邪魔ゴマを考慮しない利きから拾ってきた立っているbitの位置 if (index & (1 << i))//indexはどこに邪魔ゴマを置くかという情報を0と1で持っている result ^= sq;//障害物の位置としてresultに足す } return result; };
// Rookの障害物を考慮した利きの範囲を調べて bitboard で返すための関数。 // occupied 障害物があるマスが 1 の bitboard auto effectCalc = [](const Square square, const Bitboard& occupied, const Piece piece) { auto result = ZERO_BB; // 角の利きのrayと飛車の利きのray const SquareWithWall deltaArray[4] = { SQWW_U, SQWW_D, SQWW_R, SQWW_L }; for (auto delta : deltaArray){ // 壁に当たるまでsqを利き方向に伸ばしていく for (auto sq = to_sqww(square) + delta; is_ok(sq); sq += delta) { result ^= to_sq(sq); // まだ障害物に当っていないのでここまでは利きが到達している if (occupied & to_sq(sq)) // sqの地点に障害物があればこのrayは終了。 break; } } return result; };
ゆゆゆ...わからないところがたくさんあるよ...
最初のRookEffect[495616+1]っていうところからわからないよ...
3次元配列になってくれてたらまだわかるかもしれないけど一次元配列さんにされるとわからないよ....
じゃあまずそこから説明していくのじぇ
RookEffectっていうのはすべての飛車の位置に対するすべての邪魔ゴマの位置を考慮したひしゃのききが格納されている配列なのじぇ
まずはこの図を見てどこに飛車があればどれだけのマスに利きが生まれるのかを理解してほしいのじぇ
一番端のマスには飛車が一番端のマスに居ない限り利きを作らないということに注意してほしいのじぇ
ここでこの飛車の利きのある青色の升に駒をおいてみるとしようじぇ。
駒は全く置かなくてもいいし青い升すべてにおいてもいいのじぇ。
そうすると駒の置き方の総数は（そこに駒を置くかおかないか）＾(駒を置けるマスの総数)のじぇ
つまり駒を置けるマスをｎ升とすると
2＾n通りあるのじぇ。
これはbit演算を用いると
1<<nということなのじぇ
またこの図の場合を考えると
2進数で14桁ある整数（i）を用いて
1番下の桁に1一のマスに邪魔ゴマを置くかどうかの情報を格納する
2番下の桁に2一のマスに邪魔ゴマを置くかどうかの情報を格納する
3番下の桁に3一のマスに邪魔ゴマを置くかどうかの情報を格納する
....
とすると
2一と３一のマスに邪魔ゴマを置くという情報は
i=000000000000110
とあらわされるのじぇ。
ということはつまり
iの値を000000000000000から11111111111111になるまで１ずつ増やして行くと
すべての邪魔ゴマの配置を表現できるということなのじぇ
ということはすべての飛車の位置に対するすべての邪魔ゴマの位置を考慮したひしゃのききを格納するためには
(1<<12)49+(1<<14)4+(1<<13)*28=495626だけbitboardがひつようということになるのじぇ
ここに飛車が盤上にない時のことを格納するための場所をつけ足して+1しておけばいいのじぇ。
これでRookEffect[495616+1]はりかいできたはずなのじぇ。
ゆゆっ！これはすごいよ！
後はさっき解説した
iの値を000000000000000から11111111111111になるまで１ずつ増やして行くと
すべての邪魔ゴマの配置を表現できるということを利用して
邪魔ゴマの位置を格納したoccupied bitboardを作って
それをもとに邪魔ゴマの位置を考慮した飛び利きを格納していけばいいだけなのじぇ。
// sqの利きはのある場所bit立っているのか const int bits = masks[sq].pop_count(); //ocuppied bitboardは利きを遮る邪魔ゴマの位置 //つまり利きのある場所の数をnとすると2^n乗だけ邪魔ゴマの位置としては通りがある const int num = 1 << bits; //iを1ずつnumまで増やしていくことですべての邪魔ゴマの通りを考えることができる for (int i = 0; i < num; ++i) { Bitboard occupied = indexToOccupied(i, bits, masks[sq]);//index(iのこと)からoccupied_bitboardを作る //利きのある場所における障害物の位置はnum（1 << bits）通りある //障害物の位置を考慮した利きをここで計算する。 //index どこに利きの原因となる駒があるかによるインデックス occupiedToindex 障害物の位置の組み合わせによるインデックス effects[index + occupiedToIndex(occupied & masks[sq], masks[sq])] = effectCalc(sq, occupied, pc); } index += num;
２歩テーブルの初期化も内容は飛び利きの初期化と似たことをやっているのでここにコードだけはっておくのじぇ
//511=2^9-1//筋が9個あるうちのどこに歩があるかの組み合わせの数(ex 1筋に歩 3筋に歩などなど。。) for (int i = 0; i <= 0x1ff; ++i) { Bitboard b = ZERO_BB; for (int k = 0; k < 9; ++k) if ((i & (1 << k)) == 0)//iが 000001100であれば b |= FILE_BB[k];//bは3番目と4番目の筋のところに1が入ったbitboardになる。 //PAWN_DROP_MASK_BB[512] i番目の筋には歩を打てないときには1<<(9-i)に１が格納される。 //bit0..9筋に歩が打てないなら1, bit1..8筋に, …, bit8..1筋に歩が打てないなら1 PAWN_DROP_MASK_BB[i][BLACK] = b & rank1_n_bb(WHITE, RANK_8); // 2～9段目まででよい(どうせ1段目には歩は打てない) PAWN_DROP_MASK_BB[i][WHITE] = b & rank1_n_bb(BLACK, RANK_8); // 1～8段目まででよい }
平岡さんtwitterを見てる限りではわからなかったけれどすごい人なのね,,,
これを使えばrotated bitboardなんて必要ないし
AVX2以降に使えるPEXTを使えばmagic bitboardも必要なくなるのじぇ
本当にすごい人なのじぇ
～～追記～～
「なぜ大ゴマの利きは一番端の段、筋には伸びないのか」
「なぜ大ゴマの利きはp[0]とp[1]でAND演算をした時に重なる部分がないのか」
これは1~7筋目を格納しているbitboardのp[0]、8~9筋目を格納しているp[1]
の中に合計で飛び利きがあるマスが何マスあるかを求めるためにPEXTという命令を使うんだけれどそれを使える範囲が64bitだけであるので、
もし128bitすべてにたいして飛び利きのあるマスの数を調べようとすると2回pextを呼び出さなければいけなくなってしまい時間がかかってしまうので
何とか1回のPEXTで済むようしよう考えられた方法なのじぇ。
具体的な方法としてはp[1]とp[0]の利きの場所を絶対に被らないようにしてp[1]とp[0]のOR演算をして、利きの場所をどちらかにまとめようということなのじぇ
この場合を例にとって考えるのじぇ。
この図をp[0]に格納されているところ
p[1]に格納されているところに分けた結果がこうなのじぇ
そしてOR演算した結果がこれなのじぇ
これを見れば確かに利きの範囲はかぶってないことがわかるのじぇ
他の場合も考えてみればわかると思うけれど利きの範囲は絶対かぶらないのじぇ
これは大ゴマの利きを一番端の段、筋には伸ばさないことと、p[1]とp[0]を1~7筋目と8~9筋目に分けている2点のおかげなのじぇ
確かに利きが重なる部分はなくなったよ！でもよく考えてね！ふつう大ゴマの利きは端っこまで聞いてないとおかしいよ！
飛車が端っこのマスの駒をとれないような動きしかできなくなっちゃうよ！
大丈夫なのじぇ利きさんは最終的に邪魔ゴマの位置を考慮した一次元配列を作るときにちゃんと端っこのマスまできかせるようにしてあるのじぇ。
端まで利きをきかせないのは邪魔ゴマの位置として考えられる場合の数を考えるときだけなのじぇ
邪魔ゴマの位置を考えるとき邪魔ゴマが一番端のマスに居てても、
利きはその駒の上まで伸ばすことができるのでそれは別にそこに邪魔ゴマがないのと一緒なのじぇ
だから別にこの部分ではこれでいいのじぇ。
なるほど！とっても賢いんだよ！ゆっくりりかいしたよ！
それともう一つ
「なぜp[0]の63bit目を０にしておくひつようがあるのか」
についてまりちゃが考えた理由をここでいっておくのじぇ。もしかしたら間違ってるのかもしれないのじぇ
63bit目を空にしておくのはさっき述べたようにPextを一回で済ますためにbitboardをOR演算する必要があるためなのじぇ。
64bitの数え方は0~63であり、p[0]には7筋目まで格納されるので9かける7の0~62bitまでが盤として必要なのじぇ
つまり63ビット目はあまりであり、そこをpextで数えてしまわないように必ず0にしておくということだとまりちゃはかんがえているのじぇ。
この考え方が正しいことの理由付けはAll_BBの定義の仕方なのじぇ。
その部分のコードはこうなっているのじぇ
Bitboard ALL_BB = Bitboard(UINT64_C(0x7FFFFFFFFFFFFFFF), UINT64_C(0x3FFFF));
0x7FFFFFFFFFFFFFFFというのは63bitが立っている整数で64bit目は立っていないのじぇ
よって使わない部分のbitを0にしておくために63bit目は絶対立てないようにするのじぇ
次回はほかの部分の初期化について説明していくのじぇ
