CodinGame Fall Challenge 2020 参加記
CodinGameで開催されていた Fall Challenge 2020に参加しました！
Fall Challenge 2020って何？というかたは、こちらの記事を参考にしてください。
要約
- 初めてヒューリスティクス的なコンテスト/コンペに参加しました
- Silverリーグまで行けました 嬉しい～～
- Goldも行ってみたかった / ビームサーチとかをこの機会に学びたかったけど失敗 次も参加したいね
あらすじ
(~11/12)
Twitterでこどげのイベントがそろそろ、みたいな発言をちょくちょく見つける
興味あるけど難しそうだし、自分はパスかな...
(11/13)
Twitterに参加者の所感が出始める
- 実在のボードゲームを題材にしてるっぽい
- なんか絵柄がシュール
まあ... (メールフォルダを開く)
やるか～～～～～～～～～～～～～～～～～～～～～～～～～～～～
Wood League
(11/13)
サイトを開く。Errichitoさんがなんか実況してる動画をみる。実況動画のアドバイスに従い、適当に BREW ${ID}を出力する。
Wood 2 → Wood 1昇格 嬉しい～～～～
以降、最後まで基本戦略は「できるだけ早くBREWをする」で固定です。
さて、コードを書き換えて
何かしらBREW > 何かしらCAST > REST
の順に優先順位をつけて行動させるようにしました。
すると、ポーションを1, 2個作って動作停止して負けるパターンが見受けられました。調べます。
どうやら、
level 0 生成 → level 1に変換 → level 2に変換 → level 3に変換 → level 0 生成 → ....
を無限にやっていたようです。
画面には10個のlevel 3素材を格納したインベントリと動作停止した婆が映っていました。あほくさ 同じ素材は3個まで、みたいな縛りを追加すると良い感じに回りました
Wood 2 → Bronze昇格 嬉しい～～～～
Bronze League
さて、ランダムに呪文を唱えていても当然勝てません そもそも急にルールが難しい...
こういうコンテストでの探索手法とかが全く分からないので、普段の競プロ的アプローチでできる手を取ります。
問題: 現在の状態(インベントリ、呪文、ポーション) から、最も短いターンで何らかのポーションをBREWできるルートを見つける
相手のことは全く考えていませんでした(余裕がない)
あと3ターンでとれるルートを走っていたら次ターンでとられて台無し、という危険性もありますが、しょうがないと割り切り毎ターン計算しなおしています。
この問題は、インベントリの状態ごとにたどりつける最短ターン数を記録しておくDPで解くことができます。
( インベントリの状態 ... [Level 0, Level 1, Level 2, Level 3] = [2, 2, 1, 1] とか [0, 0, 3, 3] とか、そういうこと )
計算量は 状態数(10 ** 4) × 選択可能な呪文の数(せいぜい20とか) × 探索を打ち切るターン数(10ターン以内に無理ならLEARNをするようにしていました) 程度です。
その後、多少のバグ取りをしてアリーナに放出すると、対戦結果がポコポコ出はじめて楽しい！
ですがBronze上位3割くらいにとどまり、う～んという感じに
適当に情報取集をすると、呪文のなかでもアドであるものとそうであるものがあり、初期の呪文はかなり弱いとのこと。
レベルの低い素材から 1, 2, 3, 4点として変換効率考えると、確かに...
ということで、最初の数ターンはLEARNに専念させることにして提出。
したのですが、バトル結果は勝率5割くらいで振るわなそう？うーむ
疲れたのでこの日は諦めることにしました。
1時間ほどYouTubeを見て、寝る前にメールをチェックします。
？？？
Bronze → Silver昇格 嬉しい～～～～～～
Silver League
どうやらビームサーチというもので戦える！ということを聞いていたので、Silverに上がったらすっぱり切り替えようと思っていました。
ですが、Bronzeまでの手法にもまだやれそうなことがあり(一番顕著なのはRepeatableを1回ずつ唱えているところとか)、調整していたところバグの沼に.......
ビームサーチの勉強に使おうと思っていた時間を溶かし、撤退することになりました。
まとめ
ひとまず始めたときはSilverを目標にしていたので、達成できて嬉しいです。
この機会にビームサーチを勉強しよう作戦は失敗してしまったのですが、これは次のイベントまでの宿題に。
今回のコドゲで「やべぇぇ、ビームサーチやchokudaiサーチ勉強しなきゃ！」って思ったそこのあなた！ビーム系アルゴリズムのうってつけのゲーム、HyperSonicをやろう！題材もボンバーマンで、日本人になじみが深いぞ！https://t.co/34FUnr1B3u
— thunder≦4 (@thun_c) 2020年11月23日
元々日本勢が盛り上がっているという話は聞いていたのですが、Twitterでこどげのことをつぶやくと参加者リストに入れてもらったり、実際に参加する側の空気を感じることもできて楽しかったです。
次はGold目指してリベンジしたいですね～～
それでは、ここまでお読みいただきありがとうございました！
