CODINGAME SPRING CHALLENGE 2020 に参加した
こんにちは！！！！！！！！！！！！！！！！！！！！！！
自分の思考の過程や気付きを書き残しておけば後々再利用できる気がしたのでブログを書くことにしました。 具体的な解法、方針の解説というより、もっとざっくりとした考え方のお気持ちが中心になります。
CodinGameって何さ
今回初参加だったので全体像は掴めていないのですが、ゲームAIを作成してその強さを競い合うコンテストサイトのよう。 ゲームAI？ 難しそうじゃない？ と思いましたが、標準入力からゲームの状態を取得し、標準出力からあらかじめ決められた行動コマンドを出力する、という形式なので楽に参入できた。
春休みくらいから気になってたのでバイトと研究の進捗を生贄にして時間を特殊召喚しました。
CODINGAME SPRING CHALLENGE 2020
今回のゲームは複数のパックマンを操作し、2Dグリッドの盤面上に設置されたエサを相手より多くゲットする、というもの (詳細は他の人がちゃんと書いてくれるでしょう)
ゲームの特徴として
- 不完全情報ゲー
- マルチエージェント
- 対戦ゲーム
などが挙げられる。それぞれについて書いていく
不完全情報ゲー
敵パックや残っているエサの位置を全て取得できる訳ではなく、 毎ターンごとに自分のパックから見て上下左右の道の上にあるものしか情報は取得できない。 つまり、盤面上のどこに何があるかほとんどわからないということになる。
情報が足りないケースこそできる限り情報を使い尽くす必要がある、と痛感した。 すでに持っている情報から新しく情報を確定できる場合が多い。 貪欲、焼きなまし、ビームサーチ、何をやるにしても評価関数の正確性は重要なので些細な "確定埋め" の作業は思っている以上に恩恵が大きい(はず)(面倒なんだけどね...)。
盤面の評価がガバガバのうちにいろいろやってもいい結果が出ないのは、それはそう
マルチエージェント(？)
操作するパックが複数いるだけだからマルチエージェントは不適切かも？(各エージェントが得た情報が共有できず、それぞれが得た情報から個別に行動を決定してくのが"マルチエージェント"？)
とにかく、複数のキャラクターを同時操作するので協調した行動をが必須。同じような場所を探索するのは効率が悪いし、まして味方同士で衝突なんてことは絶対に避けなければならない。
今回の場合、各パックが進むべき経路を決める際に、
- 他のパックの経路は無視して全てのパックの経路を個別に決定 -> 経路を少しずつ変えながら調整
- パックの経路を順に決定(後から経路を決めるパックはすでに決定された他パックの経路の影響を受ける) -> 順番をいろいろ試す。
という方針が多かったっぽい。 順番の入れ替え、というのは自分が見落としがちな典型な気がする。
対戦ゲーム
相手が存在するというのは僕が普段やっているマラソンマッチと一番異なる点だと感じた。 相手の戦術を察知しメタっていく、というのはゲームAIコンペ特有の面白さなのかもしれないが、不慣れな僕はできるだけ相手に関与しないという方針をとった。 これはまあ良かったかも。戦術メタをしようとすると方針がルールベースに寄ってしまって自分の苦手な土俵になりそう。
あと、マラソンよりゲームの方が問題特有の性質が細かく色々なところに散らばっていて、それらをかき集めてバランスよく実装するのが大変そうだった (僕は問題特有の性質なんて気にするレベルのところまでいけませんでした)
一応、自分の解法
そんなに大したことやってないからツイート引用するだけでいい？いいよ。
結局dfsして良さげなところ行くだけしてた
— しぶんぎ (@Shibungi_kyopro) May 18, 2020
ツリーにもうちょいいろいろ書いてあります。
いつもお気持ち評価関数書いて満足してる気がする。
懺悔とか
やっぱり文章書くの苦手だなあ......
他人が見ること一切考慮せずに箇条書きオンリーにして完全自分用にした方がいいかもしれない。
しかし、マラソンマッチとかは競プロのアルゴ界隈に比べてノウハウの共有、蓄積が進んでないという印象もうけるし多少なりとも貢献したいという気持ちもなくはないので......(葛藤)
あ、木曜日から始まるTopcoder Marathon Match 118 にも参加予定です。気分が乗ったらその感想もアップするかもしれません
