ビットボードの凄さをざっくりと解説してみる

概要

　なぜかQiitaに無かったので書いてみました。

そもそもビット演算とは？

　コンピュータ内部では、データは全て0/1の2進数で管理されています。整数の場合、それが8bit・16bit・32bit・64bitなどと並ぶことで表現されます。変換方法は略しますが、10進数での「841」は2進数での「11 0100 1001」、10進数での「123456789」は2進数での「111 0101 1011 1100 1101 0001 0101」となるわけですね。
　ここで2進数の重要な性質としては、AND演算やOR演算などのビット演算を行うことで、ビット単位でのデータ処理ができるということです。つまり、ビットに情報を格納すれば、ビット演算によってそれを操作できます。一般的にビット演算は普通の加減乗除演算より速く、しかも並列処理ができるという強力な特徴があり、そのことから高速な計算速度が求められる分野ではしばしば用いられます。
　その応用例の一つとして、今回はビットボードを取り上げたいと思います。なお、説明中、幾つかの用語が出てきますので先に書いておきます。

• ビットが立つ……ある位置のビットが1になること。「ビットを立てる」も同様
• ビットマスク……特定の位置のビットだけを対象としたい場合に、それ以外の位置のビットをAND演算で0にしたり、OR演算で1にしたりさせるための事前操作(マスク)に用いるビット列のこと

ビット＋ボード＝ビットボード

　端的に書けば、「盤面をビットで表したもの」です。ごくシンプルなゲームしか無理そうですがさにあらず、その応用範囲は非常に広いものとなります。幾つかのゲームを例にして見てみましょう。

オセロの場合

　まず手始めにオセロから。盤面のサイズは通常8x8ですので64bit分……32bit整数なら2つ・64bit整数なら1つが単位の基準になります。盤面に置かれるのは黒石・白石の2種類ですので、それぞれ64bit用意しても1つの盤面を128bitで表現できることになります。例えば1つのマスごとにchar型を割り当てたりすると、charが8bitでも1つの盤面が512bitになりますので、その無駄の無さがよく分かります。

　もちろんそれで遅ければ意味がありません。各種計算が高速に実行可能なことも利点の一つです。
　例えば局面を評価する際、「黒石や白石の個数を数えたい」ということがよくあります。普通に配列に入れると**「forループで地道に数える」ことが必要なところ、ビットボードでは「立っているビットを数える」**だけで実行できます。立っているビットを高速に数えるアルゴリズムを使うことによって、条件分岐どころかループを使わずにカウントできるのです。
　また、オセロなので石を反転させる処理も必要です。着手した石の位置のビットだけを立てたものをmov・それにより反転する石の位置をrevとし、手番プレイヤーの石をm_stone・非手番プレイヤーの石をy_stoneとすると、次のような操作で反転できます。XOR演算なので、同じ操作をもう一度やれば1手戻せるというのもポイントです。

code1.cpp

m_stone ^= mov | rev;
y_stone ^= rev;

もちろんこれだと「どうやってrevを求めるんだ」ということになりますが、次のようにすれば可能です(ソースはWikipediaより)。要するに、「特定方向への移動」も、「ある場所に石が存在するか」も、ビット演算だけで表現することができるということです(より高速にしたい場合はループ展開することも可能)。

code2.cpp

/* BitBoard……オセロの盤面を格納するための64bit整数型(32bit×2でも可)
 * 説明の都合上、blackがm_stone・whiteがy_stoneに対応している
 */

BitBoard transfer(BitBoard m)  //  右方向へ移動させたパターンを返す
{
//  ビットマスクがない場合、左右や上下が盤面上で繋がってしまうことになる
    return (m>>1) & 0x7f7f7f7f7f7f7f7f;
}

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; // 反転パターン
}

なお、実際にテストしてみると、明らかな速度差がありました。

○通常
石数カウント(-20石差)：2137.66ns
着手可能箇所(10点)：7087.82ns
○ビットボード
石数カウント(-20石差)：54.8874ns
着手可能箇所(10点)：6069.57ns

将棋の場合

　次に将棋。盤面が9×9＝81マスなので81bit……となりますが若干半端なので、実装としては2つの64bit型整数か3つの32bit型整数で1つの駒を表現することが多いです。「ある位置に駒を動かせるか」も勿論ビット演算で表現できる……のですが、飛び道具である香車・角行・飛車の処理が面倒という問題があります。この対策としては主に「Rotated Bitboard」と「Magic Bitboard」がありますが、とりあえずこの資料を読んでおけば大丈夫でしょう。
　ちなみにD言語だとベクトル型や演算子オーバーロードが強力なので将棋の実装が楽だったという報告もありました。

囲碁の場合

　そして囲碁。**ビットボードで実装できるのかよ……**と思っていましたが、横方向に囲まれた位置と縦方向に囲まれた位置とをAND演算することで可能だそうです。(生死判定とか地の計算とかがどうなるかについては不明)
　ただ、昨今のコンピュータ囲碁がモンテカルロ法をベースにしていることから、ビットボードはモンテカルロ法に向いてないのではないか(したがって使うべきではないのでは)といった声もあるのですが詳細は不明です。

ライフゲームの場合

　上記3ゲームと別ベクトルですが一応紹介。ルール上、「あるビットの周囲で何ビット立っているか」をなるべく高速に計算したいものですが、ビットボードを使えばそれを全要素に対して同時に計算できます。詳しくはこちらのページやこちらのページをご覧ください。

参考資料

オセロにおけるビットボード
超高速ビットカウント
明日使えないすごいビット演算
コンピュータ将棋における Magic Bitboard の提案と実装
D言語でコンピュータ将棋プレイヤを作りました
ビット演算での考察 [第02局目]
ビットボード(Bitboard)を用いたライフゲームのソースコード
ビット演算（ビットボード）によるライフゲーム高速化