CODINGAME FALL CHALLENGE 2020 参加記
CodinGame FALL CHALLENGE 2020に参加しました。
https://www.codingame.com/contests/fall-challenge-2020
結果は全体267位/7011, 国内67位/320でした。
初めてCodinGameのコンペに参加しましたがゴールドに到達できて嬉しいです。日本人の参加者が多く、良い刺激になりました。
以下にコンペの内容とやったことと反省点を書きます。
コンペの内容とルール
コンテストの内容としては、 ゲームのAIを作成して、 他の参加者と競い合いより上位を目指すみたいな感じです。
ルールは, ツカモさんの記事を参考にしてください。
tsukammo.hatenablog.com
実際に対戦するとこんな感じになります
https://www.codingame.com/replay/506409206
（センチュリー:スパイスロードというボードゲームのルールと類似しているみたいです。）
やったこと
WOOD1 WOOD2
WOOD1, 2ではBREWとCAST、RESTを使うことができます。
とりあえず相手より良い点を取りたいので、コストの最もポーションを決め打ちして貪欲にキャストを行う、みたいのを書いてWOOD2に昇格
目的のポーションを相手に先に取られてしまうと、かなりまずいこと（具体的には直立不動）になります。
WOOD2でも同じようなコードを書いたと思います。
BRONZE
WOOD2ではLEARNのスペルにrepeatableが付いている + 初期スペルに対して強い(具体的には後述)ので最初10ターンはLEARNして、そこから貪欲にキャストをしました。
また、各ルピーを[1, 2, 3, 4]と重み付けして、あるポーションとインベントリにあるルピーとの差をとって、スコア/そのポーションが獲得できるまでの消費ターンから最も大きいものを選ぶようにしました。
このあたりから緑橙黄でスタックする現象に何度も苦しめられていたが具体的な改善策が浮かばず、うんうん言っていた。
SILVER
一手先では限界を感じ、ビームサーチの実装を試みた。マラソン初参加だったので色々なサイトを参考にした。
ナップサック問題でマラソンマッチ入門 - notブログ
競技プログラミングにおけるゲーム木探索の面白さ - Qiita
1つ目のリンクに則って実装した、状態の持ち方や評価関数のつけ方にかなり困ったがとりあえず、
- インベントリにある各ルピーの個数
- 現在使えるスペルのビット集合
- これまでの操作列(CAST, RESTを遷移先の行動として選択)
を状態とし、評価関数として、現状態のルピーとポーションをBREWするために必要なルピーとの差を適当に重み付けしたものを持って、幅20、深さ10のビームサーチをした（ここの幅、深さは適当につけています）
これがかなりのブレイクスルーでrepeatableを利用できていない問題や上記のスタックしてしまう問題をいい感じに解決できた。
これまでSilver下位を彷徨っていたが100位以内に入ることができ、特にプログラムを変更しなくともそのままGoldまで昇格できた。
GOLD
先ほどと同じようにルピーを[1,2,3,4]と重み付けしたとき、[1,0,0,0]->[0,1,0,0]は1だけ重みの総和が変化するように、スペルによって変化量に差があることに気づいたのでこれを状態と評価関数に組み込む。
あと適当にパラメータをｶﾞﾁｬｶﾞﾁｬしていたが、結果はあまり変わらず撃沈
