AIカップを消化します。 5つのコードウィザード2016の戦略

12月、 ロシアのAIカップ2016は終了しました。毎年開催される人工知能プログラミングチャンピオンシップです。 明快さ、明快さ、シンプルさのチャンピオンシップはゲーム形式で開催されます。

今年、参加者はアルゴリズムを作成しました-MOBAゲームのゲーム戦略です。 結果として得られたボットは同じ種類の他のボットと戦い、それらのベストがラウンドに勝ちました。 したがって、一連のラウンドは、いくつかの段階で行われるトーナメントをもたらしました。

チャンピオンシップ終了時のメイン賞の配置は次のようになりました。

1. アントン・チュマチェンコ（モスクワ、ロシア）。 彼は1位を獲得し、MacBook Proを獲得しました。
2. Alexey Dichkovsky（ @DragoonXen 、Grodno、ベラルーシ）。 2位とMacBook Air。
3. マキシム・ポサジェンニコフ（ベラルーシ、バラノビチ）。 3位、Apple iPad Air 2。

参加者の2人は、RAIC2016-1、2に基づいて、すでにギーク誌に記事を投稿しています。

さらに、チャンピオンシップフォーラムには特別なスレッドがあり、参加者が戦略を書く経験を共有し、アルゴリズムのキーポイントについて話しました。 一部のアルゴリズムは非常に興味深いことが判明したため、急いであなたと共有します。 また、戦略を構築する上での主要な原則を説明する理解可能な記事もいくつか取り上げました。

ゲームのルールを知らずにゲーム戦略を検討することは非常に困難です。 ロシアのAIカップについて聞いたことがない場合は、最初の記事をご覧になることをお勧めします。 または、ネタバレの下をざっと見てください。

そして、参加者自身による興味深いアルゴリズム：

@tyamgin -Ivan Tyamgin、決勝で6位

私の戦略では、多くの場合と同様に、戦闘におけるポジショニングは潜在的な分野で機能します 。 これは私の心を越えた最も簡単なことです。 それはどのように見えますか：

（4倍の加速）

マップ上の各ポイントで、魅力的な（+）フィールドと反発的な（-）フィールドが機能します。 ポイント/セグメントまでの距離に応じた線形関数。 主なものは次のとおりです。

（-）敵のウィザード
（+）敵のウィザードが終了する
（-）敵の塔
（+）終了する敵の塔
（+）（-）敵のミニオンが近すぎる場合に退却し、接近戦のために駆け上がる
（-）連合軍ユニット：念のため、機動の余地がある
（+）敵の玉座の後ろに配置する
（-）ミニオンのリスポーンポイント
（+）ボーナスへの方向を示すポイント：ボーナスに向かってまっすぐ走るのではなく、戦闘中の危険ゾーンを考慮するため
（-）フォレスト（三角形を押すだけで、再びそこに行かないように）
（-）マップの壁とコーナー
（-）壁と塔に挟まれた場所

各ティックで、電位が大きくなるポイントへのオフセットが選択されました。 極大値に到達するのを避けるために私が思いついたのは、次のティックだけでなく、15ティック先（選択した方向）を考慮することです。 予測が遠いほど、影響は少なくなります（指数関数的にフェードします）。

パスを見つけるために、 ダイクストラのアルゴリズムが使用されました 。そのコードは年々行きます。 マップ全体には、サイズ80×80のグリッドが付いています。8方向（対角線に沿って、横に）移動できます。 木のあるリブは、これらの木の健康に比例して罰金が科されました。 さらに、パスが構築された後、グリッドへの分割の結果を除去するために「平滑化」され、カットされるツリーのリストが構築されます。

また、別の車線に移動し、森の奥深くに入ったときのペナルティ、途中の敵の数、最終的な位置も考慮しました（木の側ではなく、手下の列に立つことが望ましいためです）。

最初のラウンドでは、多かれ少なかれ既製のダッジが使用されました。 20を超える出発方向と、方向転換が必要かどうかを判断しました。 それが見えた-すべてが考慮されたが、後で私はすべてをさらに2回書き直し、ほぼ毎日バグと欠点を見つけました。 複数の砲弾または火の玉が同時に飛んでいる場合、合計ダメージが最小のリトリートが選択されました。

ポンピングのメインブランチはFireballになりました。 彼がリリースされる角度で整理し、どの範囲が彼にとって飛ぶのが良いかを決定しました。 また、連合国は新しくリリースされた火の玉に関する情報を受け取りました。 理論的には、これは通常の方法で行うことができましたが、「ダンス」で行いました。移動を四捨五入しました。

Rangeは2番目のブランチを揺らしましたが、フィナーレではRangeBonusPassive1、Hasteのみを行いました。

最終戦に0-5-0スキームを使用したくありませんでした。 私はスキーム2-2-1を試し始めました。 最終週の初めには、安定して勝ちました（Commandos、Antmsu、Recarを除く全員：50/50で）、これは長くは続かないことに気付きました。 0-5-0は入りませんでしたので、彼は何を開発することに決めました。 その結果、最終バージョンは1-3-1で、「状況に応じて」再構築されました。

→ コード

Antmsu-アントン・チュマチェンコ、決勝で1位

第1ラウンド。 ボーナスに加えてより広いラインを使用する方が便利であるという事実のため、私はセンターにのみ行きました。 戦略は潜在的なフィールドを通じて実装されていたため、ボーナス間の凍結を避けるために、それらのそれぞれに弱い引力が現れてから700から800ティックになり始めました。

ミニオン、敵と味方のウィザード、敵の塔とそのクールダウンの位置に応じて（これらの依存関係を直接考慮しませんでした）、ウィザードはボーナスを取る側の1つを選択しました。 約300〜400ティックの間、弱いボーナスがオフになりました。

ボーナス自体の近くで、ウィザードともう1つの同盟者がいたとき（敵がもっといる場合、最後のボーナスに行き、ボーナスは他のすべてよりも優先されると考えられたため、しばしば死亡しました）、小さな「キラー機能」を使用しました「：ボーナスと味方のウィザードの間のポイントで立ち上がって、彼が現れてボーナスに近づこうとすると、味方のウィザードとボーナスの間にある小さな半径に沿って移動しました。 より多くの同盟国がいた場合、それはもはや不可能でした。

また、最初のラウンドで彼は回避を実現し、その時点ではうまく機能していました。ほとんどのウィザードは正確に中央で撃たれ、発射体が横に飛んでいる間に逃げるのは簡単でした。 彼は敵の魔法のミサイルを見たときではなく、ショットの瞬間から走り始めました。

実際、撮影のより有利なポイントは、ウィザードの中心に向かって約7〜8ピクセル移動します（異なる方向の移動速度の違いのため）。 後に、（同じウィザード内で）撮影するのに最適なポイントを選択するために、敵のウィザードがショットの時点で横に立った場合のために、角度を中心から数度±+から始めました。

ある時点で、上位30のサンドボックスの多くが回避し、ショットの時点で多くがマジックミサイルを回避し始めていることにも気付きました。 最初に、かわすためにダニに早く走る人としない人を統計情報を収集したかった（move.speedで発火ポイントをシフトする価値があるかどうかに依存する）。 しかし、彼はよりシンプルなソリューションを思い付きました。それは、マイクロでこのような利点を提供するチップでした。 その瞬間、敵の魔法使いを撃つことができたとき、私は撃ちませんでしたが、1ティックを待ちました。 ほとんどの場合、これにより、次の瞬間の移動方向を推測し、少し離れた距離からウィザードを回避することになりました。

また、最初から戦略のビジュアライザーを書いたので、デバッグなしでははるかに時間がかかります。

2回戦。 Fireballスペルは、時間単位でダメージを与えるという点で否定できない利点がありました。また、非常に遠くにいる場合にのみ回避できます。 また、最初のラウンドから、私は手先との緊密な戦いを実施したので、このブランチは他のブランチと比べて完璧でした。

したがって、敵の本館は、敵がやったよりも平均して少し速く破壊されることが判明しました。 この呪文を使うことだけを学んだとき、私は42ゲームのうち35ゲームで勝ちました（10 * 1 +モードで）。 もちろん、非常に多くの人がこのブランチを選択し始めましたが、利点はほとんどありませんでした。

そして残りは、彼がより頻繁に死なないようにボーナスをより慎重に始めました。さらに、ゲームの開始時に、彼は最も速い経験のために同盟者が少ないラインを選びました。 当時のマイクロはまだ決まっていないので、ライン上の敵の数値的優位性を持つ開発の別のブランチを選択しませんでしたが、これはラウンドでもう少しポイントをもたらすでしょう。

基地を守る価値があるのか​​、敵の基地を伝えるほうが利益があるのか​​、またどのタワーが発射されるのかを判断するために、ほとんどの時間をマップ上のすべてのユニットのシミュレーションに費やしました。

シミュレーションは迅速かつ多かれ少なかれ正確に機能しましたが、十分ではありませんでした。最終的には、ミニオンをリードしてFireballを投げて最大のダメージを与えるためだけに使用しました。

ウィザードの動作を終了しなかったという事実により、不正確な点が現れました。 それに加えて、バランスは守備に行くことはめったに有益ではないことが判明しました。 また、このシミュレーションは、大規模な戦闘で前進するか撤退する価値があるかを予測するために使用できます。 実際、これはそれほどリソースを必要としない方法-ライフの有効数、ショットのクールダウン、オーラ、キャラクター特性を考慮した影響マップ-を使用して解決するのは悪くありませんが、私はこの方法をフィナーレまで実装することができました。

フィナーレ。 最終日まで、真ん中の5位に行きたくなかったので、1-3-1を試しました。 活発なラッシュに対して、私は側面に沿って通過する時間を最小限に抑えようとしました（ここでは乱闘の枝が最も収益性が高かった）。

決勝のほんの1日前に、最初から戦略に存在していたいくつかの欠点を修正することができました：大量の乱闘に沿って立ち、すべてのウィザードと一緒にボーナスを求めず、高速で正しく移動し、敵ユニットの速度オーラの効果を考慮して解雇時に逃し、余分な木を切ってはいけません。

これらの修正により、5×5はうまく戦うことができ、さらに、係数が異なるためにマイクロがわずかに改善されました。 私は1つの特徴にも気付きました：建設が広くなるほど、平均して戦闘を行うことができましたが、これはおそらくチームがターゲットの選択を認識せず、1人の敵ウィザードが私の5人をちょうど1人のように恐れていたためです（ほぼ敵の距離+ 20の距離に保たれます。

「人工的に」私は、自分と並んでいる敵ウィザードの数に応じて攻撃性のレベルを上げました。 ファイナルの第2部の前は、マイクロでナイツを倒すことができませんでした。そのため、いくつかの条件の下で、ウィザードの1人で、敵の建物を5人の敵のウィザードが中心線に沿って押すよりも速く敵の建物を破壊することを期待して、別の行に行きました。

しかし、最終的にはバグが発生しましたが、幸運は私の側にはありませんでした。なぜなら、NighTursと同じバージョンのファイナルの前にはスコアが5：0で、ファイナルでは1：4がNighTursに有利だったからです（ファイナルの後-再び私の好意で2-0）。

決勝後、喜びに満ちた勝者はいませんでした。戦略は理想とはほど遠いようで、2位と3位の差は非常に小さいため、勝利は主に運によるものでした。

そして最後の「キラー機能」：大学時代、DotAをたくさんプレイし、それが得意でした:)もちろん、ゲームのスキルは競技の開始時にのみ関心を高めたため、この機能について冗談を言いました。

@ m0rtido-アレクサンダー・キセレフ 、決勝で12位

アルゴリズムの基礎は潜在的なフィールドです。私たちは自分自身の下で+の周りの32ポイントを見て、最適な方向に進みます。 最初は、ポイントは同じ距離ではなく、最大のステップで取得されましたが、同じ方向に（グラデーションの方向ではなく）向きを変え、ボットは斜めに進むのを非常に嫌がりました。 その結果、私は常に反勾配の方向に進み始めましたが、今はそこに曲がるだけで、最大のステップでアクセスできる最高のポイントに行く必要があると思います。

歩くときにローカルミニマムに落ちないように（戦闘でオフにした）、彼は過去の位置に「丘」を追加しました。 ビデオから取ったアイデア：

原則として、合計で4つのタイプのフィールドがありました。現在の「ターゲット」（ウェイポイント、ボーナス）、「障害物」-フィールドはそれらの近くで急速に成長しましたが、遠くではほとんど成長しませんでした。 最後のフィールドは「ターゲット」フィールドをオフにし、ターゲットの位置とリトリートポイントを考慮した（森にぶつからないようにする）unningな公式でした。

危険度はすべてのユニットで異なる方法で計算されましたが、私の速度、そのcd、攻撃範囲、現在のミニオンターゲット、現在のタワーターゲット、マジシャン、ターンタイムを考慮に入れました。

T1-後退地点、T2-到達する目標、およびその危険性

多くの人がそうであるように、最適化のために私は世界を「切り刻み」、大きな障害物とオブジェクトのみを残しました。

ウェイポイントとダイクストラのアルゴリズムに行きましたが、チームと「所有者」の「影響力」を持つポイントにアップグレードしました。 ポイントを獲得するには、一定の強さで一定の時間、そのポイントに影響を与える必要がありました。

ダッジ：最も興味深いと問題がある。 3つのバージョンがありました。

最初のバージョン。 潜在的な分野では、彼はすべての将来の発射体の位置に反発的な危険領域を追加しました。 主な問題：2つの発射物があなたに向かって飛ぶ場合、魔術師は真ん中に上がり、両方を捕まえます。

2番目のバージョン。 32方向の出発をモデリングし、回避/代替/休息するまで静止し、ダメージの少ない場所に着きます（氷のダメージを増やしました）。 彼は残りの方向を潜在的なフィールドに沿って歩く機能に与えました-そして、第2ラウンドの終わりまでとても楽しく生きました。

主な問題は、まだリリースされていない発射物を評価しないことです。 マジシャンからの危険なフィールドでさえ、カーストの範囲を考慮しましたが、私が非常に速いなら、私は近づいて、まだすべてをかわすことができることを考慮しませんでした。 次に、このバージョンの回避を使用して、敵を撃つかどうかを評価しました。 「確率的」MMを世界に追加する前のダメージがその後よりも少ない場合、私は撃ちました。

それから彼は、次の5ティックで撃つ準備ができている同盟ウィザードから発射物を追加し始めました。 これにより、グループでの撮影の精度とcさがわずかに向上しました。 彼は中央ではなく、すべての方向に同時に走った地点で撃った。

public static V2d getShootPoint(V2d aimPos, V2d aimAngle, double projectileRadius) { return aimAngle.copy().mul((projectileRadius + 35.0d) / 7.0d).add(aimPos); } 

3番目のバージョン。 発射物のコレクションには、次の50ティックで魔術師が解放できるものが追加されました。 各方向について、彼らは独自に生成したので、魔術師は常に最も不快なポイントで撃ちました。

次のようになりました。

• 最初、彼は32（+1）方向のすべての実際のシェルをかわすことを試みましたが、動きながら「確率的」なシェルを作成しました。
• シェルがこの方向に私を襲った場合、彼はダメージを追加しました。
• タワーフィールドに着いて、そこにいるターゲットで、cd = 0-タワーからさらにダメージを加えた場合。
• 単一のシェルがもう当たらない場合は、この方向から、すでに「確率的」なシェルの32（+1）方向で新しい検索を開始し、すべてのシェルをかわすか、障害物に遭遇しました。

シェルが飛ぶ距離にわたって指数関数的に減衰する「確率的」シェルの損傷を追加しました。その結果、時間の経過とともに魔術師が近づきすぎた魔術師から逃げ出し、「何が違うのか、何が起こるのか、国境の安全なエリアから1ピクセルある」とは思わなくなりました。

これはプロジェクトの中で最も困難で最も松葉杖の部分です。多くのことを編集し、仕上げて、余分な恥ずかしさを取り除き、いつ撃つことができるかを確認し、100％回避する必要があるときに確認しなければなりませんでした） マジシャンがわずかに走ることができるという事実に松葉杖を作ります。

ウィザードの危険フィールドを削除し、さらに接近してショットをかわすことを可能にした3番目のバージョンがあります（まだ撮影されていないものでも）。

これがおそらくアルゴリズムの基礎です。 もちろん、ダニの束がありました、3回目の回避、定数のエラーとバグの数に間に合いました、定数のいくつかのバグは、私が文字通り即座に10-20位高くなりました（トップ100で）。

@ivlevAstef-アレクサンドル・イヴレフ、第2ラウンドに行った

従来、アルゴリズムを2つの部分に分割します。

アルゴリズムの最初の部分は、障害物をバイパスすることです。 2番目の部分は最初の部分を使用しますが、木を切り倒してパスの長さを推定する問題を解決します（最初の部分は回避できましたが、ポイントまでの距離を推定できませんでした）。

最初のもの：
実際、これはパスの検索ではなく、障害物の定性的な回避です。 アルゴリズムは、関連するオブジェクトのグループとそれらの接線を中心に構築されます。

ビデオを見ると、木々の間に紫色の線がたくさんあることがわかります。 これらの線はアルゴリズムには存在しませんが、グループを視覚化するために作成されました。 ビデオの冒頭と、魔術師が森に入る40秒の時点で、「左」の森に2つの大きなグループがあり、その間に魔術師が40秒で通過することが非常に明確です。

グループ構築アルゴリズム

多くのオブジェクトと多くのグループがありますが、最初は空です。

多くのオブジェクトからオブジェクトを取得し、それが1つのグループ（グループのオブジェクトの1つに近い場所にある）に該当するかどうかを確認し、そこに追加します。 複数の場合、これらのグループを結合して、新しいオブジェクトを新しいグループに追加します。

次に、現在の目盛りのどこに移動するかを決定します。 入り口には、多くのグループ、魔法使い、私たちが来たい場所があります。 私はこのアルゴリズムをいわゆるレイスローと呼びますが、実際にはこれらはレイではなくセグメントです。最大長です。

まず、来たい場所にビームを投げます。 グループ（グループからのオブジェクト）との交差点を見つけます。これは最も近いものです。 グループのすべてのオブジェクトを調べて、グループの各オブジェクトの両方の内部接線を検討し、現在のビームから最大の偏角を与えるものを見つけます-2つ（左側に1つ、右側に1つ）があります。

さらに、マジックロジックに沿って（アルゴリズムの最初のバージョンでは、2接線の選択関数は困難でした。最小の偏角を与えるものを選択するのは非常に悪いためです。グループの端に近づくと、この角度はしばしば最大になります）、2つのいずれかを選択します。 連絡先（ただし、マジシャンの半径を考慮に入れる）は、移動先の新しいポイントになります。 その後、再び交差しているグループを以前に削除して、新しいポイントにレイをキャストします。

最初のアルゴリズムにはいくつかの欠点がありました。 私はこの関数が好きではありませんでした。 ポイントまでの距離を推定できませんでした。 木を切り刻まなかった。

2番目のアルゴリズムは同じ関数を使用して障害物を回避しましたが、その前に、近似経路を計算し、そこから木を削除しました。

最初は、リーアルゴリズム （波）を使用して、マップ全体に自分から波を作成しました（マップは125×125のグリッドで表されます）。 建物と手先は通行不能と見なされましたが、樹木は、それらのXPと中心からの距離に応じて、通過価格が高騰していました（樹木は同時に複数のセルに落ちる可能性があり、これらすべてのセルに同じ重みを付けることは非論理的です）。

Leeアルゴリズムに精通している人は怒ります。このアルゴリズムはパスを探す方法を知っていますが、移行価格を考慮しておらず、正しいでしょう。 このため：
a）地図全体で波を数えました。
b）アルゴリズムはダイクストロイとわずかに交差しています。 実際、グラフが2D配列として表示されるリーではなく、ダイクストロイと呼ばれることもあります。

一般的に、これがリーまたはダイクストラであると言うことは困難です。なぜなら、ダイクストラからの迂回を使用したが、最適化を行ったが、リーについてはデータを保存したからです。

その結果、マップがあり、任意のポイントからマジシャンへの最適なパスを見つけることができます。 ティック中にいくつかのパスを見る必要がある場合があるため、これは各パスのすべてを再計算する必要がある*と比較して利点もありました。 また、完全な最適化のために、カード自体を60ティックごとに更新します。 セルが60ティック以上変化した場合（常に数回発生します）、クイックアップデートを使用しました。以前のセルは太りすぎで、新しいセルは過小評価されていました。

次のステップは、パート1と交差させることです...簡単です。パスを取り、半径300の円で交差します（最初に600だった理由を覚えていません）。 交差点は、障害物のバイパスを検討する点です。 解決策は、方向ベクトルから最小変位角をとることが可能になったため、古いバイパスアルゴリズムを簡素化するのに役立ちました。ベクトル自体は短く、どこに行くかはすでに示されていました。

最後の段階はロギングです。 入り口には、小さな長さのセグメント（125×125のグリッドに基づいて構築された）の形で提示されたパスと、多くの木があります。 目的：迅速に切り倒すことができ、回避することができず、パスが通過する（または通過する）ツリーを見つけること。 アルゴリズムは単純ですが、バグがあります-時々、あまりにも多くの部分をカットします。 私がそれをしたとき、私はすでに書かれたものの完全な無意味さを認識し、理想に追いついていませんでした。

アルゴリズム：パスをたどり、現在のセグメントに最も近いツリーを見つけます。 このツリーは実際に私たちに合っていると確信しています（バイパスすることはできません）。 これを行うために、私たちは比ative的に競技場を2つの部分に分けます。パスの一方の側ともう一方の側です。 パスの反対側に属するツリーがあり、2つのツリー間を通過できない場合は、現在のツリーを破棄する必要があります。

問題があります。パスがツリーの中央付近を通過する場所では、結果としてツリーがパスの半分になることはありません。 その結果、彼は致命的ではなかったため、この問題を解決しませんでした。

なぜこのすべてが機能するのですか？ パスが構築されると、ツリーの半径が価格に非線形に影響するようにパスが通過します。 したがって、切り倒しやすい木は、まるでそこにあるかのように評価され（非常に小さな価格）、大きな木はほとんど通過できないポイントに匹敵します。 そして、木の重さは時間の経過とともに消えていくため、ほとんどの場合、パスは木の間を通りますが、小さな木に近づきます。 これにより、ログハウスの下に小さなツリーが選択されます。 バイパスはグローバルではなくローカル（半径300）になり、グループを検索するときに切り倒す必要があるツリーを削除するため（障害物回避をグループなしで計算できるように）、アルゴリズムの最初の部分はさらに美しく表示されます。障害物を何キロメートルも回ります、彼女は今ここでそれらを回ります。

ビデオでムーブメントのほぼ最終バージョンを見ることができます：

しかし、実際の生活では、すべてがそれほど良いわけではありません。 森の真ん中で走る場所が変わることもあれば、クリープが追いかけてくることもあります。森を切り倒すか、クリープを打ち負かすか、その他多くの小さな要因を選択する必要があります。

→ コードへのリンク

パス検索はAlgorithms / A_PathFinderファイルにあります。 障害物回避-アルゴリズム/ A_Moveで。 グループビルディング-環境/ E_World。
さまざまな2D数学-共通/ C_Math。

そして、オリンピアードの反対側についてのいくつかの言葉-時間について：

• 最初の週-26時間;
• 2週目-26時間;
• 3週目-27時間;
• 4週目-34.5時間;
• 5週目-38.5時間;
• 私が採点した6週目には、わずか10〜10時間しかありません。
• 先週-8時間。

合計：170時間。

途中、私は殺した：49時間。
多かれ少なかれ通常の状態（約70クラス-C ++で140ファイル）でアーキテクチャを維持するには：28時間。
回避：26時間。

その他：67時間-バグ修正、オッズ調整、その他の退屈なこと（ライン選択、ハザードマップ、攻撃するタイミングと逃げるタイミングの理解）。

ALEXks-アレクサンダー・コルガノフ、第2ラウンドに行った

コンセプト：条件と現在の状況に応じて戦略が進むことができる一連の状態に基づいていました。 そのような状態には、ボーナスへの移動、攻撃、タワーの仕上げ、攻撃の回避などがあります。各状態は他の状態に影響を与える可能性があります。ほとんどの場合、状態のアクションをブロック（キャンセル）します。 コードは実際には線形であるため、すべての状態が毎回単純にチェックされ、条件に一致する状態がアクティブ化されます。 たとえば、私たちがラインにいて、ボーナスを取る時間である場合、時間に加えて、さまざまな条件がチェックされます：次の前線がありますか、利点がありますか、ボーナスを残すことができるゾーン内にいますか、またはベースを運ぶ。

いくつかの間違い：おそらくそのような大量のプロパティのために、詳細な実装の時間は本当に十分ではなかったので、ほとんど最後の瞬間まで、動きは非常に不器用でした：クイックスタート戦略からのキーポイント+後退する能力が、その後修正されました。

何らかの理由で、キャストの距離を超えて、さらに遠くにダメージを与えることができるとは思いませんでした。 2回目のラウンドの開始のほぼ前に、多くの人はこの事実を考慮に入れず、すべてがOKでしたが、その後、私の層が失われ始め、私は遠くから攻撃することが可能であることに気づき始めました、そしてフォーラムのどこかでもそれが聞こえました。

移動：主なポイントは再帰関数であり、深さ7×6およびしきい値25％まで6ティックを計算できます。 一番下の行は、グリッドに沿って私たちの周りの最大距離まですべてのステップを通り、長辺に沿って7ステップ（前後）と短辺に沿って6ステップ（左右）を行い、この位置を評価します：その上に立つことができますか？罰金とボーナス-これはまさにPPの使用がある場所です。 次に、しきい値で、評価関数によってこのポイントのセットをフィルターで除外し、残りのポイントに対して再帰を繰り返します。 評価関数は、距離、敵の攻撃、攻撃前のクールダウン、木の半径に応じて線形です-立ち往生しないように連合軍のミニオンを考慮する試みさえありました。 また、他のすべてのユニットの動きも6ティックでシミュレートされますが、再帰手順が開始される前に記録された同じ方向および同じ速度です。 木も罰金を与えました。 周囲に敵ユニットがいなかった場合、時間を節約するために計算ミスが簡素化されました。

上記のいくつかは、ネストと複数の距離計算のために、再帰は長いプロセスであると書いています。 プロファイラーを介して、この手順ではhypot（x、y）関数が常にかかることを確認し、ネット上でグーグルで調べると、単純なsqrt（x x + y y）よりもはるかに長く（約40倍）動作することがわかりました。 座標が0〜5000の範囲にあるこの場合、hypot関数はまったく必要ありません（hypotがsqrtよりも優れている理由を自分で調べることをお勧めします）。 そして最終的に、可能な場合はルート抽出を中止することを決定し、それによってすべてを平方和に転送しました。 結局のところ、ユニット間の距離でさえ、ルートを計算せずに推定することができます：二乗の合計で十分です。 乗算と加算はルート抽出よりも高速です。その結果、かなり詳細なグリッド（またはツリー）で6〜7ティックをカウントすることが可能になり、最後のレベルでは3〜6ポイントになる可能性があります。

唯一のマイナス-私は木々の間の局所的な最小値にいることができ、しばしば動けなくなる。 その理由は、木自体への許容距離が近すぎることと、再帰関数のティック数が少ないことです。 私はこれに苦労したことはありませんでしたが、私の魔術師が将来彼に干渉する可能性のある木を破壊することを確認することにしました。

最初のラウンドの後にバランスを変更した後、私はトップ30〜50のエリアにとどまりました。 5×5の戦いでは、多くの戦術も試しましたが、中央の5で止まりました。 しかし、再び、相手のより正確な評価が欠けていました。 罰金は、上位20社には粗すぎました。

奇妙なことに、なんらかの理由で、私は敵にオンラインで攻撃させ、攻撃範囲と速度を高速化させないとプラスになるため、火災は最善の選択肢ではないと判断しました。 私は、スピード+フリーズ、および射撃+射程の両方を通して、さまざまな戦術を試しました。 それらはすべてコード内にあります。 5×5の場合、範囲+速度に1つのメイジをダウンロードし、残りを射撃しました。

コードへのリンク （なんらかの理由で、このプロジェクトでこれだけでロシア語のコメントを書くことにしました;そこにはかなりの数のコメントが付けられており、非常に簡単に理解できると思いますので、C ++で書いてください）。

ロシアのAIカップは終了しました。 次は？

現在、 ML Boot Campプラットフォームで一連のMLチャンピオンシップを実施しています。 初心者からプロまで、誰もが参加できる場所があります。 初心者向けに、機械学習に関するトレーニング記事とプロを提供します。これは、私たちの課題に関する深刻なテストです。 数週間で次のチャンピオンシップにご参加ください ！

Mail.Ru Groupが主催するすべてのチャンピオンシップに関する最新ニュースは、 公式電報グループにあります。