interprism's blog

インタープリズム株式会社の開発者ブログです。

ビットボードによる αβ 法

Java ビットボード αβ法

この投稿は インタープリズムの面々が、普段の業務に役立つ記事を丹精込めて書き上げる！ Advent Calendar 2016 - Qiitaの4日目 の記事です。

こんにちは、andoです。

業務に役立つことはないかもしれないビットボードによる αβ 法の話。

今回こそ 1 位

今年の6月下旬頃、プログラミングコンテスト第 2 回を開催するということで、前回 2 位の雪辱を果たすため、 また、以前、オセロの AI を実装したこともあり、興味があったので参加することにしました。

過去のプログラミングコンテストの記事は、こちら
第 1 回（その 1 、その 2 ）
第 2 回（その 1 ）

戦略

期間が 1 ヵ月もない中、Logistello、Thell、WZebra レベルはともかく、中盤の評価関数の精度が高い AI が参戦してくることはないだろうという結構失礼な予測のもと、 中盤の評価関数はネットで得た知識でそこそこの実装に留め、終盤の読み切りを、如何に相手より早く開始するかで勝負することにしました。

実装

当初は実装をシンプルにしておきたいという思いから、序盤から終盤まで一貫して 1 次元の byte[91] を用いる予定でした。 オセロ（リバーシ）における一般的なデータ構造であり、空いているビットで開放度も管理できたので最初のバージョンはそれで実装を進め、残り 14 手完全読みにしてエントリーしました。

X white
O black
# wall

/*
 *#########
 *#........
 *#........
 *#........
 *#...XO...
 *#...OX...
 *#........
 *#........
 *#........
 *##########
 */

コンテスト開始後、しばらくすると一部参加メンバーからビットボードという言葉が聞こえてきました。 ビッドボードは知っていたものの、それだけでは石の有無しかわからないため、開放度等を用いる中盤の評価関数では別のデータ構造を用意しなくてはなりません。 そのため、byte 配列よりも手間がかかりそうで採用を見送っていましたが、ゲーム木の探索速度に優れることは分かっていたので、 相手が使用するならばこちらも対抗しなければと、急遽、終盤におけるゲーム木の探索をビットボードに切り替えました。

ようやく本題です。

合法手の候補

なるべくループは展開し、条件分岐も少なくなるようにしました。

public static long getMoves(final long own, final long enemy) {
    long topBottomMask = 0b1111111111111111111111111111111111111111111111111111111111111111L;
    long leftRightMask = 0b0111111001111110011111100111111001111110011111100111111001111110L;
    long emptyCells = getEmptyCells(own, enemy);
    // top
    long m = getMovesL(own, enemy, emptyCells, topBottomMask, 8);
    // top right
    m |= getMovesL(own, enemy, emptyCells, leftRightMask, 7);
    // right
    m |= getMovesR(own, enemy, emptyCells, leftRightMask, 1);
    // bottom right
    m |= getMovesR(own, enemy, emptyCells, leftRightMask, 9);
    // bottom
    m |= getMovesR(own, enemy, emptyCells, topBottomMask, 8);
    // bottom left
    m |= getMovesR(own, enemy, emptyCells, leftRightMask, 7);
    // left
    m |= getMovesL(own, enemy, emptyCells, leftRightMask, 1);
    // top left
    return m | getMovesL(own, enemy, emptyCells, leftRightMask, 9);
}

public static long getEmptyCells(final long own, final long enemy) {
    return ~(own | enemy);
}

private static long getMovesR(final long own, final long enemy, final long emptyCells, final long mask, final int offset) {
    long e = enemy & mask;
    long m = (own << offset) & e;
    m |= (m << offset) & e;
    m |= (m << offset) & e;
    m |= (m << offset) & e;
    m |= (m << offset) & e;
    m |= (m << offset) & e;
    return (m << offset) & emptyCells;
}

private static long getMovesL(final long own, final long enemy, final long emptyCells, final long mask, final int offset) {
    long e = enemy & mask;
    long m = (own >>> offset) & e;
    m |= (m >>> offset) & e;
    m |= (m >>> offset) & e;
    m |= (m >>> offset) & e;
    m |= (m >>> offset) & e;
    m |= (m >>> offset) & e;
    return (m >>> offset) & emptyCells;
}

合法手の選択

下位ビットから選択するのが低コストです。

public static long selectMove(final long moveCandidates) {
    return Long.lowestOneBit(moveCandidates);
}

合法手の適用

public static long getReverses(final long own, final long enemy, final long move) {
    long topBottomMask = 0b1111111111111111111111111111111111111111111111111111111111111111L;
    long leftRightMask = 0b0111111001111110011111100111111001111110011111100111111001111110L;
    // top
    long m = getReversesL(own, enemy, move, topBottomMask, 8);
    // top right
    m |= getReversesL(own, enemy, move, leftRightMask, 7);
    // right
    m |= getReversesR(own, enemy, move, leftRightMask, 1);
    // bottom right
    m |= getReversesR(own, enemy, move, leftRightMask, 9);
    // bottom
    m |= getReversesR(own, enemy, move, topBottomMask, 8);
    // bottom left
    m |= getReversesR(own, enemy, move, leftRightMask, 7);
    // left
    m |= getReversesL(own, enemy, move, leftRightMask, 1);
    // top left
    return m | getReversesL(own, enemy, move, leftRightMask, 9);
}

private static long getReversesR(final long own, final long enemy, final long move, final long mask, final int offset) {
    long e = enemy & mask;
    long m = (move << offset) & e;
    m |= (m << offset) & e;
    m |= (m << offset) & e;
    m |= (m << offset) & e;
    m |= (m << offset) & e;
    m |= (m << offset) & e;
    long o = (own >>> offset) & e;
    o |= (o >>> offset) & e;
    o |= (o >>> offset) & e;
    o |= (o >>> offset) & e;
    o |= (o >>> offset) & e;
    o |= (o >>> offset) & e;
    return m & o;
}

private static long getReversesL(final long own, final long enemy, final long move, final long mask, final int offset) {
    long e = enemy & mask;
    long m = (move >>> offset) & e;
    m |= (m >>> offset) & e;
    m |= (m >>> offset) & e;
    m |= (m >>> offset) & e;
    m |= (m >>> offset) & e;
    m |= (m >>> offset) & e;
    long o = (own << offset) & e;
    o |= (o << offset) & e;
    o |= (o << offset) & e;
    o |= (o << offset) & e;
    o |= (o << offset) & e;
    o |= (o << offset) & e;
    return m & o;
}

局面の評価

単純な石の差でなく、空いているマスが多いほうがスコアがより高くなるエキサイティングな仕様にしました。 この辺りはもう少しビット演算にできそうです。

private static int evalColorCount(final long ownBoard, final long enemyBoard) {
    int ownCount = Long.bitCount(ownBoard);
    int enemyCount = Long.bitCount(enemyBoard);

    // 途中で終了した場合は、勝利した方に空いてるセルの2倍のスコアをプラスします。
    int remain = (64 - ownCount - enemyCount) << 1;
    if (ownCount > enemyCount) {
        ownCount += remain;
    } else if (enemyCount > ownCount) {
        enemyCount += remain;
    }
    return ownCount - enemyCount;
}

合法手の削除

public static long deleteMove(final long moves, final long move) {
    return moves ^ move;
}

ゲーム木の探索

αβ 法による完全読みです。

public static int alphabetaPerfect(final long ownBoard, final long enemyBoard, final boolean alreadyPassed, final int limit, final int alpha, final int beta, final MoveRef ref) {
    if (limit == 0) {
        return evalColorCount(ownBoard, enemyBoard);
    }
    int bestScore = alpha;
    boolean pass = true;
    long moves = getMoves(ownBoard, enemyBoard);
    long move;
    while ((move = selectMove(moves)) != 0) {
        long reverses = getReverses(ownBoard, enemyBoard, move);
        pass = false;
        int score = -alphabetaPerfect(enemyBoard ^ reverses, ownBoard ^ (move | reverses), pass, limit - 1, -beta, -bestScore, null);
        if (score > bestScore) {
            if (score >= beta) {
                // cut
                return score;
            }
            bestScore = score;
            if (ref != null) {
                ref.move = move;
            }
        }
        moves = deleteMove(moves, move);
    }

    return pass
            ? alreadyPassed
            ? evalColorCount(ownBoard, enemyBoard)
            : -alphabetaPerfect(enemyBoard, ownBoard, pass, limit, -beta, -bestScore, null)
            : bestScore;
}

実装後、現実的な時間で終わるよう探索深度を調整し、残り 20 手、19手が必勝読み、残り 18 手以降を完全読みで再エントリーしました。

再帰呼出しをやめてみたが

たかだか 20 手程の読みなので StackOverflowError の心配はないものの、関数呼出しのオーバーヘッドはあるかもという興味から、 再帰呼出しをやめて単純な while ループに変更しましたが、10 % 程の劣化が生じてしまいました。 書き方が悪いのか、JIT が悪いのか、1 ループにおける処理量をパターン毎に最適化してみたり、逆に平準化してクリティカルパスを短くしてみたり色々試してみましたが、どうにも改善しません。 アセンブリコードを頑張って解析するという方法もありましたが、そこまでの気力もなく、あきらめることにしました。

勝負は中盤で決していた、、、

AI をリリースした当初は、予想通り順調な結果となっていたのですが、コンテストの終盤にアップされた N 部氏の AI は非常に強く、接戦だったものの勝つことはできませんでした。 対戦結果を見てみましたが、私の AI のような着手可能手数、開放度、角、星、辺、確定石といった多角的な総合評価を用いた際の重みづけのチューニング不足から生じる穴がないように感じました。 コンテスト終了後にソースコードを見せてもらいましたが、複雑な条件分岐となっており、辺の攻防に関わる様々なシチュエーションをきちんと考慮していることが見て取れました。

なんとか勝つ方法はないかと、N 部氏との対戦結果から、自分の手番の残り 22、24、26 マスの盤面を数時間かけて読ませてみましたが、いずれも必敗となり、N 部氏の AI が敗着となる手を打つことはありませんでした。 こうなると必勝読みの探索深度を 1、2 段、深くしても勝率が大きく改善されることはないため、 中盤の評価関数に手を入れる必要がありますが、既存の評価関数の重みづけの変更程度では勝てず、 かといって抜本的に変更するには知見も時間もないということで終了となりました。

おわりに

というわけで、今回も終盤で逆転され 2 位となってしまいました。 敗因は中盤の評価関数（辺の攻防）の弱さですが、評価の難しさから最初に見切りをつけた箇所であり、 逆に、その部分に真摯に取り組んだ N 部氏に負けるのであれば、当然というか納得でした。 もし次回があれば、そのあたりの評価関数をディープラーニングで作ってみたいですね。
それでは。

インタープリズムの面々が、普段の業務に役立つ記事を丹精込めて書き上げる！ Advent Calendar 2016 - Qiitaの5日目の記事

PAGE TOP