ビットボード

前提知識: 基本型（Square, PieceType, Piece の定義）

このページの要点

Bitboard は「盤面のマス集合をビット列で表現する」データ構造。集合演算がビット演算に直結する
将棋では 81 マスのため 128 ビット表現（[u64; 2] + SSE2 __m128i）を使用
Bitboard は盤面のすべてを置き換えるものではなく、集合操作が頻繁な情報（駒の配置、利き）に使い、個別アクセスが必要な情報（各マスの駒種）には配列を併用する
pop_lsb() により、セットされたビットだけを O(駒数) で列挙できる（81マスのループは不要）

なぜ Bitboard か

81 人が座る教室を想像してください。「眼鏡をかけている人」を探したいとき、1 人ずつ確認すると最悪 81 回のチェックが必要です。しかし、「眼鏡リスト」（眼鏡=1, それ以外=0 のビット列）を持っていれば、リストを見るだけで一瞬です。さらに「眼鏡かつ男性」を知りたければ、「眼鏡リスト AND 男性リスト」で 1 命令で交差集合が得られます。

Bitboard はまさにこれと同じ原理です。「先手の歩の位置」「飛車の利き範囲」「空きマス」といった集合を 128 ビットの値として保持し、AND/OR/XOR で高速に操作します。

歴史的背景

Bitboard の概念は 1960 年代のソビエトのチェスプログラム Kaissa に遡ります。¹ チェスは 64 マスなので 1 つの u64 に収まり、単一レジスタで盤面全体を操作できるため普及しました。

将棋への適用は 2000 年代の Bonanza が先駆的です。 Reijer Grimbergen（山形大学）が 2007 年に将棋ビットボードの体系的な研究を発表しました。² その後参照実装が SIMD 命令を活用した 128 ビット実装を確立し、現在の将棋エンジンの標準となっています。³ rsshogi もこの流れを継承しています。

Bitboard とは

Bitboard は「盤上のマス = ビット」を対応付ける集合表現です。将棋では 9×9 = 81 マスのため 128 ビット表現を採用します。

各マスを 1 ビットに割り当て、駒の位置や攻撃範囲を集合演算で操作します。

実装詳細

#![allow(unused)]
fn main() {
/// 81マス将棋盤のビット表現
///
/// 下位81ビットを使用し、各ビットが1つのマスに対応する。
/// `SQ_11`（0）が最下位ビット、`SQ_99`（80）がbit80となる。
#[derive(Copy, Clone)]
#[repr(C, align(16))]
pub struct Bitboard {
    p: [u64; 2],
}

const _: () = {
    assert!(core::mem::size_of::<Bitboard>() == 16);
    assert!(core::mem::align_of::<Bitboard>() == 16);
};
}

ソースコード

Bitboard: P(Squares) → {0,1}^n
  ここで P(S) は集合 S の冪集合、n は盤面のマス数

ビット演算 = 集合演算

集合演算はビット演算へ直接マッピングできます。

集合演算	ビット演算	用途例
和集合 A ∪ B	`a \| b`	自駒と敵駒を統合
積集合 A ∩ B	`a & b`	攻撃範囲と敵駒の交差
差集合 A \ B	`a & !b`	合法手から自駒を除外
対称差 A △ B	`a ^ b`	局面の差分更新
補集合 Ā	`!a`	空きマスの抽出

ミニ例: オセロの裏返し

bitboard_black ^= move | flipped;  // 差集合 + 和集合
bitboard_white ^= flipped;         // 対称差

このように、配列ループを伴う処理が 1-2 命令のビット演算で表現できます。

駒の配置と利き

まずは 5 筋に 3 枚だけ置き、駒の向きと座標を確認します。 5九の香と5三の歩は先手、5一の香は後手です。盤面上では先手駒は読者側を向き、後手駒は反対向きに表示されます。丸はこの例で注目する駒、矢印は「先手の歩が5三から5二へ利く」ことだけを示しています。香の長い利きは次のレイアウトで扱うため、ここでは表示していません。

AND でフィルタする

ビットボードの核心は「集合演算 = ビット演算」です。たとえば「先手の歩」は、by_piece[PAWN]（歩があるマス集合）と by_color[BLACK]（先手駒があるマス集合）の共通部分です。 AND は方向を持つ操作ではないため、矢印では表しません。下の3枚の盤では、左から順に入力集合、入力集合、結果集合を黄色で示します。

by_piece[PAWN]

by_color[BLACK]

AND result

// 先手の歩だけを抽出（AND 演算 1 命令）
let black_pawns = bitboards.by_piece[PAWN] & bitboards.by_color[BLACK];
//                 ^^^^^^^^^^^^^^^^^^^^^^^^   ^^^^^^^^^^^^^^^^^^^^^^^
//                 全歩の集合                  先手駒の集合
//                 → 交差 = 先手の歩のみ

OR で利きを合成して王手を判定する

複数駒の利きを OR で合成し、王の位置と AND で王手判定します。赤い矢印が飛車の利き、オレンジの矢印が角の利き、青い丸が王の位置です。

// 王手判定: 飛車と角の利きを OR で合成し、王の位置と AND
let attackers =
    (rook_attacks(king_sq, occ)   & enemy_rooks)   |  // 飛車の利き
    (bishop_attacks(king_sq, occ) & enemy_bishops);    // 角の利き
let in_check = attackers.any();  // 1 命令で判定完了

速習スニペット

以下はビット演算の最小例です。

// 先手の歩だけを抽出
let black_pawns = bitboards.by_piece[PAWN] & bitboards.by_color[BLACK];

// 最下位ビットを取り出して列挙
let mut moves = black_pawns;
while moves.any() {
    let to = moves.pop_lsb();
    emit_move(to);
}

全データを Bitboard で表現するのか？

いいえ。必要な情報だけを選択的に Bitboard 化します。 Bitboard は「盤面の全て」を置き換えるデータ構造ではありません。

実際のエンジンでは以下のように使い分けます：

struct Position {
    // Bitboard: 集合演算が必要な情報
    bitboards: BitboardSet,  // 駒種別・先後別の配置

    // 配列: ランダムアクセスが必要な情報
    board: [Piece; 81],      // 各マスの駒（「5五に何がある？」）
    hand: [Hand; 2],         // 持ち駒

    // スカラー: 単一の値
    side_to_move: Color,     // 手番
    ply: u16,                // 手数
}

Bitboard が得意:

「先手の歩が何処にあるか？」（集合演算）
「飛車の利きと敵駒の交差」（AND演算）
「王手している駒の列挙」（ビット走査）

配列が得意:

「5五のマスに何の駒があるか？」（O(1) アクセス）
「持ち駒の枚数」（駒種ごとのカウンタ）

使い分けの原則:

集合操作 → Bitboard
個別アクセス → 配列

よくある誤解：「Bitboard は利きの一括生成だけが速い？」（クリックで展開）

真の強みは集合演算のワンライナー化とビット列挙の高速性です。置換表や評価、差分更新との連携が全体の速度を左右します。滑り利きは Qugiy 方式（差分抽出＋byte_reverse）で O(1) 算出しています。

誤解 1：配列版とほぼ同じで、利きを作る部分だけが速い

実際には、Bitboard の高速化の本質は集合演算にあります。

配列ベースの王手判定（概念例）

fn is_in_check_array(position: &ArrayPosition) -> bool {
    let king_sq = position.king_square;

    // 全敵駒をループ (平均 20-40 駒)
    for piece in position.enemy_pieces() {
        if piece.attacks(position).contains(king_sq) {
            return true;  // 王手発見
        }
    }
    false
}

Bitboard ベースの王手判定（概念例）

fn is_in_check_bitboard(position: &Position) -> bool {
    let king_sq = position.king_square;
    let enemy_color = position.side_to_move.flip();
    let bitboards = position.bitboards();
    let occupied = bitboards.occupied;

    // 王から見た攻撃範囲と敵駒の交差を一括チェック
    let attackers =
        (rook_attacks(king_sq, occupied) & bitboards.by_piece[ROOK]) |
        (bishop_attacks(king_sq, occupied) & bitboards.by_piece[BISHOP]) |
        (GOLD_ATTACKS[king_sq][position.side_to_move] & bitboards.by_piece[GOLD]) |
        // ... 他の駒種
        ;

    (attackers & bitboards.by_color[enemy_color]).any()  // 1-2 命令
}

高速化しやすい理由:

駒種ごとの集合をまとめて扱える
AND/OR 演算で候補集合を合成できる
セットされたビットだけを列挙できるため、81 マス全走査を避けられる

誤解 2：「Bitboard から手を読み出す際に 81 マス全部チェックする」

実際には駒がある場所だけを O(駒数) で巡回します。

素朴な実装（遅い）

for sq in 0..81 {
    if moves.is_set(sq) {  // 81 回ループ
        emit_move(from, sq);
    }
}

popcount/trailing zeros を使った実装（速い）

while moves.any() {  // 駒数回だけループ
    let to = moves.pop_lsb();  // trailing_zeros + clear
    emit_move(from, to);
}

読了順序

レイアウト：縦型インデックス、ビット順序、ファイル/ランク定義
基本操作：マスク、シフト、between/line、pop_lsb() 等
利きの計算：ステップ駒・遠方駒の利き生成
飛び利きアルゴリズム比較：Qugiy, PEXT, Magic, LZ/TZ 法の比較

参考文献

Rustic Chess, “Bitboards” — Rust でのビットボード実装入門 ↩
Reijer Grimbergen (2007). “Using Bitboards for Move32 Generation in Shogi”. ICGA Journal Vol. 30, No. 1, pp. 25-34. ↩
やねうら王 “magic bitboard論争に終止符を” ↩

Keyboard shortcuts

rsshogi Documentation