組込み屋でもアプリがしたい！第6局

前回、オセロの盤面を64ビット整数で表現するBit Boardをやりましたが、今回はビット演算を駆使したBit Boardの処理の高速化に取り組みます。とくに合法手(その局面で打てる有効な着手)を列挙する処理の高速化に著しい効果がありました。

石の数を数える

BitBoardでは、石の数を数えるとは64ビット整数の立っているビットの数を数える処理です。実は、IntelのCPUにはpopcntという、立っているビットの数を数える命令があるらしいですが、今回はビット演算を駆使する方法を使います。

// 立っているビットを数えるアルゴリズム
private int popcnt( ulong data )
{
    // 以下のコメントでは
    // dataの第nビット(n=0..31)をdata[n]と表す
    // dataの第nビットから第mビットまでをdata[m:n]と表す

    // data[2n]とdata[2n+1]の立っているビットの合計数をdata[2n+1:2n]に格納
    data = (data & 0x5555555555555555) + (data >> 1 & 0x5555555555555555);

    // data[2n+1:2n]とdata[2n+3:2n+2]の合計をdata[2n+3:2n]に格納
    data = (data & 0x3333333333333333) + (data >> 2 & 0x3333333333333333);

    // data[2n+3:2n]とdata[2n+7:2n+4]の合計をdata[2n+7:2n]に格納
    data = (data & 0x0f0f0f0f0f0f0f0f) + (data >> 4 & 0x0f0f0f0f0f0f0f0f);

    // data[2n+7:2n]とdata[2n+15:2n+8]の合計をdata[2n+15:2n]に格納
    data = (data & 0x00ff00ff00ff00ff) + (data >> 8 & 0x00ff00ff00ff00ff);

    // data[2n+15:2n]とdata[2n+31:2n+16]の合計をdata[2n+31:2n]に格納
    data = (data & 0x0000ffff0000ffff) + (data >> 16 & 0x0000ffff0000ffff);

    // data[31:0]とdata[63:32]の合計をdata[31:0]に格納
    data = (data & 0x00000000ffffffff) + (data >> 32 & 0x00000000ffffffff);

    return (int)data;
}

簡単のため8ビット整数について、1行目の処理を図示します。

合法手を列挙する

ここでは、自分の石の左側にある相手の石をひっくり返す合法手の列挙について考えます。他の7方向についても同様の処理になります。

// myStone: 自分の石, hisStone: 相手の石
private ulong getNextMovesL(ulong myStone, ulong hisStone)
{
    // 空いているマス
    ulong noStone = ~(myStone | hisStone);
    
    // 相手の石にマスクを施す(隅の石がシフト演算で回り込むのを防止)
    hisStone &= 0x7E7E7E7E7E7E7E7E;

    // 自分の石の左隣にある相手の石
    ulong moves = (myStone << 1) & hisStone;

    // さらに左隣にある相手の石も加える(最大6個まで)
    moves |= (moves << 1) & hisStone;
    moves |= (moves << 1) & hisStone;
    moves |= (moves << 1) & hisStone;
    moves |= (moves << 1) & hisStone;
    moves |= (moves << 1) & hisStone;

    // それらの左隣の空いているマス
    moves = (moves << shift) & noStone;

    return moves; // すべての合法手が列挙されたBit Boardを返す
}

右方向のときは右1ビットシフトになります。真上方向は左8ビットシフト、真下方向は右8ビットシフト、左上方向は左9ビットシフト…となります。また、真上方向と真下方向のときはシフトによる回り込みがあり得ないので、マスクは不要となります。

ひっくり返る石を列挙する

ここでは、自分の石の左側にある相手の石をひっくり返す処理について考えます。他の7方向についても同様の処理になります。

// myStone: 自分の石, hisStone: 相手の石, move: 着手
private ulong getReversesL(ulong myStone, ulong hisStone, ulong move)
{
    // 相手の石にマスクを施す(隅の石がシフト演算で回り込むのを防止)
    hisStone &= 0x7E7E7E7E7E7E7E7E;

    // 着手の右隣にある相手の石
    ulong r1 = (move >> 1) & hisStone;
    // さらに右隣にある相手の石も加える(最大6個まで)
    r1 |= (r1 >> 1) & hisStone;
    r1 |= (r1 >> 1) & hisStone;
    r1 |= (r1 >> 1) & hisStone;
    r1 |= (r1 >> 1) & hisStone;
    r1 |= (r1 >> 1) & hisStone;

    // 自分の石の左隣にある相手の石
    ulong r2 = (myStone << 1) & hisStone;
    // さらに左隣にある相手の石も加える(最大6個まで)
    r2 |= (r2 << 1) & hisStone;
    r2 |= (r2 << 1) & hisStone;
    r2 |= (r2 << 1) & hisStone;
    r2 |= (r2 << 1) & hisStone;
    r2 |= (r2 << 1) & hisStone;

    // 両者の重なり部分がひっくり返される
    return r1 & r2;
}

全ての合法手を試行する

まず、複数のビットが立っている整数値のうち、いちばん右側のビットのみを残してゼロにする処理は以下のようになります。xと-x(2の補数)の論理積をとると、いちばん右側のビットのみが残ります。ここで(0-x)と書いているのは、C#の符号なし整数型で-xと書くとエラーになるからです。もちろん、1つもビットが立っていない場合にはゼロが返ります。

private ulong lowestOneBit(ulong x)
{
    return (x & (0-x));
}

ちなみに、1つだけビットが立っている整数値があるとき、その立っているビットの位置は以下の処理で求められます。x-1とすると立っているビットが下がって、それより下のビットが全て立ちます。この立っているビットの数を数えれば、それが求めるビット位置となります。

private int bitPosition(ulong x)
{
    x = x-1;
    return popcnt(x);
}

さて、合法手を列挙したBit Boardから、合法手を1個ずつとりだして処理するループは次のようになります。

// nextMoves: 合法手を列挙したBit Board
// いちばん右側の立っているビットをmoveに取り出す。それがゼロであれば終了
while ((move = (nextMoves & (0 - nextMoves))) != 0)
{
    // nextMoves から move のビットのみ落とす
    nextMoves = nextMoves ^ move;
    
    // 以下、moveについて処理する
    ;
}

滴了庵日録

組込み屋でもアプリがしたい！第6局

石の数を数える

合法手を列挙する

ひっくり返る石を列挙する

全ての合法手を試行する

今回のソースのスナップショット

ひとこと

参考URL