hamray's blog

主に競プロについて書きます

CODINGAME FALL CHALLENGE 2020 参加記

CodinGame FALL CHALLENGE 2020に参加しました。
https://www.codingame.com/contests/fall-challenge-2020

結果は全体267位/7011, 国内67位/320でした。
初めてCodinGameのコンペに参加しましたがゴールドに到達できて嬉しいです。日本人の参加者が多く、良い刺激になりました。

f:id:becnical:20201126022002p:plain
ゴールド到達!

以下にコンペの内容とやったことと反省点を書きます。

コンペの内容とルール

コンテストの内容としては、 ゲームの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だけ重みの総和が変化するように、スペルによって変化量に差があることに気づいたのでこれを状態と評価関数に組み込む。
あと適当にパラメータをガチャガチャしていたが、結果はあまり変わらず撃沈

反省

・改善できそうなアイデアはあったが具体的な実装が浮かばない、実装できなかった。
「相手の手を読んで、ポーションを先取りする」や「前半中盤後半と戦略を変更する」、「探索の細かな高速化」など
・パラメータガチャを信じすぎ/ビームサーチを信じすぎ
特に後半ですが思考が完全にビームサーチや評価関数に偏りすぎて、ほかの本質に気づかないみたいなことになってた(気がする)

全体の感想

初日から生活を崩壊させてガッツリと取り組んで、前半(Gold解放まで)はサクサクと順位を上げることができたのですが、後半は明確に結果が変わるような改善案が浮かばず力不足を感じました。(長期間のコンペの中でなかなか進捗がでないのはなかなか辛かった)
ラソンのモチベが上がったのでAtCoderで行われる日立北大ラボ×北大コンテストにも参加したいです。