第9章 探索の高速化テクニック

第8章では Alpha-Beta 探索と PVS の原理を学びました。 しかし、将棋の合法手は平均 80 手前後あり、素朴な Alpha-Beta だけでは深い読みは困難です。 本章では、Hayanagi が実装している高速化テクニックを詳しく解説します。

• 置換表（Transposition Table）
• ヌルムーブ枝刈り（Null-Move Pruning）
• Late Move Reduction (LMR)
• 着手順序の最適化（Move Ordering）
• SEE（Static Exchange Evaluation）
• キラー手とヒストリーヒューリスティック

9.1 置換表（Transposition Table）

将棋の探索木では、手順前後（transposition）により同じ局面に異なる経路から到達することが頻繁に起こります。 置換表は、既に探索済みの局面の結果をハッシュテーブルに記録し、再利用するための仕組みです。

9.1.1 TTEntry の構造

enum class BoundType : std::uint8_t {
    Exact = 0,
    Lower,
    Upper,
};

struct TTEntry {
    std::uint64_t key = 0;       // Zobrist ハッシュキー
    int depth = -1;              // 探索深度
    int score = 0;               // 評価スコア
    BoundType bound = BoundType::Exact;  // スコアの種類
    Move best_move;              // 最善手
    std::uint8_t generation = 0; // 世代番号
};

各フィールドの意味は以下のとおりです。

• key — 局面の Zobrist ハッシュキー。衝突検出に使用します。
• depth — このエントリが何手先まで読んだ結果かを示します。現在の探索深度以上であれば結果を信頼できます。
• score — 探索結果の評価値です。
• bound — スコアの種類を示します。
  • Exact — 正確な値（PV ノード）
  • Lower — 下界（Beta カットが起きた）
  • Upper — 上界（全ての手が alpha 以下だった）
• best_move — この局面で見つかった最善手。着手順序の改善に使います。
• generation — エントリの鮮度を管理する世代番号。

9.1.2 ビットパッキング

メモリ効率のため、TTEntry は 2 つの uint64_t（key と payload）にパックされます。 payload の内部構造は次のとおりです。

std::uint64_t pack_tt_payload(const TTEntry& entry) {
    const std::uint16_t score_bits =
        static_cast<std::uint16_t>(static_cast<std::int16_t>(entry.score));
    const std::uint8_t depth_bits =
        static_cast<std::uint8_t>(std::max(entry.depth, -1) + 1);
    const std::uint64_t move_bits = encode_move(entry.best_move);

    return move_bits                                          // bit  0-19: 着手
         | (static_cast<std::uint64_t>(score_bits) << 20)    // bit 20-35: スコア
         | (static_cast<std::uint64_t>(depth_bits) << 36)    // bit 36-43: 深度
         | (static_cast<std::uint64_t>(
               static_cast<std::uint8_t>(entry.bound)) << 44) // bit 44-45: bound
         | (static_cast<std::uint64_t>(entry.generation) << 46); // bit 46-53: 世代
}

1 エントリあたりわずか 16 バイト（key 8 バイト + payload 8 バイト）で済むため、 限られたメモリに多くのエントリを格納できます。

9.1.3 SharedTranspositionTable と 4エントリクラスタ方式

置換表はグローバルに 1 つだけ存在し、全スレッドで共有されます（デフォルト 16MB）。 ハッシュの衝突を緩和するため、1 つのインデックスに対して4 つのスロット（クラスタ）を持ちます。

ハッシュの衝突を緩和するため、1 つのインデックスに対して4 つのスロット（クラスタ）を持ちます。

constexpr std::size_t kTtClusterSize = 4;

struct AtomicTTEntry {
    std::atomic<std::uint64_t> key{0};
    std::atomic<std::uint64_t> payload{0};
};

struct AtomicTTCluster {
    std::array<AtomicTTEntry, kTtClusterSize> entries{};
};

各スロットの key と payload を std::atomic<uint64_t> で保持し、 ロックなしでマルチスレッド安全な読み書きを実現しています。

9.1.5 probe() と store() — acquire-release セマンティクス

probe() は局面キーでクラスタ内の 4 スロットを順に検索します。

for (const AtomicTTEntry& atomic_entry : cluster.entries) {
    const std::uint64_t stored_key =
        atomic_entry.key.load(std::memory_order_acquire);
    if (stored_key != key) { continue; }
    const std::uint64_t payload =
        atomic_entry.payload.load(std::memory_order_relaxed);
    // key を再読みして一貫性を確認（ダブルチェック）
    if (atomic_entry.key.load(std::memory_order_acquire) == stored_key) {
        out = unpack_tt_entry(stored_key, payload);
        return true;
    }
}

key の読み込みに memory_order_acquire、書き込みに memory_order_release を使い、 key と payload の一貫性を保証します。payload 読み取り後に key を再読みし、別スレッドによる上書きを検出します。

store() では、(1) 同一局面が既にあれば上書き（ただし同世代で浅い場合は拒否）、 (2) 空きスロットがあれば書き込み、(3) 全スロットが埋まっていれば最も古い/浅いエントリを置換します。 書き込みは常に payload → key の順で、key に memory_order_release を使います。

9.1.6 世代管理（next_generation）による置き換え戦略

各探索開始時に next_generation() で世代番号をインクリメントします。 置き換え候補の評価は replacement_score() で行います。

static std::size_t replacement_score(const TTEntry& entry,
                                     std::uint8_t generation) {
    const std::size_t age_penalty =
        entry.generation == generation ? 0 : 1024;
    const int bounded_depth = std::max(entry.depth, -1);
    return age_penalty
         + static_cast<std::size_t>(255 - std::min(bounded_depth + 1, 255));
}

スコアが高いほど「置き換えやすい」ことを意味します。 古い世代のエントリには 1024 のペナルティが加算されるため、優先的に上書きされます。 同世代であれば、深度が浅いエントリほど置き換えられやすくなります。

9.1.7 hashfull_permille() — 使用率計測

int hashfull_permille(std::uint8_t generation) const {
    constexpr std::size_t kSampleEntries = 1000;
    int used = 0;
    for (std::size_t sample = 0; sample < kSampleEntries; ++sample) {
        // テーブル全体から均等にサンプリング
        const std::size_t entry_index =
            sample * (cluster_count * kTtClusterSize) / kSampleEntries;
        // ...
        if (entry.generation == generation) { ++used; }
    }
    return used;  // パーミル（千分率）で返す
}

USI プロトコルの info hashfull で報告する値を計算します。 テーブル全体を走査するのは高コストなので、1000 個のエントリを均等にサンプリングして 現在の世代のエントリ数を数えます。結果はパーミル（0〜1000）で返されます。

9.1.8 score_to_tt() / score_from_tt() — 詰みスコアの ply 補正

詰みスコアは「ルートからの手数」に依存するため、置換表に保存・取得する際に補正が必要です。

int score_to_tt(int score, int ply) {
    if (score >= kMateThreshold) { return score + ply; }
    if (score <= -kMateThreshold) { return score - ply; }
    return score;
}

int score_from_tt(int score, int ply) {
    if (score >= kMateThreshold) { return score - ply; }
    if (score <= -kMateThreshold) { return score + ply; }
    return score;
}

例えば、ply=5 で「3手詰め」を発見した場合、スコアは kMateScore - 8（5+3=8手後に詰み）です。 置換表に保存する際は ply を足して kMateScore - 3（ルートから3手の詰み）に変換します。 別の ply で取り出す際は、新しい ply を引いて正しいスコアに戻します。

9.1.9 negamax() での置換表利用

TTEntry tt_entry;
if (shared_tt().probe(key, tt_entry)) {
    tt_move = tt_entry.best_move;  // 着手順序に利用
    if (tt_entry.depth >= depth) {
        const int tt_score = score_from_tt(tt_entry.score, ply);
        switch (tt_entry.bound) {
            case BoundType::Exact:
                return tt_score;        // 正確値 → そのまま返す
            case BoundType::Lower:
                alpha = std::max(alpha, tt_score);  // 下界で alpha 更新
                break;
            case BoundType::Upper:
                beta = std::min(beta, tt_score);    // 上界で beta 更新
                break;
        }
        if (alpha >= beta) { return tt_score; }  // カット
    }
}

9.2 ヌルムーブ枝刈り（Null-Move Pruning）

ヌルムーブ枝刈りは「もし自分がパス（何もしない）しても相手が beta を超えられないなら、 実際に手を指せばさらに良いはずなので、この局面は beta カットできる」という発想に基づく枝刈りです。

原理

将棋では一手パスは合法手ではありませんが、探索上の仮想操作として手番だけを相手に渡します。 パスした後の局面を通常より浅い深度で探索し、結果が beta 以上であれば枝刈りします。

const int static_eval = evaluate(position);
if (can_try_null_move(position, depth, beta, static_eval)) {
    Position null_position = position.make_null_move();
    const int reduction = kNullMoveBaseReduction + depth / 4;  // R = 2 + depth/4
    const int score =
        -negamax(null_position, depth - 1 - reduction, ply + 1, -beta, -beta + 1);
    if (aborted_) { return 0; }
    if (score >= beta) {
        return score;  // パスしても良い → 枝刈り
    }
}

縮小量 R = 2 + depth/4 は深度に応じて増加します。 深い探索ほど大胆に刈り取ることで、計算量を大幅に削減します。

can_try_null_move() の条件

bool Search::can_try_null_move(const Position& position,
                               int depth, int beta,
                               int static_eval) const {
    if (depth < 3) { return false; }
    if (beta >= kMateThreshold || beta <= -kMateThreshold) {
        return false;
    }
    if (position.is_in_check(position.side_to_move())) {
        return false;
    }
    if (!has_non_pawn_material(position, position.side_to_move())) {
        return false;
    }
    return static_eval >= beta - 96 - depth * 16;
}

ヌルムーブを試す条件は5つあります。

1. depth >= 3 — 浅い探索では効果が薄いため無効化します。
2. 詰みスコア付近でない — 詰みの読みではヌルムーブは危険です。
3. 王手がかかっていない — 王手中にパスすると不正な局面になります。
4. 歩以外の駒がある — 歩と玉しかない終盤（いわゆる Zugzwang）ではパスが最善になりうるため、ヌルムーブは不適切です。
5. 静的評価が beta に近い — static_eval >= beta - 96 - depth * 16 の条件で、評価値が beta から大きく離れている場合はスキップします。

9.3 Late Move Reduction (LMR)

LMRは「着手順序の後ろの方にある静かな手は、おそらく最善手ではない」という仮定に基づき、 そのような手を浅い深度で試すテクニックです。

const bool gives_check = child.is_in_check(child.side_to_move());
const bool quiet = is_quiet(position, move) && !gives_check;
const bool late_move = quiet && !in_check
                     && depth >= 4 && move_index >= 4;
const int reduction = late_move
    ? (depth >= 6 && move_index >= 8 ? 2 : 1)
    : 0;

LMR の適用条件は以下のとおりです。

• 静かな手 — 捕獲でも成りでもなく、王手も与えない手（is_quiet() は !move.promote && piece_at(move.to) == 0）。
• 王手回避中でない — 王手がかかっている局面では全ての手を正確に読む必要があります。
• depth >= 4 — 浅い探索では効果が薄いため無効化。
• move_index >= 4 — 最初の 4 手は順序が高いため縮小しません。

縮小量は次の2段階です。

• 1手縮小 — 基本の LMR。
• 2手縮小 — depth >= 6 かつ move_index >= 8 の場合。深い探索で順序がさらに後ろの手は、より大胆に刈ります。

LMR で縮小された探索が alpha を超えた場合は、通常深度のヌルウィンドウ探索で再確認し、 さらに alpha を超えればフルウィンドウで再探索します（PVS との組み合わせ、第8章 8.5 節参照）。

9.4 着手順序の最適化（Move Ordering）

Alpha-Beta 枝刈りの効率は着手順序に大きく依存します。 最善手を早く調べるほど、beta カットが早期に起こり、探索ノード数が減ります。 Hayanagi の move_order_score() は各手にスコアを付け、降順にソートします。

int Search::move_order_score(const Position& position,
                             const Move& move, int ply,
                             const Move& tt_move) const {
    int score = 0;

    // (1) 置換表の最善手: +4,000,000
    if (same_move(move, tt_move)) {
        score += 4000000;
    }

    // (2) 捕獲手: 120,000 + captured_value*12 + SEE*24
    const int captured = position.piece_at(move.to);
    if (captured != 0) {
        const int see = position.static_exchange_eval(move);
        score += 120000 + piece_value(piece_type(captured)) * 12 + see * 24;
        if (see < 0) {
            score += see * 48;  // 負のSEEにはさらにペナルティ
        }
    }

    // (3) 成り: +1,200
    if (move.promote) {
        score += 1200;
    }

    // (4) 駒打ち: 200 + piece_value/8
    if (move.drop) {
        score += 200 + piece_value(move.piece) / 8;
    }

    // (5) キラー手: +90,000 (第1) / +80,000 (第2)
    if (ply < kMaxDepth) {
        if (same_move(move, killer_moves_[ply][0])) {
            score += 90000;
        } else if (same_move(move, killer_moves_[ply][1])) {
            score += 80000;
        }
    }

    // (6) ヒストリーヒューリスティック
    if (captured == 0 && !move.promote) {
        score += history_score(position.side_to_move(), move);
    }

    return score;
}

優先度を整理すると、次の階層構造になっています。

置換表の最善手が圧倒的に高いスコア（400万）を持つ点に注目してください。 前回の探索で最善だった手を真っ先に調べることが、枝刈り効率の鍵です。

9.5 SEE（Static Exchange Evaluation）

SEEは「ある駒を取ったとき、取り返しの連鎖が終わった後に駒得になるか損になるか」を 実際に手を指すことなく静的に見積もる手法です。

SEE は着手順序と静止探索の両方で使われます。

• 着手順序 — 捕獲手のスコアに SEE 値を加算し、良い取り合いを優先します。
• 静止探索のプルーニング — SEE < -120 の捕獲手はスキップします（第8章 8.6 節）。

SEE の仕組み

SEE は、攻撃側と防御側が対象マスに最も安い駒で交互に取り合うシミュレーションを行います。 各プレイヤーは「取り返しても損になるなら中断する」最善の判断を行い、最終的な駒の価値差を返します。 Hayanagi では Position::static_exchange_eval() として position.cpp に実装されています。

// 着手順序での使用（search.cpp）
const int see = position.static_exchange_eval(move);
score += 120000 + piece_value(piece_type(captured)) * 12 + see * 24;

// 静止探索でのプルーニング（search.cpp）
if (!in_check && captured != 0
    && position.static_exchange_eval(move) < -120) {
    continue;
}

9.6 キラー手とヒストリーの記録

9.6.1 キラー手（Killer Moves）

キラー手は「同じ ply（探索の深さレベル）で Beta カットを引き起こした静かな手」を記録し、 同じ ply の他の局面でも優先的に試す手法です。

void Search::record_killer(int ply, const Move& move) {
    if (ply >= kMaxDepth || same_move(move, killer_moves_[ply][0])) {
        return;
    }
    killer_moves_[ply][1] = killer_moves_[ply][0];  // 第1を第2にシフト
    killer_moves_[ply][0] = move;                    // 新しい手を第1に
}

各 ply に 2 つのスロットがあり、新しいキラー手が記録されると古い方が押し出されます。 Beta カット発生時、その手が静かな手（捕獲でも成りでもない）であれば記録されます。

// negamax() 内、Beta カット時
if (alpha >= beta) {
    if (quiet) {
        record_killer(ply, move);
        record_history(position.side_to_move(), move, depth);
    }
    store_tt(key, depth, ply, best_score, alpha_original, beta, best_move);
    return best_score;
}

9.6.2 ヒストリーヒューリスティック

ヒストリーヒューリスティックは、過去の探索で Beta カットを引き起こした手に 累積スコアを与え、着手順序に反映する手法です。キラー手が ply 固有なのに対し、 ヒストリーは探索全体を通じて蓄積されます。

void Search::record_history(Color color, const Move& move, int depth) {
    const int bucket = from_bucket(move);
    int& score = history_[static_cast<int>(color)][bucket][move.to];
    score += depth * depth * 8;  // 深い探索でのカットほど高スコア
    score -= score / 16;         // 減衰（飽和を防ぐ）
}

ヒストリーテーブルのインデックスは以下のように構成されます。

• 第1次元 — 手番の色（Black / White）
• 第2次元 — 移動元バケット。盤上の移動なら from マス（0〜80）、駒打ちなら kSquareCount + hand_index(piece)
• 第3次元 — 移動先マス（0〜80）

int Search::history_score(Color color, const Move& move) const {
    return history_[static_cast<int>(color)][from_bucket(move)][move.to];
}

depth * depth * 8 により、深い探索で有効だった手ほど大きなスコアを得ます。 同時に score -= score / 16 で減衰させることで、値の飽和を防いでいます。

9.7 探索結果の置換表への記録

探索が完了すると、結果を置換表に記録します。store_tt() は bound の種類を自動判定します。

void Search::store_tt(std::uint64_t key, int depth, int ply,
                      int score, int alpha, int beta,
                      const Move& best_move) {
    TTEntry entry;
    entry.key = key;
    entry.depth = depth;
    entry.score = score_to_tt(score, ply);
    entry.best_move = best_move;
    entry.generation = tt_generation_;

    if (score <= alpha) {
        entry.bound = BoundType::Upper;  // 全ての手が alpha 以下
    } else if (score >= beta) {
        entry.bound = BoundType::Lower;  // Beta カットが起きた
    } else {
        entry.bound = BoundType::Exact;  // alpha < score < beta
    }
    shared_tt().store(entry);
}

ここで alpha は探索開始時に保存した alpha_original です。 探索中に alpha が更新されても、元の alpha と比較することで正しい bound を判定できます。

9.8 まとめ

本章で解説した高速化テクニックを整理します。

これらのテクニックは個別に効果を発揮するだけでなく、互いに補強し合います。 置換表が着手順序を改善し、良い着手順序が LMR の精度を高め、 LMR で節約した時間がさらに深い探索を可能にする — この好循環が現代の将棋エンジンの強さの源泉です。

次章では、通常探索とは別系統の詰み探索（王手限定の専用探索）を解説します。