利きの計算

前提知識: 基本操作（マスク、シフト、pop_lsb() の使い方）

このページの要点

ステップ駒（歩・桂・銀・金・玉・成駒）は事前計算テーブルの参照だけで利きが確定する
遠方駒（香・角・飛）は Occupancy 依存のため、Qugiy 方式（差分抽出＋byte_reverse）で O(1) 検出する
成駒の利きは小駒（と・成香・成桂・成銀）が金の利き、大駒は「元の駒の利き + 王の利き」（馬 = 角 + 王、龍 = 飛 + 王）で合成する
駒打ちでは二歩・行き所のない駒・打ち歩詰めをビットマスクで早期フィルタする

このページでは、短い利き（歩・桂・銀・金・玉・成駒）と長い利き（香・角・飛）の両方について、ビットボードを使った利き計算の手法を解説します。

短い利き（ステップ駒）

ステップ駒は現在地の周囲の固定パターンで攻撃集合が決まります。¹ したがって、事前計算済みの攻撃テーブルと集合演算だけで疑似合法手を列挙できます。

主要ステップ駒の利きパターン

以下のアニメーションで、各ステップ駒の利きパターンを矢印で確認できます。 5五に配置した駒の全利き方向が表示されます。

ステップ駒の攻撃テーブル参照

#[inline]
#[must_use]
pub fn pawn_attacks_unchecked(sq: Square, color: Color) -> Bitboard {
    PAWN_ATTACKS[sq][color.to_index()]
}

#[inline]
#[must_use]
pub fn knight_attacks_unchecked(sq: Square, color: Color) -> Bitboard {
    KNIGHT_ATTACKS[sq][color.to_index()]
}

#[inline]
#[must_use]
pub fn silver_attacks_unchecked(sq: Square, color: Color) -> Bitboard {
    SILVER_ATTACKS[sq][color.to_index()]
}

#[inline]
#[must_use]
pub fn gold_attacks_unchecked(sq: Square, color: Color) -> Bitboard {
    GOLD_ATTACKS[sq][color.to_index()]
}

#[inline]
#[must_use]
pub fn king_attacks_unchecked(sq: Square) -> Bitboard {
    KING_ATTACKS[sq]
}
/// 飛車の StepAttacks（空盤での利き = 4方向ビーム結合）
#[inline]
#[must_use]
pub fn rook_step_attacks(sq: Square) -> Bitboard {
    let b = ROOK_BEAMS[sq.to_index()];
    b.n | b.e | b.s | b.w
}

/// 角の StepAttacks（空盤での利き = 4方向ビーム結合）
#[inline]
#[must_use]
pub fn bishop_step_attacks(sq: Square) -> Bitboard {
    let b = BISHOP_BEAMS[sq.to_index()];
    b.ne | b.se | b.sw | b.nw
}

/// 香車の StepAttacks（空盤での片方向ビーム）
#[inline]
#[must_use]
pub fn lance_step_attacks(sq: Square, color: Color) -> Bitboard {
    let beams = LANCE_BEAMS[sq.to_index()];
    match color {
        Color::BLACK => beams.black,
        _ => beams.white,
    }
}

ソースコード

例として先手の歩を考えます。

let us = side_to_move;
let pawns = pieces_cp(us, PAWN);
let empty = !occupied();
let push = shift_forward(pawns, us) & empty;
for to in push { let from = back_from(to, us); emit_move(from, to, promote_if_needed(from, to)); }

銀や金、玉も同様に、attacks = ATTACKS[piece_type][from] を取り、自駒集合を引いて targets = attacks & !our_pieces を列挙すれば十分です。桂馬は前方二つ×左右一つの固定オフセットで計算します。

成りは「移動元または移動先が成りゾーンに入るか」をビットテストし、必要に応じて 2 手（成・不成）を出力します。

この方式では、短い利きの駒は数命令で候補集合を作り、pop_lsb で列挙するだけです。高速かつ実装が単純で、分岐も少なく保守性に優れます。

駒打ち（ドロップ）の生成

持ち駒の種類ごとに「打てる升集合 = 空升 − 禁止条件」を作ります。二歩、行き所のない駒、打ち歩詰めといった将棋特有の制約は、この段階で早期にフィルタします。²

歩の打てるマス（二歩フィルタ）

先手が歩を持っている状態で、5筋に既に歩がある場合の打てるマスを可視化します。黄色ハイライトが実際に歩を打てる空きマス、赤い丸が 5 筋の自歩によって二歩で除外されるマスです。緑の矢印は、打てるマスの一例として 3五への歩打ちを示しています。

let empties = !occupied();
let files_without_our_pawn = FILE_MASKS & !our_pawns;
let pawn_drop_targets = empties & files_without_our_pawn & not_last_rank(us);
for to in pawn_drop_targets { emit_drop(PAWN, to); }

長い利き（飛び利き）の難しさ

香・角・飛は途中の駒の有無で利きが動的に変わります。単純なテーブル参照では済まず、占有（Occupancy）依存の計算が必要です。つまり、短い利きと同じ感覚では実装できません。

この問題に対しては複数の定番アプローチが知られています。どれも「占有から一次元の線形表現を取り出し、最近接遮蔽駒までの区間を切り出す」ことを、高速に行う工夫です。

Rotated Bitboards（90°/45° 回転）：ファイルや対角線を一次元化し、index = rotated_occ & mask でテーブル参照します。
PEXT Bitboards（BMI2）：pext 命令で疎なビット列を圧縮してインデックス化します。
Magic Bitboards：乗算シフトによる完全ハッシュでテーブル参照します。
LZ/TZ（Leading/Trailing Zeros）法：線形に並ぶ各方向で「最近接遮蔽駒」を ctz/clz 相当で直接求めます。
Qugiy 方式（差分抽出＋byte_reverse）：減算の借位伝播で遮蔽駒までのビーム区間を一括抽出し、byte_reverse で逆方向も処理します。rsshogi はこの手法を採用しています。

各手法の詳細な比較は飛び利きアルゴリズム比較を参照してください。

rsshogi の選択: Qugiy 方式（差分抽出＋byte_reverse）

rsshogi は WCSC31（2021）で Qugiy が発表した差分抽出法を採用しています。減算の借位伝播と byte_reverse を組み合わせ、事前テーブルなしで遠方駒の利きを O(1) で算出します。

角の対角線に遮蔽駒がある場合

角の斜め利きが味方駒（6四の歩）で遮られる例を表示します。 4方向の対角線ビームのうち、左上方向だけが歩で遮断されています。

🔵 青い矢印: 通過可能な対角線ビーム（遮蔽駒なし）
🔴 赤い矢印/丸: 遮蔽駒（味方歩）で遮断される方向

概要

Qugiy 方式は減算の借位伝播と byte_reverse（バイト反転） の 2 つを組み合わせます。³ やねうら王の開発者による完全解説記事では、このアルゴリズムが 4 段階のアイデアの積み上げであることが解説されています。⁴

加算による繰り上がり: occ + pawnStepEffect(sq)（pawnStepEffect はやねうら王の呼称。rsshogi の *_step_attacks に相当）で最近接遮蔽駒まで繰り上がりが伝播する性質を利用
減算への改良: (occ − 1) ^ occ に書き換えることで、参照テーブルが不要になる
byte_reverse で逆方向処理: SSSE3 の pshufb でバイト順を反転し、同じ減算トリックで逆方向の利きも一括処理
128bit decrement の並列化: AVX2 の unpack 命令で lo/hi を分離し、Bitboard256 で 4 方向を同時に decrement 処理

CPU 依存性が小さく、AMD Zen2 の PEXT 問題を回避しつつ多様な環境で安定して高速です。 Magic Bitboard のようなテーブル探索が不要で、実装が簡潔な点も採用理由です。

ビーム＆遮蔽駒検出の流れ

飛車の4方向ビームを段階的に可視化するアニメーションです。各フレームで1方向ずつビームを表示し、遮蔽駒の検出を示します。

Qugiy 方式のステップ（飛車の場合）:

縦方向: 香車の利き（lance_attacks）を先手・後手の両方向で呼び出して合成
横方向: 占有を byte_reverse して順方向・逆方向を揃え、減算（decrement_pair）→ XOR で区間を抽出
4方向を OR で合成 → 最終的な飛車の利き

4方向の対角線を Bitboard256（AVX2 の __m256i、256 ビット SIMD レジスタ）で並列に処理します。 Bitboard256 は 128 ビットの Bitboard を 2 つ束ねたラッパーで、AVX2 対応 CPU では単一の 256 ビットレジスタで演算し、非対応環境では [u64; 4] のスカラーフォールバックに切り替わります（SIMD 概論参照）。

fn bishop_attacks(sq: Square, occupied: Bitboard) -> Bitboard {
    let mask_lo = QUGIY_BISHOP_MASK[sq][0];  // 事前計算マスク
    let mask_hi = QUGIY_BISHOP_MASK[sq][1];

    // splat: 同じ Bitboard を 256 ビットレジスタの上下に複製
    //   AVX2 では _mm256_broadcastsi128_si256 に相当
    let occ2 = Bitboard256::splat(occupied);
    // byte_reverse: SSSE3 の pshufb でバイト順を反転し、逆方向の処理を実現
    let rocc2 = Bitboard256::splat(occupied.byte_reverse());
    let (hi, lo) = Bitboard256::unpack(rocc2, occ2);

    // マスク適用 → 減算（decrement）→ XOR → マスク
    //   AVX2 では _mm256_and_si256, _mm256_sub_epi64, _mm256_xor_si256 を使用
    let hi = hi.and(mask_hi);
    let lo = lo.and(mask_lo);
    let (t1, t0) = Bitboard256::decrement(hi, lo);
    let t1 = t1.xor(hi).and(mask_hi);
    let t0 = t0.xor(lo).and(mask_lo);

    // 逆方向の結果を byte_reverse で戻して合成
    let (hi, lo) = Bitboard256::unpack(t1, t0);
    hi.byte_reverse().or(lo).merge()
}

bishop_attacks のソースコード

飛車（`rook_attacks`）

縦方向は香車 2 方向の合成、横方向は byte_reverse（SSSE3 pshufb）+ decrement_pair で処理します。角と異なり Bitboard256 は使わず、128 ビットの Bitboard で完結します。

fn rook_attacks(sq: Square, occupied: Bitboard) -> Bitboard {
    // 縦方向: 香車の先手・後手ビームを合成
    let mut attacks = lance_attacks(sq, occupied, Color::BLACK);
    attacks |= lance_attacks(sq, occupied, Color::WHITE);

    // 横方向: byte_reverse + 差分抽出
    let mask_lo = QUGIY_ROOK_MASK[sq][0];
    let mask_hi = QUGIY_ROOK_MASK[sq][1];
    let occ_rev = occupied.byte_reverse();
    let (hi, lo) = Bitboard::unpack(occ_rev, occupied);
    let hi = hi.and_raw(mask_hi);
    let lo = lo.and_raw(mask_lo);
    let (t1, t0) = Bitboard::decrement_pair(hi, lo);
    let t1 = t1.xor_raw(hi).and_raw(mask_hi);
    let t0 = t0.xor_raw(lo).and_raw(mask_lo);
    let (hi, lo) = Bitboard::unpack(t1, t0);
    attacks | hi.byte_reverse() | lo
}

rook_attacks のソースコード

// 龍の利き = 飛車の利き | 王の利き
let dragon_attacks = rook_attacks(sq, occ) | KING_ATTACKS[sq];
// 馬の利き = 角の利き | 王の利き（直交4マス）
let horse_attacks = bishop_attacks(sq, occ) | KING_ATTACKS[sq];

SIMD 命令の利用マップ

利きの計算で使われる主な SIMD/拡張命令の対応関係です。各命令の詳細は拡張命令リファレンスを参照してください。

処理	使用命令	ISA	備考
Bitboard の AND/OR/XOR	`_mm_and_si128` 等	SSE2	全演算の基盤
`byte_reverse`	`_mm_shuffle_epi8`	SSSE3	Qugiy 方式の逆方向処理
`pop_lsb()`	`tzcnt`	BMI1	ビット列挙
`count()`	`popcnt`	POPCNT	駒数カウント
`Bitboard256` 演算	`_mm256_*`	AVX2	角の 4 方向並列
`lance_attacks` の MSB 検出	`lzcnt`	BMI1	先手香の遮蔽駒検出

フォールバック: AVX2 非対応環境では Bitboard256 がスカラー実装（[u64; 4]）に切り替わります。 SSE2 は x86-64 の必須仕様のため、基本的な 128 ビット演算は常に利用可能です。

まとめ

ステップ駒: テーブル参照 1 回 + マスク演算 → 数命令で完了
遠方駒: Qugiy 方式（差分抽出＋byte_reverse）で方向ごとの利きを O(1) 算出
駒打ち: 空マスから二歩・行き所のない駒をビットマスクで除外
成駒の利きは元の駒 + 王の利きで合成（見落としやすいバグ源）
SIMD は利き計算の全レイヤーに関与: SSE2（基本演算）、SSSE3（byte_reverse）、AVX2（角の並列処理）

次に読む

→ 飛び利きアルゴリズム比較: Qugiy, Magic, PEXT, Rotated, LZ/TZ の詳細比較に進みます。

参考文献

psilord, “Representation of a Chess Board with a Bitboard” — ステップ駒の攻撃テーブル参照 ↩
やねうら王, “縦型Bitboardの唯一の弱点を克服する” (2015) — 二歩判定のための PEXT + 加算トリック。縦型 Bitboard で歩の打てるマスを高速判定する手法 ↩
すぎゃーんメモ, “Bitboardでleading/trailing zerosを使って遠方駒の利きを求める” — LZ/TZ 法と差分抽出法の日本語解説 ↩
やねうら王, “Qugiyの飛び利きのコード、完全解説” (2021) — 加算→減算→byte_reverse→128bit decrement の 4 段階アイデア発展と、やねうら王への統合経緯 ↩

rsshogi Documentation

利きの計算

このページの要点

短い利き（ステップ駒）

主要ステップ駒の利きパターン

ステップ駒の攻撃テーブル参照

駒打ち（ドロップ）の生成

歩の打てるマス（二歩フィルタ）

長い利き（飛び利き）の難しさ

rsshogi の選択: Qugiy 方式（差分抽出＋byte_reverse）

角の対角線に遮蔽駒がある場合

概要

ビーム＆遮蔽駒検出の流れ

実装の仕組み

香車（`lance_attacks`）

角（`bishop_attacks`）の Bitboard256 並列処理

飛車（`rook_attacks`）

事前計算マスク（build.rs）

将棋盤を用いた可視化

落とし穴

香車の方向間違い

桂馬の成りゾーン

成駒の利き合成

龍の利き = 飛車 + 王

SIMD 命令の利用マップ

まとめ

次に読む

参考文献

Keyboard shortcuts

rsshogi Documentation