CodinGame Spring Challenge 2020 参加記

これはなに

5/8 00:00 ~ 5/18 17:00 の期間で開催されたゲームAI開発コンテスト、CodinGame Spring Challenge 2020 の参加記録になります。
もう１ヶ月も前の話なのですね。遅くなって申し訳ないという気持ちです。ゆるして。
ちなみにコドゲに参加した人向けに書きます。ゆるして。

ルール

結構ややこしいです。 ツカモさんの記事を見ていただければと思います。
tsukammo.hatenablog.com

ありがとうございます、ツカモさん。

結果

世界111位/4955人、日本18位 / 227人でLegendLeagueでした。

コンテスト後は何も触ってないんですが、今見たら 世界80位/5089人、日本16位 / 233人まで上がってました。何でだろう。

戦術について

本題です。

探索について

「どうペレットを探すか」です。 ここに無限に時間を使い、実に５日間ほどハマりました。

結局探索については以下のようなロジックで行うことになりました。
このロジックはWood1で考えたあと、最後まで使い続けることになりました。

1. 自分のパック全てについてどの方向に動くのかを決める。
   例えば、今回自分のパックは最大５体ですから４方向を考えて、最大ケースで 4 × 4 × 4 × 4 × 4 = 1024通りの探索を行いました。
   実際には上記のようなケースは極めて稀で、壁があったりとかしてまぁまぁ少なくなります。

2. １ターン後の移動したパックの位置から、全位置について最短距離を計算。
   これは多始点幅優先探索をして計算しました。

3. 最短距離の情報から各セルに対する価値を求め、その総和を「その移動の評価値」とする
   あるセルの価値を以下のように定めました。
   
   +1をしているのは、最短距離が0だとゼロ徐算をしてしまうためです。（この式は記事が進むにつれて進化していきます） これで 近くのものがより近くなったらかなり嬉しい。遠くのものがもっと遠くなっても割とどうでもいい が実現されるかなと思いました。
   あとは の総和を「その移動」の評価値として、最も評価値の高い移動方法を選びます。
   
   

不完全情報について

今回のゲームは不完全情報ゲームで、手に入る情報は自パックの視界にあるもののみです。
これをどうしようか迷った結果、各セルには以下の３種類の状態がある と定義することにしました。

• 実在セル
  目に見えるペレットがあるセルです。

• 空セル
  ペレットがないとわかったセルです。
  一度取られたペレットが復活することはないため、一度空セルになったセルはずっと空セルです。

• 不定セル
  ペレットがあるかもしれないし、ないかもしれないセルです。かっこいいので不定セルと呼んでました。
  この不定セルの価値をいかに正しく見積もるのかが１つのカギだと考えました。

では不定セルの価値をどう見積もるか、ですがゲーム開始直後はだいたいどの不定セルにもペレットがあるし、逆にゲーム終盤はほとんどの不定セルにペレットがない な、と思いました。
そういう訳で不定セルの価値を以下のように定めることにしました。実在セルの何%の価値があるか、とも言い換えられます。

これらは入力から与えられる得点情報から計算できます。スーパーペレットは１０点ですが、丁寧に取られているかを追うと残りペレット数が計算できます。

そういう訳で、各セルに対する評価式は以下のようになりました。

実在セルの状態価値は１として、空セルの状態価値は０として扱います。

スーパーペレットについて

これは間違いなくとるべきです。
なので、最優先でスーパーペレットを取りに動いてくれるよう、評価式を以下のように修正しました。

補正値は100とかだった気がします。
さらに、ライバルの方が近いスーパーペレットについては、最初から空セルとして扱うことにしました。
強い人がスーパーペレットを取り逃がすことはないだろう & スーパーペレットを取り逃がすような人には結局自分のスーパーペレット分勝つからいいや
という気持ちです。

じゃんけんについて

見えている相手のパックから周囲１マス（SPEED状態なら２マス）を「（グー・チョキ・パー）で殴られるゾーン」して、近づかないようにしました。
相手パックがアビリティを使える状態なら、そのマスを「全部の手で殴られるマス」にしたんですが、なんか弱くなりました（なんでだろう。どこかバグってるのかな）

また自分のパックについては、「あ、このままだとどうやっても死ぬわ」という時に、アビリティがあれば相手パックを狩る手にSWITCH、というようにしました。SWITCH使い始めたのはGoldからですね。

SPEEDについて

大事です。打っても死なない時にはガンガン打っていきました。厳密には損することもある（スーパーペレットを挟んでいる時とか）んですが、めんどくさいので処理しませんでした。
SPEEDを使い始めたのはSilverからでした（は？）

で、ここまででGold80位ぐらいでした。
最後の工夫として、以下を取り入れました。

相手の方が距離が近いセルについては、価値を大きく落とす

負けたゲームを眺めていると、相手の後ろを丁寧についていって「ペレットないよぉ。。。」をしている試合がたくさんありました。
なので、見えている相手パックから多始点幅優先探索を行って、相手の方が距離が近いセルについては価値を落とすことにしました。
この工夫を取り入れて、評価式は最終的に以下のようになりました。

相手が取っちゃいそう補正は最初は0.1にしてたんですが、Gold10位とかで停滞したので、0.2にしたらLegendにいきました。
ほんとはこれも距離に応じて「相手がとりそうな確率」を出すべきなんでしょうが、時間ギリギリだったのでできませんでした。（あと面倒）

DEADについて

DEADはとりのぞきました。

感想

平日５時間、休日１２時間ぐらいやりました。 ５日目まで進捗０だったので死んでました。まじでWood１で終わるかと思った。
Pythonで書いたらTLEしたので泣きながらC++に書き直しました。
C++で書いてもTLEしやがるので頑張りました。

Legendに上がれたのは嬉しいんですが、Legend内ではボコられたので結構悔しい気持ちが残っています。 次は最終日に有給を使うぜ！という気持ちになりました。

こんな調子なので楽しむ余裕などなく、ほとんどの時間を苦しい思いをしながらやってました。
７日目ぐらいからようやく楽しくなってくれてよかったです。
（もちろん思い出として振り返るとYeah~~って感じです。よくがんばったねME.）

次回のコンテストも必ず参加します！もっといい成績とってやるぞ〜〜〜〜〜〜〜〜〜〜！！！ ではではお疲れ様でした！！！！

戒め

体調管理は大事です。本当に大事。 次回は気をつけてください。

あっとより