Qugiyのビット演算を試す - TadaoYamaokaの開発日記

やねうら王の方で、Qugiyのビット演算の取り込みがされているので、dlshogiも追随したいと思う。

ひとまず実装が簡単な香車の利きと、飛車の縦方向の利き、歩の駒打ちについて対応を行い、速度の測定を行った。

香車の利き

変更前

dlshogiはAperyのコードを流用しており、変更前は以下のようになっている。

inline Bitboard lanceAttack(const Color c, const Square sq, const Bitboard& occupied) {
    const int part = Bitboard::part(sq);
    const int index = (occupied.p(part) >> Slide[sq]) & 127;
    return LanceAttack[c][sq][index];
}

sqの筋のoccupiedからインデックスに変換して、LanceAttackテーブルから表引きして利きのビットボードを求めている。
Slide[sq]は、

const int Slide[SquareNum] = {
    1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 ,
    10, 10, 10, 10, 10, 10, 10, 10, 10,
    19, 19, 19, 19, 19, 19, 19, 19, 19,
    28, 28, 28, 28, 28, 28, 28, 28, 28,
    37, 37, 37, 37, 37, 37, 37, 37, 37,
    46, 46, 46, 46, 46, 46, 46, 46, 46,
    55, 55, 55, 55, 55, 55, 55, 55, 55,
    1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 ,
    10, 10, 10, 10, 10, 10, 10, 10, 10
};

と定義されており、1段のoccupiedは値が0でも1でも結果は同じなので、インデックスを8bitにして節約している。

変更後

Qugiyのアピール文章を元に、やねうら王でビットボードのpartごとに処理を分けているのを参考にして実装した。
処理の解説は、やねうら王のブログで解説されているので省略する。

template <Color US>
inline Bitboard lanceAttack(const Square sq, const Bitboard& occupied) {
    if (US == Black) {
        if (Bitboard::part(sq) == 0) {
            const u64 se = lanceAttackToEdge(US, sq).p(0);
            u64 mocc = se & occupied.p(0);
            mocc |= mocc >> 1;
            mocc |= mocc >> 2;
            mocc |= mocc >> 4;
            mocc >>= 1;
            return Bitboard(~mocc & se, 0);
        }
        else {
            const u64 se = lanceAttackToEdge(US, sq).p(1);
            u64 mocc = se & occupied.p(1);
            mocc |= mocc >> 1;
            mocc |= mocc >> 2;
            mocc |= mocc >> 4;
            mocc >>= 1;
            return Bitboard(0, ~mocc & se);
        }
    }
    else {
        if (Bitboard::part(sq) == 0) {
            // 9段目が0、その他のマスが1になっているmask
            constexpr u64 mask = 0x3fdfeff7fbfdfeffULL;
            const u64 em = ~occupied.p(0) & mask;
            const u64 t = em + pawnAttack(US, sq).p(0);
            return Bitboard(t ^ em, 0);
        }
        else {
            // 9段目が0、その他のマスが1になっているmask
            constexpr u64 mask = 0x000000000001feffULL;
            const u64 em = ~occupied.p(1) & mask;
            const u64 t = em + pawnAttack(US, sq).p(1);
            return Bitboard(0, t ^ em);
        }
    }
}

飛車の縦方向の利き

変更前

LanceAttackテーブルを先手と後手について表引きして論理和をとっている。

inline Bitboard rookAttackFile(const Square sq, const Bitboard& occupied) {
    const int part = Bitboard::part(sq);
    const int index = (occupied.p(part) >> Slide[sq]) & 127;
    return LanceAttack[Black][sq][index] | LanceAttack[White][sq][index];
}

変更後

lanceAttackを先手と後手について求めて論理和をとっても良いが、同一の条件文が2回実行されるのを省略するため、1つの処理にする。
これも、やねうら王の実装を参考にした。

inline Bitboard rookAttackFile(const Square sq, const Bitboard& occupied) {
    if (Bitboard::part(sq) == 0) {
        // 先手の香の利き
        const u64 se = lanceAttackToEdge(Black, sq).p(0);
        u64 mocc = se & occupied.p(0);
        mocc |= mocc >> 1;
        mocc |= mocc >> 2;
        mocc |= mocc >> 4;
        mocc >>= 1;

        // 後手の香車の利き
        // 9段目が0、その他のマスが1になっているmask
        constexpr u64 mask = 0x3fdfeff7fbfdfeffULL;
        const u64 em = ~occupied.p(0) & mask;
        const u64 t = em + pawnAttack(White, sq).p(0);

        return Bitboard((~mocc & se) | (t ^ em), 0);
    }
    else {
        // 先手の香の利き
        const u64 se = lanceAttackToEdge(Black, sq).p(1);
        u64 mocc = se & occupied.p(1);
        mocc |= mocc >> 1;
        mocc |= mocc >> 2;
        mocc |= mocc >> 4;
        mocc >>= 1;

        // 後手の香車の利き
        // 9段目が0、その他のマスが1になっているmask
        constexpr u64 mask = 0x000000000001feffULL;
        const u64 em = ~occupied.p(1) & mask;
        const u64 t = em + pawnAttack(White, sq).p(1);

        return Bitboard(0, (~mocc & se) | (t ^ em));
    }
}

速度測定

香車の利きと飛車の縦方向の利きを変更したもので、変更前後のNPSを測定した。
floodgateからサンプリングした100局面を1秒思考した際のNPSを10回測定して平均を算出した。

GPU1枚(RTX3090)、Core i9 2スレッド

	変更前	変更後	変更後/変更前
平均	29144	28990	99.3%
中央値	30260	30316	100.2%
最小値	18205	17384	94.9%
最大値	31713	31847	100.6%

平均値、中央値、最大値はほぼ変わらず誤差の範囲である。
最小値は低下している。
速度改善の効果がないと判断してよさそうだ。

GPU8枚(A100)、ZEN2 4スレッド

	変更前	変更後	変更後/変更前
平均	304283	279886	92.0%
中央値	308605	283135	92.0%
最小値	229106	217205	87.6%
最大値	354780	328941	96.0%

8GPU、ZEN2 4スレッドだと、平均値、中央値、最小値、最大値すべてで低下した。

歩の駒打ちのビット演算

変更前

歩の駒打ちの二歩の回避は、変更前は以下の通り実装されている。

			// 一段目には打てない
			const Rank TRank1 = (US == Black ? Rank1 : Rank9);
			toBB.andEqualNot(rankMask<TRank1>());

			// 二歩の回避
			Bitboard pawnsBB = pos.bbOf(Pawn, US);
			Square pawnsSquare;
			foreachBB(pawnsBB, pawnsSquare, [&](const int part) {
					toBB.set(part, toBB.p(part) & ~squareFileMask(pawnsSquare).p(part));
				});

歩のあるすべての筋について、マスクを作成して論理積を計算している。

変更後

Qugiyのアピール文章では、二歩の回避をビット演算で求める方法を提示しているが、やねうら王の実装を参考にして、一段目を除外する処理と合わせて求めるようにした。

			// 二歩の回避
			Bitboard pawnsBB = pos.bbOf(Pawn, US);
			// 9段目が1のbitboard
			const Bitboard left(0x4020100804020100ULL, 0x0000000000020100ULL);
			Bitboard t = left - pawnsBB;
			// 一段目には打てない
			if (US == Black) {
				t = (t & left) >> 7;
				toBB &= left ^ (left - t);
			}
			else {
				t = (t & left) >> 8;
				toBB &= left.notThisAnd(left - t);
			}

速度測定

歩の駒打ちを変更したもので、変更前後のNPSを測定した。
floodgateからサンプリングした100局面を1秒思考した際のNPSを10回測定して平均を算出した。

GPU1枚(RTX3090)、Core i9 2スレッド

	変更前	変更後	変更後/変更前
平均	29114	29086	99.9%
中央値	30172	30266	100.1%
最小値	18183	17947	95.8%
最大値	31673	31750	100.4%

平均値、中央値、最大値はほぼ変わらず誤差の範囲である。
最小値は低下している。
こちらも速度改善の効果がないと判断してよさそうだ。

GPU8枚(A100)、ZEN2 4スレッド

	変更前	変更後	変更後/変更前
平均	304283	292713	96.2%
中央値	308605	295337	95.9%
最小値	229106	225959	92.1%
最大値	354780	337019	101.2%

8GPU、ZEN2 4スレッドだと、平均値、中央値、最小値で低下し、最大値はわずかに速くなった。

まとめ

香車の利きと、飛車の縦方向の利き、歩の駒打ちについてQugiyのビット演算を実装して、変更前後の速度を測定した。
結果、速度は変わらないかむしろ遅くなることがわかった。
表引きしていた部分をビット演算に置き換えており、処理する命令数は増えているため、表がキャッシュに載っていればかえって遅くなったのではないかと考える。

飛車と角の飛び利きについても別途実装して測定する予定である。

ソースコード

香車の利きをビット演算で求める · TadaoYamaoka/DeepLearningShogi@1bfc808 · GitHub
歩の駒打ちをビット演算で求める · TadaoYamaoka/DeepLearningShogi@06d93fe · GitHub