※画像は公式Visualizerよりお借りしました
はじめに
本日は12/13 - 1/5の期間にCodinGameで開催されたコンテスト「Fall Challenge 2022」についての記事になります。全文に目を通してられない方は上の目次だけでもぜひ見ていってください。
CodinGameコンテストに参加するのは今回が4回目だったのですが、前回に引き続きLegendに到達することができました！
最終順位は
世界6位/4577人、日本4位/201人でした！（JP強すぎないか？？？）
いまだ用語がよくわかっておらずところどころ間違っていたりすると思いますが、発見された方は優しくご指摘いただけると嬉しいです。
（早く公開することを第一にしたために「何をしたか」しか書いておりません。解法共有の重要ポイントである「どのようにしてやったか」をかけていないので、諸々の箇所に「詳細を聞きたい方がいらっしゃれば教えてください」みたいな部分があります。該当箇所にかかわらずお気軽にお申し付けください。）
→おまけとしていくつか書いてみました。
前回書いたAHC016 のPostmortemはこちら
ゲーム概要
ゲームルールにつきましては、おそらくここにたどり着いている方の多くがご存じだと思いますので割愛します。雑にいえば色塗り合戦です。
最終提出AIの詳細（戦術など）
言語:Go言語
いつもの。特に言語的な利点はないです。
解法:ランダム＋貪欲
いわゆる乱択貪欲というものになるんでしょうか・・・。もともとLegend解放前は貪欲で戦っていたので、順当に時間いっぱい考えるようにした結果です。
以下、AIの概要です。
・衝突地点を割り出す
各ターンマップ上のマスのうち以下のような点を取り出します。
・自分のほうが1or2ターン早く到達できるマス(DefencePoint)
・両者同じターンで到達できるマス(NeutralPoint)
・相手のほうが1or2ターン早く到達できるマス(AttackPoint)
主にこの点を守るor攻撃することを考えます。
例として、ある試合のゲーム開始直後の衝突地点は以下のようになっています。
青:DefencePoint 黄:NeutralPoint 赤:AttackPoint
数字は近い側の陣営が到達するまでのターン数
（Recyclerなどによりあと何ターンでマスが通れなくなるかなどを考慮しながら各陣営からの距離を求めます。このあたりの詳細が知りたい方がいらっしゃれば教えてください。）
・衝突地点にユニットを割り当て
これら3種類のマスにそれぞれ4段階の割り当て数目標を与えます。ここでは次ターンで敵が攻撃に来うるようなDefencePointでの基準をやんわりと書きます。
1.隣接している敵が、防衛用のユニットを残したと仮定して、攻めてくる数
2.隣接している敵が、周辺のユニットをかき集めて防衛用のユニットを残したと仮定して、攻めてくる数
3.隣接している敵が全員で突っ込んできた場合の数
4.次ターンまでに突っ込んできうる最大数（つまり、3.に加えてspawn→moveの流れできうる数、距離2にいる敵なんかも加算されます）
（4は満たされることはほぼほぼないと思います）
割り当て可能なユニットが複数いる際は等確率で選び出します。
（DefencePoint、NeutralPoint、AttackPointに割り当て続けていたらユニットが足りなくないか？みたいな部分はもし聞きたい方がいらっしゃれば教えてください。）
・割り当てを評価
上の割り当て方ですが、どの衝突地点から割り当てるか、どのユニットを割り当てるかによって解は大きく異なります。したがって、評価関数を用意し、最高点を出せた割り当てを採用します。
各衝突地点のスコアは
（衝突地点の重要度を数値化したもの）×（衝突地点の基準充足状況を数値化したもの）
を基本として、全衝突地点のスコアを足し合わせたものが割り当てのスコアになります。
・recyclerのbuildは割り当てとは無関係に雑に行う
recyclerの設置は上の割り当ての前に以下を鑑みて設置します。
・自身のエリア確保状況（戦闘が終わりかけていて不利だとrecyclerは自陣を減らすことになるので基本置きません）
・ユニット、保有matter(戦線で戦えるユニット数や保有matterで上回っていると、マター集めのrecyclerはよほどの効率がないとしません。)
・隣接マスにいる敵ユニット(隣接する敵が多い場合など、防御効果が感じられる場合は防衛することがあります)
recyclerの設置で失う土地については
(消える自陣のマス)-(消える敵陣のマス)+(消える中立のマス)+(到達不可能にしてしまうマスの数)
として、この値と設置した場合に得られるmatterを天秤にかけて最終的に設置するかを考えます。
（到達不可能にしてしまうmatterの数はどう計算したのみたいなことが聞きたい方がいらっしゃれば教えてください）
弱点
序盤はなかなかに長期のコンテストで万事を尽くせるなどと思っていましたが、最終提出の自身のbotには数々の粗があります。うち、特に問題のある点を残しておきます（未来の自分がもしこのコンテストを継続する場合のことも考えて書き記しておきます）
・recycler設置係とユニット割り当て係のディスコミュニケーション
これは最大の問題点。前のrecyclerの方針では「隣接マスにいる敵ユニット(敵が多い場合など、防御効果が感じられる場合は防衛することがあります)」などと書いておきながら、recycler設置係はあまり賢くないので切迫した状況にもかかわらず適当なところにbuildして、前線にspawnさせるためのmatterが足りなくなることが結構あります。
・割り当て評価のスコアが雑
全力でspawnしていたら最重要ポイント（ここはとれなかったら負け確定みたいな点）を守れていたのに、分散して守らせてしまったことにより敗北するというのもしばしばありました。今回終盤に割り当て評価をガラッと変えてしまったので調整が不完全です。（ここは多少のじゃんけん要素の絡むところではありますが・・・）
途中で世代交代となったbotたち
Wood Killerくん
これは相手の陣地に全力で迫っていくタイプのもの。WoodBossを倒すことを目標に育成しました。WoodBossはmatterを使い切らないうえにbuildもしないので、毎ターン1スポーンすれば数で押し切れると思い、ただただ敵陣に向かって突っ込むように実装しました。BronzeBossもbuildをしないタイプだったので結果的にBronzeKillerにもなりました。
Falconくん
silverでは、WoodKillerくんはrecyclerでマター集めをした人たちに返り討ちにあったり、そもそもrecyclerで進路が阻まれたり。そこでsilverリーグで限界を迎える初代 WoodKillerくんに代わる2代目Falconくん登場。Falconくんには高い周囲観察力や攻防の機敏さを期待してこの名前を付けました。
FalconくんにはWoodKillerくんの数々の弱点を克服してもらいました。「防衛地点にユニットを割り当てる」という基本方針をここで固めました。また、Recyclerを、消してしまう土地に対して得られるmatterが最大のところに置くようになりました。
他にも戦闘終了後に自陣を塗ったりなど、最後まで必要になる根幹はここで生まれました。割り当て順を工夫するなどしてFalconくんは当時の50位付近まで成長しました。
（ここで成長できたのがこの後コンテストへのモチベーションを保てた気がします）
Radial Flowくん
RadialFlowくんはFalconくんの突撃体質による防御面の弱さを治すことを目標に生まれました。距離計算の際にrecyclerによる緑化を考慮したり、複数体スポーンさせないと守れないような衝突地点をBuildで防いだり。DefencePointを一体で複数カバーできる場合もあるので、複数に割り当ててみたり。RadialFlowくんは当時のメモによると12月末Goldリーグの14位まで行けたらしい。
Towering Cliffsくん
自分の頭の中にある良さげな解法、実装にn日かかりそうです
— MON.T+α (@montplusa) 2022年12月30日
たぶんこのときのやつ。3代目RadialFlowくんの負けた試合を見ていると
「いや、ここはこのユニットに任せておけば真ん中一足先にとれるぞ」
「いやいやここはスポーンで対応したほうが・・・」
みたいな盤面をちょくちょく見かけました。これは山登り法を実装するときなのでは（あわよくば人生初焼きなましを・・・）、と思い、ToweringCliffsくんの育成に取り掛かりました。
まず山登りを実装する（割り当てをやり直したりする）にあたって、持っている割り当て情報をもう少し扱いやすくしなければならなかったので、RadialFlowくんのコードはほぼほぼ解体しました。また、扱いやすさのためにこれまでに実装していた多くの機能を失うことになりました。
ツイートではn日かかるといっていましたが、ゲームのアクションをかなり制限した形での実装に2日、RadialFlowくんの持っていた機能の8～9割の復元にさらに2~3日かかっており、実装力のなさに危機感を覚えております・・・。それも結果的に山登りではなく貪欲を時間いっぱいやり直すという方針になりました・・・。
ToweringCliffsくんはさらに、Recyclerを置いた際に自陣に到達不可能なマスを作ってしまうという問題や、無限ループ時に自分の拠点を塗らない問題を解決し、リサブの上振れ次第でちょくちょく1位に上がることもありました。（あれは潜伏、リサブの下振れ等いる中の仮初の1位だと思っていますが・・・。）
なお、最終提出のThe Bumpinessくんとの違いは、「顔文字を出力するか」と若干のパラメータ調整くらいしかないです。
おわりに
ここまで読んでいただきありがとうございます。CodinGameのコンテストに前回参加したのはGreenCircleになりますが、その時に引き続き一桁順位をとれたのがとてもうれしかったです。（もともと3桁順位の住人なので・・・）
大変長いコンテストでしたが、コンテストを開催してくださったCodinGame様、Arenaでお世話になった皆さん、楽しい時間をありがとうございました！
