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

第IV部 並列化とプロトコル

第12章 並列探索

現代のCPUはマルチコアが標準であり、将棋エンジンもこれを活用して探索速度を向上させることが求められます。 しかし、アルファベータ探索は本質的に逐次的なアルゴリズムであり、単純に並列化できるものではありません。 本章では、Hayanagiが採用する並列探索の手法と、スレッド間でデータを共有するための仕組みを解説します。

12.1 並列探索の動機と課題

探索を並列化する動機は明確です。4コアのCPUであれば理想的には4倍の速度で探索でき、 同じ持ち時間でより深い読みが可能になります。 しかし、アルファベータ探索には以下の課題があります。

12.2 Hayanagiのアプローチ: Root Move Splitting

Hayanagiは「Root Move Splitting」と呼ばれる手法を採用しています。 これはルート局面の合法手を複数のスレッドに分配し、各スレッドが独立に探索を行うものです。 実装が比較的単純で、スレッド間の同期コストが小さいという利点があります。

RootMove 構造体

ルートの各候補手は RootMove 構造体で管理されます。 

struct RootMove {
    Move move;
    int order_score = 0;
    int score = -kInfinity;
    std::string pv;
    std::size_t worker_index = 0;
};

ルートの合法手を各スレッドに分配

find_best_move() の中で、マルチスレッド探索時には以下のようにワーカーを生成し、 候補手をアトミックなインデックスで動的に分配します。 

std::atomic_size_t next_index{0};
std::vector<std::thread> threads;
threads.reserve(workers.size() > 0 ? workers.size() - 1 : 0);

auto worker_body = [&](std::size_t worker_index) {
    Search& worker = workers[worker_index];
    while (true) {
        const std::size_t move_index =
            next_index.fetch_add(1, std::memory_order_relaxed);
        if (move_index >= root_moves.size()) {
            break;
        }
        root_moves[move_index].score =
            worker.search_root_move(root, root_moves[move_index].move, depth);
        root_moves[move_index].worker_index = worker_index;
        if (worker.aborted_) {
            break;
        }
    }
};

for (std::size_t worker_index = 1; worker_index < workers.size(); ++worker_index) {
    threads.emplace_back(worker_body, worker_index);
}
worker_body(0);
for (std::thread& thread : threads) {
    thread.join();
}

この実装のポイントは以下の通りです。 

int Search::search_root_move(const Position& root, const Move& root_move, int depth) {
    if (should_stop()) {
        aborted_ = true;
        return 0;
    }

    Position child = root;
    child.do_move(root_move);
    return -negamax(child, depth - 1, 1, -kInfinity, kInfinity);
}

各ワーカーは alpha = -kInfinity, beta = kInfinity の全窓で探索を行います。 Root Move Splitting ではスレッド間でアルファ値を共有しないため、 各手の探索は独立したフルウィンドウ探索になります。

12.3 Threads オプションとスレッド管理

スレッド数はUSIオプション Threads で設定され、SearchOptions::threads に格納されます。 find_best_move() では合法手の数を上限として実際のスレッド数を決定します。 

const int thread_count = std::max(1, std::min(options.threads, static_cast<int>(legal_moves.size())));

各ワーカーは独立した Search オブジェクトであり、 キラー手テーブルやヒストリーテーブルなどの探索状態を個別に保持します。 

std::vector<Search> workers;
if (thread_count > 1) {
    workers.resize(static_cast<std::size_t>(thread_count));
    for (Search& worker : workers) {
        worker.reset_state(options, stop, start_time_, &shared_nodes, tt_generation);
    }
}

reset_state() は各ワーカーに共通の設定（探索オプション、停止フラグ、開始時刻、 共有ノードカウンタ、置換表世代番号）を渡し、探索状態を初期化します。

結果の集約

全スレッドが終了した後、各候補手のスコアを比較して最良の手を選びます。 

if (!aborted_) {
    for (std::size_t move_index = 0; move_index < root_moves.size(); ++move_index) {
        const RootMove& root_move = root_moves[move_index];
        if (!found_move || root_move.score > best_score) {
            found_move = true;
            best_score = root_move.score;
            best_move = root_move.move;
            best_index = move_index;
        }
    }
}

いずれかのワーカーが中断された場合は、そのイテレーション全体の結果を破棄し、 前回のイテレーションの結果を使用します。

12.4 共有置換表のスレッドセーフティ

Hayanagiの置換表（トランスポジションテーブル）は全スレッドで共有されます。 あるスレッドが発見した局面情報を他のスレッドが再利用できるため、並列探索の効率が向上します。 しかし、複数スレッドからの同時アクセスにはスレッドセーフティの保証が必要です。

AtomicTTEntry / AtomicTTCluster

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（スコア・深さ・最善手・世代などをパックした64ビット値） の2つのアトミック変数で構成されます。 クラスタサイズは kTtClusterSize = 4 で、同一ハッシュインデックスに4エントリを格納できます。

acquire-release memory ordering

置換表の読み書きには acquire-release メモリオーダリングが使われています。 

// 読み取り（probe）
const std::uint64_t stored_key = atomic_entry.key.load(std::memory_order_acquire);
// ...
const std::uint64_t payload = atomic_entry.payload.load(std::memory_order_relaxed);
if (atomic_entry.key.load(std::memory_order_acquire) == stored_key) {
    out = unpack_tt_entry(stored_key, payload);
    return true;
}

// 書き込み（store）
atomic_entry.payload.store(pack_tt_payload(entry), std::memory_order_relaxed);
atomic_entry.key.store(entry.key, std::memory_order_release);

書き込み側では、まず payload を relaxed で書き込み、 次に key を release で書き込みます。 これにより、読み取り側が acquire で key を読んだとき、 対応する payload が確実に見えることが保証されます。

読み取り側ではさらに、key を2回読んで一致を確認するダブルチェックを行います。 書き込みの途中で読み取りが割り込んだ場合、keyが変化するため不整合なデータの使用を防げます。

ロックフリー設計の利点とトレードオフ

この設計はミューテックスやスピンロックを一切使わないロックフリー実装です。

12.5 ノードカウンタの共有

探索ノード数の正確なカウントは、ノード制限（go nodes N）の判定や info出力のNPS計算に必要です。Hayanagiでは std::atomic<std::uint64_t> を使って 全スレッドのノード数を集約します。 

std::atomic<std::uint64_t> shared_nodes{nodes_};

各ワーカーの count_node() でアトミックにインクリメントされます。 

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

std::uint64_t Search::current_nodes() const {
    if (shared_nodes_ != nullptr) {
        return shared_nodes_->load(std::memory_order_relaxed);
    }
    return nodes_;
}

memory_order_relaxed を使用しているため、厳密なリアルタイムの正確性は保証されませんが、 カウンタの更新自体はアトミックであり、最終的な合計値は正確です。 ノード制限の判定は多少の誤差を許容するため、relaxed ordering で十分です。

12.6 並列探索の限界と考察

Root Move Splitting は実装の単純さが大きな利点ですが、いくつかの限界があります。

探索オーバーヘッド

逐次探索ではPVS（Principal Variation Search）により、最善手を見つけた後の候補手は 狭い窓（ゼロウィンドウ）で高速に棄却できます。 しかし Root Move Splitting では各スレッドが独立にフルウィンドウ探索を行うため、 逐次探索なら枝刈りできたノードまで探索してしまいます。

Hayanagiのシングルスレッド探索では PVS を使用しています。 

if (move_index == 0) {
    score = -negamax(child, depth - 1, 1, -beta, -alpha);
} else {
    score = -negamax(child, depth - 1, 1, -alpha - 1, -alpha);
    if (!aborted_ && score > alpha && score < beta) {
        score = -negamax(child, depth - 1, 1, -beta, -alpha);
    }
}

マルチスレッド時にはこの最適化が効かないため、 スレッド数に比例した線形のスピードアップは期待できません。 典型的には4スレッドで2〜3倍程度の速度向上が現実的です。

ロックフリーの衝突

置換表のロックフリー設計では、同一クラスタへの同時書き込みにより エントリが上書きされる可能性があります。 特にスレッド数が多い場合、有用なエントリが失われる頻度が増加し、 探索効率が低下する場合があります。 置換表サイズ（Hash オプション）を十分に大きく設定することで、この影響を軽減できます。

より高度な並列化手法

Stockfish等の強豪エンジンでは、Lazy SMP（各スレッドがルートから独立に異なる深さで探索する手法）や ABDADA（探索木の内部ノードレベルで作業を分配する手法）が採用されています。 これらはRoot Move Splittingよりも高いスケーラビリティを実現しますが、 実装の複雑さも増します。Hayanagiの設計は教育目的として、 並列探索の基本概念を理解するのに適した構成となっています。

12.7 まとめ

Hayanagiの並列探索は以下の設計で構成されています。

Root Move Splitting は最も単純な並列探索手法のひとつですが、 共有置換表によるスレッド間の情報共有と組み合わせることで、 少数のスレッドでは十分な速度向上を実現できます。