AHC008 でやったこと - クラス設計編

2 週間自分なりに気を使いつつコードを書いたのでここに言語化しておきます。

問題ページはこちら。

人の動きは誰が管理する？

今回の問題のように複数のエージェントを同時に動かして目的を達成する系の問題では、それぞれのエージェントの動きをどのように管理するかで迷います。

例えば、5 人で分担して固定パターンの壁を構築する場合を考えてみましょう。それぞれの人に与えられる目的は、担当のエリア内の壁の構築です。この場合、それぞれの人はそれぞれの目的（どのエリアの壁を構築中なのか）の情報を持っておけば、各人が自律的に行動を決定することができそうです。

では 4 人で協力して 1 体の動物を追い詰める場合はどうでしょう。この場合、4 人で協調して動きを決める必要が出てくるので、各人が自律的に行動を決定するよりかは、その動物を追い詰めたい意志を持つ何かが 4 人に指示を出して操作する方がうまくいきそうな気がします。

今回は協調するような動きが鍵になりそうなので、後者の考えをベースに設計を進めていくことにします。

目的ベースで動きを制御したい

今僕の頭の中には次の 3 フェーズを順に進める戦略が浮かんでいます。

画面端に一本道を作り、その両端に人を全員集め、犬を一網打尽にする。
固定パターンの袋小路を構築する。
人をパトロールさせ、動物が入った袋小路に蓋をする。

これらのロジックを一箇所に記述するとごちゃごちゃしてしまいそうです。なので、フェーズごとのロジックは別のところに移譲して、適宜それらを呼び出してあげるような形にすると、全体の大まかな流れを記述する場所と細かい動きを記述する場所が分かれて嬉しそうな気がしてきます。

で、どうするの

GoF の Command パターンを使うことにします。

それぞれの目的に対し Command オブジェクトを用意します（CaptureDogCommand, BuildFukurokojiCommand 等）。これらは Command クラスの子クラスとして実装します。
Command オブジェクトを生成する際にはその目的にアサインする人のポインタを渡してあげます。Command オブジェクトはこの人たちを制御して目的の達成を目指します。目的によっては void add_human(shared_ptr<Human> human) のようなインターフェースを用意して後から人を追加できるようにします。
Command オブジェクトを生成する際にはゲーム情報（人・動物の位置、設置済みの壁、侵入不可セルの情報等）のポインタを渡してあげます。Command オブジェクトは人を操作した際、このゲーム情報を適宜更新します。
Command オブジェクトは void execute(int current_turn) メソッドを public なメンバ関数として持ちます。これを呼ばれた時、Command オブジェクトはゲーム情報を見つつ、自身の目的を達成するべくアサインされている人を 1 ターン分行動させます。これは Command クラスの仮想関数であり、各子クラスでこのメソッドを実装します。
Command オブジェクトはその目的を達成した時、アサインされていた人のポインタを返却します。これによりこれらの人が他の Command にアサインされることが可能になります。（実際の実装では、オブジェクト自身はメンバ変数である is_completed フラグを立てるにとどめ、外部でこのフラグの監視やポインタの返却をやりました。このせいで何かと public になっていたりしてう〜ん...という感じなのですが、本質ではなかったので妥協してしまいました。）

以下は実装のイメージです。

struct Human {
    int x, y;
    char action;
}

class Command {
public:
    bool is_completed = false;
    vector<shared_ptr<Human>> my_humans;  // アサインされた人
    shared_ptr<Game> game;                // ゲーム情報
    
    Command(shared_ptr<Game> game) : game(game) {}

    virtual void execute(int current_turn) = 0;
};

class SpecificCommand : public Command {
public:
    SpecificCommand(shared_ptr<Human> human, shared_ptr<Game> game) : Command(game) {
        my_humans.push_back(human);
    }

    void execute(int current_turn) override {
        // 目的を達成するべく my_humans の人を操作
        // 目的を達成したら is_completed = true; する
    }
};

このようにすることで、Command は手持ちの人を使って自分の目的を達成することに集中できます。

Command によって管理する人の人数や追加タイミングはまちまちです。例えば、先ほどの戦略のための Command は以下のような実装になりました。

犬を捕まえる Command は全員で協調した動きをする必要があるため、コンストラクタで全員を渡し、1 つの Command で管理します。
固定パターン袋小路を構築する Command は、盤面を 5 つのエリアに分け、コンストラクタでは 1 人の人と担当するエリアの id を渡します。エリアごとに 1 つの Command が発行されることになります。
パトロール&蓋の Command は、同じ動物を複数人で狙ってしまうといったことを防ぐため、パトロール中の人全員を 1 つの Command で管理します。袋小路構築をやっていた人を後から追加でアサインすることもあるため、それ用のインターフェースも用意します。

Command 呼び出し側

Command オブジェクトを生成する側（ここでは Solver と名付けることにします）はこんな感じになります。メンバ変数や各メソッドの詳細は端折っています。

class Solver {
protected:
    // 実行中の Command を格納する配列
    vector<shared_ptr<Command>> commands;

    // Command にアサインされていない人をプールするオブジェクト
    // human_pool.get_nearest(座標) みたいなことをすると座標から一番近い暇な人を貸してもらえたりする
    HumanPool human_pool;

    virtual void create_command(int current_turn) = 0;

public:
    void solve(const vector<Pet>& pets, const vector<Human>& humans) {
        initialize(pets, humans);

        for (int current_turn = 0; current_turn < MAX_TURN; current_turn++) {
            // 状況を見つつ必要に応じて Command を生成し、commands に push する
            // Command に渡す人は human_pool から借りてくる
            create_command(current_turn);

            // commands に格納されているオブジェクトの execute メソッドを叩く
            // 叩いた結果 is_completed フラグが立ったコマンドは commands から取り除き、人を返してもらう
            // 返してもらった人は human_pool に突っ込む
            execute_commands(current_turn);

            // 人オブジェクトを覗いて行動を出力する
            output_human_moves();

            input_pet_moves();
        }
    }
};

これで戦略の大まかな流れは Solver にて Command を生成する形で記述、細かい動きは Command 内で記述することができるようになりました。ハッピー！

Command ベースで行動を制御するので Solver の戦略を決定づけるのは create_command メソッドの中身のみであり、Solver 内の他の処理は戦略に依存しません。そのため、この create_command メソッドを仮想関数とし、子クラスでこれを実装するような形にすれば、入力のパラメータによって戦略を変えたい場合等は使用する Solver クラスを切り替えることで対応できます。僕は最終的に 3 つの Solver を使い分けました。

Solver* solver;
if (num_humans == 10 && num_pets <= 17
    || num_humans == 9 && num_pets <= 12
    || num_humans == 8 && num_pets <= 11) {
    solver = new ShelfSolver2();
} else if (num_humans == 5 && num_pets <= 15 || num_humans >= 6) {
    solver = new ShelfSolver();
} else {
    solver = new RingAvenueSolver();
}

solver->solve(pets, humans);

ソースコード

atcoder.jp

やってみてどうだった？

👍 複数の戦略で共通する処理の記述が楽でした。今回だとゲーム序盤に犬を一網打尽にするフェーズはいろんな戦略で使い回したのですが、それらは各 Solver で CaptureDogCommand を生成してあげるだけで実現できます。
👍 新しい戦略を実装するとなったとき、やるべきタスク（新しい Command の実装 + Solver の create_command メソッドの実装）が明確化かつ分割されていて実装の見通しが立ちやすかったです。
👎 今回は支障はなかったですが、Command による役割の分担がかっちりしすぎていて、途中で役割が変わるような柔軟な戦略を取ろうとすると少し工夫が必要かもと感じました。