ロシアAIカップ2012での勝利への道

こんにちは、Khabravchans！

CodeTanks 2012プログラミングコンテストの決勝への参加と勝利の歴史に注目してください。







私はHabréでの競争について学び、さらに調べることに決め、プロジェクトのWebサイトにアクセスしました。 Linuxでタンバリンと踊らずにC ++で書く機会に満足しました。 私はすぐに、Java / Pythonのような言語で書く参加者に比べてパフォーマンスが向上すると思いました。 まあ、私は競技自体の形式が好きでした：最初のラウンドの2週間前、そしてラウンド間の休憩の1週間後。 ひどいzeynoteで正しく動作するコードを作成する必要はありませんが、すべてを比較的冷静に考えてプログラミングできます。 サイトでのルールと戦いのさらなる調査は、参加する決定を強化しただけです。ボードゲームなどの完全に正式な環境よりも、複雑で定義が不十分な環境でAIをプログラミングすることにずっと興味があります。

ゲームワールドブリーフ

長方形のフィールドで、6個の長方形の戦車が乗って射撃します。 まず、各自（ラウンド1）、次に2チーム3チーム（ラウンド2）、および3戦車2チーム（最終）です。 フィールドは非常に小さく、シェルターは3対3の戦闘でのみ出現したため、戦闘は本物の肉に変わります。 移動するには、右と左のトラックを独立して制御する必要があり、物理学は非常に複雑です。Box2Dのようなものです（後のリバースエンジニアリングでは、対応するJavaのPhys2Dが使用されたことが示されました）。 戦車はかなり不器用で、何とか直進することができるだけで、実際にターン中に停止します。 戦車には射撃用の銃を備えた砲塔があり、砲塔の回転速度は履帯の助けを借りて船体全体の回転速度よりはるかに低くなっています。 砲弾の飛行速度も低く、長距離をかわすことはかなり可能です。



戦車には、乗組員の健康と戦車の装甲の2種類のヒットポイントがあります。 これらの2つの値のいずれかがゼロに達すると、戦車は死んだとみなされます。 発射物によって引き起こされる損傷は、その種類、速度、ヒットが発生したタンクの側面、および発生した角度によって決まります。 発射物は装甲を貫通する場合としない場合があり、2番目のケースでは損傷は装甲のみにあり、1番目のケースでは乗組員はまだそれを受け取ります。 乗組員の健康状態は非常に重要な特性です。健康状態が低いと、トラックに伝達されるエンジンの出力と銃のリロード速度が半分になります。 誤ってマップに表示されるボーナスを収集することで、健康と鎧を回復できます。 ライフポイントを回復するためのボーナスに加えて、3つ目の種類があります：プレミアムシェルが3つ入った箱です。 このようなシェルは、リバウンドが不可能であり、損傷が大きく、速度が遅いという点で、従来のシェルと区別されます。



1人のプレイヤーの戦車のみがフィールドに残るか、5000ティックタイムに達するまでゲームがプレイされます。 さらに、生存者は勝利を保証されていません：スコアリングは、敵にダメージを与えたり、戦車を仕上げたり、自分自身を復活させたり（これを殺した戦車を回復ボーナスに押し込んだ場合）、すべての敵を殺すために行われ、蓄積されたポイントに応じて場所が割り当てられます。

初期戦略

戦車の挙動を分析した後、破線に沿った動きをモデルとして採用することにしました。 つまり、タンクは転換点に直接移動し、次に所定の位置に曲がり、次のセグメントに沿ってまっすぐに移動し続けます。 したがって、それぞれの瞬間に、直線で前進を続けるかターンを開始するかを決定する必要があります。 これを行うために、一連の方向を開始し、この方向に沿って障害物までの距離を維持しました。 配列のゼロ方​​向は順方向に対応し、残りは円の周りに均等に分布していました。 障害物までの距離と、この方向のボーナスの有無に基づいて、各方向を評価し、最適な方向を選択しました（前方方向に追加のボーナスを受け取りました）。 さらに、最良の方向があったセクターに基づいて、トラック上のいくつかの個別のギアの1つを含めました。



ローカルテストでは、すぐに個別のダイヤルの不適切さが示されました。最初に戦車が見出しでほぼ直接ボーナスを見て、接近したときにすでに斜めに見えていた場合、急にブレーキをかけて回転し始めました。 コードを作り直し、順方向の周りの小さなセクターで、電源が「全順」（1.0 1.0）から「最速ターン」（1.0 -1.0）にスムーズに変わるようにしました。 戦車はかなり速く運転し始め、ボーナスを集め始めました。 また、敵の戦車の攻撃ベクトルを回避する最も単純なシステムを実装しようとしましたが、離陸しませんでした。 これらすべてに夢中になって、身体の回転と最も単純なリードを考慮に入れた最短の銃誘導時間に基づくターゲット選択システムは、戦略の最初のバージョンをサイトに送りました。



実際の戦闘では、ターゲットを選択する際に、前方への移動とともに後方への移動を追加し、敵の戦車までの距離を考慮に入れなければなりません。 また、リードを計算するコードを変更し、発射体の飛行時間の正確な式を追加しましたが、最終的にリードを完全にリセットするバグを導入しました。 それにもかかわらず、この戦略では、ランキングで200位になり、より複雑なアルゴリズムの実装を開始しました。これは、競技会の最初からほぼ念頭に置いていました。

危険フィールド

新しいアルゴリズムの主なアイデアは、この「危険」自体を最小限に抑えるために「危険フィールド」を構築し、それに沿って移動することでした。 危険度は、敵の戦車までの距離、視認性、および銃の方向を考慮して、正方形のセル（異なる時間のセルサイズは10から16ユニットの範囲）の通常のグリッドで計算されました。 また、飛翔する発射体の邪魔になる危険性を真剣に加えます。 特定の数式は何度も変更されており、係数が調整されているため、ここでは説明しません。 タンクが障害物を迂回するために、固体オブジェクト内の危険度の値は十分に大きい数に設定されました。 結果のフィールドは、半径約3.5セルの円形フィルターによってぼけており、これは自分のタンクのサイズにほぼ相当します。



この機能を実装するには、ジオメトリを真剣に扱う必要がありました。 それ以前は、別のプロジェクトからコピーして調整したベクタークラスしかありませんでした。 これで、任意に回転した長方形のクラスと、このような2つの長方形の重なりを決定する機能を実装しました。 敵の戦車のある地点から視界を確認するために、この地点から戦車の位置、砲弾の幅まで細い長方形を作成し、他のオブジェクトとの交差を確認しました。



他の多くの競合他社とは異なり、私はグラフィカルインターフェイスをデバッグの戦略にねじ込むのが面倒だったので、標準的なLinuxターミナルの機能を夜に費やしました。 固定の256色パレット（xterm-256color）に色を設定するコマンドが見つかりました。このパレットでは、25階調の黒と白のグラデーションがありました。 その結果、私の戦略の要点は、ターミナルの危険フィールドの値で写真を表示できることでした。 最初に、1つのセルが対応する背景色の値を持つ2つのスペースに対応し、次にスペースを文字U + 2584（）に置き換えて、画像の解像度を2倍にしました。

危険領域での動き

結果のハザードフィールドを使用して、進行方向を選択しました。 モーションモデルは同じままで、破線に沿って、最初のセグメントのみが最適な方向を選択するために使用されました。 つまり、タンクはまず特定の角度で所定の位置に向きを変え、一定の速度で直進し、特定の距離を走行した後に停止すると信じていました。 新しいアルゴリズムの最初のバージョンでは、戦車がすでに速く動いていた場合に備えて別のブランチがありましたが、それ自体は正当化しませんでした。 選択した運動モデルを使用して、時間とともに線形に減少する重みを持つ危険フィールドの統合を実行しました。







どこで -危険フィールド、および -モーションモデルに応じた、時間tでのタンクの位置。 積分は数値的に実行され、対応する空間ステップがハザードフィールドのグリッドピッチの領域にあるように、時間ステップが選択されました。 任意のポイントでのハザードフィールド値は、双線形フィルタリングを使用して計算されました。



プログラムでは、移動方向を選択し、（一定速度の近似値で）回転に必要な時間を計算し、積分の現在値の回転時間に対応する係数を乗算した開始点のフィールド値を書き込みました。 さらに、選択した方向に沿って移動し、積分の現在の値を更新し、最後に考慮されたポイントで停止が行われた場合、ケースの完全な積分を考慮しました。 ボーナスが途中で来た場合、ハザード積分の現在の値から特定の量を減算します。 ある方向に沿って最適な距離を見つけたので、次の方向に進みました。 選択した方向への乗車は、以前の戦略と同様に編成されました。



最初に、私はボーナスのコレクションを、それらの位置にある危険フィールドの値を下げることで実装しようとしました。 これにより、タンクはボーナスをすぐに食べて移動し続けるのではなく、ボーナスの隣にできるだけ多くの時間を費やそうとするようになりました。 ボーナスを配列に整理し、タンクの開始位置からの距離で並べ替え、各ボーナスの達成を一度だけ考慮する必要がありました。



戦車ははるかにインテリジェントになり、障害物の後ろに隠れることを学びましたが、これは戦略のランキングに大きな影響を与えませんでした。 彼は、少なくとも1人の敵が見えるエリアで危険を少し軽減し、ゲームの終了時に私の戦車が待ち伏せされないようにしました。 当時のトップスはほとんどすぐに彼を運んだ。彼はフィールドの中心に行き、それぞれ一度にいくつかのヒットを受け、彼は中心の危険の価値を高めようとした。 危険の統合における重み関数を変更しました。線形減少を指数で置き換えました。 発射体の飛行時間の計算にバグが見つかりました-リードを修正しました。



重み関数の指数関数への変更は最初から計画されていましたが、実装の複雑さにより延期されました。重みがリセットされるまでの最大時間はありません。 ハザード積分の下限を現在の瞬間に見つかった最小値と比較することにより、サイクルを停止する条件を置き換える必要がありました。

物理的に正確な動きと覆い焼き

このすべての後、彼は交通問題に注意を引きました：時々、タンクはボーナスを逃し、その周りを輪になって走り始めました。 ハザード積分の計算は運動モデルとほとんど独立しているため、現実に近い物理学を使用することにしました。 ローカルランナーで実験して、必要な定数をすべて取得しました（物理エンジンの構造に関する知識と、グラフ上で目で指数を決定する能力が大いに役立ちました）。 一連の運転方向を、トラックに供給される一連のパワーペアに置き換えました。 ハザード積分を計算するアルゴリズムでは、タンクの予測位置に対応する座標のフィールド値を取りました。 以前のバージョンからエンドポイントで即時停止がありましたが、これはアルゴリズムの効率に影響しませんでした。 新しいモーションアルゴリズムは、画期的な製品でした。 私はすぐにランキングで20〜30位になりました。 すでに勝利の鍵は物理学の正確なモデリングであることが明らかになりました。



戦略はより強力になりましたが、これはトップに対して十分ではありませんでした。 私はコーナーの危険値を減らし、さまざまな係数を調整し、ハザード積分の計算で瞬時停止を削除し、再帰の深さを増加させようとしました：トラックの容量のペアを1つではなく、最初に適用し、しばらくしてから2番目に適用しましたが、十分ではありませんでしたCPU時間。



それから私は発射体回避を改善することにしました。 これに先立ち、発射体の弾道は危険フィールドに大きく貢献し、戦車は遠ざかろうとしました。 しかし、フィールドの解像度は非常に低く、覆い焼きする時間がほとんどないため、この方法は効果的ではありません。 しかし、将来の時点でタンクの正確に予測された位置（および四角形の重なりを決定する機能）が既にあったので、発射体が私のタンクに当たるかどうか、もしそうなら、どの角度からかを正確に見つけることができました。 特定の軌道のハザード積分に適切な値を追加することで、ヒット数が最小で跳ね返る可能性が高いものを選択できます。 これは、正確な物理学に関連する2番目のブレークスルーでした。 この戦略により、私はサンドボックスで10〜20位に上がり、最初のラウンドで3位になりました。



さらに、単にヒット/ミサイルのタンクへの侵入を決定するだけでは十分ではありませんでした。 砲弾が当たる角度を考慮に入れることにより、深刻な利益が得られました。 彼のおかげで、私は中距離での跳ね返りのほとんどを減らしました。 それから私は、フィールド境界の近くにいるときのシェルからの回避を改善するために壁との衝突を考慮に入れようとしましたが、衝撃中に送信されたインパルスについて物理的にばかげた結果を受け、この改善の実施を延期しました。

定数の選択

2回目のラウンドの1週間前に、コードのリファクタリングと最適化を行い、係数と複数の戦車を発射する同期システムを試しました。 同期システムはそれ自体を正当化しなかったため、その後、同期係数を徐々に下げて完全にオフにしました。 また、ターゲットを選択するときに敵の戦車の方向を考慮し、サンドボックスで1位になりました。 しかし、第2ラウンドでは、チーム戦での私の戦略が比較的弱いことが示されました。



状況を改善するために、私は危険フィールドを修正して、戦車が互いに接近しようとするが、接近しないようにし、アルゴリズムで最適な定数を選択する問題に真剣に取り組むことにしました。 これを行うために、任意の定数セットを使用して戦略を自動的に起動するシステムを実装し（ローカルランナーのリバースエンジニアリングにはud1、戦略を任意の組み合わせで実行するにはRun.classを使用）、遺伝的アルゴリズムを編成しました：異なる定数を持つ戦略のプールがあり、それらはペアで再生されますそれぞれと戦い、結果に応じて最悪のものが破棄され、最高の突然変異でコピーされます。 このような最適化の結果に基づいて、私の戦略は敵を積極的に攻撃し始めました。 集合的な心は、壁の衝撃の物理学にも対処しました。Phys2Dエンジンにエラーがあり、送信された運動量に対して受け取った不条理な表現は、現実に対応していました。 その結果、私の戦車はフィールドの境界の近くで振る舞うためにより有意義になりました。

正確な物理シューティング

しかし、これだけでは十分ではありませんでした。ファイナルまでは、時間はますます短くなりました。 そして、射撃システムを根本的に改善することにしました。ターゲットへの方向を選択する際に、敵の戦車の正確な物理を考慮するためです。 すべてのオプションを整理するにはリソースが足りないため、タンクが両方のトラックに同じパワーを供給する場合に限定することにしました。 これらのケースには、将来のタンクの可能な位置の主な範囲を定義する完全な前方および完全な後方が含まれます。 これらの場合、力の角運動量は存在しないため、すべての角量は共通であり、タンクの位置と速度のみが異なります。 さらに、位置は、2つのベクトル、たとえば、「フルフォワード」と「フルバック」の場合の位置によって設定できます（トラック上のパワーがゼロの位置と、ゼロからの「フルフォワード」位置の変位のベクトルがあります）。 他のすべての位置は、線形補間によって取得できます。



特定の時点でのタンクの可能な位置の範囲と、同じ瞬間の発射体の位置を知って、ヒットが発生するサブレンジを見つけ、時間と衝撃の角度に応じて、このサブレンジに特定の数のポイントを割り当て、次の時点に進みます。 可能な位置の全範囲にわたって積分すると、このシェルに対応するポイントの総数がわかります。 砲弾の可能な方向を確認し、砲塔の旋回時間を考慮して、最適な砲塔を見つけ、可能であれば砲撃します。 これは、正確な物理学に関連する3番目のブレークスルーでした。 更新された戦略は決勝戦の最初の部分で最初に行われ、休憩中に交差点を見つけることでバグを修正し、可能な限り広い範囲の位置をカバーするためにすでに飛んでいる発射体からのポイントを考慮し、敵の戦車がそれ自体を見つけるそれらの位置を破棄することでそれを改善しました障害物の中。



計画していたすべてを実装するために、ジオメトリに取り組む必要がありました;先に書いた長方形の交差点では十分ではありませんでした。 ランダムな方向の長方形を直線に沿って移動すると、この長方形が別の静止した長方形と重なる位置の範囲が見つかりました。 また、移動する長方形の次元がゼロ、つまり点である場合の特別なケースも個別に実装しました。



可能性のある位置の範囲にわたる統合は完全に簡単ではありませんでした。 タンクが既にヒットしている場所に火の密度を追加するのではなく、閉じていないセクターをカバーすることを好むために、ポイント数の低い値の積分への影響を強化し、電力変換によって大きなものの影響を弱めました：







ショットの最適な方向を検索するのは、単純な網羅的な検索ではなく、半分にする方法にやや似たアルゴリズムでした。 敵の戦車のビームの周りに等間隔でいくつかの方向を確認した後、私は最良のものを選択し、角のピッチを半分にして、発見された方向を確認しました。 この手順を再帰的に数回繰り返し、さらに銃の現在の方向を確認して、別の敵戦車に切り替えました。

未実現のアイデア

おそらく、私が欠けていた最も重要な改善は、敵に向かって横向きに自動的に戦車を向けることでした。 このシステムの欠如のため、私の戦車は長距離戦闘で比較的弱く、リスクがはるかに大きい突進をしなければなりませんでした。 私の体育は、スカラーの危険フィールドを四重極に置き換える、つまり、各ポイントに5つの円形高調波を保存するように促しました。 しかし、これは危険フィールドから選択する機能の5倍以上の速度低下につながり、私の戦略は利用可能なプロセッサ時間の制限ですでに実行されました。



別の未実現の機会は、空中のシェルの衝突を記録することです。 発砲時に他の砲弾を避けることだけに自分を制限することは不可能なので、ここで私を止めました。 敵の砲弾の十分な割合が自分の砲弾で脱出します。回避を追加すると、危険な敵の砲弾を撃つためのコードを記述する必要があります。



試合のウェブサイトで私のプロフィールで試合の記録を見ることができます。

戦略の最終バージョンのソースコードはこちらにあります 。

定数オプティマイザーのコードはこちらです。