AT274の技術だったりなかったり

あっとのTECH LOG

競プロのこととか技術のこととか。たまに日常を書きます。

CodinGame Fall Challenge 2020 参加記

お久しぶりです。
CodinGame Fall Challenge 2020 に参加したので参加記を書きます。もう眠いです。。。

注意

「自分でもなんで強いかわからない」みたいな改善案ばかりなので、多くの方の役に立たない可能性が高いです。
あと普通に間違ってる可能性も高いです。優しさに自信がある方はご指摘ください。
こんなことしてる人もいるんだなぁ、ぐらいの気持ちで読んでいただけると嬉しいです。

ルール

ツカモさんに全てを託します(ありがとうございます) tsukammo.hatenablog.com

ざっくりボドゲっぽくいうと、
デッキ構築 + セットコレクション + (拡大再生産)かな、という感じです。

ボドゲっぽく言わないと、いい感じに素材の交換を繰り返して決められたセット(ポーション)を作っていこう、という感じです。

結果

f:id:AT274:20201124213751p:plain 世界 57位 / 7043人(日本 14位 / 320人)で、Legendでした。
終了3時間前にギリギリレジェンドに上がりまして、最終提出も結局そのコードを出したのですが思ったより上に行けたのは嬉しい誤算でした。

やったこと

やったことを書きます。
つらつらと箇条書きです。

各Tierの価値について

  • 1, 2, 3, 4 にしました
  • 最初はポーションのデッキで連立方程式らしきものを立てて近似して、「1, 2.5, 2.6, 4が最強だぜ!」みたいな天啓を得ましたが嘘でした。

探索について

  • 幅75、深さ25のビームサーチを行いました。
  • 探索内容は、各ターンでできるムーブを全て試す、です。(LEARNについては少し違うので後述します)
  • ただし、現在のターンに自分が取れずに相手が取れるポーションについては考慮から外しました。
  • 本当は安いポーションを相手がとるとは限らないから、そこも考慮した方がいいらしいです。

  • 「実は先にRESTする方が強い」「実は先にLEARNする方が強い」みたいなのを取りこぼしたくなかったので、 3手目までは全探索することにしました。

  • 最初はビームサーチで書いていて、途中でchokudaiサーチに切り替えたのですが、思うように順位が上がらず、最終日にビームサーチに戻したら順位が爆上がりしました。
  • たぶんどこか壊れてます(chokudaiサーチもgold30位とかに入ってたから特別弱い訳ではないと思うんですが)

評価値について

  • 5つ目のポーションを取得するまでは、 (インベントリのTier価値総和 + 獲得したポーションの点数)の、探索前からの伸びを探索ターン数で割ったものを評価値としました。
  • 25手目のRESTについては分母に入れてはかわいそうなので、無視することにしました。
  • 「インベントリの価値を高め続けるよりも、途中でポーション作ったほうが点が高くなるよ」とおばあちゃんに教えてあげました。
  • が、準トライフォース職人おばあちゃんになってしまいました。
  • ので、ポーションの価値を一律 +7しました。 (は?)
  • するとなんかいい感じにバランス高い動きをするようになりました。(えらいぞ)

  • ポーション価値をターンに応じて減衰させようとは思ったのですが、インベントリ価値が相対的に高くなって壊れそうなのでやりませんでした。

  • 6手目はとにかく速くポーションを作るようにしました。超大事だと思ったんですが、そこまで伸びませんでした。

  • 6つ目のポーションで相手より9点リードしている場合に限り、速さを重視するようにしたら強くなりました。
  • なんとなく、「どうせ相手はこの数ターンで点を伸ばすから〜」の気持ちでした。
  • ターン開始時に5つポーションを取ってないと速さを重視しないバグがあったのですが、外すと弱くなったのでそのままにしました。
  • 25手とか読むと多分皮算用色が強くなるのかなと思ったり。 (というか25手先の状況って妥当な推測ができるのかといまだに思ってます)

  • 振り返ると激ヤバ関数ですが、激ヤバ探索にはfitしたのでヨシ!

LEARNについて

  • 初手7回一番下からLEARN。それに加え、先読み税3以下のものを最大3つまで、後の探索で取得できるようにしました。
  • いい詰み回避になったと思いましたが、実は初手6手で良かった説が高いです。だって後の探索を最大4回にすればほとんど変わらないもの。
  • 各探索におけるLEARNは最大1回までとしました。状態数がぐっと減ってより幅を持たせられるようになった気がします。

呪文について

  • 特に評価はつけてません。
  • 下7回が普通にSilverまで強かったのと、最大3回の追加LEARNでそこそこまとまるだろうと考えました。
  • 初手の青+2 以外の呪文は禁止しました。

その他

  • トライフォースは5個までしか価値がないようにしました(集めすぎるの回避)
  • 勝てる時はキッチリ勝つようにしました。
  • 相手が6つ目のポーションを作れる時には、得点を最大化するようにしました。(たとえ勝っている時でも!)
  • 普通に考えたら無駄に負ける可能性が上がるバグなんですが、上位陣で勝戦判定をやってない人はほぼいないでしょうし、いい感じに混乱をうんだのかもしれません。

振り返り

  • SpringChallenge2020が大苦戦したことに比べれば、中盤までは比較的高い順位をキープしながら楽しめました。
  • Legendが解放されてからは、案の定?大苦戦しました。

  • SilverまではPython、Gold解放後は11月からこっそり勉強していたRustに乗り換えました。

  • お受験ママみたいなコンパイラに叱られ続けてつらかったです。
  • Rust移行も大苦戦しましたが、最終日にはそれなりに慣れれてよかったなと思います。

  • 初めてビームサーチとchokudaiサーチを書きました。

  • 後者は実は壊れてたかもしれませんが、新しいことずくめの中でなんだかんだ結果を出せて嬉しく思います。

生活の破壊について

  • 木金と有休を使って怒涛の5連休を作り出しました。
  • 平均して平日は1日3時間、休日は14時間近くやったと思います。
  • 最後の2日ぐらいはご飯も食べずにずっとやってました。
  • 生活を破壊するのはやめよう!
  • やめような!!!

まとめ

振り返ってみれば春に負けず劣らず、苦戦したコンテストでしたがいい結果が出てほっとしています。
特に全力を出した感については春よりも大きいかな。。。

対戦してくださった方々、ここまで読んでくださった方々、ありがとうございました! CodinGame Spring Challenge 2021 でお会いしましょう!!!