CodinGame Fall Challenge 2020

世界114位/7000人くらい

日本34位/300人くらい

でした。

ゲームの概要はツカモさんの記事などに投げます。

最終的にやっていること

余計なテンプレとかを含めて400行弱、本質部分だけだと300行強です。

一番下の呪文を10個引きます。色々試した結果これが一番マシだったので結局こうなりました。 15個揃えているかと思っていたのですが今最終版のソースコードを見たら14でした（？？）

最初に呪文を揃えたら以後は一切LEARNを考慮していません。

できるだけ素材の価値が増えるような、ポーションを醸造できるような操作を幅2000深さ12のビームサーチで探索し、その最初の操作を出力します。

評価関数は操作のゲイン（素材に1~4の価値を与え、CASTなら増える価値、BREWなら値段-素材の価値）を基本として、BREWには若干のボーナスを、RESTにはペナルティを加えているだけです。

ポーション5個まではビームサーチで操作を決めますが、最後の1個はできるだけ早く完成させて試合を終わらせてしまうのが良いことが多いので、ダイクストラ法で最短手を探します。ターン数だけならBFSでよいのですが、操作のゲインが出来るだけ高い経路を選びたいのでダイクストラ法になっています。

インベントリの状態（1001通り）と使用済み呪文の状態（2の呪文数乗通り）の組で状態が表せるので、覚えている呪文数が12くらいまでならそのまま探索が回るのですが、13や14となると厳しくなってくるので、初期呪文を適度に無視することでなんとかしています。

コドゲをやりたさも山々だったのですが、ひとまず去年最後に抜かれて1位差で賞金を逃したハル研プロコンの方に全振りして終わってからやれるだけやることにしていたので、ゲームの概要も見ていませんでした。

結局ハル研の方は10位にも届かず残念な結果に終わり、かなり精神的に疲労が残っていたので終わった当日はまだ手を付けませんでした。

MPが回復したのでツカモさんの記事とIDEを見比べながらようやくルールを理解しました。

どんな方針にせよインベントリに対して呪文を唱えられるか、醸造できるか、操作の後どうなるか、を頻繁に知りたくなるので、効率的なインベントリの状態の持ち方をまず考えました。

1つの素材の個数が0~10なので4bitで表せます。これをそのまま4bit*4で詰めれば並列に加減算が行え、メモリ的にも嬉しいですが、どこかで正負方向のオーバーフローが発生すると左右の領域と干渉してよくわからないことになり、呪文に対して素材が足りているか調べたりするのには使いにくそうです。

そこで1bitの間隔を空けて5bitずつ格納すると、並列に引き算を行い、どこかで負になってしまった場合はオーバーフローにより1bitの間隔の部分に1が立つのでビットマスクで実行不可であることを検出できます。

ただ、これは正方向の制約には適用しにくく、インベントリの領域溢れが検出できないので、追加で「空き領域数」を持ってこれが負になるかを見ることにしていました。

とりあえず、可能なBREWを適当に実行するコードでWood1に、一番左のポーションが作れるようになるまで適当にCASTしてからBREWを繰り返すコードでBronzeに上がりました。

どうでもいいんですが、このWood1→Bronzeはゲーム性が本来のルールとだいぶ異なっていて、Bronzeに上がってからコードを再利用しにくい上に実装が結構面倒で、微妙な気持ちになりました。

呪文セットを固定とすれば簡単なBFSでポーションを作るまでの最短経路が出せることが分かったので、これを実装して一番左のポーションを作り続けるコードを投げるとあっさりSilverに上がりました。

狙うポーションを適切に選んでみたり工夫してみたもののこれだけだとGoldに行けそうな雰囲気が無かったので、距離に価値のゲインの総和も持たせ、ダイクストラ法にしたところ少し強くなりました。

また、ある程度ゲインで差が付くとターン数の分の差を埋められるようにして生産効率をさらに重視したところSilver20位程度まで上がるようになりました。

この日は陸上の記録会（3000m走）で、電車の中や競技場で順位表を見ながら上振れでGold上がっちゃわないかな～と言い続けていました。

そのままほっとくと勝手に一桁順位まで上がり、1位～2位で定着するようになり、帰宅してから少し待っていたら本当にそのままGoldに上がりました。

ARCもあったのでこの日はほとんど触っていません。

さすがにアルゴ解ではもう上がれなさそうだったのでビームサーチを書きました。この時点で評価関数というかAIの内容は最終的なものとほぼ同一です。Gold50位くらいまで上がるようになりました。

LEARNをさすがに工夫しようと思い、適当な評価関数を付けてうまく先読みするようにしてみたものの圧倒的に弱くなりました。

呪文の強さを単体で評価するのではなく、本棚にある呪文の部分集合について、今の呪文セットにそれらを追加したとき、Tier0の素材×2個の状態から規定ターンで価値をどれだけ増やせるようになるか、をビームサーチで求めたものを評価値として呪文を評価するようにしてみました。

めちゃくちゃ弱いという感じではなく、対Boss勝率は上がったような気もしましたが、Submitして振るわないので捨てました。

最後の1個のポーションの完成は早さが命なので、元々使っていたダイクストラ法に回帰してそれを使うようにしました。これはさすがに有効そうでした。

相手の状態を一切見ていないのはさすがに残念なので、相手に対してもBFSで各ポーションまでの最短距離を求めておき、ビームサーチにおいてあるポーションを作るタイミングが相手の最早ターンより後なら特に評価しない、というようなものも書きましたが、これも強くなったのか微妙でした。

結局前日のシンプルなビームサーチが収束時の順位的には一番良かったので、これに明らかに有効だったラストポーション用の探索切り替えのみ実装したものを最終提出としました。

Gold70位切ればよいかと思っていましたが予想以上に伸び、Gold30位程度で終わることができました。提出期間が終わってから日本人集団のデッドヒートが起こっていて面白かったです。

なぜLEARNを探索に組み込むことを試さなかったのか全く謎です。一瞬でも考えたことは全部実装しましょう。

ビームサーチの物量は強みになっていたようなのでちゃんと時間計測してもう少しそこを伸ばしてもよかったかもしれません。