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;
}