daruma3940の日記

理解や文章に間違い等あればどんなことでもご指摘お願いします

Bitboardの作り方

f:id:daruma3940:20160520223745p:plain
以前RotatedBitboardとはどんなものなのかということについては述べたので、
daruma3940.hatenablog.com

初心者向けに具体的にどう作るかについて書いていこうじぇ。
ここから下に出てくるコードは
GPLで公開されているプログラム(Stockfish)を改変したり、自らのプログラムの一部として組み込んだ場合など、派生的・二次的な著作物を作成した場合には、これにもGPLを適用して公開しなければならないらしいので
GPLライセンスになり、使うのは注意なのじぇ。

今回のbitboardは縦型bitboardにするのじぇ。

とりあえず最初に縦型bitboard[81]のとあるマス(index)が
90度,±45度の回転を受けたときにrotated90bitbord[81],rotated±45bitboard[81]
のどのindexになるのかの対応を記したテーブルをつくろうじぇ?

これが縦型bitboardの升(index)の並び
f:id:daruma3940:20170813122054p:plain
これが反時計回り90度回転bitboardの升の並び
f:id:daruma3940:20170813123015p:plain
これのindexとマスを対応づけようとすると以下のようになるw

/*

bitboardは縦型bitboardで[0]が44bit迄使用

bitboard 90のレイアウト

 0 1 2 3 4 5 6 7 8
 91011121314151617
181920212223242526
272829303132333435
363738394041424344
454647484950515253
545556575859606162
636465666768697071
727374757677787980

 */

//sqのindexをsq90のインデックスに変換するために使うテーブル
const int sq2sq90[SQ_NUM] = {

	72,63,54,45,36,27,18,9,0,
	73,64,55,46,37,28,19,10,1,
	74,65,56,47,38,29,20,11,2,
	75,66,57,48,39,30,21,12,3,
	76,67,58,49,40,31,22,13,4,
	77,68,59,50,41,32,23,14,5,
	78,69,60,51,42,33,24,15,6,
	79,70,61,52,43,34,25,16,7,
	80,71,62,53,44,35,26,17,8,

};

ちょっとわかりにくいかもしれないけど、
sq2sq90[0]=72
sq2sq90[1]=63

0番目のindexが72番目のindexに移り
1番目のindexが63番目のindexに移り
ということなので
追いかけてみるとさっきのレイアウトと一致していることがわかるはずw


同様にしてプラスマイナス45度回転bitboardの升との対応表もつくろうじぇ

/*

bitboard_plus45

 1 2 3 4 5 6 7 8 0
11121314151617 910
212223242526181920
313233343527282930
414243444737383940
515253454647484950
616254555657585960
716364656667686970
727374757677787980

*/
const int sq2sqplus45[SQ_NUM] = {

0,72,63,54,45,36,27,18, 9,10,//9
1,73,64,55,46,37,28,19,20,11,//19
 /*20*/2,/*21*/74,/*22*/65,/*23*/56,/*24*/47,/*25*/38,/*26*/29,/*27*/30,/*28*/21,/*29*/12,
/*30*/3,/*31*/75,/*32*/66,/*33*/57,/*34*/48,/*35*/39,/*36*/40,/*37*/31,/*38*/22,/*39*/13,
 /*40*/4,/*41*/76,/*42*/67,/*43*/58,/*44*/49,/*45*/50,/*46*/41,/*47*/32,/*48*/23,/*49*/14,
/*50*/5,/*51*/77,/*52*/68,/*53*/59,/*54*/60,/*55*/51,/*56*/42,/*57*/33,/*58*/24,/*59*/15,
/*60*/6,/*61*/78,/*62*/69,/*63*/70,/*64*/61,/*65*/52,/*66*/43,/*67*/34,/*68*/25,/*69*/16,
/*70*/7,/*71*/79,/*72*/80,/*73*/71,/*74*/62,/*75*/53,/*76*/44,/*77*/35,/*78*/26,/*79*/17,
/*80*/8,

};


/*

bitboard minus 45

 7 6 5 4 3 2 1 0 8
151413121110 91716
237221201918262524
313029282735343332
393837364443424140
474645535251504948
555462616059585756
637170696867666564
807978777675747372

*/
const int sq2sqminus45[SQ_NUM] = {

	/*0*/9,18,27,36,45,54,63,72,/*8*/0,
	/*9*/19,28,37,46,55,64,/*15*/73,/*16*/1,/*17*/10,
	/*18*/29,38,47,56,65,74,/*24*/2,/*25*/11,/*26*/20,
	/*27*/39,48,57,66,/*31*/75,/*32*/3,12,21,/*35*/30,
	/*36*/49,58,67,/*39*/76,/*40*/4,13,22,31,/*44*/40,
	/*45*/59,68,77,/*48*/5,14,23,32,41,/*53*/50,
	/*54*/69,78,/*56*/6,15,24,33,42,51,/*62*/60,

	/*63*/79,7,16,25,34,43,52,61,/*71*/70,
	/*72*/8,17,26,35,44,53,62,71,80,

};

次はシフトとマスクでindexを作成するときに
どれだけシフトすればよいのか、int64 bb[2]のうちどちらに対してシフトをすればよいのかということについて記述したテーブルをつくろうじぇ?
ちなみに私のソフトのbitboardは縦型bitboardでbb[0]がマス番号44迄使用して(マス番号44とは盤の右半分のちょうどいいとこ。自玉の位置)それ以降はbb[1]に格納しているのに注意なのじぇ
ちなみにマスクは7bit固定なのじぇ。

const int effectmask = (0b1111111);//7bitが立っている。

なぜ7bitかというと邪魔ゴマとして考慮しないといけいないのは7つで十分だからなのじぇ。9*9=81なので9bit何じゃないかと思うかもしれないけど9bitは別に要らないのじぇ
daruma3940.hatenablog.com

まずは無回転bitboardにたいしてなのじぇ。

/*
利きを求めるために何ビットシフトさせないといけないか
*/
extern int shift_table_tate[SQ_NUM];//何bit shiftさせるか
extern int index_table_tate[SQ_NUM];//bb[0]かbb[1]のどちらを見るのか
inline void make_shifttate() {

	for (Square sq = SQ_ZERO; sq < SQ_NUM; sq++) {
		shift_table_tate[sq]= int(1 + 9 * (sqtofile(sq) % 5));
	}
}
inline void make_indextate() {
	for (Square sq = SQ_ZERO; sq < SQ_NUM; sq++) {
		sq > 44 ? index_table_tate[sq] = 1 : index_table_tate[sq] = 0;
	}
}

次は反時計回り90度

extern int shift_table_yoko[SQ_NUM];
extern int index_table_yoko[SQ_NUM];

inline void make_shiftyoko() {

	for (Square sq = SQ_ZERO; sq < SQ_NUM; sq++) {
		Rank r = sqtorank(sq);
		//File f = sqtofile(sq);
		if (RankA <= r&&r <= RankD) {
			shift_table_yoko[sq]= (1 + (9 * (3 - r)));
		}
		else {
			shift_table_yoko[sq] = (1 + (9 * (8 - r)));
		}
	}
}
inline void make_indexyoko() {

	for (Square sq = SQ_ZERO; sq < SQ_NUM; sq++) {
		File f = sqtofile(sq);
		(9 * (int)f <= (int)sq&& (int)sq <= 9 * (int)f + 3) ? index_table_yoko[sq]= 1 : index_table_yoko[sq]= 0;
	}
}

ナナメ+45度

extern int indexPlus45[SQ_NUM];
extern int shiftPlus45[SQ_NUM];


void make_indexplus45() {

	for (Square sq = SQ1A; sq < SQ_NUM; sq++) {

		int s = sq % 10;
		if (s == 0 || s == 9 || s == 8 || s == 7 || s == 6 || sq == 5 || sq == 15 || sq == 25 || sq == 35) {

			indexPlus45[sq] = 0;

		}
		else {
			indexPlus45[sq] = 1;
		}

	}

}

int shiftPlus45[SQ_NUM];


void make_shiftplus45() {

	for (Square sq = SQ1A; sq < SQ_NUM; sq++) {

		//10で割ったあまりの値で大体は区別できる
		int s = sq % 10;
		
		if (s==0) {
			shiftPlus45[sq] = 1;
		}
		else if(s==9){
			shiftPlus45[sq] = 2 + 9 * 1;
		}
		else if (s == 8) {

			//これは端っこであるのでどのようなobstacleであろうが機器の数はゼロ
			if (sq == 8) {
				shiftPlus45[sq] = 9 * 1;
			}
			else {
				shiftPlus45[sq] = 3 + 9 * 2;
			}

		}
		else if (s == 7) {

			if (sq <= 17) {
				shiftPlus45[sq] = 9 * 2;
			}
			else {
				shiftPlus45[sq] = 4 + 9 * 3;
			}
		}
		else if (s == 6) {
			if (sq <= 26) {
				shiftPlus45[sq] = 1 + 9 * 3;
			}
			else {
				shiftPlus45[sq] = 5 + 9 * 4;
			}
		}
		else if (s == 5) {
			if (sq <= 35) {
				shiftPlus45[sq] = 1 + 9 * 4;
			}
			else {
				shiftPlus45[sq]= 6;
			}
		}
		else if (s == 4) {
			if (sq <= 44) {
				shiftPlus45[sq] = 1;
			}
			else {
				shiftPlus45[sq] = 7 + 9 * 1;
			}
		}
		else if (s == 3) {
			shiftPlus45[sq] = 1 + 9 * 1;
			//63 73の場合は別に場合分けする必要はない
		}
		else if (s == 2) {
			//72の場合も考えられるが72は一番端っこであるため利きはゼロに成るので無視していい
			shiftPlus45[sq] = 1 + 9 * 2;
		}
		else if (s == 1) {
			shiftPlus45[sq] = 1 + 9 * 3;
		}
	}

}

ナナメ-45度

extern int indexMinus45[SQ_NUM];
extern int shiftMinus45[SQ_NUM];

int indexMinus45[SQ_NUM] = {

	0,0,0,0,1,1,1,1,0,//8
	0,0,0,1,1,1,1,0,0,//17
	0,0,1,1,1,1,0,0,0,//26
	0,1,1,1,1,0,0,0,0,//35
	1,1,1,1,0,0,0,0,0,//44
	1,1,1,0,0,0,0,0,1,//53
	1,1,0,0,0,0,0,1,1,//62
	1,0,0,0,0,0,1,1,1,//71
	0,0,0,0,0,1,1,1,1,


};

void make_shiftMinus45()
{
	for (Square sq = SQ1A; sq < SQ_NUM; sq++) {

		int s = sq % 8;

		if (s == 0) {
			if (sq == 0) {
				shiftMinus45[sq] = 0;
			}
			else if (sq == 80) {
				shiftMinus45[sq] = 0;
			}
			else {
				shiftMinus45[sq] = 1;
			}
		}
		if (s == 1) {
			if (sq <= 9) {
				shiftMinus45[sq] = 0;
			}
			else {
				shiftMinus45[sq] = 2 + 9 * 1;
			}
		}
		if (s == 2) {
			if (sq <= 18) {
				shiftMinus45[sq] = 1 + 9 * 3;
			}
			else {
				shiftMinus45[sq] = 3 + 9 * 2;
			}
		}
		if (s == 3) {
			if (sq <= 27) {
				shiftMinus45[sq] = 1 + 9 * 4;
			}
			else {
				shiftMinus45[sq] = 4 + 9 * 3;
			}
		}
		if (s == 4) {
			if (sq <= 36) {
				shiftMinus45[sq] = 1;
			}
			else {
				shiftMinus45[sq] = 5 + 9 * 4;
			}
		}
		if (s == 5) {
			if (sq <= 45) {
				shiftMinus45[sq] = 1 + 9 * 1;
			}
			else {
				shiftMinus45[sq] = 6;
			}
		}
		if (s == 6) {
			if (sq <= 54) {
				shiftMinus45[sq] = 1 + 9 * 2;
			}
			else {
				shiftMinus45[sq] = 7 + 9 * 1;
			}
		}
		if (s == 7) {
			if (sq <= 63) {
				shiftMinus45[sq] = 1 + 9 * 3;
			}
			else {
				shiftMinus45[sq] = 0;
			}
		}
			
	}
}

f:id:daruma3940:20160521003616p:plain
きったないソースコード恥ずかしくないの??
f:id:daruma3940:20160520223745p:plain
恥ずかしい...
この辺bonanzaとかshogi686とかはもっときれいに作ってるのでみんなそっちを参考にしようね!

ここからが邪魔ゴマを考慮したとび効きの作り方なのじぇ
(やばいもう飽きてきてしまった....)

/*
追加シフト三角行列
*/

int additional_plus45(Square sq) {
	File f = sqtofile(sq);
	Rank r = sqtorank(sq);

	return std::max(int(f - r), 0);
}

int additional_minus45(Square sq) {
	File f = sqtofile(sq);
	Rank r = sqtorank(sq);

	return std::max(int(f+r-8), 0);
}

//LongEffect
	
	for (Square sq = SQ1A; sq < SQ_NUM; sq++) {
		for (int obstacle = 0; obstacle < 128; obstacle++) {
			int obstacle2 = obstacle<<1;//一つシフトしてやらないといけない!!!
			int direc_rook_yoko[2] = { 9,-9 };
			
			File tofile;
			for (int i = 0; i < 2; i++) {
				to = sq;
				do {
					to += Square(direc_rook_yoko[i]);
					tofile = sqtofile(to);
					if (is_ok(to)&&(to != sq)) {
						LongRookEffect_yoko[sq][obstacle] ^= SquareBB[to];
					}
					//横や縦の関係であればこの方法は使えるけど斜めでは通用しないぞ...(縦横に射影すればいいだけ)
				} while ((!(obstacle2&(1 << tofile))) && is_ok(to));
			}

		}
	}
	//縦。下端が上手くいっていないなぜだろう?解決済み
	for (Square sq = SQ1A; sq < SQ_NUM; sq++) {
		File sqfile = sqtofile(sq);
		for (int obstacle = 0; obstacle < 128; obstacle++) {
			int direc_rook_yoko[2] = { 1,-1 };
			int obstacle2 = obstacle<<1;//一つシフトしてやらないといけない!!!
			Rank torank;
			File tofile;
			for (int i = 0; i < 2; i++) {
				to = sq;
				do {
					to += Square(direc_rook_yoko[i]);
					torank = sqtorank(to);
					tofile = sqtofile(to);
					if (is_ok(to) && (to != sq) && (tofile == sqfile)) {
						LongRookEffect_tate[sq][obstacle] ^= SquareBB[to];
					}
					//横や縦の関係であればこの方法は使えるけど斜めでは通用しないぞ...(射影すればいいだけ)
				} while ((!(obstacle2&(1 << torank))) && is_ok(to)&&(tofile==sqfile));//縦の場合はfileが同じかどうかも調べなければならない。
			}
		}
	}
	//香車の効きテーブルの作成
	for (Color c = BLACK; c < ColorALL; c++) {
		for (Square sq = SQ_ZERO; sq < SQ_NUM; sq++) {
			for (int obstacle = 0; obstacle < 128; obstacle++) {
				LanceEffect[c][sq][obstacle] = (LongRookEffect_tate[sq][obstacle] & InFront_BB[c][sqtorank(sq)]);
				//cout << LanceEffect[c][sq][obstacle] << endl;
			}
		}
	}


	/*
	よく考えると斜めもrankに射影してしまえば横と同じように処理できるか(´・ω・`)
	横のほうが処理が簡単なので横で計算する。
	*/
	//斜めプラス45度
	//この方法では上から角の効きが伸びてきてしまうということが起こりうる!!(解決済み)
	for (Square sq = SQ1A; sq < SQ_NUM; sq++) {
		/*File sqfile = sqtofile(sq);
		Rank sqrank = sqtorank(sq);*/
		for (int obstacle = 0; obstacle < 128; obstacle++) {

			int direc_bishop_p45[2] = { -10, + 10 };
			int obstacle2 = obstacle << (1+additional_plus45(sq));//シフトさせる。

			Rank torank;
			File tofile;//横方向への射影。
			Square oldto;
			Rank oldrank;
			for (int i = 0; i < 2; i++) {
				to = sq;
				//tofile = sqtofile(to);
				do {
					/*
					oldtoを保持してoldtoとnewtoのrankが2つ以上離れないようにする。
					*/
					oldto = to;
					oldrank = sqtorank(oldto);
					to += Square(direc_bishop_p45[i]);
					torank = sqtorank(to);
					tofile = sqtofile(to);
					if (is_ok(to) && (to != sq)&&(abs(torank-oldrank)<2)) {
						LongBishopEffect_plus45[sq][obstacle] ^= SquareBB[to];
					}
				} while (!(obstacle2&(1 << (tofile))) && is_ok(to) && (abs(torank - oldrank)<2));
			}
		}
	}


	//斜め-45度
	for (Square sq = SQ1A; sq < SQ_NUM; sq++) {
		/*File sqfile = sqtofile(sq);
		Rank sqrank = sqtorank(sq);*/
		for (int obstacle = 0; obstacle < 128; obstacle++) {

			//int obstacle_ = change_indian(obstacle);
			int direc_bishop_m45[2] = { -8, +8 };
			int obstacle2 = obstacle << (1+additional_minus45(sq));//

			Rank torank;
			File tofile;//横方向への射影。
			Square oldto;
			Rank oldrank;
			for (int i = 0; i < 2; i++) {
				to = sq;
				//tofile = sqtofile(to);
				do {
					/*
					oldtoを保持してoldtoとnewtoのrankが2つ以上離れないようにする。
					*/
					oldto = to;
					oldrank = sqtorank(oldto);
					to += Square(direc_bishop_m45[i]);
					torank = sqtorank(to);
					tofile = sqtofile(to);
					if (is_ok(to) && (to != sq) && (abs(torank - oldrank)<2)) {
						//obstacleのbitを1を7に7を1にというように入れ替えなければならない。
						LongBishopEffect_minus45[sq][(obstacle)] ^= SquareBB[to];
					}
				} while ((!( obstacle2&(1 << (tofile)))) && is_ok(to) && (abs(torank - oldrank)<2));
			}
		}
	}


そして使い方はこんな感じ

Bitboard long_effect(const Occ_256 & occ, const Color c, const Piece pt, const Square sq)
{

	uint8_t obstacle_tate;
	uint8_t obstacle_yoko;
	uint8_t obstacle_plus45;
	uint8_t obstacle_Minus45;
	switch (pt)
	{
	
	case LANCE:
		obstacle_tate = (occ.b64(0) >> occ256_shift_table_tate[sq])&effectmask;
		return LanceEffect[c][sq][obstacle_tate];
		break;
	case BISHOP:
		obstacle_plus45 = (occ.b64(2) >> occ256_shift_table_p45[sq])&effectmask;
		obstacle_Minus45 = (occ.b64(3) >> occ256_shift_table_m45[sq])&effectmask;
		return LongBishopEffect_plus45[sq][obstacle_plus45] | LongBishopEffect_minus45[sq][obstacle_Minus45];
		break;
	case ROOK:
		obstacle_tate = (occ.b64(0) >> occ256_shift_table_tate[sq])&effectmask;
		obstacle_yoko = (occ.b64(1) >> occ256_shift_table_yoko[sq])&effectmask;
		return LongRookEffect_tate[sq][obstacle_tate] | LongRookEffect_yoko[sq][obstacle_yoko];
		break;
	case UNICORN://馬のこと
		obstacle_plus45 = (occ.b64(2) >> occ256_shift_table_p45[sq])&effectmask;
		obstacle_Minus45 = (occ.b64(3) >> occ256_shift_table_m45[sq])&effectmask;
		return LongBishopEffect_plus45[sq][obstacle_plus45] | LongBishopEffect_minus45[sq][obstacle_Minus45]| StepEffect[BLACK][KING][sq];
		break;
	case DRAGON:
		obstacle_tate = (occ.b64(0) >> occ256_shift_table_tate[sq])&effectmask;
		obstacle_yoko = (occ.b64(1) >> occ256_shift_table_yoko[sq])&effectmask;
		return LongRookEffect_tate[sq][obstacle_tate] | LongRookEffect_yoko[sq][obstacle_yoko]|StepEffect[BLACK][KING][sq];
		break;
	default:
		UNREACHABLE;
		return ALLBB;
		break;
	}
}

縦方向の効きは1段目9段目に邪魔ゴマがあっても1段目9段目に効きを作ることができるので縦方向occupiedbitboardは1段目9段目を表すbitを除いて7*9=63bitあればよく
横方向も1筋目9筋目のbitはいらないので7*9=63bit
斜めはそれぞれ7*7=49bitあればよいので
実はoccupiedbitboardはすべて256bitに収めることができ
これによって駒が動いた時のoccupiedbitboardのこうしんの処理はSIMD演算を使えば一気に処理できる
という工夫を使っているのでocc_256とかocc.b64(1)とかが出てきていて説明した内容とはちょっと異なるけど基本こんな感じでシフトしてマスク取ってindexを作って
そのindexを用いてテーブル引きをしているだけなのじぇ(飽きたのでおしまい)