Bonanza 以来の定番は盤面を 90° / ±45° 回転させた Occupancy を保持し、Bitboard のシフトとマスクでテーブル参照する方法です。⁷ Robert Hyatt が開発した 90 度回転では、ファイル方向のビットを横並びに変換することで直接的なテーブル参照を可能にします。 DarkThought の 45 度回転は対角線をファイル整列バイトにパックし、数学的にはやや複雑ですが効率的です。⁸

動作原理

縦筋や対角線を一次元化し、index = mask & rotated_occ のように参照するため、遠方駒の列挙が定数時間で行えます。

初心者向け：なぜ「回転」が必要なのか？

問題: 縦型 Bitboard では筋方向のビットが連続していますが、段方向（段目）や対角線方向のビットは離れています。

5筋の縦利き:
ビット位置: 36, 37, 38, 39, 40, 41, 42, 43, 44
→ 連続している！シフト演算で簡単に処理可能

5段目の横利き:
ビット位置: 4, 13, 22, 31, 40, 49, 58, 67, 76
→ 9ビットずつ離れている！シフトだけでは処理できない

解決策: 盤面を 90° 回転させることで、段方向（段目）のビットを連続配置に変換します。

// 回転前: 5段目のビットは 9 ビット間隔
let rank5_bits = [4, 13, 22, 31, 40, 49, 58, 67, 76];

// 回転後: 5段目（元の5筋）のビットが連続
let rot90_rank5_bits = [36, 37, 38, 39, 40, 41, 42, 43, 44];

これにより、同じテーブル参照コードで縦方向も横方向も処理できます。

回転の直感：横で遮られる飛車

遮蔽駒の有無で横利きが変わる様子を盤面で確認します。 通常配置では段方向のビットが分散していますが、90°回転すると連続配置になりテーブル参照が容易になります。

• Frame 1: 🔵 縦方向（筋）の利き。ビットが連続しているのでシフト演算だけで処理可能
• Frame 2: 🟢🔴 横方向（段）の利き。ビットが 9 間隔で分散、6五の味方歩で 🔴 遮断。回転が必要な理由
• Frame 3: 4 方向の合成結果。縦（回転不要）+ 横（90°回転で処理）= 飛車の全利き

遮蔽駒の処理方法

初心者が最も混乱するポイントは「占有状態からどうやって利きを計算するのか？」です。

具体例: 5五の飛車が上方向に利きを伸ばす場合

盤面の状態（5筋のみ表示）:
一段目: □ (空)
二段目: ■ (敵駒) ← ここで止まる
三段目: □ (空)
四段目: □ (空)
五段目: 飛 (自駒)
六段目: □ (空)
七段目: ■ (味方) ← ここで止まる
八段目: □ (到達不可)
九段目: □ (到達不可)

ステップ 1: 占有状態を抽出

// 5筋の占有ビット: bit 36-44
let file5_occ = occupied & FILE5_MASK;  // 0b000110010 (二段目と七段目に駒)

ステップ 2: 関連ビットのみに圧縮

// 5五 (bit 40) より上側 (bit 36-39) のみ抽出
let upper_occ = (file5_occ & UPPER_MASK[40]) >> 36;  // 0b0001 (二段目のみ)

// 5五より下側 (bit 41-44) のみ抽出
let lower_occ = (file5_occ & LOWER_MASK[40]) >> 41;  // 0b001 (七段目のみ)

ステップ 3: テーブル参照で利きを取得

// 事前計算されたテーブルから利き範囲を取得
let upper_attacks = ROOK_UPPER_ATTACKS[40][upper_occ];  // 三段目〜二段目
let lower_attacks = ROOK_LOWER_ATTACKS[40][lower_occ];  // 六段目〜七段目

let total_attacks = upper_attacks | lower_attacks;

テーブルの中身（事前計算）:

// ROOK_UPPER_ATTACKS[sq][占有パターン] の例
ROOK_UPPER_ATTACKS[40][0b0000] = 0b1111;  // 遮蔽なし: 一段目〜四段目
ROOK_UPPER_ATTACKS[40][0b0001] = 0b0011;  // 二段目に駒: 三段目〜二段目
ROOK_UPPER_ATTACKS[40][0b0100] = 0b1100;  // 三段目に駒: 四段目〜三段目
ROOK_UPPER_ATTACKS[40][0b1000] = 0b1110;  // 一段目に駒: 四段目〜一段目

このテーブルは build.rs で全 2^n 通り（n = 方向のマス数）を事前生成します。

遮蔽駒パターンと利きの変化

占有状態によってテーブルが返す利きがどう変わるかをアニメーションで確認します。⁹

• Frame 1: 遮蔽なし → 一段目まで全到達（ROOK_UPPER[0b0000]）
• Frame 2: 🟢 二段目に敵駒 → 二段目まで到達して取れる（ROOK_UPPER[0b0001]）
• Frame 3: 🔴 三段目に味方駒 → 四段目のみ到達（ROOK_UPPER[0b0100]）

なぜ高速か？

1. ループなし（O(1) のテーブル参照）
2. 分岐なし（占有パターンで直接インデックス）
3. キャッシュフレンドリー（小さなテーブル）

Rotated Bitboards の変換フロー

graph LR
    A[通常 Bitboard] --> B[90° 回転]
    A --> C[45° 時計回り]
    A --> D[45° 反時計回り]

    B --> E[飛車の横利き<br/>段方向]
    A --> F[飛車の縦利き<br/>筋方向]
    C --> G[角の利き<br/>北東→南西]
    D --> H[角の利き<br/>北西→南東]

    E --> I[OR演算]
    F --> I
    G --> J[OR演算]
    H --> J

    I --> K[飛車の全利き]
    J --> L[角の全利き]

    style A fill:#e1f5ff
    style B fill:#ffe1e1
    style C fill:#fff4e1
    style D fill:#fff4e1
    style K fill:#d4edda
    style L fill:#d4edda

処理の特徴:

• 各方向を独立に計算（並列化可能）
• 最終的に OR 演算で統合
• 1手の更新で4種類の Bitboard を同期する必要がある

現代の採用状況と ISA の相性

• 採用傾向:
  • チェス系トップエンジンでは、Rotated は現在ほぼ使われません。
  • Magic や PEXT、あるいは LZ/TZ（計算系）に置き換えられています。
  • 将棋でも 9×9 由来のテーブル膨張と更新コストのため、Rotated は選択されにくい傾向です。
• SIMD/ISA の相性（SIMD 概論も参照）:
  • SSSE3 の pshufb 等で「回転を都度再構成」する手もありますが、更新/分岐コストのメリットを打ち消しがちです。
  • Rotated は「別表現を常時同期する」設計が本質で、SSE2/AVX2 の単純論理演算で十分な一方、BMI2 のような特効はありません。
• まとめ:
  • Rotated は設計が明快で教育的価値はありますが、現代 CPU では Magic/PEXT/LZ-TZ が概ね優位です。

元のボード:      90度回転後:     45度回転後:
□■□□□          □□■□□        □■□
■□□■□   →     ■□□□■   →   ■□■
□□■□■          □■□■□        □■□

90 度回転（縦・横変換）

飛車の縦方向の利きを高速化するため、ファイル（筋）をランク（段）に変換します。

変換例（5筋の遮蔽駒検出）:

通常の盤面（縦型）:
９筋 ８筋 ７筋 ６筋 ５筋 ４筋 ３筋 ２筋 １筋
 □   □   □   □   ■   □   □   □   □   一段目
 □   □   □   □   □   □   □   □   □   二段目
 □   □   □   □   飛  □   □   □   □   三段目
 □   □   □   □   ■   □   □   □   □   四段目

↓ 90度回転（5筋を一段に変換）

回転後の盤面（段が横並びに）:
９  ８  ７  ６  ５  ４  ３  ２  １   ← 元の筋が段になる
┌──┬──┬──┬──┬──┬──┬──┬──┬──┐
│ 1│ 0│ 0│ 0│ 飛│ 0│ 0│ 0│ 0│ 五段目  ← 元の5筋が5段目に
└──┴──┴──┴──┴──┴──┴──┴──┴──┘
   ↑              ↑
 一段目に       四段目に
 駒あり         駒あり

回転後のビット: 0b100010000 (連続した9ビット)

左: 🔵 通常配置。5筋のビット（bit 36-44）が連続。縦方向の利きはシフトだけで処理可能。 右: 🟢 90°回転後。5段目のビットが連続配置に変換。横方向の利きもテーブル参照で O(1) に。

// 一段のテーブルで遮蔽駒を検出
let rank_occ = rotated_occ[file] & RANK_MASK;
let index = rank_occ >> file_shift;
let attacks = RANK_ATTACKS[sq][index];

実装パターン:

struct RotatedBitboards {
    normal: Bitboard,       // 通常の盤面
    rot90: Bitboard,        // 90度回転（筋→段変換）
    rot45_clockwise: Bitboard,   // 45度時計回り
    rot45_counter: Bitboard,     // 45度反時計回り
}

impl RotatedBitboards {
    // 飛車の利き（縦横）
    fn rook_attacks(&self, sq: Square) -> Bitboard {
        let file_attacks = self.file_attacks_from_rot90(sq);
        let rank_attacks = self.rank_attacks_from_normal(sq);
        file_attacks | rank_attacks
    }

    // 角の利き（対角線）
    fn bishop_attacks(&self, sq: Square) -> Bitboard {
        let diag1 = self.diag_attacks_from_rot45_cw(sq);
        let diag2 = self.diag_attacks_from_rot45_ccw(sq);
        diag1 | diag2
    }
}

45 度回転（対角線変換）

角の対角線を一次元化してテーブル参照します。

初心者向け：対角線のインデックス計算

90度回転は「筋→段」の置換で直感的ですが、45度回転は対角線番号の計算が必要です。

対角線の番号付け:

北東→南西方向の対角線（diag）:
9  8  7  6  5  4  3  2  1
8  7  6  5  4  3  2  1  0
7  6  5  4  3  2  1  0  1
6  5  4  3  2  1  0  1  2
5  4  3  2  1  0  1  2  3  ← 中央対角線（diag=8）
4  3  2  1  0  1  2  3  4
3  2  1  0  1  2  3  4  5
2  1  0  1  2  3  4  5  6
1  0  1  2  3  4  5  6  7

北西→南東方向の対角線（anti_diag）:
0  1  2  3  4  5  6  7  8
1  2  3  4  5  6  7  8  9
2  3  4  5  6  7  8  9 10
3  4  5  6  7  8  9 10 11
4  5  6  7  8  9 10 11 12
5  6  7  8  9 10 11 12 13
6  7  8  9 10 11 12 13 14
7  8  9 10 11 12 13 14 15
8  9 10 11 12 13 14 15 16

ビット変換テクニック（64 ビット基礎）

Vertical Flip（縦反転）

// SWAR 法（並列プレフィックス）
fn flip_vertical(mut x: u64) -> u64 {
    const K1: u64 = 0x00FF00FF00FF00FF;
    const K2: u64 = 0x0000FFFF0000FFFF;

    x = ((x >> 8) & K1) | ((x & K1) << 8); // バイト単位の反転
    x = ((x >> 16) & K2) | ((x & K2) << 16);
    x = (x >> 32) | (x << 32);               // ダブルワードをスワップ

    x
}

// x86-64 の bswap 命令（1 命令）
fn flip_vertical_fast(x: u64) -> u64 {
    x.swap_bytes()  // Rust では標準ライブラリで提供
}

性能比較:

• 素朴な実装: 21 命令
• 並列プレフィックス: 13 命令
• bswap: 1 命令（推奨）

Horizontal Mirror（横ミラー）

// Delta swap 法
fn mirror_horizontal(mut x: u64) -> u64 {
    const K1: u64 = 0x5555555555555555;
    const K2: u64 = 0x3333333333333333;
    const K4: u64 = 0x0F0F0F0F0F0F0F0F;

    x = ((x >> 1) & K1) | ((x & K1) << 1);   // 1ビットペアをスワップ
    x = ((x >> 2) & K2) | ((x & K2) << 2);   // 2ビットペアをスワップ
    x = ((x >> 4) & K4) | ((x & K4) << 4);   // 4ビットペアをスワップ

    x
}

将棋（9×9 盤）への適用:

// 128ビット版（上位47ビットをマスク）
fn mirror_horizontal_shogi(mut x: u128) -> u128 {
    let lo = mirror_horizontal(x as u64);
    let hi = mirror_horizontal((x >> 64) as u64);
    ((hi as u128) << 64) | (lo as u128)
}

Diagonal Flip（対角線反転）

// Main diagonal (A1-H8) のフリップ
fn flip_diag_a1h8(mut x: u64) -> u64 {
    let mut t: u64;
    const K1: u64 = 0x5500550055005500;
    const K2: u64 = 0x3333000033330000;
    const K4: u64 = 0x0F0F0F0F00000000;

    t = K4 & (x ^ (x << 28));
    x ^= t ^ (t >> 28);

    t = K2 & (x ^ (x << 14));
    x ^= t ^ (t >> 14);

    t = K1 & (x ^ (x << 7));
    x ^= t ^ (t >> 7);

    x
}

// Anti-diagonal (A8-H1) のフリップ
fn flip_diag_a8h1(x: u64) -> u64 {
    flip_vertical(flip_diag_a1h8(x))
}

90° / 180° 回転

// 90度時計回り回転
fn rotate_90_clockwise(x: u64) -> u64 {
    flip_vertical(flip_diag_a1h8(x))
}

// 90度反時計回り回転
fn rotate_90_counter_clockwise(x: u64) -> u64 {
    flip_diag_a1h8(flip_vertical(x))
}

// 180度回転
fn rotate_180(x: u64) -> u64 {
    flip_vertical(mirror_horizontal(x))
}

45° 回転（疑似回転）

// 45度回転のインデックス変換
fn rot45_index(sq: Square) -> usize {
    let file = sq.file();
    let rank = sq.rank();
    let diag = (file - rank + 7) & 15;  // 0..14
    let shift = [0, 1, 3, 6, 10, 15, 21, 28, 36, 43, 49, 54, 58, 61, 63];
    shift[diag] + rank.min(file)
}

性能比較（64 ビット）

推奨実装:

• Vertical Flip: swap_bytes() を使用（1 命令）
• Horizontal Mirror: Delta swap 法（9 命令）
• Diagonal Flip: SWAR 法（12 命令）

将棋での適用例と注意

Bonanza では縦型 Bitboard に 90 度回転を組み合わせ、飛車の段方向の利きを高速化しました。 しかし持ち駒の差分更新との相性が悪く、現代の実装では Magic や PEXT に置き換えられる傾向にあります。

実装上の注意:

• 将棋は 9×9 盤のため、128 ビット版の変換が必要
• 縦型レイアウトでは回転の定義が異なる（筋方向が連続）¹⁰
• 参照実装では Bitboard::part() で 64 ビット片に分割して処理

代替アプローチ: ByteBoard

Bitboard とは異なるアプローチとして、ByteBoard（各マスを 1 バイトで表現する方式）も提案されています。¹¹ たこっと氏が提案したこの方式は、SIMD のバイト単位演算（_mm_add_epi8 等）を活用して利き計算を行います。 Bitboard のビット演算とは設計思想が根本的に異なりますが、やねうら王の開発者はビットボードが十分に高速であるため革命的とまでは言えないと評価しています。

pext の代わりに乗算とシフトでインデックス化する、完全ハッシュによる高速な攻撃生成手法です。⁴ Stockfish を含む多くのエンジンが Magic と pext を切り替える設計を採用しています。¹²

動作原理

Magic Bitboard は以下の 4 ステップで攻撃集合を取得します。

1. マスク適用: 関連する Occupancy のみ抽出（occ &= mask[sq]）。
2. Magic 乗算: 特殊な乗数でビットを折り畳み（occ *= magic[sq]）。
3. シフト: 上位ビットを切り出してインデックス化（index = occ >> shift[sq]）。
4. テーブル参照: 事前計算された攻撃集合を返す。

Magic 乗算の入出力

同じ起点でも占有パターンによって Magic が返す攻撃集合が変わります。 occ & mask → × magic → >> shift → table[index] の流れをアニメーションで確認します。¹³

• Step 1: ⬜ マスク適用。飛車から 4 方向のビーム範囲を抽出（occ & mask[sq]）
• Step 2: 🔴 占有ビット検出。6五の味方歩が唯一の遮蔽駒
• Step 3: 🔵 テーブル参照結果。magic * occ >> shift で得たインデックスから攻撃集合を取得

fn rook_attacks(sq: Square, occupied: Bitboard) -> Bitboard {
    let occ = occupied & ROOK_MASK[sq];
    let index = ((occ * ROOK_MAGIC[sq]) >> ROOK_SHIFT[sq]) as usize;
    ROOK_ATTACKS[ROOK_OFFSET[sq] + index]
}

処理フロー（概念図）

graph TB
    A[占有 Bitboard] --> B[マスク適用<br/>occ & mask]
    B --> C[Magic 乗算<br/>occ * magic]
    C --> D[シフト<br/>結果 >> shift]
    D --> E[インデックス取得<br/>0 ~ 2^n-1]
    E --> F[テーブル参照<br/>attacks_table]
    F --> G[攻撃 Bitboard]

    H[事前計算<br/>build.rs] -.->|初期化| I[Magic Number 探索]
    I --> J[乱数生成 & 検証]
    J --> K{全パターン<br/>衝突なし?}
    K -->|No| J
    K -->|Yes| L[Magic Number 確定]
    L -.->|埋め込み| C

重要なポイント:

• 実行時: 4 ステップ（2-3 命令）で完結。
• ビルド時: Magic Number の探索に時間がかかる（数秒〜数分）。
• 衝突: 異なる占有が同じインデックスでも、結果の攻撃集合が同じなら許容（Constructive Collision）。

ハッシュテーブルと衝突の視覚化

図: Magic Bitboard のハッシュテーブル構造。異なる占有パターンが同じインデックスにマップされても、攻撃範囲が同じなら Constructive Collision として許容されます。

マジックナンバーの探索

「衝突しない」乗算係数を見つけるため、Tord Romstad のランダム探索法が定番です。

fn find_magic(sq: Square, bits: u32) -> Option<u64> {
    let mask = compute_relevant_occupancy(sq);
    let occs = generate_all_occupancies(mask); // 2^bits 通り
    let atks = occs.iter().map(|&o| compute_attacks(sq, o)).collect::<Vec<_>>();

    for _ in 0..100_000_000 {
        let magic = random_u64_sparse();
        let mut table = vec![Bitboard::EMPTY; 1 << bits];
        let mut ok = true;
        for (i, &o) in occs.iter().enumerate() {
            let idx = ((o * magic) >> (64 - bits)) as usize;
            if table[idx] == Bitboard::EMPTY { table[idx] = atks[i]; }
            else if table[idx] != atks[i] { ok = false; break; }
        }
        if ok { return Some(magic); }
    }
    None
}

fn random_u64_sparse() -> u64 { random() & random() & random() }

Volker Annuss の Fixed Shift Magic など、シフト固定で探索を簡略化する手法もあります。¹³

バリエーション

• Fancy Magic Bitboards: マスごとに最適化されたテーブルサイズ（チェスで飛車 800KB、角 38KB）¹⁴
• Plain Magic Bitboards: 全マスで統一された大きなテーブル（実装は単純だがメモリ消費大）
• Black Magic Bitboards: ビット演算の革新的組み合わせで衝突を回避

マジックナンバーの数学的原理

Magic Bitboard の本質は「完全ハッシュ関数」の構築です。¹⁴

要求される性質:

1. 一意性: 異なる Occupancy パターンは異なるインデックスにマップされる
2. 密度: インデックス空間を効率的に利用（衝突を最小化）
3. 高速性: 乗算 + シフトの 2 命令で完結

ハッシュ関数の形式:

hash(occ) = (occ * magic) >> (64 - bits)

ここで bits は関連する Occupancy ビット数（飛車で 12 ビット程度、角で 9 ビット程度）。

将棋における特性と注意

• 9×9 盤で関連 Occupancy が 12〜14 ビットとやや大きく、テーブルの最適化が重要。
• 初期化コスト（探索時間）は CI などで事前生成・埋め込みが現実的。
• BMI2 非対応環境でも高速に動くのが利点。

将棋での適用：世界初の実装例

Reijer Grimbergen による基礎研究（2007）

Reijer Grimbergen 氏（山形大学）は 2007 年、将棋プログラム Spear で Rotated Bitboards を実装し、48.8% の高速化を達成しました。⁷

重要な知見:

• 将棋の 81 マスは 64 ビットに収まらないため、3 つの 32 ビット整数の配列を使用
• 各整数が 27 ビット（盤面の 1/3）を担当する縦型レイアウトを採用
• 90° 回転で香・飛車の縦利き、±45° 回転で角の斜め利きを算出

// Grimbergen の Bitboard 定義
typedef struct {
    unsigned int bb[3];  // bb[0]=1c-9a, bb[1]=1f-9d, bb[2]=1i-9g
} BITBOARD;

性能結果（4手固定深さ、100局面）:

• Attack Tables: 24,810 秒
• Rotated Bitboards: 12,709 秒
• 高速化率: 48.8%

山本一成らによる Magic Bitboard の将棋適用（2010）

山本一成氏（東京大学、Ponanza 開発者）らは 2010 年、世界初の将棋向け Magic Bitboard を実装しました。¹⁵

技術的課題:

• チェスの Magic Bitboard は単一の 64 ビット整数に依存
• 将棋の 81 マスを複数整数で表現する場合、通常の Magic 乗算が不可能

革新的解決策（2つのマジックナンバー + XOR）:

// 山本氏らの提案手法
fn shogi_magic_index(sq: Square, occupied: &BitboardSet) -> usize {
    // 1. 64ビット部分（bb[0]とbb[1]を結合してqとする）
    let q = occupied.q();  // bb[0]とbb[1]の64ビット
    let bb2 = occupied.bb[2];

    // 2. 関連するマスのみをマスク
    let masked_q = q & MASK_Q[sq];
    let masked_bb2 = bb2 & MASK_BB2[sq];

    // 3. 2つのマジックナンバーで個別に乗算
    let index_q = (masked_q * MAGIC_Q[sq]) >> SHIFT_Q[sq];
    let index_bb2 = (masked_bb2 * MAGIC_BB2[sq]) >> SHIFT_BB2[sq];

    // 4. XORで統合
    (index_q ^ index_bb2) as usize
}

マジックナンバー探索の工夫:

• 一様分布の乱数を 3 回論理積（random() & random() & random()）
• 論理積の回数が重要：1回や6回では 100万回試行でも発見できず
• 3回が最適（表3参照）

探索試行回数（山本氏らの実験結果）:

3回の論理積が最も効率的にマジックナンバーを発見できます。

Bonanza での実装結果（深さ15、初期局面）:

• Original (Rotated): 92,769 NPS
• Magic Simple: 86,146 NPS (92.89%)
• Magic FileM: 87,543 NPS (94.27%)
• Magic FileR: 90,240 NPS (97.37%)

Rotated Bitboards に最適化されたコードベースでは若干遅くなりましたが、Magic の利点（全方向一括算出、Occupancy 1枚のみ）は将来の最適化余地を示唆しています。

チェスとの違い

特性評価

Pros:

• CPU 依存性が低く安定。
• 実行時は 3-5 命令で完結。
• メモリ/速度のトレードオフを調整可能。

Cons:

• 探索とテーブル生成が複雑。
• 大きなテーブルは CPU キャッシュを汚染する。やねうら王の開発者は 2017 年の追記で、Magic Bitboard の巨大テーブルがマルチスレッド環境や EvalHash との並行利用でキャッシュ競合を起こし、総合的なパフォーマンスが低下する問題を指摘しています。¹⁶ 「もともと遅くないものを高速化することは出来ない」という結論は、テーブルサイズとキャッシュ効率のトレードオフを考える上で重要な知見です。
• デバッグが困難（マジックナンバーは直感的でない）。

BMI2 の pext 命令で関連 Occupancy を圧縮し、圧縮ビット列をテーブルのインデックスとして用いる方式です。 Intel Haswell 以降と AMD Zen3 以降で高速に動作します。 AMD Zen2 では pext がマイクロコード実装のため極端に遅く、実用上の制約があります。¹⁶

動作原理

関連マスだけを抽出するマスクを用意し、占有と AND を取った後 pext で詰めてインデックス化します。

// 飛車の利き計算（筋・段いずれも同様）
let occ = occupied & ROOK_MASK[sq];
let index = unsafe { core::arch::x86_64::_pext_u64(occ.as_u64(), ROOK_MASK[sq].as_u64()) } as usize;
let attacks = ROOK_ATTACKS[sq][index];

PEXT のコストは 3 サイクル程度（Intel/Zen3）で、テーブル参照と合わせても定数時間で利きを得られます。

将棋でのポイント

• 9×9 盤のため、関連ビット数は 12〜14 ビット程度になることが多いです。
• テーブルサイズは 2^bits で急増するため、縮約や Fancy テーブル設計が有効です。
• Zen2 環境を考慮し、フォールバックとして LZ/TZ や Jumpy Effect を用意するのが実践的です。
• やねうら王の開発者は “Haswell以降専用だと何が嬉しいのですか？” で、BMI2（PEXT/PDEP）だけでなく縦型 Bitboard の二歩判定最適化にも PEXT が有効であることを解説しています。¹⁷

PEXT による疎ビット圧縮

pext は関連マスの占有ビットだけを密にパックしてインデックス化します。 角の斜め利きで遮蔽駒位置によって結果がどう変わるかをアニメーションで確認します。

• Frame 1: 🔵 マスク範囲。角の 4 対角線すべてが pext の抽出対象
• Frame 2: 🔴🟢 遮蔽駒検出。3c に味方歩（🔴 遮断）、7g に敵歩（🟢 取れる）
• Frame 3: テーブル結果。pext(occ, mask) で圧縮されたインデックスから攻撃集合を取得

CPU/ISA の指針と実装ノート

• ISA と速度傾向:
  • Intel Haswell 以降（BMI2）: pext は約 3 サイクルで高速。
  • AMD Zen2: pext はマイクロコード実装で遅い（実測で 20+ サイクル）。
  • AMD Zen3/Zen4: pext が大幅に改善し、実用域に。
• 実装方針:
  • 実行時の機能検出で bmi2 の有無を判定し、未対応なら LZ/TZ にフォールバック。
  • 例（Rust/x86_64）:

    if std::is_x86_feature_detected!("bmi2") {
        // use _pext_u64/_pdep_u64
    } else {
        // fallback: LZ/TZ 法や Magic を使用
    }

• 将棋 9×9 での注意:
  • 関連ビットは 12〜14 程度になりがちで、テーブルサイズが指数的に増加。
  • Fancy テーブル（連結オフセット + 圧縮）やビーム併用でサイズを抑制。

特性評価

Pros:

• マスク抽出とテーブル参照が一回で済む。
• Intel/Zen3 以降では最高速クラス。

Cons:

• Zen2 系 CPU では pext が極端に遅い。
• 大きなテーブルがキャッシュを圧迫する。
• BMI2 非対応環境へのフォールバックが必要。

WCSC31（2021）で Qugiy が披露した、PEXT/Magic に頼らない滑り利き生成です。 ビット減算で遮蔽駒までのビームを抽出し、AVX2 を用いた 4 方向並列で高速化します。

背景: Zen2 の PEXT 問題

AMD Zen2 では pext がマイクロコード実装（約 18 サイクル）で非常に遅く、Intel/Zen3 の 3 サイクルと比べて不利でした。 Jumpy Effect はこのギャップを回避する実用的な方策として注目されました。

仕組み（概要）

1. 方向ごとのビームを構築します。
2. 「ビーム端 - Occupancy」を使って最初の遮蔽駒までの範囲を得ます（借位伝播の性質）。
3. 反転や XNOR を組み合わせて目的の区間を切り出します。
4. 4 方向を AVX2 で並列に処理します。

擬似コード:

fn ray_until_blocker(beam: u128, occ: u128) -> u128 {
    let holes = (!occ) & beam;
    let span  = holes - (1u128 << source_bit);  // 減算で借位がビームに伝播
    span & beam
}

実装では 8/16 ビットのレーンを使い、水平/垂直/対角の 4 方向を 1 回の SIMD 命令列で処理します。

減算伝播（借位トリック）の直感

ビット減算の借位（borrow）が最初の遮蔽駒で止まる性質を利用して、 遮蔽駒までの利きを一発で切り出す仕組みをアニメーションで確認します。

• Step 1: ビーム構築。5 五飛車から上方向に伸びるビーム。🔴 3c に敵駒あり
• Step 2: 🟠 減算トリック。beam_end − occ の借位がビーム端から敵駒位置まで伝播
• Step 3: 🟢 結果抽出。遮蔽駒までの利き区間が span & beam で切り出される
• Step 4: AVX2 並列。4 方向を _mm256_sub_epi64 で一括処理。🟢 敵駒は取れる、🔴 味方駒で遮断

来歴

Qugiy が公開した実装は2021年5月に参照実装へ採用されました。¹⁸ アルゴリズムの導出は解説記事にまとまっています。¹⁹

実装の詳細（上級者向け）

Jumpy Effect の実装には以下の AVX2 命令が使われます。

// 実際の実装例（簡略化）
__m256i compute_jumpy_attacks(__m256i occupied, int sq) {
    // 1. 4方向のマスクを準備
    __m256i masks = _mm256_load_si256(&DIRECTION_MASKS[sq]);

    // 2. 占有ビットを抽出
    __m256i occ = _mm256_and_si256(occupied, masks);

    // 3. ビット減算トリック（4方向同時）
    __m256i blocker = _mm256_sub_epi64(occ, _mm256_set1_epi64x(1));
    blocker = _mm256_and_si256(occ, blocker);

    // 4. XOR で利き範囲を計算
    __m256i attacks = _mm256_xor_si256(occ, blocker);

    // 5. 4方向を統合
    return combine_directions(attacks);
}

重要な AVX2 命令（拡張命令リファレンスも参照）

• _mm256_and_si256: 256ビット AND（4 方向のマスク適用）
• _mm256_sub_epi64: 64ビット×4 の並列減算（借位伝播の核心）
• _mm256_xor_si256: 256ビット XOR（差分区間の抽出）
• _mm256_shuffle_epi8: バイト単位のシャッフル（byte_reverse の実装）

特性評価

Pros:

• Zen2 問題を完全回避：PEXT を一切使わない
• テーブルサイズが小さい：Magic Bitboard の数分の一
• CPU 世代に依存しにくい：AVX2 があれば高速
• 差分更新が軽い：Occupancy の XOR 更新のみ
• 縦型 Bitboard と相性良好：筋方向の処理が単純

Cons:

• 実装が複雑：AVX2 intrinsics の理解が必要
• 可読性が低い：ビット演算のトリックが多用される
• デバッグが困難：SIMD レジスタの内容を追跡しにくい
• AVX2 非対応環境：フォールバックが必要

参考

• Qugiy Appeal（WCSC31 提出資料）: https://www.apply.computer-shogi.org/wcsc31/appeal/Qugiy/appeal.pdf