結論だけ見たい人向け

こちらにライブラリを置いてます。

skip_beam.cppのターンをスキップできる機能について、eijirouさんの修正を参考に2025/09/28に修正しました。

はじめに

著書ゲームで学ぶ探索アルゴリズム実践入門（通称thunder本）でビームサーチを取り上げて以降、多くの人がAHCでthunder本を参考にしてくれている気がします。
一方で、多くのAHCではthunder本のビームサーチの実装は不向きです。不向きな理由の一部、主に行動の復元ができないことの問題点は別の記事でも触れていますが、そもそも状態コピーによる単純な実装では、多くの問題において遅くていまいちです。
thunder本を執筆中に革命が起きてしまったこともあり、現代のAHC参加者の中には状態の差分更新によるビームサーチを扱う猛者が増えてきました。
差分更新ビームサーチとはなんぞやという話はrhooさんの記事やeijirouさんの記事に任せますが、とりあえずブラックボックスでもいいので差分更新ビームサーチを扱えることを目指し、新たにライブラリをつくりました。

c++ユーザから見た、既存の有名な実装を見て困ったこと

rhooさんの実装

rustがメインらしく、c++は使用例が載っていないし、rhooさん自身があまりc++のサンプルを推奨してなさそう

eijirouさんの実装

現状、c++で最も有名な実装だと思います。
しかし以下の点で困りました。

EvaluatorとStateに持たせる情報を分けていて、限界高速化の面では工夫の余地がありそうだけど、かなり理解しないと使い分けが難しい。むしろEvaluatorの存在のせいでどう直すべきかわかりにくい。
Hashを必ず定義して使わないといけない。ビームサーチと同一盤面除去はセットで使うものなのはわかるが、ちょこっと試す分には不便。短期でいきなりHashありのビームサーチから試すのはきつい。
namespace beam_searchの中に、修正不可のライブラリ部分と自分自身で実装する必要性がある可変部分が混在している。どこを直せばいいかが視覚的にわかりにくい。

新しい実装

方針

汎用性を考え、eijirouさんの「ターンが飛ぶビームサーチの実装 (2025/03/16)」をベースに以下の修正を加える
※ターンを飛ばすことは現状できません

Evaluatorを排除することで困った点1を解消
Hashあり版とHashなし版を両方つくり、ユーザ側でシームレスにHashなしからHashありに移行可能にし、困った点2を解消
ユーザ自身の実装が不要な部分をライブラリとして切り出し。ユーザ自身の実装が必要な部分はconceptを使って関数名や型を強制する。これにより困った点3を解消

Hashなし版の説明

concept

現在AtCoderではc++20が使われるので、c++20で導入されたconceptという言語機能が使えます。

以下の記述をすることで、自作の型に制約を加えることができます。指定した制約を破った場合、コンパイルエラーでメッセージを出してくれます。

算術演算可能な型(doubleやintなど)をCostとして使うことを要求
以下の関数を持つStateを実装することを要求
- void expand(int,Selector)
- void move_forward(Action)
- void move_backward(Action)
なんでもいいからActionにあたる型を要求

Hashなし版のconcept

  template <typename CostType>
    concept CostConcept = requires(CostType cost) {
        { std::is_arithmetic_v<CostType> };
    };

  template <typename StateType, typename CostType, typename ActionType, typename SelectorType>
    concept StateNoHashConcept = CostConcept<CostType> &&
                                 requires(StateType state, SelectorType selector) {
                                     { state.expand(std::declval<int>(), selector) } -> same_as<void>;
                                     { state.move_forward(std::declval<ActionType>()) } -> same_as<void>;
                                     { state.move_backward(std::declval<ActionType>()) } -> same_as<void>;
                                 };
                                 
    template <typename Action, CostConcept Cost, template <typename> class State>
    struct BeamSearchNoHash{};

使い方

githubの置き場からlib/skip_beam.cppの全文をコピペし、その下に以下のようなコードを書く。
※README.mdに書いたやり方で分割コードを統合することもできる。

Action: 状態遷移を行うための情報。できるだけメモリ使用量を減らす
Cost: 状態のコストを示す算術型。値が小さいほど良いように設計する
StateBase: 状態を表すクラス。メモリをたくさん使ってもいい。
- expand: 現在の状態から次の状態候補を全てselectorに追加する。各候補の評価も一緒に渡す。
- move_forward: actionを実行して次の状態に遷移する
- move_backward: actionを実行する前の状態に遷移する

hashなし版の使うユーザ側のサンプルコード


#include "lib/skip_beam.cpp" // 提出用コードではlib/skip_beam.cppの全文をここにコピペ
using namespace std;

/// @brief TODO: 状態遷移を行うために必要な情報
/// @note メモリ使用量をできるだけ小さくしてください
struct Action
{
    // TODO: 何書いてもいい
};

/// @brief TODO: コストを表す型を算術型で指定(e.g. int, long long, double)
using Cost = int;

/// @brief TODO: 深さ優先探索に沿って更新する情報をまとめたクラス
/// @note expand, move_forward, move_backward の3つのメソッドを実装する必要がある
/// @note template<typename MultiSelectors>を最初に記述する必要がある
template <typename MultiSelectors>
class StateBase
{

public:
    /// @brief TODO: 次の状態候補を全てselectorに追加する
    /// @param parent 今のノードID（次のノードにとって親となる）
    /// @param multi_selectors 次の状態候補を追加するためのselector
    void expand(int parent, MultiSelectors &multi_selectors)
    {
        // 合法手の数だけループ
        {
            Action new_action; // 新しいactionを作成
            Cost new_cost;     // 新しいコストを作成

            // move_forward(new_action); // 自由だが、ここでmove_forwardすると楽
            Cost new_cost;      // move_forward内か、その後にthisから計算すると楽
            bool finished;      // ターン最小化問題で問題を解き終わったか
            int skip_count = 1; // 何ターン後に遷移するか。通常は1
            // move_backward(new_action);// 自由だが、ここでmove_forwardすると楽

            multi_selectors.push(new_action, new_cost, parent, finished, skip_count);
        }
    }

    /// @brief TODO: actionを実行して次の状態に遷移する
    void move_forward(const Action action)
    {
    }

    /// @brief TODO: actionを実行する前の状態に遷移する
    /// @param action 実行したaction
    void move_backward(const Action action)
    {
    }
};

// TODO: Action,Cost,StateBase の定義より後に以下を記述
using BeamSearchUser = BeamSearchNoHash<Action, Cost, StateBase>;
BeamSearchUser beam_search;
using State = StateBase<BeamSearchUser::MultiSelectors>;
// TODO: ここまで

int main()
{
    // 適切な設定を問題ごとに指定
    BeamSearchUser::Config config = {
        /*max_turn*/ 0,
        /*beam_width*/ 0,
        /*nodes_capacity*/ 0,
    };
    State state;
    BeamSearchUser::Node root(Action(), /*cost*/ 0);
    auto output =
        beam_search.beam_search(config, state, root);
    // outputを問題設定に従い標準出力に掃き出す
    return 0;
}

Hashあり版の説明

concept

Hashなし版をベースとし、Hashの制約を追加

非負整数(uint32_tやuint64_tなど)をHashとして使うことを要求

hashを含めたconcept


+   template <typename HashType>
+    concept HashConcept = requires(HashType hash) {
+        { std::is_unsigned_v<HashType> };
+    };

-   template <typename StateType, typename CostType, typename ActionType, typename SelectorType>
-   concept StateNoHashConcept = CostConcept<CostType> &&    
+   template <typename StateType, typename HashType, typename CostType, typename ActionType, typename SelectorType>
+   concept StateConcept = HashConcept<HashType> &&
+                          CostConcept<CostType> &&
                           requires(StateType state, SelectorType selector) {
                               { state.expand(std::declval<int>(), selector) } -> same_as<void>;
                               { state.move_forward(std::declval<ActionType>()) } -> same_as<void>;
                               { state.move_backward(std::declval<ActionType>()) } -> same_as<void>;
                           };
    
-    template <typename Action, CostConcept Cost, template <typename> class State>
-    struct BeamSearchNoHash{};
+    template <HashConcept Hash, typename Action, CostConcept Cost, template <typename> class State>
+    struct BeamSearch

使い方

今回つくったライブラリの推しポイントです。
さきほどのHashなし版で動くコードを作れたら、そこから簡単にHashあり版に移行できます。
以下の部分だけ修正を加えればそのままHashありで重複除去をする処理になります。

StateBase.expandでmulti_selector.pushをする部分にhashを引数に加える
BeamSearchUserの型をBeamSearchに変更する
BeamSearchUser::Configにhash_map_capacityを加える
ルートノードの初期化に初期hashを加える

hashあり版を使うためのhashなし版との差分


// ~ 略 ~
template <typename MultiSelectors>
class StateBase
{
// ~ 略 ~
    void expand(int parent, MultiSelectors &multi_selectors)
    {
        // 合法手の数だけループ
        {
            Action new_action; // 新しいactionを作成
            Cost new_cost;     // 新しいコストを作成

            // move_forward(new_action); // 自由だが、ここでmove_forwardすると楽
+           Hash new_hash;      // move_forward内か、その後にthisから計算すると楽
            Cost new_cost;      // move_forward内か、その後にthisから計算すると楽
            bool finished;      // ターン最小化問題で問題を解き終わったか
            int skip_count = 1; // 何ターン後に遷移するか。通常は1
            // move_backward(new_action);// 自由だが、ここでmove_forwardすると楽

-           multi_selectors.push(new_action, new_cost, parent, finished, skip_count);
+           multi_selectors.push(new_action, new_cost, new_hash, parent, finished, skip_count);
        }
    }
// ~ 略 ~
};

// TODO: Action,Cost,StateBase の定義より後に以下を記述
- using BeamSearchUser = BeamSearchNoHash<Action, Cost, StateBase>;
+ using BeamSearchUser = BeamSearch<Hash, Action, Cost, StateBase>;
BeamSearchUser beam_search;
using State = StateBase<BeamSearchUser::MultiSelectors>;
// TODO: ここまで

int main()
{
    // 適切な設定を問題ごとに指定
    BeamSearchUser::Config config = {
        /*max_turn*/ 0,
        /*beam_width*/ 0,
        /*nodes_capacity*/ 0,
+       /*hash_map_capacity*/ 0 // 要素数の16倍ぐらいは必要らしい
    };
    State state;
-   BeamSearchUser::Node root(Action(), /*cost*/ 0);
+   BeamSearchUser::Node root(Action(), /*cost*/ 0, /*hash*/ 0);
    auto output =
        beam_search.beam_search(config, state, root);
    // outputを問題設定に従い標準出力に掃き出す
    return 0;
}

AHC021での例

skip_beam.cppのhashなし版を使う例

Score: 13565485
当日順位8位相当、赤パフォ相当

skip_beam.cppのhashあり版を使う例

Score: 13598570
当日順位1位より高い

edge_beam.cppのhashなし版を使う例

Score: 13538695
当日順位15位相当、橙パフォ相当

edge_beam.cppのhashあり版を使う例

Score: 13620885

当日順位1位より高い

おわりに

今回、eijirouさんの「ターンが飛ぶビームサーチの実装 (2025/03/16)」をベースに、僕が個人的に使いづらいと感じた部分を修正してビームサーチライブラリをつくりました。
もし同じ点で苦戦した人がいれば、使ってもらえるとうれしいです。

最後にライブラリ置き場を再掲します。
READMEにもうちょい詳しいオススメの使い方など書いてます。