Hayanagiで学ぶ将棋エンジンの仕組み

第III部 探索と評価

第10章 詰み探索

将棋エンジンにおいて「詰み」を確実に発見することは、勝利に直結する最重要課題のひとつです。 しかし通常のアルファベータ探索だけでは、探索深さの制限や枝刈りにより短手数の詰みを見逃してしまう場合があります。 本章では、Hayanagiが実装する専用の詰み探索アルゴリズムについて、コードを読みながら解説します。

10.1 なぜ専用の詰み探索が必要か

通常の反復深化探索では、各深さにおいてアルファベータ枝刈りやLMR（Late Move Reduction）、 ヌルムーブ枝刈りなどの高速化手法が適用されます。 これらの手法は大部分の局面で正しく機能しますが、詰み手順は「王手の連続」という非常に特殊な手順であるため、 通常の評価関数による枝刈りで重要な王手が切り捨てられることがあります。

例えば、3手詰みの局面であっても、通常探索の深さ3では王手以外の手も含めて膨大な候補手を調べるため、 時間制約内に詰み手順に辿り着けないことがあります。 専用の詰み探索では、攻撃側は王手をかける手のみ、防御側は合法手すべて（逃げ手）を調べるという制約を加えることで、 探索木を大幅に削減し、短時間で短手数の詰みを発見できます。

10.2 find_forced_mate() の設計

詰み探索のエントリーポイントは find_forced_mate() です。 この関数は最大手数（max_ply）を受け取り、その手数以内の詰みがあるかどうかを判定します。 Hayanagiでは定数 kMateSearchMaxPly = 5 が定義されており、最大5手詰みまでを探索します。 

bool Search::find_forced_mate(const Position& position, int max_ply, std::vector<Move>& pv) {
    pv.clear();
    const int normalized_ply = std::max(1, max_ply | 1);
    return mate_search_attack(position, normalized_ply, &pv);
}

max_ply | 1 によって手数が必ず奇数に正規化されます。 これは詰み手順が「攻撃→防御→攻撃→...→攻撃」と奇数手で終わるためです。 結果はPV（主変化手順）として pv ベクタに格納されます。

10.3 mate_search_attack() — 攻撃側の探索

攻撃側の探索関数 mate_search_attack() は、王手をかける手のみを生成して探索します。 

bool Search::mate_search_attack(const Position& position,
                                int remaining_ply,
                                std::vector<Move>* pv) {
    if (should_stop()) {
        aborted_ = true;
        return false;
    }
    count_node();

    if (remaining_ply <= 0) {
        return false;
    }

    auto checking_moves = position.generate_checking_moves();
    if (checking_moves.empty()) {
        return false;
    }

    const Move no_tt_move;
    const auto ordered_moves = score_moves(position, checking_moves, 0, no_tt_move);
    for (const OrderedMove& ordered_move : ordered_moves) {
        const Move& move = ordered_move.move;
        Position child = position;
        child.do_move(move);
        std::vector<Move> defense_line;
        std::vector<Move>* next_pv = pv != nullptr ? &defense_line : nullptr;
        if (mate_search_defense(child, remaining_ply - 1, next_pv)) {
            if (pv != nullptr) {
                pv->clear();
                pv->push_back(move);
                pv->insert(pv->end(), defense_line.begin(), defense_line.end());
            }
            return true;
        }
        if (aborted_) {
            return false;
        }
    }

    return false;
}

この関数の重要なポイントを整理します。

10.4 mate_search_defense() — 防御側の探索

防御側の探索関数 mate_search_defense() は、玉方のすべての合法手を試し、 逃れ手があるかどうかを判定します。 

bool Search::mate_search_defense(const Position& position,
                                 int remaining_ply,
                                 std::vector<Move>* pv) {
    if (should_stop()) {
        aborted_ = true;
        return false;
    }
    count_node();

    auto legal_moves = position.generate_search_legal_moves();
    if (legal_moves.empty()) {
        return position.is_in_check(position.side_to_move());
    }
    if (remaining_ply <= 0) {
        return false;
    }

    const Move no_tt_move;
    const auto ordered_moves = score_moves(position, legal_moves, 0, no_tt_move);

    Move selected_move;
    std::vector<Move> selected_line;
    std::size_t selected_length = 0;
    bool has_selected = false;

    for (const OrderedMove& ordered_move : ordered_moves) {
        const Move& move = ordered_move.move;
        Position child = position;
        child.do_move(move);
        std::vector<Move> attack_line;
        std::vector<Move>* next_pv = pv != nullptr ? &attack_line : nullptr;
        if (!mate_search_attack(child, remaining_ply - 1, next_pv)) {
            return false;
        }
        if (pv != nullptr) {
            const std::size_t candidate_length = 1 + attack_line.size();
            if (!has_selected || candidate_length > selected_length) {
                has_selected = true;
                selected_move = move;
                selected_length = candidate_length;
                selected_line = std::move(attack_line);
            }
        }
        if (aborted_) {
            return false;
        }
    }

    if (pv != nullptr) {
        pv->clear();
        if (has_selected) {
            pv->push_back(selected_move);
            pv->insert(pv->end(), selected_line.begin(), selected_line.end());
        }
    }

    return true;
}

防御側の探索における重要な判定ロジックは以下の通りです。

10.5 通常探索との統合

詰み探索は find_best_move() の冒頭、反復深化ループに入る前に呼び出されます。 

std::vector<Move> mating_line;
if ((options.infinite || options.max_depth >= 3 || options.time_limit_ms >= 200) &&
    find_forced_mate(root, kMateSearchMaxPly, mating_line) && !mating_line.empty()) {
    result.best_move = mating_line.front();
    result.has_best_move = true;
    result.score_cp = kMateScore - 1;
    result.completed_depth = kMateSearchMaxPly;
    // ... info出力 ...
    return result;
}

呼び出し条件として、探索深さが3以上、または持ち時間が200ms以上、あるいは無限探索モードであることが要求されます。 これは、極めて短い探索（深さ1〜2）で詰み探索のオーバーヘッドを避けるための配慮です。

詰みが見つかった場合、通常の反復深化探索を一切行わず、即座に詰み手順を返します。 スコアは kMateScore - 1 として報告され、これはGUIに対して「1手詰み以上の詰みが見つかった」ことを示します。

10.6 詰みスコアの表現

Hayanagiでは詰みスコアを kMateScore - ply という形式で表現します。 kMateScore は十分に大きな定数で、通常の評価値とは明確に区別されます。 

int terminal_score(const TerminalStatus& status, int ply) {
    switch (status.outcome) {
        case TerminalOutcome::Win:
            return kMateScore - ply;
        case TerminalOutcome::Loss:
            return -kMateScore + ply;
        case TerminalOutcome::Draw:
            return 0;
        // ...
    }
}

ply を引くことにより、より短い手数での詰みがより高いスコアを持ちます。 例えば1手詰み（ply=1）は3手詰み（ply=3）よりも高く評価されます。 これにより探索は最短の詰み手順を優先的に選択します。

また、詰みスコアかどうかの判定には閾値 kMateThreshold = kMateScore - 256 が使われます。 スコアがこの閾値を超える場合は「詰みに近い」と判断し、 置換表への保存時にply補正（score_to_tt / score_from_tt）を適用して、 異なる深さからの参照でも正しい手数情報を維持します。

10.7 まとめ

Hayanagiの詰み探索は、以下の設計方針に基づいています。

この仕組みにより、計算コストを抑えつつ、対局において重要な短手数の詰みを確実に発見できます。