AHC029 備忘録 349位

AHC029お疲れ様でした。
毎回記録付けておきたいのですが、やってる途中は夢中で忘れてしまう……。

問題

概要

• 手札の方針カードを使って、場にあるプロジェクトカードを操作する
• 方針カードには労働力、プロジェクトには残務量があって、方針カードを使うたびに労働力分だけ残務量が減る
• プロジェクトの残務量が0以下になるとプロジェクトを「完了」でき、プロジェクトに定義された報酬を獲得して所持金に加算する
• プロジェクト数は常に一定数に保たれ、完了したり消去された場合は補充される
• 方針カードには価格があり、所持金の範囲で自由に購入できる
• 方針カードは毎ターン終了後にランダムに生成されて場に置かれる
• 場に置かれた方針カードから、毎ターン1枚手札に必ず補充する

方針カードの一覧

カード名	概要
通常労働カード	1プロジェクトに適用可能、労働力分の残務量が減る
全力労働カード	全プロジェクトの残務量を労働力分だけ減らす
キャンセルカード	1プロジェクトに適用可能。指定のプロジェクトを消去する
業務転換カード	全プロジェクトをキャンセルする
増資カード	今後出現するプロジェクトの残務量・報酬、価方針カードの労働力・価値がすべて2倍になる。増資カードの効果は重複する。1000ターンの中で20回までしか使用できない

目的

1000ターン後の所持金を最大化せよ

やったこと

初期考察

そもそも、どうやったら所持金が増えるかがよくわからない。
カードやプロジェクトの生成方法を軽く読んだ感じ、カードやプロジェクトにはコスパの良い悪いがありそうなので、コスパのいいカードでコスパのいいプロジェクトを消化するのが良さそう。
また、増資カードはゲーム内20回までしか使えないという制約から増資カードを使うタイミングがめちゃくちゃ重要OR増資カードをできるだけ早く上限まで使うのが大事そうな感がある。

キャンセルカードや業務転換カードは、コスパの悪いプロジェクトを消すのに使うのだろうが、普通に労働するよりもお得なケースがいまいち見えてこない。まずは労働カードと増資カードの使用を前提にルールベースのロジックを組み立てながら、強いムーブや弱いムーブを探そう。

1日目

サンプルそのままで正の得点を得る

絶対スコア：54,598
ひとまずサンプル通り、価格0労働力1の通常労働カードを使い続けるムーブを提出。これをビジュアライザにかけて観察すると、明らかに強そうなカードが時々出現しているのに取らないのがもったいない。また、コスパのよさげなプロジェクト（残務のわりに報酬が高い）を無視しているのももったいない。

コスパの良いtype1カードを採用して使う& コスパの良いプロジェクトを進める

絶対スコア:90,970
まずは、コスパの良いプロジェクトに注力するよう書き換える。これは単に、$得られる報酬/残務$ が大きいものを優先するだけ。これに加えて、取得するカードや使うカードを、その時点の最良コスパプロジェクトに合わせて変更するようにした。
具体的には、そのカードが今後毎ターン使えると仮定したときに、そのプロジェクトが完了するまでのターン当たりの利益(プロジェクトの報酬-カードの購入価格)を最大化するように方針カードを選ぶ。これにより、その場その場で最もコスパの良いプロジェクトに最もコスパの良いカードを使えるようになった。

上記に全力労働カードも採用するようにする＆増資カードを買える限り買って使う

絶対スコア:528,148
上記に加え、これまで考慮していなかった全力労働カードを加える。全力労働カードはすべてのプロジェクトに効くのでその分を考慮すべきだが、まずは通常労働カードと同様に、最良コスパプロジェクトのみに対して得られる利益を考えて、採用可否を決めるようにした。
また、増資カードについても、買えるなら買う、持っているなら最優先で使うというロジックを追加した。
これで絶対スコアの桁が一つ増えた。相対スコアはあんまり増えてない…。

3日目

終盤だけモンテカルロを入れる

https://atcoder.jp/contests/ahc029/submissions/48834863
絶対スコア：658,008
ここで、

を思い出し、モンテカルロ法を採用する。というのは、今回は1000ターンちょうどの所持金を最大化する必要がある。ただ、ルールベースだと終盤に完了できないプロジェクトに注力してしまったり、使いどころのない高すぎるカードを買ってしまうということがあり、最大所持金は高いが最終所持金は低いということが多々あった。つまり、最終盤の行動を最適化することがスコアにめちゃくちゃ寄与するということ。
全ターンにモンテカルロを入れると計算時間が大変なことになったので、最後100ターンだけモンテカルロ法で先読みするようにした。
思ったよりは伸びなかったが、最終盤のムーブがルールベースよりもいい感じになったので、これをベースに改良することを考える。

考えるが、あんまりうまくいかない。というのは、モンテカルロ法を終盤のみに適用しているため。序盤にも使っているなら、キャンセルカードを使ったり選択肢が生きそうだが、終盤はプロジェクトを入れ替えてもその後に生成されるプロジェクトを完遂できる可能性がそんなに高くなく、嬉しさがない。

実際のカードの出現率から確率の乱数を推定する

絶対スコア: 791838点
ここで発想を転換し、カードの生成確率を実際の確率に近づけられないか考える。カードの生成方法にも記載されている通り、テストケースごとに方針カードの生成確率は異なる。これまではそれを考慮せず、平均的な生成確率に従って方針カードを生成していた。それに代えて、実際のカードの出現履歴を記録しておき、それと平均的な生成確率を混ぜ込んで使うようにした。
これでモンテカルロ法非適用時のスコアを超えられた。

キャンセルカードを使う

https://atcoder.jp/contests/ahc029/submissions/48840103
絶対スコア：515,828
下がった。これもモンテカルロ法を終盤で適用しているため。終盤にキャンセルする理由はあまりないので、やるなら序盤のルールベースで頑張っているとき。。。

スコアが上がらないので終盤モンテカルロ＋乱数推定に戻る

• 試行中変更しない要素を切り出すなどの高速化
• モンテカルロ法適用時、追加で生成されるカードやプロジェクトを固定することで、同条件で複数カードを比較する
  
  絶対スコア: 1,055,828
  初7桁。これまでの挙動を見ていると、あまり最適ではない行動を踏んでいることが多く気になっていた。そこで気づいたことが、モンテカルロ法適用時に、生成されるカードやプロジェクトの条件がそろっていなかったのでは？ということ。たまたま都合よく、コスパの良いプロジェクトやカードを生成できたケースの評価が不当に高まってしまい、最適ルートを選べていなかったようなので、ここを改善。選ぶカードやターゲットにかかわらず、同一のカードやプロジェクトが生成されるようにした。
  これでケースごとの偏りが少なくなり、スコアも大きく改善。
  （とはいえ、カードやプロジェクトの出方の影響が大きすぎるので、単発のスコアはあまりあてにならないのですが）

50ターン後の所持金を最大化するよう800ターン頃からモンテカルロ

絶対スコア: 2,295,649
ラスト100ターンだけをモンテカルロしてたのを、50ターン後までしか見ないかわりに800ターンから実施するようにする。これもかなりスコアが伸びた。これより開始ターンを早めてもあまりスコアは改善しなかった。

改めてキャンセルカードがただで買えるなら買う、コスパの悪いプロジェクトに適用する　を採用

絶対スコア:3,775,973
さらに伸びた。裏で計算量改善のための愚直な努力もして、先読みを100ターンまで伸ばしたのも効いた。
これに加えて、キャンセルカードの生成方法を見るとただで買えるパターンがあるようなので、無料で出ていて手持ちのカードになければ買うというロジックを追加。また、残務量が価値の30倍くらいあるようなコスパの悪いプロジェクトを消すロジックを追加。
キャンセルカードに関するロジックがどれくらい効いているかはよくわからないが、あんまり損するムーブには見えないのでこれも改善に効いていると信じる。

パラメータによって試行回数を調整する

絶対スコア： 3,067,280
N,M,Kが小さければ選択肢が少ない分、1回の試行にかかる時間が短くなるし、逆なら長くなりそう。制限時間を有効活用するためには、いい感じにN,M,Kを使って試行回数を補正するのが有効なはず。
そこで、いくつかの入力パターンで実行時間を計測し、それを元に試行回数を調整するようにした。
絶対スコアは下がったが、手元のテストケースではそこまで差が開くように見えないし、暫定テストのテストケースと相性が悪い説を信じてこれで突っ込む。

結果

暫定321位でフィニッシュ。⇒最終349位でした。正直まだまだ伸びしろがありそうだなと思っていましたが、うまく改善できませんでした。

反省

①
モンテカルロ法が終盤にしか使えなかったのが痛かったです。計算量をもっと劇的に落とす手段とか、10ターンくらいをまとめて10倍速で雑にシミュレーションするとかそういうアプローチがあったんじゃないかなと思っていますが、にっちもさっちもでした。
上位の方のスコアを見てもめちゃくちゃ差があるので、うまく増資カードを使いにいくルートを見つける方法があるんだろうなぁ。あとはルールベースの部分がほとんどを占めているので、ここの改善がもっと頑張れた気がします。
②
また、ランダム性が高いので、改善がほんとに効いているかがよくわからない状況が続きました。手元のテストケースをもっと増やせばいいんだろうけど、計算資源が足りないがち。
③
時折絶対スコアが上がったのに相対スコアが下がるみたいな現象がありました。相対スコアの計算方法を考えると、たまたま特定のテストケースでハマって高い点を取ることで相対スコアが伸びていたのだと思いますが、システムテスト実行時にそれが均されて気にしなくてよくなるのか、それとも特定のケースにはまるようなアプローチが強いのか…。
④
この手のインタラクティブなやつって、どうプロファイリングしたらいいのかわからなくて、計算量が重いポイントがわからないのがつらかったです。ヒューリスティックは計算量目当てでC++を使っているのですが、インタラクティブな時は言語仕様とかをよくわかってるPythonとかを使うほうがいいのかもしれない。C++はまだまだ初心者なので、雰囲気で書いてるコードが多すぎる。

とはいえ、ランダムシミュレーションが込みのヒューリスティックは初めてだったので、楽しかったです。C++もっとわかりて～～。