第8章 探索アルゴリズム — 基礎編

将棋エンジンの心臓部は探索です。 合法手生成（第6章）で得た手の候補を先読みし、評価関数（第11章）で局面の良し悪しを数値化し、 最も有利になる手を選び出す — この一連の処理が探索アルゴリズムです。

本章では Hayanagi の探索コア部分を構成する以下のトピックを解説します。

• 探索のエントリポイント find_best_move()
• 反復深化（Iterative Deepening）
• Negamax 法
• Alpha-Beta 枝刈り
• Principal Variation Search (PVS)
• 静止探索（Quiescence Search）
• 時間管理とノード制限

8.1 探索の全体像 — find_best_move()

探索の起点は Search::find_best_move() です。 この関数は局面 root、探索オプション、停止フラグ、情報コールバックを受け取り、 最善手を含む SearchResult を返します。

SearchResult Search::find_best_move(const Position& root,
                                    const SearchOptions& options,
                                    std::atomic_bool& stop,
                                    const std::function<void(const SearchInfo&)>& on_info) {
    const std::uint8_t tt_generation = shared_tt().next_generation();
    reset_state(options, stop, std::chrono::steady_clock::now(), nullptr, tt_generation);

    SearchResult result;
    result.terminal = root.terminal_status();
    if (result.terminal.is_terminal()) {
        result.score_cp = terminal_score(result.terminal, 0);
        result.elapsed_ms = elapsed_ms();
        result.hashfull_permille = hashfull_permille();
        return result;
    }

    auto legal_moves = root.generate_search_legal_moves();
    if (legal_moves.empty()) {
        result.elapsed_ms = elapsed_ms();
        return result;
    }
    // ... 反復深化ループへ続く
}

処理の流れは次のとおりです。

1. 置換表の世代更新 — shared_tt().next_generation() で新しい世代番号を取得し、古いエントリの置き換え優先度を制御します。
2. 内部状態のリセット — reset_state() でキラー手テーブル、ヒストリーテーブル、ノードカウンタなどを初期化します。
3. 終局判定 — ルート局面がすでに終局（詰み・千日手・入玉宣言など）であれば即座に返します。
4. 詰み探索 — 短手数の強制詰みがないか専用探索で確認します（第10章で詳述）。
5. 反復深化ループ — 深さ 1 から max_depth まで段階的に探索を深めます。

8.2 反復深化（Iterative Deepening）

反復深化とは、深さ 1 の探索から始めて、深さ 2、3、4 … と探索深度を 1 ずつ増やしながら繰り返す手法です。 一見すると同じ局面を何度も探索するので無駄に思えますが、実際には大きな利点があります。

反復深化の利点

• 時間管理との相性 — 任意のタイミングで打ち切っても、前の深さの結果が使えます。
• 着手順序の改善 — 浅い探索で得た最善手を次の深さの探索で最初に調べることで、枝刈りの効率が飛躍的に向上します。
• 置換表の活用 — 浅い探索結果が置換表に蓄積され、深い探索で参照されます。

Hayanagi の反復深化ループの骨格は以下のようになっています。

Move previous_best = fallback;

for (int depth = 1; depth <= options.max_depth; ++depth) {
    if (coordinator_should_stop()) {
        break;
    }

    // 置換表から前回の最善手を取得
    Move tt_move;
    TTEntry tt_entry;
    if (shared_tt().probe(root.position_key(), tt_entry)) {
        tt_move = tt_entry.best_move;
    }

    // ルート手を順序付け（前回の最善手に +2M ボーナス）
    std::vector<RootMove> root_moves;
    for (const Move& move : legal_moves) {
        int score = move_order_score(root, move, 0, tt_move);
        if (same_move(move, previous_best)) {
            score += 2000000;
        }
        // ...
    }
    std::sort(root_moves.begin(), root_moves.end(), /* スコア降順 */);

    // 各手について negamax を呼び出す（PVS方式）
    // ...

    previous_best = best_move;
}

各反復の開始時に、前回の最善手 previous_best に 200万点のボーナスを加えて最優先で探索します。 これにより Alpha-Beta 枝刈りの効率が大幅に改善されます。

8.3 Negamax 法の原理

二人零和完全情報ゲームの探索にはミニマックス法が基本となります。 自分の手番では評価値を最大化し、相手の手番では最小化する — これがミニマックスの考え方です。

Negamax 法はミニマックスの実装を簡潔にするテクニックです。 「相手にとっての評価値は、自分にとっての評価値の符号を反転したもの」という性質を利用し、 常に「最大化」のコードだけで済ませます。

// Negamax の原理（擬似コード）
int negamax(Position position, int depth) {
    if (depth == 0) return evaluate(position);

    int best = -INFINITY;
    for (Move move : legal_moves(position)) {
        Position child = position.do_move(move);
        int score = -negamax(child, depth - 1);  // 符号反転がポイント
        best = max(best, score);
    }
    return best;
}

再帰呼び出しの戻り値に - を付けるだけで、手番の切り替えと最小化が同時に表現されます。 Hayanagi の negamax() 関数もこの原理に基づいています。

8.4 Alpha-Beta 枝刈り

単純な Negamax は全ての手を最深まで調べるため、分岐数が大きい将棋では現実的ではありません。 Alpha-Beta 枝刈りは、「この手をこれ以上調べても結果が変わらない」と判明した時点で 探索を打ち切る最適化です。

Alpha と Beta の意味

• alpha — 現在のプレイヤーが保証できる最低スコア（下界）
• beta — 相手が許容する最大スコア（上界）

もし評価値が beta 以上になれば、相手はこの局面を選ばない（もっと良い手が他にある）ため、 残りの手を調べる必要はありません。これをBeta カット（fail-high）と呼びます。

// Alpha-Beta 枝刈り（擬似コード）
int alphabeta(Position position, int depth, int alpha, int beta) {
    if (depth == 0) return evaluate(position);

    for (Move move : legal_moves(position)) {
        Position child = position.do_move(move);
        int score = -alphabeta(child, depth - 1, -beta, -alpha);
        alpha = max(alpha, score);
        if (alpha >= beta) {
            break;  // Beta カット
        }
    }
    return alpha;
}

Hayanagi の実際のコードでは、置換表参照・ヌルムーブ枝刈り・LMR などの高速化テクニックが加わりますが（第9章で詳述）、 核心部分は上記の Alpha-Beta ロジックです。

int Search::negamax(const Position& position, int depth, int ply,
                    int alpha, int beta) {
    // 停止判定・終局判定・深さ0で静止探索へ
    if (should_stop()) { aborted_ = true; return evaluate(position); }
    const TerminalStatus terminal = position.terminal_status();
    if (terminal.is_terminal()) { return terminal_score(terminal, ply); }
    if (depth <= 0) { return quiescence(position, ply, alpha, beta); }

    count_node();
    const int alpha_original = alpha;
    // ... 置換表参照、ヌルムーブ枝刈り（第9章） ...

    auto legal_moves = position.generate_search_legal_moves();
    const auto ordered_moves = score_moves(position, legal_moves, ply, tt_move);

    Move best_move;
    int best_score = -kInfinity;

    for (std::size_t move_index = 0; move_index < ordered_moves.size(); ++move_index) {
        const Move& move = ordered_moves[move_index].move;
        Position child = position;
        child.do_move(move);

        int score = 0;
        if (move_index == 0) {
            score = -negamax(child, depth - 1, ply + 1, -beta, -alpha);
        } else {
            // PVS（次節で解説）
            score = -negamax(child, depth - 1, ply + 1, -alpha - 1, -alpha);
            if (!aborted_ && score > alpha && score < beta) {
                score = -negamax(child, depth - 1, ply + 1, -beta, -alpha);
            }
        }

        if (aborted_) { return 0; }
        if (score > best_score) { best_score = score; best_move = move; }
        if (score > alpha) { alpha = score; }
        if (alpha >= beta) {
            // Beta カット — キラー手・ヒストリー記録
            store_tt(key, depth, ply, best_score, alpha_original, beta, best_move);
            return best_score;
        }
    }

    store_tt(key, depth, ply, best_score, alpha_original, beta, best_move);
    return best_score;
}

関数の冒頭で alpha_original を保存している点に注目してください。 これは探索終了後に置換表へ記録する際、スコアが Exact（正確値）なのか Upper/Lower bound なのかを判定するために使います。

8.5 Principal Variation Search (PVS)

Alpha-Beta 枝刈りの効率は、最善手を最初に調べるほど高くなります。 着手順序が完璧であれば、最初の手（principal variation）だけが alpha を更新し、 残りの手は全て Beta カットされるはずです。

PVS（Principal Variation Search）はこの性質を積極的に利用します。

PVS のアルゴリズム

1. 最初の手はフルウィンドウ [-beta, -alpha] で探索する。
2. 2番目以降の手は、まずヌルウィンドウ [-alpha-1, -alpha] で探索する。
   • 結果が alpha 以下なら、この手は最善手ではないと確定 — 次の手へ進む。
   • 結果が alpha を超えたら、この手が予想より良い — フルウィンドウ [-beta, -alpha] で再探索する。

Hayanagi のルートノードでの PVS 実装を見てみましょう。

for (std::size_t move_index = 0; move_index < root_moves.size(); ++move_index) {
    Position child = root;
    child.do_move(root_moves[move_index].move);

    int score = 0;
    if (move_index == 0) {
        // 最初の手: フルウィンドウ
        score = -negamax(child, depth - 1, 1, -beta, -alpha);
    } else {
        // 2番目以降: ヌルウィンドウで試す
        score = -negamax(child, depth - 1, 1, -alpha - 1, -alpha);
        if (!aborted_ && score > alpha && score < beta) {
            // 改善された — フルウィンドウで再探索
            score = -negamax(child, depth - 1, 1, -beta, -alpha);
        }
    }
    // ...
}

ヌルウィンドウ探索は幅が 1 しかないため、非常に高速に Beta カットまたは fail-low が判明します。 着手順序が良ければ、再探索が必要になるケースは稀であり、全体として大幅な高速化が実現します。

内部ノード（negamax() 内）では、さらに LMR（Late Move Reduction）と組み合わせた 3段階の探索が行われます。

if (move_index == 0) {
    score = -negamax(child, depth - 1, ply + 1, -beta, -alpha);
} else {
    // LMR: 順序が後ろの静かな手は浅い深さで試す
    const int reduced_depth = std::max(0, depth - 1 - reduction);
    score = -negamax(child, reduced_depth, ply + 1, -alpha - 1, -alpha);
    if (!aborted_ && score > alpha) {
        // 縮小なしのヌルウィンドウで再探索
        score = -negamax(child, depth - 1, ply + 1, -alpha - 1, -alpha);
        if (!aborted_ && score > alpha && score < beta) {
            // フルウィンドウで最終確認
            score = -negamax(child, depth - 1, ply + 1, -beta, -alpha);
        }
    }
}

8.6 静止探索（Quiescence Search）

Alpha-Beta 探索は指定された深さに達すると評価関数を呼び出しますが、 局面が「戦闘中」の場合、その評価値は信頼できません。 たとえば銀で飛車を取った直後に深さ制限に達すると、飛車を取り返される手を考慮せずに 「飛車得」と誤評価してしまいます。

静止探索（Quiescence Search）は、この「水平線効果」を軽減するために、 通常探索の深さ 0 以降で戦術手（捕獲・成りなど）のみを追加で探索する手法です。

Stand-Pat（静的評価によるカット）

int Search::quiescence(const Position& position, int ply,
                       int alpha, int beta) {
    if (should_stop()) { aborted_ = true; return evaluate(position); }

    count_node();
    const TerminalStatus terminal = position.terminal_status();
    if (terminal.is_terminal()) {
        return terminal_score(terminal, ply);
    }

    const bool in_check = position.is_in_check(position.side_to_move());
    if (!in_check) {
        const int stand_pat = evaluate(position);
        if (stand_pat >= beta) {
            return stand_pat;  // 何もしなくてもbeta以上 → カット
        }
        alpha = std::max(alpha, stand_pat);
    }
    // ...

王手がかかっていない場合、まず現在の局面の静的評価値（stand-pat）を計算します。

• stand_pat >= beta なら、何も取らなくても十分良いのでカットします。
• そうでなければ、alpha を stand-pat で更新します（「何もしない」という選択肢が保証する下界）。

戦術手の生成と SEE プルーニング

    auto tactical_moves = position.generate_quiescence_moves();
    if (tactical_moves.empty()) {
        if (in_check) {
            return -kMateScore + ply;  // 王手回避手がない → 詰み
        }
        return alpha;
    }

    const Move no_tt_move;
    const auto ordered_moves = score_moves(position, tactical_moves, ply, no_tt_move);
    for (const OrderedMove& ordered_move : ordered_moves) {
        const Move& move = ordered_move.move;
        const int captured = position.piece_at(move.to);
        if (!in_check && captured != 0
            && position.static_exchange_eval(move) < -120) {
            continue;  // SEE が -120 未満の捕獲はスキップ
        }
        Position child = position;
        child.do_move(move);
        const int score = -quiescence(child, ply + 1, -beta, -alpha);
        if (aborted_) { return 0; }
        if (score >= beta) { return score; }
        alpha = std::max(alpha, score);
    }

    return alpha;
}

静止探索のポイントをまとめます。

1. 戦術手のみ生成 — generate_quiescence_moves() は捕獲手・成り手・王手回避手を返します。静かな手（移動のみ）は生成しません。
2. SEE プルーニング — 捕獲手であっても、SEE（Static Exchange Evaluation、第9章で詳述）の値が -120 未満の場合はスキップします。 これは「明らかに駒損になる取り合い」を排除するための枝刈りです。閾値 120 は香車の価値（約 430）よりも十分小さく、 わずかな損であれば調べる方針です。
3. 王手時の特別処理 — 王手がかかっている場合は stand-pat を使わず、全ての王手回避手を調べます。 回避手がなければ詰みスコア -kMateScore + ply を返します。

8.7 時間管理 — should_stop()

実際の対局では、エンジンは制限時間内に指し手を返さなければなりません。 Hayanagi は should_stop() 関数で停止判定を行います。

bool Search::should_stop() {
    if (stop_ != nullptr && stop_->load()) {
        return true;
    }
    if (options_.node_limit > 0
        && current_nodes() >= options_.node_limit) {
        return true;
    }
    if (!options_.infinite && options_.time_limit_ms > 0
        && elapsed_ms() >= options_.time_limit_ms) {
        return true;
    }
    return false;
}

停止条件は3つあります。

1. 外部停止フラグ — USI の stop コマンドや ponder hit で stop_ が true に設定されます。std::atomic_bool を使用しているため、探索スレッドから安全に参照できます。
2. ノード制限 — go nodes N で指定された場合、探索ノード数が上限に達したら停止します。current_nodes() はマルチスレッド時に共有アトミックカウンタを参照します。
3. 時間制限 — go btime/wtime などから計算された制限時間を超えたら停止します。infinite モードの場合はこの条件は無効です。

should_stop() は negamax() と quiescence() の冒頭で毎回呼ばれます。 停止が検出されると aborted_ = true がセットされ、再帰呼び出しの巻き戻し中に 各レベルで即座に return 0 が実行されます。

経過時間の計測

int Search::elapsed_ms() const {
    const auto now = std::chrono::steady_clock::now();
    return static_cast<int>(
        std::chrono::duration_cast<std::chrono::milliseconds>(
            now - start_time_).count());
}

std::chrono::steady_clock を使用しているため、システム時刻の変更に影響されません。 探索開始時に start_time_ を記録し、そこからの経過ミリ秒を返します。

8.8 ノード制限

ノード制限は主にベンチマーク（bench nodes N）やテスト時に使用されます。 ノードカウントは count_node() で管理されます。

void Search::count_node() {
    ++nodes_;
    if (shared_nodes_ != nullptr) {
        shared_nodes_->fetch_add(1, std::memory_order_relaxed);
    }
}

シングルスレッド時はローカル変数 nodes_ をインクリメントするだけです。 マルチスレッド時は、各ワーカーのローカルカウンタに加えて、共有アトミックカウンタ shared_nodes_ も更新します。 memory_order_relaxed を使用しているのは、ノードカウントは厳密な正確さを必要としないためです。

8.9 終局スコアの計算

探索中に終局状態（詰み・千日手・入玉宣言など）に到達した場合のスコア計算も重要です。

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;
        case TerminalOutcome::None:
        default:
            return 0;
    }
}

詰みスコアから ply（ルートからの手数）を引く・足すことで、 最短で詰ます手と最長で粘る手を自然に選ぶようになります。 勝ちの場合は kMateScore - ply（短い方が高スコア）、 負けの場合は -kMateScore + ply（長い方が高スコア＝被害が少ない）です。

8.10 まとめ

本章で解説した探索の基礎を整理します。

次章では、これらの基礎アルゴリズムを実用的な速度にするための高速化テクニック — 置換表、ヌルムーブ枝刈り、LMR、着手順序の最適化、SEE — を解説します。