詰み判定

前提知識: 合法手生成

solve_mate_in_one は現局面で指せる一手詰めを一つ返す。 詰み手がなければ None を返し、入力 Position は変更しない。

一手詰めが表すこと

一手詰めは、手番側が合法な一手で王手し、その直後の防御側に合法手が一つもない状態である。 防御側の手には玉の退避、王手駒の捕獲、遠方王手への合駒、逆王手を含む王手回避が含まれる。 候補が相手玉へ利くだけでは詰みにならない。

API

入力局面を変更しない通常の呼び出しには solve_mate_in_one を使う。

use rsshogi::mate::solve_mate_in_one;

if let Some(mv) = solve_mate_in_one(&position) {
    assert!(position.is_legal_move32(mv));
    // `mv` を適用すると相手に合法手がない。
}

返る Move32 は局面から生成された移動後の駒情報を持つ。 候補が複数ある場合、どの詰み手が返るかは API の契約に含まれない。

探索側が変更可能な Position をすでに保持している場合は、solve_mate_in_one_in_place を使える。 この API は作業局面を複製せず、候補を入力局面へ適用してから undo する。

use rsshogi::mate::solve_mate_in_one_in_place;

let mate = solve_mate_in_one_in_place(&mut position);
// 正常終了時の `position` は呼び出し前と一致する。

呼び出し前に Position の state stack が現局面と同期している必要がある。 SFEN から構築した直後の局面と、apply_move 系 API で指し進めた局面はこの条件を満たす。 独自に局面を組み立てた場合は Position::init_stack() を呼ぶ。 panic 後の局面状態は保証されない。

attacking side candidate
        ↓ legal check
apply to working position
        ↓ defender LegalAll
empty replies => mate in one
non-empty replies => try next candidate

判定の流れ

非王手局面では、駒打ち王手を盤上移動の王手より先に一手ずつ生成する。 候補ごとに is_legal_move32 で自玉の安全と将棋の禁手を確認し、詰みを確定した時点で残りの生成を停止する。 王手中の局面では、現在の王手を合法に回避しつつ相手玉へ王手する手だけを候補にする。

合法な候補は、玉の逃げ、王手駒の捕獲、合駒のいずれかを構成できる場合に、局面へ適用せず棄却する。 歩打ちで詰ませる手は打ち歩詰めになるため、候補から除外する。 この静的な判定で棄却できない候補だけを作業用の局面へ適用し、防御側の LegalAll を生成する。 防御側に合法手が一つもなければ、その候補は一手詰めである。 合法な防御手があれば候補を undo して次を調べる。

静的な判定は非詰みを早く証明するためだけに使い、詰み自体は適用後の合法応手生成で確定する。 このため成りと不成を含む完全な合法手契約を維持する。

防御側の LegalAll は任意の不成を含む。 したがって、防御側が不成で逃れられる局面を詰みとして誤判定しない。

王手中の呼び出し

手番側が王手されている局面でも solve_mate_in_one を呼べる。 この場合、単に相手玉へ利く手ではなく、自玉への王手を解消する合法手だけが候補になる。 したがって、王手を放置する反撃は返さない。

王手されている側の一手詰めは、回避しながら相手玉を詰ませる特殊な反撃である。 候補を単純な generate_checks だけから選ぶとこの条件を落とすため、solver はまず合法回避手の集合を使う。

探索との使い分け

この API は一手で詰ませる手を探す。 探索エンジンは浅い終端判定にこの API を使い、複数手の詰み、最短手数、手順の列挙は 探索木で扱う。

手番側に合法手がないかを調べるだけなら Position::is_mated() を使える。 この API は最初の合法手を見つけた時点で手生成を停止する。

複数の詰め手がある局面では、そのうち一手を返す。 特定の詰み手を選ぶ必要がある消費者は、返った一手だけでなく自分の優先規則を持つ候補探索を実装する。

検証時の観点

solver の返り値は is_legal_move32 を満たし、適用後の LegalAll が空であることを確認できる。 テストでは先後両方、駒打ち、捕獲、成り、逃げ、捕獲、合駒がある非詰み候補を分けて扱う。 この区分は solver の実装方式ではなく、将棋ルールの観測可能な契約である。

次に読む

→ 探索エンジンとの統合 で、詰み判定と通常探索を組み合わせる境界を確認する。