※画像は公式Visualizerよりお借りしています
はじめに
本日は6/16 - 6/27の期間にCodinGameで開催されたコンテスト「Green Circle」についての記事になります。全文に目を通してられない方は上目次だけでもぜひ見ていってください。
CodinGameコンテストに参加するのは今回で3回目になりますが、結果5位/1758人(Legend内 5位/56人)でした。まだ夢の可能性を疑っています。
いまだ用語等よくわかっておらずところどころ間違っていたりすると思いますが、発見された方は優しくご指摘いただけると嬉しいです。（かなり走り書きなのでいろいろ誤字脱字あるかもです。抜けてる大事な情報があれば随時加筆します）
前回書いたSpring Challenge 2022 のPostmortemはこちら
ゲーム概要
ゲームルールにつきましては、おそらくここにたどり着いている方のほとんどが既知だと思いますので割愛します。雑にいえばアプリケーションを早く5個リリースするゲームです。
最終提出AIの詳細（言語、探索、戦術）
言語:Go言語
今回コンテストに提出したAIはGo言語を使用したものになります。特にこの言語ならではのことをしたわけではないので、あまり関係はないです。
探索:1サイクル分の（ほぼ）全探索
今回のゲームはカードをDrawするという操作が入ると何が出てくるかわからず一気にシミュレーションの価値が下がってしまうので、相手に手番が渡るまでにどんなパターンがあるかを調べ、それぞれのパターンについて、相手に手番を渡すタイミングで、どんな山札・捨て札になっているか、何がリリースされているかなどを見て得点化することにしました。それに加え、最大で3ターン目まではif文で分岐した「定石」を見て動くことがあります。（実はこれでLegendリーグでの後手の勝率が大きく上がりました。）
ほぼ全探索というのは、MOVE Phaseから考えたときは一番パターン数が膨れ上がりがちなので、この時だけRELEASEの選択肢をよさげな一つのみにしています。（たぶん今パターン数見たら全部見ても何の問題もなかった気がします）
1サイクル分の全探索には貪欲であるというところにかなり明確な弱点があります。このターンは問題ないからと言ってリファクタリングに駆け込むと、次のターンはAdminで逆に負債を抱えることもありますし、無理してターン中にアプリケーションをリリースして山札・捨て札が負債だらけになることもあります。ここは、将来性のある状態に加点する必要があります。なお将来性へのだいたいの加点は5RELEASE目に近づくほどに弱くしていき、無駄に将来性を考えなくてよいようにしています。
以下、AIの概要です。
・ボーナスカードを4枚AUTOMATEDに入れ、手札と絡めて最後のRELEASE
AUTOMATEDが終わってから1RELEASE目ではLegendでは間に合わないので3つボーナスカードを入れたあたりからRELEASE数に応じて加点します。この戦術のためBONUSカード4枚以上（予備を考え5枚）は手札、山札、捨て札、AUTOMATEDにあってほしいところです。また、そのためCONTINUOUS_INTEGRATIONとBONUSをセットで同時に引いていきたいところです。
簡易的な引きやすさの指標として山札や手札、捨て札のすべてから二枚引いたらCONTINUOUS_INTEGRATIONとBONUSになる確率を使ったり、厳密に次のターン引いた時にそれぞれの出てくる枚数の期待値を求めたりしました。（ランダムに何度もドローしてみるのではなく数学的に四則演算で求めるのでかなり高速なうえに、なんか妥当っぽい値になります）
・初手2に行くか5に行くか問題
自分のAIは
・先手なら2に行くタイプ
・後手なら5に行くタイプ、無理なら2に行く
となっています。個人的には最初に5に行ったほうが安定してBONUSカードをAUTOMATEDに入れる手順があると思っていますが、1ターン全探索と相性が良いのは2に行く場合だと思っています。後手だと5としていますが、たいてい先手は2,5のどちらかに行くので、選ばれなかったほうに行くことになります。後手で5に行く際は一度Adminを通過するまでは「定石」を片手に隣で手を引っ張ってやることで、山札からどんな引きをしたとしてもたった一枚の最強カードCONTINUOUS_INTEGRATIONをAdminで手放さないようにします。
・移動量に応じては中程度の減点
いくらCONTINUOUS_INTEGRATIONが欲しいからと言って2ターンごとに回られては負債もたまり他の有益カードも減り困ります。かといって負債に大きなペナルティを与えるとすぐにリファクタリングルームに駆け込む開発チームの出来上がりですので、移動にペナルティを与えます。移動を抑えることは将来Adminを通らなければいけない回数を減らすことにつながります。
諸々の小細工
上だけだと他の人と差がつけられないため、順位を上げるためにいろいろと細工しました。その一部を簡単に書いておきます。
・adminを通過すると少し加点
基本的にadminを通ると手持ち札の加点部分は少なくなりがちなので、こうすると、adminを通ってもあまり痛くない場合にREFACTORINGルームまで粘らずに通過します。
・REFACTORINGルームにいるとき、CONTINUOUS_INTEGRATIONの引きやすさといった加点は小さめにする
そんなに次引きやすいのなら、REFACTORINGに止まらずこのターンのうちにadminを通っておいてください。
・後手ならは相手の2マス先にいると加点(特に、2マス先が5,6の場合)
前提として、後手は（少なくとも自分のAIは）弱いです。特に最上位陣の先手にはなかなか勝てません。そこで、突然5,6に顔を出すとadminでの予想外な負債増加や有用カード紛失などを誘発できます。きっちり組み立てている格上ほど効果があり、システムテストではそれなりに貢献できている感じでした。ちなみにこの要素が少し強めに出ているので先手と後手は得意な相手がかなり違います。
・各appのRELEASEに必要な各スキルについて、adminを通らずに取りに行ける位置のスキルなら加点、このときもう一方のスキルが山札にあるならその引きやすさによって加点量を大きくする
各appをみて加点していくのでいろいろなappに使えるスキルについては多重に加点することになります。これは現在のリリース数やAUTOMATEDのBONUSに応じて加点の強さを変えると5リリース目の見通しが良くなります。相手について考え減点すると5リリース目がしづらくなります。
・各appのRELEASEに必要な各スキルについて、次ターン山札からの引きやすさによって加点
この加点量は小さいです。まれに勝敗が変わるくらいだと思います
・（3つほどRELEASEを行うころ）今いる場所の番号が小さいほど加点
これは、5リリース目のスキルを取りに行く際にadminを通らずに目的の場所へ行ける可能性を上げるためのテクニックです。少し先に陣取っているので相手の邪魔にも多少なるかもしれません
・Training、Codingのスキル仕様を変更
ドロー枚数が山札の枚数以上の場合に山札が全部手に入る劣化スキルに変更
TrainingやCodingは確実な部分だけを適用しました。ランダムで引くとかなり負けやすくなります
ちなみにですが、これを一気に実装してもアンバランスなものができてしまいますので、料理のように少しずつfloat64を足して手作業でなじませてからまた新しいfloat64を追加します。（コンテスト終盤は小細工を思いついては実装し、整えてからまた新しい小細工を入れています）
サブミットを繰り返して戦績を見るのも有効です。
おわりに
ここまで読んでくださった方、ありがとうございます。今回は、Goldボスで苦戦していた時に考えた小細工がLegendでも効果を発揮し、Legendでさらに進化させられたのでとても満足しています。また次回が楽しみです。
