CodinGame Fall Challenge 2022に参加しました！
2位でした！ﾑｷｨｰ！
ゲーム内容
tsukammoさんによる要約です。いつもありがとうございます。
tsukammo.hatenablog.com
最終的なbot
目標セルとユニットの割り当て
未占領の各セルについて、相手と自分が最短何ターンで到達できるかを計算し、相手のほうが先に到着できるセルの周りのセルを目標セルとします。（自分と相手の同距離のセルは目標セルになる）
目標セルのうち、壁際にあるセルを重要目標セルとし、優先的に狙うようにします。
目標セルは連続でとれるような配置になっている場合は一番近くの目標セルのみを抽出。
ユニットと抽出した目標セルを到達ターンをコストとした最小費用流でマッチングさせます。
この時、目標セルまでのターン数が最短＋1までのユニットのみ割り当てます。最短+2かかるとSPAWNしたユニットに向かわせたほうが早いからです。
1ターン目～相手と接触するまで
1ターン目にビームサーチで相手と接触する直前までのターンを探索します。
2ターン目以降はその結果を出力していくだけです。
行動はBUILD->SPAWN->MOVEの順にしました。BUILD/SPAWN数やユニット数によって1ターンにおける行動回数が変わりますが、ターン開始時点の深さが揃うようにしました。
評価値
- matterが多いほど良い
- recyclerによって将来取得できるmatterが多いほど良い
- 占領したセル数が多いほど良い
- ユニット数が多いほど良い
- 目標セルとの距離が近いほど良い
- 相手側に近いほど良い
相手と接触後
以下の手順で行動を決めていきます。
- 重要目標セルへ移動
- 防衛行動
- 残りの行動
行動を決める際に評価値を使って行動後の状態の優劣を評価します。
重要目標セルへ移動
重要目標セルへマッチングされているユニットを目標セルに向けて移動させます。移動先候補が複数ある場合は評価値の高いほうを採用します。
防衛行動
こちらの占領済みセルであって、相手ユニットの周りにあるセルを防衛対象セルとします。
相手の1ユニットがこちらの複数の領域へ進める状態の場合、評価値が悪くなる方向へのみ進むものとして防衛セルを決めます。（例外的に移動されるとまずい場所は評価値にかかわらず強制的に防衛セルにします）
防衛セルのうちBUILD可能なセルを洗い出します。それらのセルへのBUILDする/しないの組み合わせはbit全探索で、BUILDされていないセルについてユニットとSPAWNをどの防衛セルに割り当てるかを最小費用流で決めます。
相手から遠いユニットを優先的に割り当てたりなど、コストを微妙に調整します。
防衛成功した割り当てのうち評価値が最大のものを採用します。
全ての防衛セルを守ることが不可能だった場合
どのセルをあきらめるかを決めることにしました。各セルのあきらめる/あきらめないのパターンをbit全探索します。
あきらめたセルへは相手のユニットが移動してきたものとして評価値を算出します。評価値が最大となるようなあきらめ方を採用します。
処理時間的に間に合わないことがあるため、処理時間を見て打ち切り、防衛セル数が多い場合は諦めるセルを貪欲的に決めたりします。
残りの行動
残っているmatterの使いみちと残ったユニットの移動を決めます。
以下の行動候補をすべて試し、行動後の状態を評価。評価値が一番良いものを貪欲的に選んでいきます。
SPAWN
- 目標セルから最短の位置にSPAWN
- 相手領域の周りにSPAWN
こちらが有利になりすぎないように、同時に相手もSPAWNしたことにする。
MOVE
- 相手領域に近づく方向にMOVE
- 相手領域+1の距離の位置にMOVE
- 上記で移動不可な場合はそれ以外の方向へも移動許可
- SPAWNしてMOVE：防衛行動が決定しているユニットの移動先位置にSPAWNし、代わりに防衛行動だったユニットを別な方向にMOVE
MOVEの際に、相手ユニットがいる場所への移動は移動する人数を制限する
相手の最大ユニット数を超えられるなら全員送る。
相手の現在のユニット数よりこちらのユニット数が多いなら、相手はこちらのユニット数に合わせてくると想定してその-1を送る（相手のユニットを0にするとBUILDされるので回避したい）
こちらが有利になりすぎないように、同時に相手もMOVEやSPAWNさせる。
BUILD
BUILDした結果壊れるセル数と得られるmatter数によりBUILDしたほうが良い度合いを計算。自分の領域が破壊されるのは減点だが、相手の領域が破壊されるなら加点する。
BUILDしたほうが良いほうから8カ所を行動候補とする。
評価値
- matterは多いほど良い
- 占領地多いほど良い
- ユニット数多いほど良い
- 将来取得予定のmatterが多いほど良い：早く取得できるほど良いようにターンで重みづけ
- 相手より先に到達できるセル数が多いほど良い
- 相手陣地に到達可能なユニット数が多いほど良い
- 各ユニットの相手陣地までの距離が近いほど良い
- 各ユニットの2マス以内に相手占領セルが多いほど良い、相手側の未占領セルが多いほど良い。相手側の未占領セルとは相手の占領地を通らないと到達できない未占領セルのこと。
- ユニットのいるセル数が多いほど良い（ユニットが同じセルにいるよりも別々なセルにばらけていたほうが良い）
- 未占領領域の隣に自分と相手ユニットがいるとき、ユニット数が多いほど良い
- 重要目標セルへの距離が近いほど良い。それが相手ユニットと同距離のセルであれば相手のユニット数+1のユニット数まで加点。ユニット数負けしているなら2番目に近いユニット数で評価。
- 現在のユニット数と現在matterと将来取得matterでユニットを作成したとき、目安のユニット数に足りない分減点。目安のユニット数は相手とこちらの中間距離のセル数×1.2とした。
- 勝ち確定なら良い。負け確定なら良くない。
その他
行動ループ対応
ゲーム終盤、recyclerもなく相手と自分が同じ行動をし続けることがあります。
相手の毎ターン送り込んでくるユニット数を記録しておき、一定ターン同じ動きが繰り返されていたら、防衛行動の時に相手の行動を前のターンと同じものとしてこちらの行動を決めるようにします。
それでも状況が変わらないなら1ユニットSPAWNして未占領領域をとってまわらせます。
相手陣地に入るときのMOVE
相手陣地への移動を行う時、1マス先の場所を指定してMOVEするようにします。もし移動先にBUILDされても相手陣地に近づくような動きをしてくれます。
場所によっては逆効果なので正確に計算したかったですが、refereeコード移植したのに一致しなくて断念。多分priority_queueの実装がjavaとC++で違うから？
距離や経路の計算にセルの寿命を考慮
距離3だけど2ターン目に壊れるセルがあるから実際は通れないということがあります。寿命を考慮したBFSで正しく距離を計算しました。
勝ち確定BUILD
BUILDすることで勝ちが確定するならBUILDするようにしました。
フローを使って置く場所を計算したけどそんなことしなくても求まるような？
没：初ターン以外のビームサーチ
思ったように動いてくれない。相手の動きを考慮しないと先のターンを探索してもあんまり意味ないかも？
あと評価関数が重くて回数回せないので没に。
初ターンだけ相手の動きの影響のない範囲なら効果があったのでそこだけ残しました。
感想
初めはルールが単純すぎて最適解みたいなものにみんなたどり着いて差がつかなりそうだし、ルール追加あると思ってました。が、行動の自由度が高いことや相手との駆け引きみたいなのもあって単純なゲームではありませんでした……
選択肢が多いのと相手と同時着手ということもあって探索が難しく、1ターンのみルールベース＆貪欲になりました。実装量が多いし泥臭いしで結構手が止まることがありましたが、やるんだやるんだ！と気合をいれて何とか実装してました。
（探索書いて省メモリ＆高速化を頑張るようなのが好きかも。ルールベースとか評価値考えるのはちょっと億劫になっちゃう）
コンテスト終了1時間ぐらい前にレートがすごく高くなってたので安心してカツ丼を買いに行きました。そしたら終了直前ぐらいに抜かされてしまい……評価値改善とかまだまだやれることはあったはずなのに手を止めてしまったのは良くなかった。
期間が長かったので序盤あんまり集中できていなかった、ゲームを単純だと思い込んでいた、方針決めが遅すぎたとか、良くないところいろいろあったので反省。
次回も頑張る！
