場所は最初にではなく（再び）撮影されましたが、何か書いておくべきことがあります まず第一に、この記事は、今年の参加者、またはそのような次のコンテストのアイデアを取り上げたい人、あるいは単にロシアのAIカップ競技のトピックに精通している人にとって興味深いかもしれません。
ゲームのルールを繰り返しません。 それらに精通している人々-精通している人々、および精通していない人々-は、いくつかのリーダーゲームを見ることができます。 私のプロフィールへのリンク。
今年のテーマは当初はあまり好きではありませんでしたが、私は参加することを事前に決めていました。 最初のバージョンが送信されるとすぐに、関心が急激に高まり、少なくともいくつかのアイデアが現れ始めました。 したがって、来年参加するかどうか疑問に思う人は、最もcな戦略を送信することをお勧めします。 意見は大きく変わる可能性があります。
管理の複雑さは、多くの参加者、さらには新参者を怖がらせました。 参加者の数は記録的に少ない。 そして、最初の3週間のトップにいるほとんどの人は、明らかに見込みのない戦術を持っています。 しかし、これらはすべて私にとって手元にあるだけです。
コンテストには多くの努力が費やされています。 自由時間を100％広げます。 しかし、これでは十分ではありません。
叙情的な余談は完了しました。私の戦略を説明します。
ビジュアライザー
ローカルランナーのフルタイムのテクニカルビジュアライザーでは十分ではありません。 デバッグ情報を描画するには、独自に記述するか、誰かのベストプラクティスを使用する必要があります。 初日、私は昨年Windows Formsの気取らないビジュアライザーを新しいルールに適応させ始めました。
最低限必要な機能があります。通常のビジュアライザーが実行できるすべての機能に加えて、ハイライト、ベクターの周りの移動、建物のキャプチャなどの小さなアニメーションがアニメーション化されます。
外観の短いビデオ：
最初のバージョン
上記で書いたように、APIを感じ、アイデアが出始めるには、少なくともいくつかの戦略を書く必要があります。 先に進み、不器用な「トルネード」は、敵ユニットを優しく「トリム」する後続バージョンをすべてテストするための優れた戦略です。
基本的な戦略を書く時が来ました。
過去のロシアAIカップの経験によると、成功する戦略の必要な要素は、動きの列挙+ゲーム世界の正確なシミュレーションでした。 何よりも私を混乱させたのは、戦略開発の明確な計画が、以前のように見えないことでした。 賭けは優れたマイクロコントロールに基づいて行われ、対戦相手が何をしているのかを見て、戦術を後で考え直すことができます。 そこにすべてが落ち着きますが、あまり変わらないカーネルを作成する必要があり、新しい機能を増やすことができる場所になります。
コードアーキテクチャは非常に単純です。 タイプMyVehicleのオブジェクト-Model.Vehicleクラスのラッパー、およびサンドボックスオブジェクト（サンドボックス）があります。 実際、後者は神のオブジェクトです。 彼に任意のコマンドを与えることができます-Model.Moveと同じであり、事前に数ティックの世界をシミュレートします。
意思決定は、グローバル評価機能に基づいています。 世界の状態を評価して実数を返す1つの関数（ハザード関数）があります。 1回の移動で、この数ができるだけ小さくなるように世界の状態を変更するよう努めています。
以前のCodeWizardsコンテストでも同じアイデアを使用しました。 なぜなら ウィザードが1つ（つまり、2次元空間）しかない場合、関数の値をグラデーションスケールとして描画することができました（昨年のビデオへのリンク ）。 ここでは、1つの共通機能を備えた500ユニット（多次元空間）を視覚化せずに実行する必要がありました。
後で、この関数の計算方法についてさらに詳しく説明します。
次に、さまざまな動きを整理する必要があります。 最後のオプションは、ユニットごとに次の動きを整理することです。
- 何もしません。 注文は与えられず、全員が同じ方向に動き続けます。
- 分隊の中心にスケールします。
- もしあれば、核爆弾の爆発の中心からのスケール。 さまざまな要因で。
- ±45°で回転します。
- 地上設備の場合、構造物のキャプチャに向かって移動します。
- ヘリコプターを航空機からのシェルター用の装甲兵員輸送車に向けて移動します。
- 航空工学の場合は、治療のためにArrvに向かってください。
- かなり長い距離（マップの4分の1など）で12方向に移動します。
このリストは、さまざまなアクティビティ全体をカバーするのに十分でした。
ハザード関数の計算。
これは、次の値の合計で構成されます（長くて面倒な係数が選択されています）：
- 機器の全体的な健康状態。 また、Arrvを補充した隠された健康のプールも考慮に入れたため、機器が回復したいという欲求がありました。
- 敵の車両の総体力。
- 殺された車両の数。
- 殺された敵車両の数。
- 潜在的な核損傷。 つまり、まるで核爆弾がnティックではなく、今すぐ爆発するかのようです。
- ポイントの数は建物をキャプチャします。
- 潜在的な損傷。 影響を受けたエリアまたはその近くにいると、罰金（指数関数的に減衰）のようなものになりました。 つまり、各ユニットについて、（0ティックに対してどの程度のダメージを与えることができるか）+（1ティックに対してどの程度のダメージを与えることができるか）/ 2 +（2ティックに対してどの程度のダメージを与えることができるか）/ 4 + ...と計算されます。 クールダウンを考慮せず、休憩中に敵を休ませるのを恐れず、休憩なしに彼らに突入しないようにするために。
上記のすべてのポイントは、ユニットに属しているかどうかに関係なく、ユニットごとに個別に考慮されます。
- 分隊の衝突に対する罰。 デタッチメントの衝突、または「ほぼ」衝突。 罰金は非常に大きいので、分遣隊の一部を大砲の飼料に入れる方が、別の分遣隊との交差点に残すよりも有益でした。
これらはすべて混戦要因です。 さらに最も難しい。 軍隊を敵に向かって移動させる方法は？ 最も近い、または最も太い？ 軍隊を敵から逃げさせ、ヘリコプターをAPCの後ろに隠す方法は？ 軍隊を動かして建物を占領する方法は？ フライを癒す方法は？
ここでは、グループ化に関する情報が必要になります。 敵ユニットのクラスター化と同様（5〜7グループの借方が500よりも便利であるという事実のみ）。
- 敵のフィールドを引き付ける/撃退します。 私のユニット、敵ユニットのダブルサイクル...私の戦略の中で最も弱く、最も苦しめられた場所の1つ...一般的に、ユニットのタイプとそのサイズのみに依存する機能があります（混合ユニットはまれなので、そうではないと思います）。 たとえば、50機の航空機があり、敵のヘリコプターが50機の場合、関数の値は非常に大きな正になります。 50戦車と50戦車の場合、少しポジティブです。 50機のヘリコプター対50機の場合、大きなマイナス。 50ヘリコプター対1機の場合、小さなネガティブ（突然！50ヘリコプターが1機に飛ぶことはありません）。
この全体に、グループ間の距離の指数関数的に減衰する関数が乗算されます。 距離が大きいほど、総量への影響は小さくなります。 マップの反対側のコーナーでゴールに向かって走るのは意味がありません。近くの誰かに行くのが良いでしょう。
また、これはすべてユニットの密度の合計、つまり（面積の合計）^ 0.25で乗算されます。 大幅に塗りつけられたユニットは、SCALEを使用して圧縮されました。 - フィールドを建物に引き付ける。 これは同じスキームです。 建物がどのようにグループに分散されているかについては、少し低くなっています。
- ヘリコプターのフィールドを装甲兵員輸送車に引き付けます。 これは、マップ上の平面の数、最も近い距離、最も近い「カバーポイント」までの距離に依存します。
- フィールドを引き付けるArrv。 アイドル状態の航空機、またはArrvが近くにある場合、それらを利用できます。 健康の損失が大きく、Arrvが近いほど、魅力的なフィールドが強くなります。
一般的に、これにはすべて太字のプラスと太字のマイナスがあります。 松葉杖がなければ、新しいアイテムを追加できます：核、建物、治療。 係数は絶えず調整する必要があります。ある状況では修復しますが、他の状況では破壊します。
シミュレーション
高いシミュレータパフォーマンスを実現するには、衝突の円をすばやく確認し、戦闘の近くにいる隣人を見つけることができるデータ構造が必要です。
コンテスト開始の少し前に、コンテスト開発者のgithubリポジトリでアクティビティを観察しました。 QuadTree.javaファイルがcodeforces-commons リポジトリに追加されましたが、 それでも最初の推測では、多数のユニットで競争が行われると思われました。 シミュレータの実装を始めて初めて、この構造を思い出し、使い始めました。 結局のところ、ローカルランナーでも使用されます。 上記の実装では、ポイントの削除、ポイントの座標の変更（削除と再追加は非効率的）、ツリーのクローン作成のための十分な方法がありませんでした。 自分で追加する必要がありました。
ユニットの衝突をチェックすることは、私のコードの中で最も費用のかかる操作であり、時間制限にはほとんど適合しません。
チームマネージャー
チームマネージャー？ 分隊の優先キュー？ 保留中のコマンドとキャンセルされたコマンド これはすべてではありません。 上記のように、すべての決定は、現在の状況に基づいてのみ行われ、各ユニットの最後の順序を知っています。 TickIndexの原則に従って、利用可能なアクションは60ティックに均等に分散されます％10 ==0。各ティックから計算するにはコストがかかりすぎます。
ラウンド1
Arrvのようなユニットを何らかの方法で適応させるのに数晩かかりました。 チェッカーボードパターンでTankとIfvとそれらをミックスすることにしました。 構造は最適ではありませんが、これまでのところは最適です。
GIF 
最初のラウンドの開始までに、私は一貫して多くのリーダーを倒しました。 「サンドイッチ」タイプのライバルの下で自分を研ぎ澄まさなければならなかったが、彼らは決勝戦には適していないことを理解した。 私は主にud1とGreenTeaに焦点を合わせました-それらの戦略は私のものに似ていました。
ラウンドの準備2。
2回目のラウンドまでに、彼らは建物を押収し、生産を管理する方法を学ばなければなりませんでした。 Arrvユニットのミキシングは捨てられなければなりませんでした。 時間がかかりすぎた-平均900ティック。 潜在的な最適化が2倍であっても、これはまだ多くのことであり、その考えは放棄されなければなりませんでした。
経路の全長を最短にするために、開始チームのArrv、Tank、Ifv、および新たに建設されたものが散在し、建物を捕獲しました。 これは、ハンガリーのアルゴリズムによって解決される標準の割り当て問題です。 その他の建物選択アルゴリズムは変更されていません。 敵の装備の種類の説明を追加する価値がありましたが、これは優先機能ではないようでした。
パフォーマンスの問題は前面に出ていません。 マップ上のユニットの数が増加し、グループの数も増加しています。これは、あらゆる種類の動きの数を意味します。
最適化に費やした約1週間。 精度を犠牲にして最適化する必要がありました。 マップ全体でアクションをシミュレートする代わりに、各グループの近くで個別にシミュレーションを実行し、結果を貼り付けました。
核爆弾による恥ずかしさを避けるため、地図上に少なくとも1つの爆弾があったときにこれらの最適化をオフにしました。
グループをまっすぐに移動したりスピンしたりすると、さらに先に進み、衝突チェックを無効にする必要がありました。
最後になりますが、周囲に敵がいない場合、Moveの12のすべての方向をソートすることは意味がありません。
しかし、いいえ、最後ではありません。 偶数のグループは偶数の動きをし、奇数のグループは奇数の動きをします。 ちょうど建てられた（別名ホームレスの人々）-3歩ごと。 選択したユニットには、核爆弾モードとゲーム開始時の両方に例外があります（<3000ティック）。
最終準備
最終的には、敵ユニットの数とそれらがどこにあるかを制御する必要がありました。 各ユニットについて、前回表示された場所を思い出しました。 3つの配列があります。
目に見える技術の通常の配列（目に見える）
チェック済みの非表示機器の配列（チェック済み）。 各Idが最後に見られた場所はわかっていますが、もう存在しないことは確かです。
チェックされていない不可視の機器の配列（チェックされていない）。 これは、敵の存在のためにこの領域を偵察する必要があることを意味します。
配列は次のように入力されます。
- ゲームの開始時に、ユニットに対称的に未チェックで入力します。 これにより、少なくとも最初の参照が提供されます。 Idのパターンは見つかりませんでしたが、これは問題ではありません。最初の外観でそれらを遅延生成できます。
それはどのように見えますか
- 各ティックの開始時に、ポイントが表示されるようになった場合は未チェックからチェック済みに移行し、ユニットがスコープから消えた場合は表示から未チェックに移行します。 ユニットが範囲内にあるが、耐久性が0の場合、ユニットは殺されます。
- ゲームシミュレーターは、新しいテクニックが登場した順にIDを記録します。 新しいユニットがどこでいつ表示されるか、どのID、どのタイプかを正確に判断するためのすべての情報があります。 1つのティックに複数のユニットが表示されるときの衝突は非常にまれです。
視界の半径は、殺されたユニットを特定するのに十分な大きさであるか、視界から消えます。 例外は核攻撃による破壊ですが、これは非常にまれなケースです。 したがって、「死んだ魂」はほとんどありませんでした。
同じQuadTreeは、特にティックごとに1回実行する必要があるため、可視性をすばやく確認するという優れた仕事をしました。
これは、おそらく、霧の中でゲームをサポートするために行われたすべてのことです。
私は時間制限を克服しませんでした。以前のように、私のプログラムは、いくつかのマップでいくつかのライバルがいて、220秒に収まりません。 しかし、それでも、転倒に対してポイントで優位に立つことができます。
決勝戦では少し不運だった-最終的には4位、サンドボックスでは2位でした。 次回は強くなります。
どうもありがとう。 ロシアのAIカップ2018でお会いしましょう。
コード