RECRUIT 日本橋ハーフマラソン 2021〜増刊号〜 「農場王X」 でやったこと

3.979G点で 106位/519人 でした。

最終解法の内容や考察内容とかを書いていこうと思います。

ざっくりの問題説明

二次元グリッド上で収穫機を使って野菜を収穫して、規定の日数の間でできるだけ多くのお金を稼ぐことを目指します。

野菜はそれぞれ所定の期間中セル上に現れ、その期間内に収穫期を野菜と同一の位置に置くことで収穫できます。
野菜ごとに異なる価値が割り当てられており、収穫することで (価値)*(そのマスに連結した収穫機数) のお金を得られます。

プレイヤーは1日に一回、以下のいずれかの操作ができます。

• 収穫機の購入・設置（購入費は (購入台数)^3）
• 収穫機を、他の収穫機と被らない任意の位置に移動
• 何もしない

(詳細なルールは他にもあるので、問題原文を参照してください。)

問題のポイントだと思ってるところ

• スコア計算式的に、収穫機は連結しておくのが基本強いはず*1
• ターン数1,000、盤面サイズ256、野菜数5,000、とコアな要素のサイズが大きく、実行時間の制約が中々厳しい
• 野菜の価値が取り得る値は、最小値は一定で最大値はターン経過に応じて指数的に伸びる。かつ、基数は固定で指数部が一定範囲の数値から一様ランダムに選ばれるため、価値の大きい野菜ほど出現率が低い。

最終提出解法の説明

コードはこちら https://atcoder.jp/contests/rcl-contest-2021-long/submissions/25807010

前半と後半でロジックを変えています。後半部分がメインのつもりです。

前後半共通でやっていること

• 収穫機は連結を保つ
• 野菜は10日先んじて出現させる(収穫はS_iを迎えるまでできない)
• 収穫機の購入は825日目までで、買える場合必ず買う
• 野菜の内、価値がその日にあり得る最大価値のに満たないものは事前に削除しておく
  • 価値の大きい野菜ほど出現率が低いため、野菜数的には個くらい消せる。

0~399日のロジック

ビームサーチをしました。

ビーム幅20で、収穫機連結成分の隣接マス達の内、以下の条件を満たすものを遷移対象ノードとして選択しています。

• 野菜が存在する
• 隣接マスのいずれかに、収穫機が無いかつ野菜が設置されているものがある

遷移に使うコマンドは、購入できる時は購入を選び、そうでない時は移動を選びます。
移動元の収穫機は、連結を崩さずに外せる収穫機の内「向こう10日間で設置予定の野菜が無いマス」にある収穫機達の中からランダムに１つ選んでいます。

評価関数は、「総獲得金額*2 + (現設置マスと重なっている先んじて設置された野菜の価値)*0.5」としました。

400日~ゲーム終了までのロジック

貪欲法です。

収穫機が連結した状態を保ちながら、(価値) / (連結成分との最短距離) が最大の野菜に伸ばす、を繰り返す感じでした。
移動元の収穫機の選び方は、399日までと同様、連結を崩さずに外せる収穫機の内「向こう10日間で設置予定の野菜が無いマス」にある収穫機達の中からランダムに１つ選ぶ、としています。

なぜこのようにしたか

元々は、前半戦に使用してるビームサーチを全ターンで使用していたのですが、スコアが伸びず*3、ビーム幅も4しか出せずで困っていました。
ただ、ローカルでビーム幅を100まで広げる*4と 1.75倍近いスコアを出せていたので、ビジュアライザを見ながらここの違いが何によって生じているのかを考えて、中距離にある価値が大きい野菜を拾えていないところが不味そうと当たりをつけました*5。
その考察が良さそうかを調べるために、とりあえずで (価値) / (連結成分との最短距離) が最大の野菜に伸ばす、という雑な貪欲を試してみたのですが、これが思いのほか上手くいったのでそのまま後半戦のロジックとして採用しました。

前半戦部分は、野菜の最大価値と最小価値との差が小さいので遠くの野菜を取りに行くメリットはあまり無さそうに感じたので、引き続きビームサーチ解を使用しました。
実際入力50ケースで試した平均値を比べてみると、こちらの方がスコアが若干良かったです。

問題に対する所感

今回はアプローチの選択肢が多いように感じて、その辺りが楽しくもあり難しくもありって感じでした。
ゲームモデルはどう作るのが良いんでしょうね。特に野菜の持ち方が時系列の問題とかも絡んで来て悩みどころでした。

焼きなましは今回どうなんでしょうね。取る野菜とその順番 とかでなんとかならないもんかな、とかを考えたりもしたんですが自分は詰め切れずでした。上位に焼きなまし解があったら見てみたいな。

その他余談

ビームサーチ解を追ってた時に、今回初めてプロファイラ(cargo-profiler)を導入してみました。Macで使うには一準備必要だったので、この辺も簡単に記事にまとめてみたいなとか思ってます。*6

感想

当たり方針を掴めたのが終了2.5時間前とかだったので、そこから詰める時間が取れずに終わってしまったのは残念でした。掴んだ方針を元に、例えば「価値が高めの野菜への連結」を遷移にする、とかでビームサーチのパターンを色々試してみたかったんですが・・。

とはいえ一方で、諦めずに検証を繰り返して当たり解法に辿り着けたのは、達成感と成長を感じられて嬉しかったです。長期AHCの中で過去最高順位取れましたし。

*1:超序盤だけは除く

*2:収穫機の購入費を含めた金額

*3:100M点前後。最終スコアは200M点弱

*4:問題制約の実行時間には全然間に合わないですが

*5:後半戦は野菜の価値の差が大きく、かつ高価値の野菜は出現率が低いため、そこの取りこぼしは影響が大きいはず。とかの考察もありました。

*6:ビームサーチ自体は最終的にあんま使わなかったんですけどね。

RECRUIT 日本橋ハーフマラソン 2021 でやったこと

例年通り、４時間で２問を解いて各問題の順位の積の小ささを競う方式で、
A問題で87位、B問題で62位を取って、総合順位は 73位 / 478人(?) でした。

それぞれの問題でやったことと、軽い所感を書いていきます。

A問題

A - 魔法使いXの戦い

300個の数値をmod 10⁸ の世界で互いに足し合わせあって、各数値をできるだけ0に近づけるって感じの問題でした。

途中の操作内容を変更すると、それ以降の操作内容ががっつり影響受けてしまう(はずな)ので、山登り系はやりづらいなあとか、
途中状態の良い感じの評価関数が思いつかないから、ビームサーチ系もやりづらいなあとかを考えてました。

結局よく分からなかった、かつなんとかなりそうなサイズ制約だったので、
とりあえず範囲の上限を設けた全探索投げてみて、悪くなかったのでそのまま採用する感じの流れでした。
内容の詳細は次節です。

解法

先頭の数値から順に、以下の操作を行う。

1. 深さ２までの手を全探索して、対象の数値を最も小さくできる手順を見つける。
2. 1 で求めた手順を適用する。

input_0.txt のビジュアライズ結果が以下。選択肢が減ってしまう後半の数値が当然やや大きくなってしまっているものの、 全体的にはパッと見結構良さそうだったので、これを採用しました。

探索範囲は 300 * 300^2 = 2.7e8 と結構大きめで、Rustで書いて1,700ms弱でした。

コンテスト後のTLを見ての感想

• スコア関数が、A_i が 0 に近づくほど1の差のスコアへの影響が大きくなるように設計されていることを、コンテスト後に把握しました。
  • スコア関数読み解くの大事だよなあと分かってはいるものの、コンテスト時間短いのもあって中々悩ましいですね。
  • 実は解法のビジュアライズ結果も、パッと見ほどは良くもないのかなあとか。
• 工夫すると深さ3まで探索できる、みたいな話をTLで見かけた気がするので、あとでちゃんと探したい。

B問題

B - マッサージチェア2021

40x40 の二次元グリッド上のそれぞれのセルに、性能1~30のチェアが置かれていて、パワーを割り当てたチェアから (性能) * (パワー) のスコアを獲得することができます。
チェアは割り当てられたパワー分のマンハッタン距離内のセルを占有するので、パワーを割り当てるチェアが他のチェアの占有領域に入らないように気をつけながら、できるだけ大きいスコアを獲りましょう。
って感じの問題でした。

取り組んだ流れ

まず、貪欲と焼きなましをそれぞれ試してみました。

貪欲は、
性能が大きい椅子から順に、最大4までパワーを上げられるだけ上げるって方針で、18.0万点でした。

焼きなましは、
性能15以上の椅子を対象に、どれか１つをランダムに選んでパワーを1上げるか下げるかするって感じの遷移をして、17.7万点でした。

単に性能が大きいものを優先してくだけでも焼きなましに僅かに勝てていることから、その方針で十分悪くないスコアが取れそうに感じたので、
時間の都合とかも鑑みて貪欲の方を伸ばす方向に決めました。最終的な解法は次節です。

解法

以下の手順を行うことで、性能が高い椅子を優先して拡げようとする意図を表現しました。

1. 基準値 b と、基準値の減少値 x を設ける。
2. b の初期値を 30-x とする。
3. 性能がbポイント以上の椅子の内、できるもの全てのパワーを１上げる。
4. b の値を x だけ減じる。
5. 2~4 を操作対象の椅子が無くなるまで繰り返す。

上記手順を、x の値が 1~7 のパターンでそれぞれ試して、最もスコアが良いものを選びました。
これが19.8万点でした。

感想

日本橋ハーフマラソンは例年こけているイメージだったんですが*1、今年は２桁順位に入れてよかったです。AHCでハーフマラソン慣れしたのが大きいのかもしれません。

今年は解説動画も有って、復習がしやすくてありがたいです。生で見てたんですが、結構ついていけてなかったので、改めて見直してみようと思っています。

*1:去年の順位を確認したら356位でした..

AtCoder Heuristic Contest 005 ~Patrolling~ でやったこと

18,424,648点で 77位/561人 でした。

最終提出はこちら Submission #24829278 - AtCoder Heuristic Contest 005

入力例１のビジュアライズ結果がこんな感じ。

最終提出の内容

1. 交点を列挙
2. 交点の内、訪れなくても別の交点でカバーできるものを全削除。削除対象の選び方はテキトー。
3. 2で残った交点をノードとして、TSPを焼きなましで解く

時間があればやりたかったこと

削除する交点の選び方、で多点スタート

所感

これまでのAHC短期マラソンより大筋の方針が見えやすい回だったように感じました。交点の一部だけ抑えればいいのだから、あとはそこをどれだけ短く巡るかだけって感じで。
TL眺めてた感じでも、大筋の方針は同様で、使う交点の選び方で差がついていたように感じました*1。

一方で実装は、コンテスト時間４時間がなかなかに厳しく感じました。

• 交点列挙・削除
• 交点間にエッジを張る
• TSP

あたりのまずまず重い実装を、時間内に仕上げなければならないのは中々キツかったように感じます*2。

*1:まだしっかり読んだわけでは無いので勘違いかもしれないですが

*2:実際バグり散らかして、完成したのが終了１分前とかでした（）

AtCoder Heuristic Contest 004 ~Alien's Genome Assembly~ でやったこと

5,356,477,323点で 114位/622人 でした。

最終提出はこちら
Submission #23750881 - AtCoder Heuristic Contest 004

最終解法

1. 自身が完全に含まれる文字列があれば、そのうち最も短いものに合成。
2. 文字列が短い順に、前後端が最も長く重複する文字列と合成していく。ただし、最長ケースが一定値を超えない場合は合成自体しない。
3. 1, 2 で残った文字列を、合成された個数が多い順に横向きに敷き詰めていく。
4. 空きスペースを集めるように縦方向に文字列を並べ替える
5. 3の余りの文字列の内、合成された個数が多い順に、4で作った空きスペースに縦向きに置けるだけ置く。

という流れを、2に出てくる一定値を変動させて複数パターン試して、最も点数が高かったものを選んだ。

思ったことを雑多に

なだらかな近傍が作れる気がしなかったので、山登り系のアプローチは早い段階で切って、大体ずっと貪欲解法を模索していました。*1
文字列合成部分とか、賢いアルゴリズムがありそうだよなあとか思いつつ、貪欲でごまかしごまかし進めていました。

4時間経過したあたりで、思いついた実装できそうなことは一通り試し終わり、残りはほとんど座っているだけになってしまっていました。
実行時間ががっつり余っていたので、なんか上手いこと使いみちを考えられるとよかったんだけどなあとかを思ったり。

こっからどう伸ばしたらいいのかてんで見当がついていないので、上位陣の解法を見て勉強して行きたいなと思います。

*1:TL見てたら、上位解法に焼きなまし系の解法がポツポツあるように感じたので、気になっています。

AtCoder Heuristic Contest 002 ~Walking on Tiles~ でやったこと

atcoder.jp

4,564,046点 の 76位 でした。
サンプル入力のビジュアライズ結果はこんな感じ。

解法と考察過程について書いていこうと思います。

最終解法

• いかに途中で詰まらせずにフィールドを全体的に周るか
• スタート地点が不定であることの実装負荷をいかに減らすか

の対処を重視して、下図のような、全体を10x10のブロックで25分割し*1、内24ブロックを使った巡回路*2を作り、そこに沿って経路を構築していく方針を取りました。
現在地点のブロック内のみの移動を許し*3、巡回路上の次のブロックに到達したらゴールって感じです。

各ブロック内の移動経路は、獲得スコアを評価関数とする幅1,200のビームサーチでもとめました。

また、細かい部分の工夫で、

• 巡回路に含まれていない右下の1ブロックへ、その１つ上か左のブロックを通過するときに侵入を許す
• 既に通過済みのブロックへの侵入を許す

とかもしました。

提出コードはこちらです Submission #22074771 - AtCoder Heuristic Contest 002

考察過程

0:00 問題文を読む

問題文を読んでみてなんとなく、

• 割とありそうな問題っぽい気もするものの、類似事例がパッと思い浮かばないなあ
• 良い感じの貪欲が思い浮かばないなあ

みたいなことを考えてた気がします。

(雑に書ける)貪欲が思い浮かばない時は、焼きなまし系かビームサーチのどちらかに持ち込めないかをとりあえず考えてみることにしてるので、ひとまずそれをしました。
焼きなましは全然方針浮かばずで、ビームサーチはまあできるだろうけど評価関数どうすべきだろ、って感じの考察状況でした。

0:30 とりあえず提出してみる

空文字列を出力するコードを提出。正の点数を得る。

1:20 ランダムウォークを試す

入出力や問題特化の基本操作を用意する目的も兼ねて、ランダムウォークするコードを実装した。
14万点で下位30%くらいだった記憶。既に時間の4分の1が経過してるのにまだこの状況かと焦っていた*4。

ビジュアライザをこのタイミングで初めて試した。コンテスト時間あんま無いことを鑑みて、さっと使えそうなウェブ版がだけを触ってローカル版はひとまず放置することにした*5。
ビジュアライズ結果を見ると、まあやはりというかスタートしてすぐのところで進行経路が塞がって動けなくなっていた。

1:50 雑なビームサーチを試す

あんまり方針が浮かばないので、とりあえず雑なビームサーチだと何が起きるのかを試しに見ることにした。獲得スコアを評価関数とするビームサーチ解を提出。
223万点。トップ層の半分弱くらいのスコアで、順位が半分よりちょい上とかだった記憶。

ビジュアライザを見てみると、上３分の1くらいのエリアしか移動できずに行き詰まって終了していることが分かった。
ここをどうにかしないと話が始まらないなってのと、一方で、この埋まり具合でこのスコアなら、雑にでも全面埋められればそれだけで結構良い順位行けそうだなという気持ちになった。

3:00 盤面を100分割して巡回路を作る方針を考察し、試す

上のビームサーチ結果の考察を受けて、どうやったら途中で詰まらずに盤面を全体的に歩けるかを考えていた。

ビームサーチの延長でやるなら、評価関数にその要素を織り込むになると思うが、何を基準にすべきだろうか？周辺の広さみたいなものを加味する評価関数とか書けると良さそうか？でもあんまり実装イメージ湧かないな。
ルールベースでやるのはどうだろうか？始点が固定じゃないのつらいな。
巡回路作れば、始点がどこでも同様に扱えるので楽そう。盤面を大まかに区切って、区切られたブロック単位では巡回路を固定で用意することにしよう。

って感じの思考を経て、盤面を5x5の100ブロックに分けて、ブロック粒度での巡回路を用意する方針を試すことに決めた。
ブロック内の経路選択は、１つ前のコードを使い回すのが楽そうだったので、先ほどのビームサーチをブロック内の移動のみを許し次のブロックに到達したらゴールとする形に書き換えて使った。

しかし提出してみたところ、68万点と大きくスコアが落ちてしまった。
ビジュアライザを見ると、ブロックが小さすぎるために移動経路を確保しきれず詰まってしまっているように見えた。

3:10 盤面を25分割して巡回路を作る方針を試す

前の結果を受けて、前より大きい10x10のブロックで盤面を25分割する方針を試すことにした。
ブロック数が奇数x奇数になるので、巡回路で全ブロック使えなくなっちゃう*6の嫌だなあとかを思ったりはしたけど、まあしょうがない。

当たり方針かが分からなかったので、とりあえず手を抜いた実装で提出してみることにした。
具体的には、右端の下から３つのブロックは巡回路から外して、それ以外の計22ブロックのみで巡回路を構成する実装とした*7。
383万点で200位くらいまで上がった記憶。

スコア・順位的に方針悪くないなって気持ちになったのと、残り時間がもうあんまり無かったので、大筋の方針はこれで決めにして細部を詰めていくことにした。

3:40 明らかな問題点を潰す

最後に訪れるブロックの移動経路が出力に含まれない実装になっていたのを修正。
390万点。

巡回路が22ブロックしか使ってなかったのを24ブロックに増やす。一番右下のブロックだけが使われていない形に。
430万点。この時点で100位くらいだった記憶。喜ぶ。

一番右下のブロックを、隣接するブロックを周っている時に侵入できるようにする。
456万点(最終スコア)。70位くらいになる。

4:00 短時間でできる改善を試みる

• ビーム幅の調整
• 通過済みのブロックへの侵入を許す

を試したりしたけど、スコア伸びずでそのままコンテスト終了した。

所感

76位の黄色パフォが取れた。大満足。

解法は割と普通のことしかしてないなあって感覚ではあったりします。やっぱり４時間は短いので、大枠の方針を外さず、早くバグらせずに実装しきることの比重が大きいのかなって気持ちになりました。ハーフマラソンはやっぱり１週間マラソンとかとは別ゲーに感じますね。
今回は割と、小さく試してその結果を元に方針決めて対処って流れが上手く回せてたかなって実感があって、この辺が結果にいい感じに繋がってくれたかなとかを思ってたりします。

あとは、コンテスト後にTLを眺めてたらちょこちょこ焼きなまし解を見かけて気になってたりします*8。近傍どうするんだろう。

終わりに

やっぱりマラソンは楽しいですね。このクオリティーのコンテストが毎月開催されるの本当にありがたい限りです。

*1:緑線部分

*2:赤線部分

*3:正確には、章末に書いた通りもう一工夫加えています。

*4:コンテスト後の今考えてみても、ここまでで 1:20 も掛かっちゃってるのよろしくない気がする。

*5:結局、終始ウェブ版でサンプル入力のみを試す形でした。

*6:はず

*7:5x5の時の実装と同じような分岐でいけるように、とかの感じ

*8:自分は真っ先に切った方針なので特に

AtCoder Heuristic Contest 001 ~AtCoder Ad~ でやったこと

AtCoder Heuristic Contest 001 - AtCoder

プレテスト時点で 48,139,425,583点 の 237位 でした。
やったことをざっと書きます。

解法

概説

1. 面積１で全広告を希望位置に設置後、希望サイズ以上になるまで広げる形で初期化
2. スコアを基準に焼きなまし。近傍は１広告を四方いずれかに１伸ばす

で、0000.txt の結果が下画像のような感じ。

out/0000.txt

提出コードはこちら https://atcoder.jp/contests/ahc001/submissions/20923126

初期化

まず面積１で全広告を希望位置に設置し、
その後、四方を順に選択し、希望サイズに達していない広告達を他広告にぶつからずに１伸ばせるなら伸ばす、
を対象広告がなくなるまでやりました。

初期化の時点で89G点くらいになります。

焼きなまし

スコア変化をそのまま判定基準に使いました。温度変化は 1e-3 ~ 5e-6。

近傍は、

• 対象広告
• 方向(四方)
• 伸ばすか縮めるか

をランダムに選び、その操作を長さ１だけ実行、としました。
伸ばす際に他の広告にぶつかるなら、その分ぶつかった広告を縮めます。

振り返り

考察過程

割と序盤に考えた方針を高速化したものが最終提出になる形だった。
１広告0.96点くらいに収束することは調査済みだったので、当然ここに着地するよなという感じ。
局所を抜けられてなさそうな感覚はとても有ったのだけど、打開策が思い浮かばなかった。

考察がここより進まなかった原因として、スコア計算式を勘違いしていた(希望面積に近いほど、面積1差のスコアへの影響が大きいと思っていたけど逆だった。コンテスト後に知った)ことが大きかった気がする。
問題文はきちんと読み込むべきってのと、出力結果や上位のスコアに違和感は感じていたので、その辺の感覚に沿って精査すべきであった。。

もう一個考察が進まなかった大きい要因として、ビジュアライザーとか作らず(れず)、近傍を感覚で考えるだけになっていた、とかがある気がした(を、コンテスト後のTLでビジュアライザー自作例を見て思った)。
次回までには対策しておきたい所。

他の方の解法を見て

• 上述した通り、ビジュアライザーは要るよなって思った。
• 広告を壊して作り直す近傍を見かけてなるほどなと思った。局所抜けるには確かにそれくらいのことが要りそうに感じる。
• スライド移動が、比較的簡単に実装できそうかつ有効そうなものに感じた。これはコンテスト中に思いつきたかったなあという気持ちに。

とかをTLをざっと見て思った。まだブックマークしただけであんまり追えていないので、これからゆっくり見ていきたいお気持ち。

Codingame Fall Challnege 2020で、コンテスト後にLegend昇格するためにやったこと

Goldリーグでコンテストを終えた FallChallenge2020 ですが、コンテスト後もポツポツと改善を繰り返して無事Legendに到達できたので、そこでやった内容をざっくりまとめました。

TL;DR

CGBenchmarkはいいぞ！pb4さんのポストモーテムはいいぞ！

やったこと

コンテスト中にやっていた内容がこちらです。ざっくり言うと価値重視のビームサーチって感じですね。
gobi-tk.hatenablog.com

参加者各位の振り返りブログ等を参考にしつつ、こちらを追加改修していきました。
変更した時系列順に書いていきます。

ひとまずやったこと

• ビームサーチを深さ重視に
  • 高速化も交えつつ、「ビーム幅700の深さ5」から「ビーム幅400の深さ9」に変更した。
  • 上位の方のブログを見ている感じ、幅は(自分と比べて)やや狭く、2桁ターン以上読んでる人が結構居たので、そっちに寄せてみました*1。
• マイナーGCをターン開始直後に実行する
  • TLで話題になっていたやつ（C#勢が特に(?)）。「謎タイムアウトの原因はGC」を真と仮定して、ターンの後半にGCが実行されることを避ける目的で行いました。
    • あんまり効果があるのか分かってないのですが、タイムアウト頻度は減ったようには感じました。雑に数えた感じですが、1/20戦毎くらいから 1/40戦毎くらいに変わった気がします。
    • そもそもそれとは別に、コンテスト後はコンテスト中に比べて安定していたような気も？

ここまでで55位でした（コンテスト終了時は103位）。

CGBenchmark 導入

CGBenchmarkは、CodinGame 専用のベンチマークツールで、
任意の対戦相手(複数人選択も可)と任意の回数戦わせて、勝率を計測することができます。

ValGrowthさんのコンテスト後放送
twitcasting.tv の終盤で紹介されたもので、今回早速使ってみました。最高でした。

導入前は提出結果順位を元に強くなったかどうかを判断していたのですが、提出毎になかなかブレがあって信頼性に欠けていました。この問題がかなり軽減したと思います。
他にも、特定の提出に固定できる*2という利点もあって、他人の提出状況に影響を受けずに済みます。
一方で欠点として、計測にある程度時間が掛かる、とかがあったりします。具体的には、1対戦毎に20秒の間隔を空ける必要があります*3（メリットに比べたら些細な気はしますが）。

私は、Goldの上位*4プレイヤー2名と計100戦するように設定して使いました*5。
本当はボスも対象に混ぜたかったのですが、当初はボスの設定の仕方が分かってなかった*6のでこうしました。*7

上記設定でこの時点の勝率を計測したら、36%でした。
このあとの変更も、この設定で計測しています。

pb4さんのポストモーテムを参考に実装

この辺りでpb4さんのポストモーテムを読んだのですが、改善案をローカルアリーナを使用してELO score換算で計測してくれており、どの方針がどの程度の効果があったかの評価値が分かるように書かれていて、とても参考になりました。

この記事の中から、簡単に実装できそうな部分を拾って織り込んでいきました。

先頭呪文だけLEARN

Systematically LEARN the first spell available (+30 ELO)

とあるように、愚直LEARNがそもそも結構強いっぽいので、よしなに選ぼうとしていたのを辞めました。

計測してみたら勝率が36% => 50% と大幅に上がりました()。下手な工夫ならしない方が良かったっぽいですね。。コンテストの終盤にここの改造に結構なコストを割いていたので、ややつらさを感じました。
提出も合わせて試していて、55位 => 23位でした。

ポーション生成ボーナスを2倍に

pb4さんの基本の評価関数 tier0 + 2*tier1 + 3*tier2 + 4*tier3 + 1.5*potionsScore に対して、私の評価関数のポーションに対する加点は ポーション取得数 * 2.0 と小さかったので、倍の4.0にしました。
計測勝率: 50% => 52%

相手に取られそうなポーションを消す

• a 10ms search is run for the opponent:
  
  • Potions are marked as unvailable in the search for my move once I believe the opponent will have taken them (+5 ELO)
    

を見て、この簡易実装として「即時で取られるポーションの内、最前にあるものを探索1ターン目の終わりに消す」をしました。
計測勝率: 52% => 58%

これを提出したら15位くらいになりました。Gold上位に安定して勝ち越せるだろうこと、は計測結果から分かっていたので、そのまま放置しました。
半日後に3位になり、その翌日に昇格してました ✌️

終わりに

コンテスト時の無念を晴らせてよかったです。
真っ当な計測ができるようになったのは、やはり開発していく上で大きいですね。

その後、CGBenchでボスを指定する方法を見つけたので*8、Goldボスと100戦した勝率を計測してみたら36%でした。ボスに勝つことが目的では無いのでまあ多少は（）

*1:そもそも探索可能ノード数がかなり負けてる、とかもあったのですがまあそれはそれ。

*2:対戦相手はagentIdで指定するのですが、これはプレイヤー毎ではなく提出毎に割り当てられます。

*3:CodinGame のレートリミットの都合っぽいです。

*4:20位以内くらい

*5:本当はもっと試行回数を増やすべきだと思うんですが、計測時間との兼ね合いでこのくらいに抑えてます。

*6:想定用法がCG statsからagentIdを拾ってくる なんですが、CG stats にはボスは表示されない。

*7:後に方法が分かったので、記事の最後の方で触れてます

*8:WebIDE画面で対戦相手にボスをつけたり外したりしてたら、レスポンスからagentIdを拾えました(ちなみに agentId=3307377 でした。)