ビットボードの任意のラインを8ビットに変換・逆変換

1. はじめに

本記事では、下記の2つの変換を取り扱う。

• 符号なし64ビット変数である8x8のビットボードの任意のライン ⇒ 8ビット変数
• ビットボードの任意のラインを変換した8ビット変数 ⇒ ビットボード

変換したいビットボードの任意のラインの指定方法は「ライン上に含まれる特定のビット＆ラインの方向」という組み合わせで指定することにする。
例えば、ビットボードのD列を8ビット変数に変換したい場合は「D列に含まれるいずれかのビット＆垂直方向」という組み合わせとなる。

2. 本記事で用いるビットボード

符号なし64ビット整数を8×8の行列だと捉えたものを用いる。
オセロの駒の位置とビット位置は下記の画像のように対応する。
例えば、位置A1の駒の状態は63ビット目で管理する。

また、ビットボードの行番号・列番号を下記とする。

よって、本記事では下記の2つの関数を使用する。

// あるビットの行番号を取得する
int getRow(int bit) {
    return bit / 8;
}

// あるビットの列番号を取得する
int getColumn(int bit) {
    return bit % 8;
}

3. ビットボードの任意のライン ⇒ 8ビットへの変換

ビットボードの任意のラインの選び方は、下記の4つが存在する。

• 水平方向のライン
• 垂直方向のライン
• 斜め上方向のライン
• 斜め下方向のライン

各ラインを8ビットに変換する方法を下記で解説する。

3-1. 水平方向のライン ⇒ 8ビットへの変換

あるビットの水平方向のラインの8ビットへの変換は
ビットの水平方向のラインをマスクし、ビットの行番号の8倍だけ右シフトすることで実現できる。

using u64 = unsigned long long;
using u8  = unsigned char;

// あるビットの水平方向のライン ⇒ 8ビット
u8 convertHorizontalTo8(u64 x, int bit) {
	int shift = getRow(bit) * 8;
	u64 mask = 0x00000000000000FF << shift;
	return (x & mask) >> shift;
}

3-2. 垂直方向のライン ⇒ 8ビットへの変換

下記の手順で実現できる。

① あるビットの垂直方向のラインを列数だけ右シフトして、右端に集める。

② 0x0102040810204080を掛け、上位8ビットに垂直方向のラインを集める。

③ 56ビットだけ右シフトする。

// あるビットの垂直方向のライン ⇒ 8ビット
u8 convertVerticalTo8(u64 x, int bit) {
	int clmn = getColumn(bit);
	u64 mask = 0x0101010101010101 << clmn;
	return (((x & mask) >> clmn) * 0x0102040810204080) >> 56;
}

3-3. 斜め上方向のライン ⇒ 8ビットへの変換

下記の手順で実現できる。2つの例を用いて解説する。

• あるビットの斜め上方向のラインが下記のとき
  
  ① 0x0101010101010101を掛け、上位8ビットに斜め上方向のラインを集める。
  
  ① 56ビットだけ右シフトする
  

• あるビットの斜め上方向のラインが以下のとき
  
  ① 0x0101010101010101を掛け、上位8ビットに斜め上方向のラインを集める。
  
  ① 56ビットだけ右シフトする。
  

// 斜め上方向のマスク
u64 dia_a8h1_mask[] = {
	0x0000000000000001, 0x0000000000000102, 0x0000000000010204,
	0x0000000001020408, 0x0000000102040810, 0x0000010204081020,
	0x0001020408102040, 0x0102040810204080, 0x0204081020408000,
	0x0408102040800000, 0x0810204080000000, 0x1020408000000000,
	0x2040800000000000, 0x4080000000000000, 0x8000000000000000
};

// ビットの行番号・列番号から斜め上方向のマスクを求める
u64 getDiagonalA8H1Mask(int bit) {
	return dia_a8h1_mask[getRow(bit) + getColumn(bit)];
}

// あるビットの斜め上方向のライン ⇒ 8ビット
u8 convertDiagonalA8H1To8(u64 x, int bit) {
	u64 mask = getDiagonalA8H1Mask(bit);
	return ((x & mask) * 0x0101010101010101) >> 56;
}

3-4. 斜め下方向のライン ⇒ 8ビットへの変換

下記の手順で実現できる。2つの例を用いて解説する。

• あるビットの斜め下方向のラインが下記のとき
  
  ① 0x0101010101010101を掛け、上位8ビットに斜め下方向のラインを集める。
  
  ② 56ビットだけ右シフトする。
  

• あるビットの斜め下方向のラインが下記のとき
  
  ① 0x0101010101010101を掛け、上位8ビットに斜め下方向のラインを集める。
  
  ② 56ビットだけ右シフトする。
  

// 斜め下方向のマスク
u64 dia_a1h8_mask[] = {
	0x0000000000000080, 0x0000000000008040, 0x0000000000804020,
	0x0000000080402010, 0x0000008040201008, 0x0000804020100804,
	0x0080402010080402, 0x8040201008040201, 0x4020100804020100,
	0x2010080402010000, 0x1008040201000000, 0x0804020100000000,
	0x0402010000000000, 0x0201000000000000, 0x0100000000000000
};

// ビットの行番号・列番号から斜め下方向のマスクを求める
u64 getDiagonalA1H8Mask(int bit) {
	return dia_a1h8_mask[(getRow(bit) - getColumn(bit)) + 7];
}

// あるビットの斜め下方向のライン ⇒ 8ビット
u8 convertDiagonalA1H8To8(u64 x, int bit) {
	u64 mask = getDiagonalA1H8Mask(bit);
	return ((x & mask) * 0x0101010101010101) >> 56;
}

4. 任意のラインを変換した8ビット ⇒ ビットボードへの変換

4-1. 水平方向のラインを変換した8ビット ⇒ ビットボードへの変換

変換した8ビットを、あるビットの行数の8倍だけ左シフトすることで実現できる。

// 水平方向のラインを変換した8ビット ⇒ ビットボードへの変換
u64 convert8ToHorizontal64(u8 x, int bit) {
	return (u64)x << (getRow(bit) * 8);
}

4-2. 垂直方向のラインを変換した8ビット ⇒ ビットボードへの変換

下記の手順で実現できる。

① 垂直方向のラインの8ビット

② 0x0101010101010101を掛ける。

③ A1からH8の対角線のマスクを取る。

④ 0x00000000000000FFを掛け、左端に垂直方向のラインを集める。

⑤ 左端のマスクを取る。

⑥ (7 - あるビットの列数)だけ右シフトする。

// 垂直方向のラインを変換した8ビット ⇒ ビットボードへの変換
u64 convert8ToVertical64(u8 x, int bit) {
	return (((((u64)x
			   * 0x0101010101010101) & 0x8040201008040201)
		       * 0x00000000000000FF) & 0x8080808080808080)
			   >> (7 - getColumn(bit));
}

4-3. 斜め上方向のラインを変換した8ビット ⇒ ビットボードへの変換

下記の手順で実現できる。

① 斜め上方向のラインの8ビット

② 0x0101010101010101を掛ける。

③ あるビットの斜め上方向のマスクを取る。

// 斜め上方向のラインを変換した8ビット ⇒ ビットボードへの変換
u64 convert8ToDiagonalA8H1(u8 x, int bit) {
    u64 mask = getDiagonalA8H1Mask(bit);
	return ((u64)x * 0x0101010101010101) & mask;
}

4-4. 斜め下方向のラインを変換した8ビット ⇒ ビットボードへの変換

先程の斜め上方向と同様に、斜め下方向のラインを変換した8ビットに0x0101010101010101を掛け、あるビットの斜め下方向のマスクを取ることで実現できる。

// 斜め下方向のラインを変換した8ビット ⇒ ビットボードへの変換
u64 convert8ToDiagonalA1H8(u8 x, int bit) {
    u64 mask = getDiagonalA1H8Mask(bit);
	return ((u64)x * 0x0101010101010101) & mask;
}