ゲーム概要

tsukammo さんが日本語に訳した記事を書いてくださっています。感謝！

tsukammo.hatenablog.com

解法

探索

15 ターンの枝刈り BFS をやりました。CAST のセットは手持ちのもののみで、探索途中での LEARN は考えません。

具体的には、下記の DP テーブルで配る DP っぽいことをしてあげます。全部なめると時間が足りないので、配られたノードを queue に入れていくイメージです。配り先のノードが既に探索済みであった場合、queue には入れません。

struct Node {
    int brewBits;        // 各ポーションが作成済みか否かを示すビット列
    long long castBits;  // 各 CAST が使用済みか否かを示すビット列
    int inv[4];          // インベントリ内の素材数
    int step;            // そのノードに辿り着いた最短ターン数
    double score;        // ノードの暫定スコア
    // ... その他、経路復元用の情報
}

Node memo[1<<5][2][11][11][11][11];
//       [1<<5] -> brewBits
//             [2] -> REST した直後か否か
//                [11][11][11][11] -> inv[0]~[3]

ポイントは DP テーブル上では "各 CAST が使用済みか否か" を "REST した直後か否か" に圧縮しているところです。これにより良い感じに枝刈りすることができました。

一応各ターン数ごとに探索するノード数は多くとも 1800 程度になって時間的には問題ないのですが、無駄な処理を省いて他のことに時間を回したいので、各ターン数ごとに次へ配っていくノード最大数はスコアの大きいものから 800 に制限してあげました。これで 1 回の探索が 10ms 程度で終わります。

各ノードのスコアは (1 × min(3, Tier0)) + (2 × min(3, Tier1)) + (3 × min(3, Tier2)) + (4 × min(3, Tier3)) + Brewボーナス、Brew ボーナスはそこまでに Brew した各ポーションについて price × (2.0 - 0.05 × Brewしたターン数) の和です。ただし、Brew したターンに Tier によるスコアが 5 未満となった場合、スコアに大きめのペナルティを与えます。

また、各ポーションについて敵が最短何ターンで BREW できるかを事前に計算しておき、「ポーションの price が大きい」かつ「敵の BREW までの最短手数が 2 以下」かつ「現在の探索ターン数がその最短手数より大きい」ならそのポーションは BREW できないようにしました。

探索の深さは 15 ターンで、時間的にはもっと伸ばすこともできたのですが、あまり先を見すぎても逆効果だったようなのでこのターン数に落ち着きました。

LEARN について

上記の探索を 1 回行って時間が余っている場合、LEARN を行うことを考えます。

具体的には、LEARN を 1 つ行って呪文を一時的に増やした後、上記の探索を深さ 14 ターンで行います。その結果が元の探索のものよりも良くなった場合、実際に LEARN を出力します。

また、ゲーム開始後手持ちの呪文数が 10 に満たない場合は強制的に index=0 の LEARN を実行します。

ボツ案

ゲーム開始後の LEARN 戦略各種。どれを取っても思考停止 index=0 連打を超えられませんでした…。Tier0 が溜まる恩恵が大きい？
敵が最短あと何ターンでこちらのスコアを超えつつポーション 6 つ作り終えるかを事前に調べて、自分の探索をそのターン数で打ち切るアイデア。試してみましたが実際は敵がその最短手でゲームを終わらせるとも限らず、こちらの攻撃力が下がったのでやめました。