オセロにおけるビットボード
このページでは、オセロにおけるビットボードを使用した計算法を説明する。
概要[編集]
8x8 = 64 マスについて、石が存在するかどうかを1ビットで表すデータ構造。
ひとつの石種について64ビット、オセロは黒白2種類の石があるので、64ビット変数 x 2 で盤面を表すことができる。
相手の石を挟んだかどうかなどの判定や、石の反転などの処理を再帰やループを使わず、シフトや論理演算だけで複数の石について同時に行うことができる（ビットパラレル性）ため、通常のデータ構造よりも処理が高速になる。
詳細[編集]
オセロの盤面は 8x8 = 64 マス、石は白黒2種類なので、64ビット整数を２つ用意すれば盤面を表現することができる。
typedef uint64 BitBoard;
class CBanmen
{
BitBoard black;
BitBoard white;
};
白黒反転[編集]
ネガマックス、ネガアルファなどの反転系のゲーム木探索アルゴリズムでは、次のレベルをコールするときに、盤面の先後を反転する必要があるが、オセロの盤面を2つのビットボード black, white で表し探索関数の引数として渡す場合は、以下のように引数で渡すときに順序を入れ替えるだけでよい。
int negaAlpha(BitBoard black, BitBoard white, int alpha, int beta, int depth)
{
....
for(すべての合法着手について) {
着手を実行;
// 白黒 と αΒ値を入れ替えて次のレベルをコール
int score = -negaAlpha(white, black, -beta, -alpha, depth-1);
着手を元に戻す;
....
}
....
}
盤面の各マス目とビットの対応[編集]
オセロのマスは左上が原点で、水平方向に A, B, C, ...H, 垂直方向に 1, 2, 3, ...8 で指標され、A1, D3 の様に指定される。
水平方向を col (0..7), 垂直方向を row (0..7) とすると、マスに対応するビットボードのビット番号を col + row * 8 とするとよい。
BitBoard cr2bitboard(int col, int row) // col (0..7), row (0..7) に対応するビットボード生成
{
return (BitBoard)1 << (col + row * 8);
}
石反転処理[編集]
黒の着手位置を BitBoard mv; それにより反転する位置を BitBoard rev; とすれば盤面の更新処理は以下のように記述できる。
black ^= mv | rev;
white ^= rev;
配列で盤面を表した場合、反転する石の数に比例して反転処理のコストがかかるが、ビットボードを用いれば、複数マスを同時に処理できるので、上記のように反転する石数に依存せず、一定コストで処理を行うことができる。
着手を取り消して元の状態に戻す処理も、上記の反転処理と同一になる。
ゲーム木探索で次の深さの関数をコールするとき、引数で白黒ビットボードを渡すのであれば、以下のようにすれば盤面の状態を戻す必要はない。
int negaAlpha(BitBoard black, BitBoard white, int alpha, int beta, int depth)
{
....
for(すべての合法着手について) {
// 着手を実行し、白黒 と αΒ値を入れ替えて次のレベルをコール
int score = -negaAlpha(white ^ rev, black ^ (mv | rev),
-beta, -alpha, depth-1);
....
}
....
}
反転パターン計算[編集]
合法着手である条件は以下の通りである。
- 着手位置が空白
- 着手箇所から８方向のひとつ以上について、相手の石が連続した後に自分の石がある
連続する相手の石が反転パターンとなる。
ループを用いる方法[編集]
以下にループを用いる場合のコードを示す。
このコードでは1方向についてのみチェックしているが、実際は8方向全てについてチェックしなくてはいけない。
BitBoard getRevPat(BitBoard black, BitBoard white, // 盤面状態
BitBoard m) // m は着手箇所、1ビットのみが1で他はすべて0
{
BitBoard rev = 0;
if( ((black | white) & m) != 0 ) // 着手箇所が空白で無い場合
return rev;
BitBoard mask = transfer(m);
while( mask != 0 && (mask & white) != 0 ) { // 白石が連続する間
rev |= mask;
mask = transfer(mask);
}
if( (mask & black) == 0 ) // 黒石がなければ、着手できない
return 0;
else
return rev; // 反転パターン
}
BitBoard transfer(BitBoard m) は特定方向へ移動したパターンを返す。 右方向への移動であれば、
BitBoard transfer(BitBoard m)
{
return (m>>1) & 0x7f7f7f7f7f7f7f7f;
}
と定義できる。
ループを用いない方法[編集]
ひとつの方向について反転する相手の石数の上限は6だから、ループを用いずそれぞれの場合について以下のように展開することができる。
BitBoard wh = white & 0x7e7e7e7e7e7e7e7e; // 横移動のための番人
BitBoard m2, m3, m4, m5, m6;
BitBoard m1 = pos >> 1; // pos : 着手箇所
if( (m1 & wh) != 0 ) {
if( ((m2 = m1 >> 1) & wh) == 0 ) {
if( (m2 & black) != 0 ) // 1個だけ返す場合
rev |= m1;
} else if( ((m3 = m2 >> 1) & wh) == 0 ) {
if( (m3 & black) != 0 ) // 2個返す場合
rev |= m1 | m2;
} else if( ((m4 = m3 >> 1) & wh) == 0 ) {
if( (m4 & black) != 0 ) // 3個返す場合
rev |= m1 | m2 | m3;
} else if( ((m5 = m4 >> 1) & wh) == 0 ) {
if( (m5 & black) != 0 ) // 4個返す場合
rev |= m1 | m2 | m3 | m4;
} else if( ((m6 = m5 >> 1) & wh) == 0 ) {
if( (m6 & black) != 0 ) // 5個返す場合
rev |= m1 | m2 | m3 | m4 | m5;
} else {
if( ((m6 >> 1) & black) != 0 ) // 6個返す場合
rev |= m1 | m2 | m3 | m4 | m5 | m6;
}
}
条件分岐を用いない方法[編集]
この節はまだ執筆途中です。加筆、訂正して下さる協力者を募集中!