基本操作

前提知識: レイアウト（ビット順序と128ビット表現）

このページの要点

Bitboard::file_mask(file) / Bitboard::rank_mask(rank)（内部テーブル FILE_MASKS / RANK_MASKS）は筋・段のマスクで、駒の配置フィルタや移動制約に使う
between(a, b) は 2 マス間の経路、line(a, b) は直線全体を返す（合駒・ピン判定の基盤）
pop_lsb() は最下位ビットを取り出して除去し、O(駒数) の列挙を実現する
差分更新は XOR ベースで分岐なし（move_piece() が by_piece と by_color を同時更新）

このページでは、Bitboard の基本的なビット演算、マスク、シフト、列挙ユーティリティをまとめます。筋・段マスク（file_mask / rank_mask）や between/line などの基礎 API の使いどころも記載します。

between/line の可視化

以下は 5五の王、5二の敵飛車、間に 5三の自駒がある例です。 between(5五,5二) は 5三と 5四を含む直線集合になります。 line(5五,5二) は 5筋の直線全体です。

赤い矢印が飛車の利き方向、緑のハイライトが between の範囲（合駒可能マス）、青い丸が玉の位置を示しています。

// 合駒判定: 王と王手駒の間に駒を打てるか？
let evasion_targets = between(king_sq, checker_sq) | checker_sq.to_bb();

ビットマスクとシフト演算

縦型ビットボードでは、段ごとに << 1 / >> 1 で前後へ移動し、筋方向は << 9 / >> 9 で表現します。

基本パターン:

筋マスク: 0b100000000 をシフトして生成。
段マスク: 0b111111111 を左シフト。
利きの合成: attacks |= mask (OR)。
遮蔽駒検出: blocked = attacks & occupied (AND)。
自駒除外: moves = attacks & !self_pieces (AND NOT)。

実例: 先手の歩を抽出

Bitboard の概要では「集合の交差」として AND を見ました。同じ題材を、Bitboards が保持する 2 つの中間集合から実際に black_pawns を作る手順として見ます。

対象局面には、後手歩が 3三・7三、先手歩が 3七・7七、先手銀が 3九・7九、先手玉が 5九にあります。この局面から「歩であるマス」と「先手駒であるマス」を別々に取り出し、最後に AND で共通部分だけを残します。

position

by_piece[PAWN]

by_color[BLACK]

AND result

by_piece[PAWN] は先後を見ずにすべての歩を含みます。by_color[BLACK] は駒種を見ずに先手駒をすべて含みます。そのため、by_piece[PAWN] & by_color[BLACK] の結果には、両方の条件を満たす 3七・7七だけが残ります。

let black_pawns = bitboards.by_piece[PAWN] & bitboards.by_color[BLACK];

配列ベースなら 81 マスを走査して「駒種が歩か」「色が先手か」を毎回判定します。 Bitboard では、すでに更新済みの集合同士を AND するだけなので、この抽出は 1 つのビット演算になります。

なぜ高速なのか

列ごとのテーブル参照や 90° / 45° 回転もビット演算のテクニックで済み、条件分岐をほとんど伴いません。¹ 探索木を展開するときは毎手局面を更新しますが、ビット演算の連鎖だけで局面差分を適用できるため、64 ビットレジスタを備えた CPU では高効率です。

rsshogi では SSE2 の __m128i を利用し、128 ビット幅の AND/OR/XOR を 1 命令で実行します。 [u64; 2] を個別に演算する場合の 2 命令が 1 命令に集約されるため、ビットボード演算全体のスループットが向上します。

筋マスク・段マスク（FILE_MASKS / RANK_MASKS）

筋（FILE）と段（RANK）のマスクは事前計算された内部テーブル FILE_MASKS / RANK_MASKS として保持され、公開 API の Bitboard::file_mask(file) / Bitboard::rank_mask(rank) 経由で取得します。

const fn build_file_masks() -> [Bitboard; 9] {
    let mut masks = [Bitboard::EMPTY; 9];
    let mut file = 0u8;
    while file < 9 {
        masks[file as usize] = Bitboard::from_packed_bits(file_mask_bits(file as i8));
        file += 1;
    }
    masks
}

const fn build_rank_masks() -> [Bitboard; 9] {
    let mut masks = [Bitboard::EMPTY; 9];
    let mut rank = 0u8;
    while rank < 9 {
        masks[rank as usize] = Bitboard::from_packed_bits(rank_mask_bits(rank as i8));
        rank += 1;
    }
    masks
}

const FILE_MASKS: [Bitboard; 9] = build_file_masks();
const RANK_MASKS: [Bitboard; 9] = build_rank_masks();

/// 先手と後手の敵陣（成りゾーン）ビットボード [Color::BLACK, Color::WHITE]
const PROMOTION_ZONES: [Bitboard; 2] = {
    let black = rank_mask_bits(0) | rank_mask_bits(1) | rank_mask_bits(2);
    let white = rank_mask_bits(6) | rank_mask_bits(7) | rank_mask_bits(8);
    [Bitboard::from_packed_bits(black), Bitboard::from_packed_bits(white)]
};

ソースコード

使用例:

// 使用例: 5筋の全駒を抽出
let file5_pieces = occupied & Bitboard::file_mask(File::FILE_5);

// 香の利き計算で遮蔽駒を筋内で検出
let file_occupied = occupied & Bitboard::file_mask(square.file());
let beams = LANCE_BEAMS[square.to_index()];
let blockers = file_occupied & if color == Color::BLACK { beams.black } else { beams.white };

// 端マスクによる盤外チェック
let edge_mask = Bitboard::file_mask(File::FILE_1)
    | Bitboard::file_mask(File::FILE_9)
    | Bitboard::rank_mask(Rank::RANK_1)
    | Bitboard::rank_mask(Rank::RANK_9);
if (attacks & edge_mask).any() {
    // 端に到達している
}

シフト演算による移動

将棋の駒の移動は定数シフトで表現できます。² 縦型レイアウトでは、段方向が ±1、筋方向が ±9 です。

金の移動方向

5五の金から 6 方向への移動をシフト演算で表現します。各矢印がシフト演算に対応しています。

方向	シフト	演算	色
前（上）	-1	`bb >> 1`	🔵 青
後（下）	+1	`bb << 1`	🔵 青
右	-9	`bb >> 9`	🟢 緑
左	+9	`bb << 9`	🟢 緑
右前	-10	`bb >> 10`	🟠 オレンジ
左前	+8	`bb << 8`	🟠 オレンジ

// 段方向の移動（縦型レイアウトでは +1/-1）
let forward_one = bitboard >> 1;   // 黒番の前進
let backward_one = bitboard << 1;  // 黒番の後退

// 筋方向の移動（9マスずつ）
let right_file = bitboard >> 9;    // 右の筋へ
let left_file = bitboard << 9;     // 左の筋へ

// 斜め移動（桂馬、角）
let knight_move = (bitboard >> 10) | (bitboard << 8);  // 桂馬の移動候補
let bishop_ne = bitboard >> 10;  // 北東（右上）
let bishop_sw = bitboard << 10;  // 南西（左下）

注意点:

端マスからのシフトは盤外へ溢れるため、マスク処理が必要。
事前計算した移動パターン（*_step_attacks などの利きテーブル）で盤外チェック済みのパターンを保持。

ビット操作の実践テクニック

以下は Bitboard 処理で頻出するビット操作パターンです。

// 1. LSB 分離（最下位ビットのみ抽出）
let lsb = bitboard & (!bitboard + 1);
// または標準ライブラリで: bitboard.trailing_zeros()

// 2. LSB リセット（最下位ビットを除去）
bitboard &= bitboard - 1;
// rsshogi では pop_lsb() で実装

// 3. MSB 分離（最上位ビットのみ抽出）
let msb = 1u128 << bitboard.leading_zeros();

// 4. ビット反転（補集合）
let empty_squares = !occupied & Bitboard::ALL_SQUARES;

// 5. ビット数カウント（POPCNT）
//    x86-64 では POPCNT 命令で 1 サイクル実行
//    (詳細は SIMD 拡張命令リファレンスの POPCNT の節を参照)
let piece_count = bitboard.count(); // rsshogi のメソッド名は count()

SIMD との関連: pop_lsb() は内部で TZCNT（BMI1）を、count() は POPCNT を使用します。いずれも x86-64 の多くの CPU で 1 サイクルで実行でき、ビットボードの列挙・カウント性能の基盤です。

`pop_lsb` の実装

pop_lsb はビットボードの心臓部です。最下位の立っているビットを取り出して除去し、セットされたビットだけを O(駒数) で列挙します。³

pop_lsb のステップ実行

以下のアニメーションは、3枚の先手歩から pop_lsb で1枚ずつ取り出す過程を示します。丸が現在取り出されるビット（最下位）です。

    /// 最下位の立っているビットを取り出してクリア
    #[inline]
    pub fn pop_lsb(&mut self) -> Option<Square> {
        let parts = self.parts_mut();
        if parts[0] != 0 {
            let lsb = parts[0].trailing_zeros();
            parts[0] = blsr_u64(parts[0]);
            // lsb は 0..=62
            Some(Square::new(lsb as i8))
        } else if parts[1] != 0 {
            let lsb = parts[1].trailing_zeros();
            parts[1] = blsr_u64(parts[1]);
            // parts[1] は 63..=80 を保持する（lsb は 0..=17）
            Some(Square::new((63 + lsb) as i8))
        } else {
            None
        }
    }

    /// 最下位の立っているビットを取り出してクリアする。
    ///
    /// # Safety
    ///
    /// 呼び出し側は、この bitboard が空でないことを保証しなければならない。
    #[inline]
    #[must_use]
    pub unsafe fn pop_lsb_unchecked(&mut self) -> Square {
        let parts = self.parts_mut();
        if parts[0] != 0 {
            let lsb = parts[0].trailing_zeros();
            parts[0] = blsr_u64(parts[0]);
            Square::new(lsb as i8)
        } else {
            debug_assert!(parts[1] != 0, "pop_lsb_unchecked requires a non-empty bitboard");
            let lsb = parts[1].trailing_zeros();
            parts[1] = blsr_u64(parts[1]);
            Square::new((63 + lsb) as i8)
        }
    }

ソースコード

`count` の実装

    /// 立っているビットの数を数える
    #[inline]
    #[must_use]
    pub const fn count(&self) -> u32 {
        let parts = self.parts();
        parts[0].count_ones() + parts[1].count_ones()
    }

ソースコード

具体的な操作例

以下の例はビット演算と Bitboard API の利用方法を示します。

use rsshogi::board::bitboard::Bitboard;
use rsshogi::types::{Square, SQ_55, SQ_56};

// 単一のマスからビットボードを生成
let pawn = Bitboard::from_square(SQ_55);
let destination = Bitboard::from_square(SQ_56);

// 占有ビットボードと目的地の交差判定
if pawn & destination != Bitboard::EMPTY {
    // 目的地に駒がいるため移動不可
    panic!("Square already occupied!");
}

// 歩の移動候補を合成（和集合）
let attack_mask = pawn | destination;

// Bitboard をループ処理
for sq in attack_mask {
    println!("reachable square: {:?}", sq);
    // 出力例: reachable square: Square(44)
    //         reachable square: Square(45)
}

ポイント:

& (AND): 交差判定。
| (OR): 和集合。
Bitboard::EMPTY: 空のビットボード（全ビット 0）。
for sq in bitboard: Iterator トレイトで直接ループ可能。

差分更新での XOR パターン:

// 移動元と移動先を同時更新
piece_bb ^= Bitboard::from_square(from) | Bitboard::from_square(to);

// 先後同時更新（持ち駒で使用）
hand_bb ^= (1 << black_index) | (1 << white_index);

飛車と遮蔽駒の例

5五の飛車の左に味方の歩がある局面です。飛車の利きが味方駒で遮られ、左方向が制限されています。青い矢印が通過可能な利き、赤い丸が遮蔽駒の位置です。

// 飛車の利き（遮蔽駒考慮）
let attacks = rook_attacks(SQ_55, occupied);
// 味方駒で利きをフィルタ
let legal_targets = attacks & !our_pieces;

between/line の基礎ユーティリティ

王手回避などで用いる、2 マス間の経路マスクの例です。

// 回避可能マスク: 王と利き駒の間 + その駒
let evasion_targets = between(king, checker) | checker;  // 2 命令

// 二歩判定（筋マスク + POPCNT）
let has_double_pawn = (pawns & file_mask).count() >= 2;  // 3 命令

実装は盤レイアウトとシフト規則に依存するため、bitboard/sliders 節の設計と整合させてください。

between と line の実装概略

以下は縦型 9×9 かつ u128 前提の概略です。境界処理と盤外マスクは省略しています。

/// 2 つのマスの間にあるビット集合を返す（端点は含まない）。
/// 直線上にない場合は空集合。
pub fn between(a: Square, b: Square) -> Bitboard {
    // 同筋（file が同じ）
    if a.file() == b.file() {
        let (lo, hi) = (a.min(b), a.max(b));
        return Bitboard::file_mask(a.file()) & Bitboard::range_exclusive(lo, hi);
    }
    // 同段（rank が同じ）
    if a.rank() == b.rank() {
        let (lo, hi) = (a.min(b), a.max(b));
        return Bitboard::rank_mask(a.rank()) & Bitboard::range_exclusive(lo, hi);
    }
    // 斜め（|Δfile| == |Δrank|）
    if (a.file() as i32 - b.file() as i32).abs() == (a.rank() as i32 - b.rank() as i32).abs() {
        let diag_mask = Bitboard::diag_mask_through(a) & Bitboard::diag_mask_through(b);
        let (lo, hi) = (a.min(b), a.max(b));
        return diag_mask & Bitboard::range_exclusive(lo, hi);
    }
    Bitboard::EMPTY
}

/// a と b を含む直線上の全ビット。
pub fn line(a: Square, b: Square) -> Bitboard {
    if a.file() == b.file() {
        return Bitboard::file_mask(a.file());
    }
    if a.rank() == b.rank() {
        return Bitboard::rank_mask(a.rank());
    }
    if (a.file() as i32 - b.file() as i32).abs() == (a.rank() as i32 - b.rank() as i32).abs() {
        return Bitboard::diag_mask_through(a) & Bitboard::diag_mask_through(b);
    }
    Bitboard::EMPTY
}

実装時の注意:

range_exclusive(lo, hi) は lo と hi の間だけを 1 にするヘルパです。
斜め用の diag_mask_through は主対角線と副対角線を分けて計算します。
盤外を含む生成は最後に ALL_SQUARES と AND して落とします。

例: 二歩判定（同一筋に 2 枚の歩）

筋マスクと POPCNT を組み合わせると、二歩を高速に検出できます。

let file_mask = Bitboard::file_mask(square.file());
let black_pawns_on_file = bitboards.by_piece[PAWN] & bitboards.by_color[BLACK] & file_mask;
let has_double_pawn = black_pawns_on_file.count() >= 2;

Mermaid でのイメージ:

flowchart LR
    A[BLACK の歩 Bitboard] -->|AND| B[FILE_n マスク]
    B --> C[POPCNT >= 2]

差分更新の流れ

BitboardSet は set_piece() / clear_piece() / move_piece() を通じて XOR ベースの更新を実行します。

`BitboardSet` の構造体定義

/// 駒種別と先後別のビットボード集合
#[derive(Clone, Copy, Debug, Default)]
pub struct BitboardSet {
    /// 駒種別のビットボード（先後の区別なし）
    by_piece: [Bitboard; PieceType::COUNT],

    /// 先後別の全駒ビットボード
    by_color: [Bitboard; Color::COUNT],

    /// 全占有マス（両者の駒すべて）
    occupied: Bitboard,

    /// 金相当の駒（GOLD | PRO_PAWN | PRO_LANCE | PRO_KNIGHT | PRO_SILVER）
    golds_cache: Bitboard,

    /// 馬・龍・玉（HORSE | DRAGON | KING）
    hdk_cache: Bitboard,

    /// 角・馬（BISHOP | HORSE）
    bishop_horse_cache: Bitboard,

    /// 飛・龍（ROOK | DRAGON）
    rook_dragon_cache: Bitboard,

    /// 銀 + 馬/龍/玉（SILVER_HDK）
    silver_hdk_cache: Bitboard,

    /// 金相当 + 馬/龍/玉（GOLDS_HDK）
    golds_hdk_cache: Bitboard,
}

ソースコード

`move_piece` の実装

    /// 駒を移動（fromからtoへ）
    pub fn move_piece(&mut self, from: Square, to: Square, piece_type: PieceType, color: Color) {
        let piece_bb = &mut self.by_piece[piece_type.to_index()];
        piece_bb.clear(from);
        piece_bb.set(to);

        let color_bb = &mut self.by_color[color.to_index()];
        color_bb.clear(from);
        color_bb.set(to);

        self.occupied.clear(from);
        self.occupied.set(to);
        self.refresh_derived();
    }

ソースコード

使用例:

// 駒を移動させる差分更新の例
let mut bitboards = BitboardSet::new();
let from = Square::SQ_55;
let to = Square::SQ_56;
let piece = PieceType::PAWN;
let color = Color::BLACK;

bitboards.move_piece(from, to, piece, color);

// 成りや取りがある場合の差分
if let Some(captured) = maybe_capture {
    bitboards.clear_piece(
        to,
        captured.piece_type(),
        captured.color()
    );
}

差分更新の利点:

XOR 演算のみで完結（分岐なし）。
Occupancy も自動的に同期。
評価関数の差分更新と統合可能。

sequenceDiagram
    participant P as Position
    participant B as BitboardSet
    P->>B: move_piece(from, to, piece, color)
    B->>B: XOR で occupied を更新
    rect rgb(230, 240, 255)
        B-->>B: by_piece[piece] ^= from \n by_piece[piece] ^= to
        B-->>B: by_color[color] ^= from \n by_color[color] ^= to
    end
    alt capture
        P->>B: clear_piece(to, captured)
    end

file_mask / rank_mask（内部テーブル FILE_MASKS / RANK_MASKS）は筋・段フィルタの基本部品
between / line は合駒・ピン判定のコア（端点の包含に注意）
pop_lsb() による O(駒数) 列挙が Bitboard の高速性の鍵
差分更新は XOR のみで分岐なし、評価関数との統合も容易

次に読む

→ 利きの計算: ステップ駒・遠方駒の利き生成アルゴリズムに進みます。

ChessProgramming Wiki, “Bitboard Board-Definition” ↩
psilord, “Representation of a Chess Board with a Bitboard” — ビットボードの基本構造 ↩
healeycodes, “Visualizing Chess Bitboards” — ビットボードの視覚化と列挙テクニック ↩

rsshogi Documentation

基本操作

このページの要点

between/line の可視化

ビットマスクとシフト演算

実例: 先手の歩を抽出

なぜ高速なのか

筋マスク・段マスク（FILE_MASKS / RANK_MASKS）

シフト演算による移動

金の移動方向

ビット操作の実践テクニック

`pop_lsb` の実装

pop_lsb のステップ実行

`count` の実装

具体的な操作例

飛車と遮蔽駒の例

between/line の基礎ユーティリティ

between と line の実装概略

例: 二歩判定（同一筋に 2 枚の歩）

差分更新の流れ

`BitboardSet` の構造体定義

`move_piece` の実装

落とし穴

`between` の端点包含に注意

`pop_lsb()` と `pop_lsb_unchecked()` の使い分け

シフト演算の盤外溢れ

まとめ

次に読む

Keyboard shortcuts

rsshogi Documentation