CodinGame Fall Challenge 2020 参加記録

2020/11/13〜11/23にCodinGameで開催されたコンテスト、Fall Challenge 2020 に参加しました。

Goldリーグまで進めました。順位は世界209位、日本59位でした。 f:id:nafuka11:20201123223823p:plain

ルール

ツカモさんの記事に詳しく載っています。呪文を唱えて素材を変換し、素材からポーションを作ってお金を稼ぎ、より多くのお金を稼いだプレイヤーが勝つゲームです。

作れるポーションの中でもっとも価値が高いポーションをBREWするようにしました。

BREWできるならする。
BREWできないならCASTする。
- 最短手で作れるポーションを求める。
- 上位の素材を生成する呪文から見て、唱えられる & ポーション製造に必要な素材ならCASTする。
CASTできなかったらREST。

としました。

3手先まで、BREW, CASTをDFSで全探索して、最も評価値の高いコマンドを選ぶようにしました。

再帰関数を使ったDFSからBFSにしたり、高速化する方法をググって実装して、4手先まで読めるようにしました。

repeatableも見て1ターンで複数回呪文を唱えるようにしました。

最初10ターンはLEARN固定。

その後はchokudaiサーチを使って7手先まで読んでコマンドを探索しました。

探索するコマンドはBREW, CAST, RESTのみ。

評価方法は、素材の数とBREWするポーションのprice, tomeIndexから計算。6個目に作るポーションはターンが早いほどボーナスをつけるようにしました。

chokudaiサーチを実装するまではビームサーチにしていて、7手先上位100手を見ていました。どちらのサーチも、実装にあたりツカモさんの記事がとても参考になりました。

初回100ms与えられるので、最初探索をして時間を有効に使うべきのだったかもしれません。
LEARNを探索に含めたバージョンも作ったのですが、あまり強くならず……。その調整にかなり時間を使ってしまったので、思い切って捨てる覚悟が必要だったかもしれません。

以前、CodinGame上で行われた、42の学校間コンテストでは、シミュレートが難しく1ターンの最善手を探索することしかできませんでした。

今回は数手先まで探索できて楽しかったです。DFS, BFS, ビームサーチ, chokudaiサーチといろいろな実装を試せました。

次回参加するときはチーム内5位以上に入りたいです（今回6位）。