CodinGame Fall Challenge 2020に参加しました

結果

世界113位 日本33位でした。
レジェンドに行けなくてとても悲しいです。
f:id:qlethon:20201123191527p:plain

学校別では世界6位 日本5位でした
f:id:qlethon:20201123210337p:plain

バグがやばかったり何も分からない時期が続いたりして終始HELP!って言ってた

やったこと

  • 最初の8ターンは一番下の呪文を取る
  • 10手読みのchokudai search
    • そのターンの評価 = 今までに作ったポーションの評価 + 0.9 * 現時点でのインベントリの評価
    • ポーションの評価: そのまま
    • インベントリの評価: tier 0-3に1-4を割り当て、その和
    • 盤面の重複はZobrist Hashで弾く
  • 探索に含めているもの
    • ポーション作成
    • 呪文キャスト
    • 下から4つまでのLEARN
    • REST
  • 終盤は相手の手をchokudai searchで4手読む(10ms)
    • 条件は自分か相手の作ったポーションが5個になったら
    • 各ターンの相手のスコアのmaxを記録して、自分がゲームを終わらせるときにbrewによって到達するスコアがmaxを超えてたらbrewするみたいなことをした
    • 相手がゲームを終わらせられるターンにポーションを作れるなら作って一番スコアが高い状態にする
  • 最終日まではdfsで4ターン全探索だった(これでも全体100位代だった)

試したけど採用しなかったこと

  • 最初に呪文取るフェーズを探索に組み込む
    • ターンごとに線形で減衰するボーナスをかける
    • まだ貼ってない辺(e.g. tier 0 -> tier 1)にボーナスをかける
    • 貼れる辺の組み合わせはいろいろ試した
    • tier 0, 1, 2からtierが上がる方向の辺とtier 3からtier 0, 1, 2にボーナスをかけるとか
    • chokudai searchにしてからは試してないのでもしかしたらうまくいったかも
    • dfsだと4ターンしか読めないのでそれでうまく行かなかったのかも
    • 素材の評価を1.41tierにする
  • ポーションの価値をターン数によって減らす
    • 途中までターン数で変えてたけど、運用効率の方が大事なことに気付き辞めた

思いついたけどやらなかったこと

  • 初ターンに全呪文のグラフを作ってなんか良さげなループを見つけ出して、tomeから構築できそうなのを取る
  • 絶対に取らない呪文を決める
    • 取る呪文を決めるのは難しいので、逆に絶対に取らない呪文を決めてやったほうがうまく行くんじゃないかと思った

全体の流れ

repeatableに対応した時点で最強になって調子に乗る(38位)
この時点でdfs 4-6ターン読みだった

なんか何もしないで19位とかになって更に調子に乗る

3日くらいバグが発見できず何もできない
180位とかに落ちる
この時、かなり精神状態が最悪だった

直したら70位くらいまで持ち直す

そこからAmong Usにハマってさらに3日間何もしない

いつの間に最終日になっているのでchokudai searchを実装するも、いろいろ間に合わずレジェンド未達