Goldリーグでコンテストを終えた FallChallenge2020 ですが、コンテスト後もポツポツと改善を繰り返して無事Legendに到達できたので、そこでやった内容をざっくりまとめました。
TL;DR
CGBenchmarkはいいぞ！pb4さんのポストモーテムはいいぞ！
やったこと
コンテスト中にやっていた内容がこちらです。ざっくり言うと価値重視のビームサーチって感じですね。 gobi-tk.hatenablog.com
参加者各位の振り返りブログ等を参考にしつつ、こちらを追加改修していきました。 変更した時系列順に書いていきます。
ひとまずやったこと
- ビームサーチを深さ重視に
- 高速化も交えつつ、「ビーム幅700の深さ5」から「ビーム幅400の深さ9」に変更した。
- 上位の方のブログを見ている感じ、幅は(自分と比べて)やや狭く、2桁ターン以上読んでる人が結構居たので、そっちに寄せてみました*1。
- マイナーGCをターン開始直後に実行する
ここまでで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 でした。)
