AHC029 参加記 - eijirouの競プロ参加記

RECRUIT 日本橋ハーフマラソン 2024冬（AtCoder Heuristic Contest 029）お疲れ様でした。

システムテストの得点率が 73.4 % で優勝しました！

問題概要

所持金の最大化を行うカードゲームです。

詳細は公式の問題文を参考にしてください。

atcoder.jp

方針

貪欲法をモンテカルロ法によって改善しました。

コンテスト上位者の中で私の貪欲法の性能は悪かったため、貪欲法についてはあまり参考にならないかもしれません。

貪欲法の準備

貪欲法を説明する前に、貪欲法の説明に必要なものについて述べます。

各ターンの流れ

各ターンの流れについて、問題文では

手札からカードを1枚選んで使う。
必要に応じてプロジェクが補充される。
補充するカードの候補が提示される。
補充するカードを1枚選んで補充する。

の順序で書かれています。

しかし、補充するカードを選んだ直後に手札のカードを使うため、これら2つの処理をまとめて考えることができます。

そこで、各ターンの流れを

補充するカードの候補が提示される。
補充するカードを1枚選んで補充し、手札からカードを1枚選んで使う。
必要に応じてプロジェクトが補充される。

のように捉えることにします。

1ターン目は、手札の1枚目のカードが欠けていて、補充するカードの候補として手札の1枚目のカードだけが提示されていることにすると実装しやすいです。また、問題文における最終ターンでは、補充するカードとして1枚目を選ぶのが最適なので、最後のカードを選ぶ手順は省略して考えることができます。

行動の定義

（補充するカード、使用するカードと対象のプロジェクト）という組を行動と定義します。問題文中の記号で表すと $(r, c, m)$ です。

貪欲法

行動価値関数を定義し、行動価値が最大になる行動を選択します。

直後に取りうる行動を全探索するため、ループ内部の時間計算量を $O(1)$ とすると、全体の計算量は $O(KNM)$ になります。

行動価値関数は、後述する状態価値関数とは直接的な関係がないことに注意してください。（強化学習における行動価値関数とは定義が異なると思います。）

行動価値関数は、以下の項目の変化を評価します。

所持金 $money$
プロジェクト
手札のカード
使用した投資カードの枚数 $L$

単位は所持金に合わせることにします。すなわち、所持金以外の項目の変化をお金に換算します。所持金ベースで考えることで、定量的な考察がしやすくなると思います。

所持金の変化

カードのコスト $p$ と、カードを使うことによって完了するプロジェクトの価値 $v$ を用いて計算することができます。

プロジェクトの残務量を減らす価値

プロジェクトが完了する場合 $(h \leq w)$ 、所持金の変化のみを考えることにします。すなわち、新しいプロジェクトの評価は0とします。

プロジェクトが完了しない場合 $(h \gt w)$ 、 $v w / h$ をベースにして評価しました。減らした残務量の割合に応じてプロジェクトの価値を得られるイメージです。

実際にはお金を稼げないことや、累積和が $v$ よりも大きくなることを踏まえると、 $v w / h$ を下方修正したほうがよさそうです。

また、カード生成方法を見ると、所持金と減らせる残務量が大体同じであることがわかります。そのため、所持金よりも大きい残務量のプロジェクトを完了するには時間がかかることが予想されます。

そこで、 $\max{(0, h - w - money)}$ が大きいほど、 $v w / h$ を下方修正するようにしました。

具体的な修正方法とその高速化

$v w / h$ に以下の値をかけました。

$1.1 / (1 + 0.5 \times (1 + \lfloor \max{(0, h - w - money)} / 2^{L} \rfloor )^{0.4})$

0.4乗の計算が重そうに見えますが、0.4乗する前の値が257以下の自然数であることから、事前計算によって配列アクセスに変更できます。0.4乗以降の計算も事前計算に置き換えることにより、浮動小数点演算の回数を大幅に減らすことができます。

プロジェクトを取りやめる価値

$h - v$ をベースとしました。

ただし、 $h$ が小さいほど、取りやめる価値を下げました。以下の2つの理由があります。

$h$ が小さければすぐに完了できるから。
途中まで進めたプロジェクトを業務転換カードで換えないようにするため。

カードの変化

カードの価値を計算すればよいです。

ゲーム終了時に強いカードを残すのは無駄なので、最後20ターンほどからカードの価値を下げるようにしています。

通常労働カードの価値

$0.9 \times w$ としました。プロジェクトの残務量を0未満にする（overkill と呼ぶことにします）ことがあるため、 $w$ よりも少しだけ小さくしています。

全力労働カードの価値

$0.6 \times M w$ としました。overkill が通常労働よりも多発することや、効率の悪いプロジェクトも進めるため、 $M w$ よりも小さくしています。

キャンセルカードと業務転換カードの価値

$2^{L}$ としました。

増資について

900ターンぐらいまで、増資カードは買えるときに必ず買うようにし、買ったらすぐに使用しました。評価値が無限大と考えることもできます。

実は増資カードが高いときには買わないべきで、増資ストックも検討するべきなのですが、コンテスト中にうまく実装できませんでした。今後暇なときに実装したいです。

増資ストックとは

増資カードを購入し、しばらく使わずに手札に残すことを増資ストックと呼ぶことにします。

増資すると多くの変数が2倍になりますが、所持金は2倍になりません。相対的に所持金が半分になると考えることができます。

所持金が少ないと効率が悪くなりやすいため、所持金が少ない期間は短いほうがよいです。

以上より、所持金が少ないときに増資カードを一気に使いたいというモチベーションが生まれます。

一方で、所持金を一時的でも極端に減らしていいのか、増資ストック中に使える手札のカード枚数を減らしていいのかなど、増資ストックのデメリットに関しては自分の中で結論が出てないです。

（2024/01/08 追記: 増資ストックではなく増資スタックでした。同じアイテムを複数まとめることをスタックというらしいです。）

貪欲法の高速化

モンテカルロ法におけるボトルネックは貪欲法になります。そのため、貪欲法は速ければ速いほどよいです。

処理をまとめる

基本的に可能な行動全てについて行動価値を計算しますが、補充したカードの価値など、いくつかの行動で共通する要素があるので、それらはなるべく1回しか計算しないようにしました。

行動価値関数として実装しないため、実装が汚くなりました。

貪欲法における枝刈り

行動を全探索すると書きましたが、明らかに無駄な探索は枝刈りします。

枝刈りするのは以下のケースです。

下位互換のカードは補充しない。すなわち、補充するカード候補の中に、同じ種類でコスト $p$ が小さくて効能がそれ以上のものがあるようなカードを補充することを禁止する。
手札に存在する効能が同じカードを同一視する。

枝刈りは貪欲法を高速化するだけでなく、モンテカルロ法でプレイアウトを行う行動の候補を選ぶときにも効果的に働きます。

状態評価関数

モンテカルロ法で状態を評価するときに使います。

状態評価値の比較は同じターン同士でしか行われないため、同じターンで評価基準が揃っていればよいものとします。

ゲームが終了している場合、所持金を評価しました。以降、ゲームが終了していない場合について説明します。

基本的には行動価値関数と同じ考え方で状態を評価します。

所持金の評価

所持金が $200 \times 2^{L}$ より大きいときは増資カードを買える可能性があるので所持金に応じて高く評価しました。

カードの評価

行動価値関数とほぼ一緒です。

プロジェクトの評価

$v - h$ をベースとしました。

ただし、キャンセルカードや業務転換カードを保持しているときは $v \lt h$ の場合のペナルティを緩和しました。

増資カード使用回数の評価

$425 \times 2^{L}$ としました。

その他

最後に評価値を 0.95 乗して極端な値の影響を下げました。スコアはあまり変わらなかったと思います。

モンテカルロ法

可能な行動について、貪欲法によるプレイアウトで評価値の期待値を求め、期待値が最大の行動を選択します。

処理の流れは以下の通りです。

行動価値が大きい7つの行動を候補として取得する。
およそ2msec経過するまで以下の処理を繰り返す。
1. プレイアウトに必要な情報を生成する。
2. 各候補について9ターンの貪欲プレイアウトを行う。
3. 一定時間が経過した場合、期待値が最小の候補を削除する。
期待値が最大の候補を選択する。

重要そうな部分について説明します。

シミュレーション回数

より正確な期待値を求めるにはプレイアウトの回数を増やすことが大切です。

そこで、プレイアウト回数を増やす工夫をいくつか行いました。

プレイアウトを行う行動の選択

可能な行動が $O(KNM)$ 通りあり、理想的にはそれら全てについて十分な回数のプレイアウトを行いたいです。

しかし、実際には実行時間が非常に限られているため、可能な行動全てに対してプレイアウトを行うとプレイアウト回数が減ってしまいます。

そこで、行動価値が大きい行動についてのみプレイアウトを行うようにしました。行動価値関数は完璧ではありませんが、上位何個か選べば最良のものが含まれているだろうという感覚です。

また、プレイアウトを行う行動候補を選ぶときに、補充するカードと使用するカードの組が等しいものは1個までとしました。すなわち、候補の中にカードを適用するプロジェクトだけが異なるような行動がないようにしました。おそらく候補の多様性が重要なのだと思います。

データ生成

基本的には問題文と同様の方法でプロジェクトとカードについてのデータを生成します。

プロジェクトの生成には隠しパラメータが使用されていないため、一度生成したプロジェクトを別のターンでも使いまわしました。

一方で、カードの生成には隠しパラメータが使用されているため、今までに出現したカードの統計データをとり、毎ターンその分布にしたがってカードを生成しました。

統計データは各カードの種類について出現した回数を数えるだけですが、出現した回数の初期値は 21, 11, 11, 6, 4 としました。序盤はデータが少ないので無情報の期待値を参考にできるということです。スコアへの寄与は小さいと思います。

プレイアウト

狭義的には最終状態までシミュレーションすることをプレイアウトと言いますが、途中までシミュレーションすることもプレイアウトと呼ぶことにします。

最終状態までシミュレーションした場合、序盤や中盤では非常に長い時間がかかるうえ、ランダム性が大きくなって評価したい行動のよさが計りにくくなります。そこで、シミュレーションを9ターン後まで行い、9ターン後の状態価値を最大化することを目標としました。ただし、9ターン後までにゲームが終了する場合はゲームを終了させ、そのときの評価は所持金になります。

候補の削除

7つの行動候補を段階的に減らし、最終的に2つの候補についてプレイアウトを行うようにしました。一定時間が経過するごとに最も期待値が低い候補を1つ削除します。

最良でなさそうな候補を途中で削除することにより、よさそうな候補のシミュレーション回数を増やすことができます。

感想

全体

モンテカルロ法について、AHCの過去問で何度も練習していて、今回結果を出せて非常に嬉しく思います。

問題文を読み終えた時点で、数ターンのプレイアウトを行うモンテカルロ法が強いことを確信し、自分の得意ジャンルであることから優勝するチャンスだと思いました。

大まかな方針はすぐに決まりましたが、「数ターンのプレイアウト」の「数ターン」は20ターンぐらいだと予想していましたし、モンテカルロ法によって、スコアはせいぜい2倍ぐらいにしかならないだろうと思っていたので、その辺りの感覚はずれていました。（スコアは平均して32倍程度、順位表のスコアは12倍程度でした。）

優勝できたのはよかったですが、感想戦において貪欲法で大きく負けていたことがわかり、貪欲法については反省点が多そうです。貪欲法（と状態評価関数）が基本で、モンテカルロ法を行う場合でも、最終的なスコアは貪欲法に大きく依存すると思っていたのでかなり意外な結果でした。

相対評価システム

自分がコンテストを荒らしている感じがして楽しかったです。

今回の相対評価が気に入らない人がいるみたいなので個人的な意見を少し書きます。

順位スコアはテストケースにおける圧倒的1位の人にとって嬉しくないので基本的にはよくないと思っています。元のスコアが指数的な分布なら、対数をとって絶対スコアか相対スコアだとバランスがいいかもしれないです。指数的な分布でないとき（一様分布など）に対数をとると、僅差になって非ACのペナルティが大きくなるのでよくなさそうです。