Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

指し手生成パイプライン

指し手生成（Move Generation）は、探索エンジンの全実行時間のうち大きな割合を占めるホットパスである。 rsshogi の movegen モジュール（crates/rsshogi/src/board/movegen/）は、ヒープアロケーションと不要な配列初期化を排除したスタックバッファ、不要な不成手をコンパイル時分岐で省く生成カテゴリ、および段階的生成（Staged Move Generation）を組み合わせたパイプライン構造をとる。

1. MoveList / Move32List と MaybeUninit によるゼロ初期化バッファ

将棋の 1 局面における合法手の理論上の最大数は 593 手である。 MoveList（16 ビット Move 用）および Move32List（32 ビット Move32 用）は、最大 600 手（MAX_MOVES = 600）を格納できる固定長配列をスタック上に直接保持する。

#![allow(unused)]
fn main() {
pub const MAX_MOVES: usize = 600;

pub struct MoveList {
    buf: [MaybeUninit<Move>; MAX_MOVES],
    len: usize,
}
}

もし buf: [Move::MOVE_NONE; 600] のように通常の配列で定義すると、合法手が 30 手しかない局面であっても、関数呼び出しのたびに 600 要素（Move32List なら 2,400 バイト）のゼロ埋め初期化命令（memset）が走ってしまう。 MaybeUninit を採用することで、MoveList::new() は len = 0 をセットするだけの実質ゼロコストとなり、実際に生成された 0..self.len の範囲だけを slice::from_raw_parts で安全にスライスとして公開する。

2. 生成カテゴリと *All バリアントの使い分け

rsshogi は、探索フェーズに応じて生成する指し手の種類を型レベルのマーカー（MoveGenType）で切り替える。 さらに各カテゴリには、探索で実質的に無意味な不成手を除外する 標準バリアント と、ルール上合法なすべての不成手を網羅する *All バリアント の 2 種類が用意されている。

標準カテゴリ全網羅カテゴリ（*All）生成される指し手の範囲
LegalLegalAll現局面のすべての合法手（王手中は回避手、非王手時は非回避手から自殺手や打ち歩詰めを除外）。
CapturesCapturesAll敵駒を捕獲する擬似合法手（および価値の高い成り手）。静止探索（Quiescence Search）の主力。
QuietsQuietsAll駒を取らない静かな擬似合法手（駒打ちを含む）。
EvasionsEvasionsAll王手がかかっている局面での王手回避擬似合法手。
NonEvasionsNonEvasionsAll王手がかかっていない局面での全擬似合法手（Captures + Quiets）。
ChecksChecksAll相手玉に王手をかける擬似合法手（直接王手 + 空き王手）。

標準バリアントで省略される「実質的に無意味な不成手」

将棋の公式ルール上は、敵陣（1〜3 段目）に入る飛車、角、歩（二段目と三段目）や、二段目に入る香車が「あえて成らない（不成）」ことも合法である。 しかし通常の対局探索において、デメリットなしに上位互換の性能を得る「飛→龍」「角→馬」「歩→と金」の成りを拒否する手や、敵陣二段目で動けなくなる香不成を読むことは探索木を無意味に肥大化させる。

そのため、Legal や Checks などの標準バリアントでは、以下の不成手を生成段階で省略する。

  • 歩、角、飛が成れる移動における不成手（成りのみを生成）
  • 香車が敵陣二段目へ移動する際の不成手（三段目の香不成のみ、打ち歩詰め回避等の戦術的意味があり得るため残す）

一方、詰将棋ソルバ（打ち歩詰め誘発のためのあえての不成が解になる場合がある）や Perft（ルール上の全合法手数検証）、UI の全合法手ハイライトでは、LegalAll や ChecksAll を用いることでルール上の全合法手を漏れなく取得できる。

3. リスト返却 API と MoveSink / Move32Sink ストリーミング API

指し手生成関数には、MoveList / Move32List を返す関数群に加えて、任意のシンク（受け皿）へ指し手を直接流し込む *_into ジェネリック関数群が提供されている。

#![allow(unused)]
fn main() {
pub(crate) trait Move32Sink {
    fn push(&mut self, mv: Move32) -> ControlFlow<()>;
}
}
  • バッファ構築パス（generate_legal / generate_checks_all_move32 等）：MoveList または Move32List に指し手を書き込む。push は常に ControlFlow::Continue(()) にインライン展開されるため、分岐オーバーヘッドは発生しない。
  • ストリーミング早期終了パス（generate_legal_into / generate_checks_all_move32_drop_first_into 等）：クロージャやカスタム構造体をシンクとして渡し、目的の指し手が見つかった時点で ControlFlow::Break(()) を返すことで、残りの駒種やマスの指し手生成をその場で打ち切る ことができる。この仕組みは Position::is_mated()（最初の 1 手の合法応手が見つかった瞬間に不詰と判定して終了する）や 1 手詰めソルバ で活用されている。

4. 段階的指し手生成（MoveGenerator）

Alpha-Beta 探索では、置換表の最善手（TT Move）や強い駒取り手で早期に Beta カット（枝刈り）が起きることが多い。 最初から全合法手を一括生成すると、カット後に残りの数百手の生成コストがすべて無駄になる。

MoveGenerator（crates/rsshogi/src/board/movegen/staged.rs）は、探索の進行に合わせて以下の順序で段階的に指し手を生成および供給するステートマシンである。

  1. 王手回避フェーズ（王手中のみ）：Evasions のみを生成して順次返す。
  2. 駒取りと主要成り手フェーズ（Captures）：まず敵駒を取る手と主要な成り手だけを生成する。ここで Beta カットが起きれば、静かな手や駒打ちの生成は一切行われない。
  3. 静かな手と駒打ちフェーズ（Quiets）：カットが起きなかった場合にのみ、盤上の静かな移動手と持ち駒を打つ手を生成して返す。

各手で生成される指し手は擬似合法手（Pseudo-legal Move）であるため、実際に apply_move32 する直前に Position::is_legal_move32 でピンや玉の自殺手、打ち歩詰めの最終検査を行う遅延検証方式をとっている。