内部設計とアルゴリズム

本章では、rsshogi の内部データ構造、ビット演算アルゴリズム、および探索ホットパスを支えるメモリレイアウトの設計根拠を解説する。 公開 API の利用方法ではなく、「なぜそのビット配置やテーブル構造を採用しているのか」という実装上の意思決定に焦点を当てる。

設計の基本方針

将棋エンジンの探索部や機械学習の自己対局パイプラインでは、局面更新（apply_move / undo_move）、合法手生成、利き計算、および 1 手詰め判定が毎秒数百万回から数千万回の規模で呼び出される。 rsshogi は以下の 5 つの設計原則によって、安全性とホットパスのスループットを両立している。

• プリミティブ型の徹底したビットパッキング：座標（Square）、駒（Piece）、持ち駒（Hand）、指し手（Move / Move32）をすべて 1〜4 バイトの固定幅整数（#[repr(transparent)]）に格納し、レジスタ内でのビット論理演算と比較のみで操作を完結させる。
• File-major 座標系と 63+18 ビット分割：盤面座標を sq = file * 9 + rank で定義し、Bitboard の下位要素 p[0] に 1〜7 筋（63 マス）、上位要素 p[1] に 8〜9 筋（18 マス）を割り当てる。各筋の 9 マスが単一の 64 ビット整数内で必ず連続した 9 ビットを占めるため、香車や飛車縦方向の利き計算において (p[part] >> shift) & 0x1ff の 1 回のシフトとマスクだけで筋の占有状態（9 ビット）を取り出し、FILE_ATTACKS[rank][occ9] テーブルを直接引ける。
• 探索パスにおけるヒープ確保ゼロ：指し手バッファ（MoveList / Move32List）はスタック上の [MaybeUninit<Move>; 600] を直接用い、局面履歴（StateStack）は 64 局面単位の固定長チャンク（Vec<Box<[StateInfo; 64]>>）で管理する。探索木の上下移動でメモリアロケータが一切介在しない。
• Hot / Cold 分離と複合ビットボードキャッシュ：StateInfo を毎ノード参照する StateHot と undo_move32 時のみ参照する StateColdPayload に分離し、Zobrist ハッシュの巻き戻しをスタックポップのみで完了させる。また BitboardSet には金相当駒や大駒を合成した 6 種類の派生キャッシュ（golds_cache、hdk_cache など）を常駐させ、王手検出や利き列挙での OR 演算を削減している。
• ビルド時コード生成と const fn テーブル：飛び駒のレイマスク、筋方向ルックアップテーブル、およびニューラルネットワーク用方策ラベルの変換表を build.rs と const fn でコンパイル時に完全展開し、実行時の初期化コストと条件分岐を排除している。

データ構造の階層関係

rsshogi の内部モジュールは、最下層のプリミティブ型から局面管理や探索アルゴリズムへと積み上がる階層構造をとる。

┌──────────────────────────────────────────────────────────────────────┐
│  上位アルゴリズム層                                                  │
│  合法手生成 (movegen) / 1 手詰めソルバ (mate) / 局面圧縮 (sfen/hcp) │
├──────────────────────────────────────────────────────────────────────┤
│  局面管理層 (Position / StateStack / StateInfo / ZobristTable)       │
│  5 層データモデル・差分ハッシュ更新・王手/ピン情報の遅延キャッシュ   │
├──────────────────────────────────────────────────────────────────────┤
│  ビットボード・利き計算層 (Bitboard / BitboardSet / AttackTables)    │
│  63+18 分割レイアウト・6 種複合キャッシュ・SIMD 双方向レイ計算       │
├──────────────────────────────────────────────────────────────────────┤
│  プリミティブ型層 (Square / Piece / Hand / Move / Move32 / MoveLabel)│
│  #[repr(transparent)] による 1〜4 バイト整数へのビットパッキング      │
└──────────────────────────────────────────────────────────────────────┘

本章の構成

• プリミティブ型のビットレイアウト：Color、File、Rank、Square、PieceType、Piece、Hand、Move、Move32、AperyMove、Ki2Notation、および方策ラベル（MoveLabel / CompactMoveLabel）のビット配置と不変条件を解説する。
• ビットボードの設計と実装：Bitboard([u64; 2]) の 63+18 ビット分割レイアウト、BitboardSet の 6 種類の複合キャッシュ、SSE2 / SSE4.1 / BMI1 / AVX2 を用いたビット操作と飛び駒の利き計算アルゴリズムを解説する。
• Position と状態管理：Position の 5 層データモデル、StateStack のチャンク分割と StateHot / StateColdPayload の分離設計、Zobrist ハッシュの差分更新、および探索エンジン連携プリミティブを解説する。
• 指し手生成パイプライン：MoveList の未初期化スタック配列、生成カテゴリ別のパイプライン、王手回避手生成、空き王手検出、二歩や打ち歩詰めの高速判定、および入玉宣言勝ち判定を解説する。
• 1 手詰めソルバ（Mate-in-One）：KingNeighborhood と MoveDelta による盤面非破壊の静的反駁フィルタ、打ち駒優先ストリーミング生成、および is_mated() による確定検証の組み合わせを解説する。
• シリアライズとビット圧縮：SFEN パーサと PositionState 境界、BitReader / BitWriter、および PackedSfen と HuffmanCodedPos の 256 ビット固定長ハフマン符号化テーブルを解説する。