スコルの知恵袋

主にプログラミング関係の気になったこと等をまとめたブログ

CODINGAME FALL CHALLENGE 2020 参加記

競プロ CodinGame C++

CodinGame で 2020/11/13 ~ 23 に開催された CODINGAME FALL CHALLENGE 2020 に参加しました。

www.codingame.com

目次

コンテスト概要

f:id:scol:20201124133510p:plain:w600

素材からポーションを作ってルピー（お金）を稼ぐゲームがあって、それを動かす AI を書いて競い合うコンテスト。

ルールなどはこちらのツカモさんの記事を、参照！（丸投げ）

tsukammo.hatenablog.com

結果

f:id:scol:20201124134212p:plain:w400

世界： 33位 / 7011人　日本：6位 / 320人　でした。初参加でこの結果はうれしい！

やるべきこと全部ぶん投げて参加した甲斐がありました！！（論文さん......）

やったこと

ビームサーチ (幅 500 深さ 8) で盤面の評価値と各操作によるボーナスの和を最大化するような操作の探索を行い、見つかった最善手を採用していくという方法を取りました。 探索の方法はコンテスト中に ビームサーチ → chokudai サーチ → ビームサーチ という変化を遂げました。 ビームサーチ / chokudai サーチ の実装は下のツカモさんの記事を参考にしました。ありがとうございます！

qiita.com

盤面の評価値

盤面の評価値は以下のように定義しました。

ルピー

1ルピー = 1000 点

素材

tier-i = 900 × (i + 1) 点 / 個

ポーションの素材とルピーの関係を見ると tier-i 1つから (i + 1) ルピー が生じていることが分かるため、素材の価値はそれから生じるルピーとほぼ同じにすべきだと考えました。

魔法

\mathrm{delta} = [ d_0, d_1, d_2, d_3 ] である非 repeatable 魔法の価値は

\displaystyle{ \mathrm{value} = (40 + a) \sum_{i = 0}^{3} (i + 1) d_i }

で計算し、 repeatable 魔法の価値は m = \max\{(\textrm{消費する素材の個数}), (\textrm{生成する素材の個数})\} として

\displaystyle{ \mathrm{value} = (40 + a) \sum_{i = 0}^{3} (i + 1) d_i \times \left\lceil \frac{10}{m} \right\rceil }

で計算しました。ただし、 a はその魔法が castable なら 10、そうでなければ 0 となるものです。repeatable の倍率が切り上げになっているのは「repeatable、強いだろ」の気持ちが入っているためです（ふつうに切り下げの方が良かったかもしれない）。係数の 40 という値はパラメータガチャで見つけました。

各操作へのボーナス

盤面の評価値に加え、各操作にボーナスを与えることも考えました。各操作のボーナスは次のように決めました。

BREW

BREW へのボーナスは、「近い BREW を優先したい」、「相手の既得ポーション数が大きくなってきたら BREW の優先度を上げたい」という気持ちから次のように決めました。

\displaystyle{ \mathrm{bonus} = \begin{cases} 5000 - 500 \times d & ((\textrm{相手の既得ポーション数}) \le 2) \\ 10000 - 1000 \times d & ((\textrm{相手の既得ポーション数}) > 2) \end{cases} }

d は現在からのターン数です。はじめは相手のポーション数に合わせてもっと細分化してたんですが、そうするよりこっちの方が安定しました。途中で評価関数がガチャガチャ変化するのはあまり良くないのでしょうか？

LEARN

LEARN へのボーナスは「はじめは LEARN を優先したい」、「近い LEARN を若干優先したい」という気持ちから次のように決めました。

\displaystyle{ \mathrm{bonus} = \begin{cases} 100000 - d + 800 \times k & ((\textrm{覚えている魔法数}) \le 7) \\ 100 - d + 800 \times k & ((\textrm{覚えている魔法数}) > 7) \end{cases} }

d は現在からのターン数、 k は tome の index です。100 という数字はゲーム中盤以降で LEARN される回数のバランスをみて決めました。 + 800 \times k には、tax として取られてしまう tier-0 の評価値を補償したいという気持ちが込められています。

CAST, REST

ターンロスとして -400 を与えました。

勝利の確定と負け確の回避

今現在の自分の既得ポーション数が 5 のときは、 相手の次ターンのルピー数としてあり得るものの最大値を求めておいて、それを次のターンで超えられるような手があればそれを確定的に選んで、逆にそれを下回るような手は探索から外すようにしました。

探索の高速化

priority_queue に Node のポインタを乗せる

Visual Studio のパフォーマンスプロファイラを見ると、やはり実行時間の大部分を priority_queue の push/pop が占めていました。 そこで、priority_queue に Node 構造体をそのまま載せるのではなく、Node のポインタを乗せるようにしました。これでだいたい 1.5 倍くらい速くなりました（ほんとはもっと速くなるとおもってたけど......）。

具体的にどのようにしたかというと、このようにしました ↓ (雑)　（もっとこうした方が良いよ！とかありましたら教えていただけると嬉しいです！）

struct Node {
    ActionType initialActionType;
    int initialActionId;
    int score;
    int bonus;
    // etc...

    bool operator<(const Node& r) const noexcept {
        return this->eval() < r.eval();
    }
    int eval() const noexcept {
        // Node の評価値を返す
    }
};

class NodePointer {
private:
    Node* nodePtr = nullptr;

public:
    explicit NodePointer(const Node& node) noexcept {
        nodePtr = new Node(node);
    }
    NodePointer(const NodePointer& x) noexcept {
        nodePtr = new Node(x.get());
    }
    NodePointer(NodePointer&& x) noexcept {
        nodePtr = x.nodePtr;
        x.nodePtr = nullptr;
    }
    ~NodePointer() noexcept {
        if (nodePtr != nullptr) memoryFree();
    }
    int eval() const noexcept {
        return nodePtr->eval();
    }
    Node& get() const noexcept {
        return *nodePtr;
    }
    void memoryFree() noexcept {
        delete nodePtr;
        nodePtr = nullptr;
    }
    NodePointer& operator=(const NodePointer& x) noexcept {
        if (nodePtr != nullptr) memoryFree();
        nodePtr = new Node(x.get());
        return *this;
    }
    NodePointer& operator=(NodePointer&& x) noexcept {
        if (nodePtr != nullptr) memoryFree();
        nodePtr = x.nodePtr;
        x.nodePtr = nullptr;
        return *this;
    }
    bool operator<(const NodePointer& r) const noexcept {
        return this->nodePtr->eval() < r.nodePtr->eval();
    }
};

// ビームサーチ
priority_queue<NodePointer> nexts;
for (int depth = 0; depth < DEPTH_LIM; depth++) {
    priority_queue<NodePointer> nextsTmp;
    for (int i = 0; i < BEAM_WIDTH && !nexts.empty(); i++) {
        nextsTmp.emplace(move(nexts.top()));
        nexts.pop();
    }
    nexts = priority_queue<NodePointer>();

    while (!nextsTmp.empty()) {
        const Node& node = nextsTmp.top().get();
        for (int i = 0; i < n; i++) {
            Node newNode;
            // hogehoge
            nexts.emplace(newNode);
        }
        nextsTmp.pop();
    }
}

QCFium 法

QCFium 法 というのは次のような pragma を書いて、コードからコンパイラオプションを指定するというもの ↓

#pragma GCC optimize("O3", "unroll-loops", "omit-frame-pointer", "inline")

これは劇的で 10 倍くらい高速化されました。

＜QCFium 法を試そうと思ったいきさつ＞

  1. 僕「手元では 12 万ノードも探索するのに向こうのサーバーでは 6000 ノードしか探索せん...... こんなことありえるか？？？」
  2. ラズパイで実行してみる → ラズパイ「8000 ノード、探索しましたよ」→ 僕「は？」
  3. codingame c++ optimization [検索] → CodinGameフォーラム「最適化オプションは指定されていません」→ 僕「は？」
  4. CodinGameフォーラム「QCFium 法をすればいいよ」→ 僕「😃」↓

＜合法？＞

CodinGame の Discord でモデレーターが こう 言ってるんで大丈夫じゃないですかね（たぶん）。

＜お気持ち＞

QCFium 法をしてもちゃんとコマンドラインからコンパイラオプションを設定するより遅いらしいしなんだかなーって感じ。

しかも、Rust はちゃんと最適化指定されてるっぽいんだよなぁ。 下のコードが 50 ms 以内に終わってしまうので（C++ はQCFium 法をしないとまったく間に合わない）。

let mut t = 0i64;
for i in 0..1000000000 {
    t += i;
}
dbg!(t);

試したけどあんまりよくなかったこと

ビームサーチの幅や深さを動的に変化させる

たとえば、自分や相手の既得ポーション数が大きくなるにつれて幅を広く、深さを浅くするといったことを試してみました。 しかし、これをすると安定性がなくなって格上にときどき勝てる一方で格下に度々負けたりするようになり、総合的にはあんまりよくなかったです。 うまくやる方法とかあるんでしょうか。

ビームサーチ / chokudai サーチ の深さを超深くする (40 ターンとか)

よわよわになりました。

ビームサーチ / chokudai サーチ の深さを超浅くする (3 ターンとか)

よわよわになりました。

序盤の LEARN しまくるときだけ深さを深くする

こうするといい感じにデッキが組まれたりするかな～～とか思いましたが、不安定になりました。

相手の方が確実に速く取れるポーションは探索から除外する

これをすると明らかに弱くなりました。多様性が下がるとかそういうのが原因でしょうか？ まぁ確かに相手が取らなかった場合の選択がなくなってしまうのは痛い気がします。

ルピーの評価値をめちゃくちゃ大きくする

「今作れるポーションをあえて作らず、より効率のいい行動をする」とかの賢い行動が減って弱くなりました。

やらなかったこと

  • 相手の邪魔をする
  • 相手の行動を予測する
  • 類似魔法の LEARN を防止する
  • 同一盤面への遷移を防止するなどの探索の効率化
  • モンテカルロ木探索 (MCTS)

感想

頑張って改善して実際にオババが強くなってるところを見られたりするのが超楽しかったです。結果も出たし本当に参加してよかったです。1週間吹っ飛んだけど。