飛び利きアルゴリズム比較

飛び利きの目的は、始点と占有から各方向で最初の遮蔽駒までを返すことである。

将棋盤は 81 マスなので、方式の選択では命令数だけでなく、テーブル量、ビルド複雑性、対応 CPU、検証可能性を比較する。

代表的な方式

方式	概要	主なトレードオフ
逐次走査	一マスずつ進み遮蔽で停止する。	最も明快で、小さな盤では基準実装に向く。
Rotated bitboards	行・列・対角を別のビット列として保持する。	参照は速いが、局面更新とテーブル管理が増える。
Magic bitboards	占有の関連ビットを乗算・シフトで表索引にする。	高速な表引きを得られる一方、マジックとテーブルの生成・検証が必要になる。
PEXT	CPU 命令で関連ビットを圧縮して表索引にする。	BMI2 が必要で、CPU 世代ごとの実測を前提にする。
レイ抽出	方向レイと占有のビット演算で最寄り遮蔽駒までを抽出する。	テーブルは方向レイ中心で、ビット順と反転方向の設計が重要になる。

方式の性能は CPU、コンパイラ、占有の分布、周辺の手生成コードで変わる。

rsshogi では、対象 CPU と手生成全体の測定結果から方式を選ぶ。

rsshogi は build.rs で方向別のビームと private な u128 レイを生成する。

香の筋方向は 9 ビットのファイル表 FILE_ATTACKS を使う。

角と飛の二方向ずつは、レイと占有の交差、減算による借位伝播、マスクで到達範囲を抽出する。

逆方向はビット反転して同じ前向き抽出として処理する。

AVX2 ビルドでは二方向の組を同時に計算できるが、非 AVX2 ビルドでも同一の結果を返す。

この章でいう「現行経路」は lance_attacks、bishop_attacks、rook_attacks の実装を指す。 private なレイのメモリレイアウトは内部最適化として扱う。

方式を変える前に、まず正確性をスカラー走査との全始点比較で固定する。

次に対象 CPU、コンパイルする target_feature、探索側の代表局面、測定回数を揃えて比較する。

採否は、攻撃テーブルの常駐量や局面更新のコストを含む手生成全体で判断する。

PEXT や Magic の導入は、対応 CPU と生成物を増やすため、根拠となる全体測定と保守上の必要性がある場合に限る。

正確性テストを通過した候補だけをベンチマークで比較する。

逐次走査は、隣接マスから盤端または遮蔽駒までを順にたどる。

最悪の反復回数は方向ごとに盤の一辺に比例するが、将棋盤ではその上限は小さい。

実装が直接ルールを表すため、他方式のテストオラクルとして最も使いやすい。

現行の攻撃テーブルのテストもこの方式を参照実装にし、各方向の最寄り遮蔽駒の組合せと疑似乱数占有を比較する。

最適化された実装は、逐次走査より命令数を減らしても、盤端・遮蔽駒・始点の扱いを変えてはならない。

Rotated、Magic、PEXT の方式は、関連する占有ビットを小さな添字へ写して利き表を引く。

表引きは高速でも、各方向の relevant occupancy、表のサイズ、初期化または生成物、添字計算を正しく維持する必要がある。

将棋の 9 × 9 盤では、飛車と角の方向ごとに長さが異なり、端の特殊ケースも表設計へ現れる。

CPU 固有の PEXT を使う場合は、ビルド対象に BMI2 があることと、対象 CPU での実測を別に保証する必要がある。

そのため表引き方式の採用判断は、関数単体の比較だけでなく、生成物、配布物、テスト量を含む総コストで行う。

方向レイを ray、占有を occupied とすると、まず blockers = ray & occupied がその方向の遮蔽駒だけを残す。

前向きにビット番号が増えるレイでは、減算の借位伝播を使って最初の遮蔽駒までの範囲をまとめて作れる。

反対方向は、ビット順を反転すれば同じ前向きの問題として処理できる。

この考え方はビットの連続性とレイの構築に依存するため、盤面用の packed_bits と内部演算用の raw_bits を取り違えないことが重要になる。

速度順位は、対象 CPU 上の同一条件で測定する。

採用候補を比較するときは、同一の合法手生成・局面更新・ビルド設定で測定する。