ロシアのAIカップ2016年次大会への参加（およびほぼ勝利）の歴史

こんにちは、Habr！ 私の名前はアレクセイ・ディチコフスキーです。DotAの簡易版のボットを書くのに1か月半費やしたことについてお話したいと思います。

毎年、Mail.ruはプログラミングゲーム戦略に関するオンラインチャンピオンシップを開催しています（ ロシアAIカップ2016 ）。 私は2012年（CodeTanks）にこのコンテストに参加し、2013年（CodeTroopers）にかなり参加しました。 今年、ウェブ開発にかなりうんざりしていたので、私は再び参加しようと決心しました。 私は当初、賞を獲得することを望んでいませんでした（もちろん、本当にやりたかったのです）。 あなたは猫の下でそれから来たものについて読むことができます。



私がrussiaaicup.ruのサイトで今後の競争の発表に気づいたのは偶然ではありません、私は準備を始めました。 以前に参加したことがあるので、カスタムビジュアライザーのテンプレートは私にとって非常に便利であり、競技自体の時間を節約できると思いました。 全体としての準備はすべて、独自のビジュアライザーを作成することで構成されていましたが、当初はいくつかの基本的な形状のみを表示できました。

RAIC 2016の開始日である11月7日、私が最初にしたことは、 ルールを公​​開し、今年開催者が準備してくれたものを読むことでした。 土田？ まあ、それはできません...はい、間違いなくDotA！ ルールを読んだ後、私はたくさんのコードを書かなければならないという強い気持ちがありました...たくさん。 そして、最初からこれを知っていたからといって、インスピレーションはあまり得られませんでした。 また今年は、コンテストの開始が妻の誕生日と一致したので、開発の開始を1日延期しなければなりませんでした。なぜなら、翌月半はPCのために選ぶのが難しいからです。 おそらくこれは、このコンテストでボットがどのようになるかをもう少し正確に理解するのにも役立ちました。 当初から何らかの計画を立てていたので、それに従いました。

最初の週、または「私は何に興味を持っていますか？」

最初の3晩はプロジェクトを作成し、攻撃するラインを引き締め、3つのラインのうちの1つを選択しにくい（ゲームの開始時-クイックスタートガイのように-死後、主催者が提供する基本戦略-より多くの敵がいる場合） ）、およびビジュアライザーをねじ込むだけでなく、その「スケルトン」はRAICの1週間前に作成されました。 さらに、どうにかして歩く方法を学ぶ必要がありました...多くのジオメトリを扱うのはひどく面倒でしたが、私はまだ手下、魔術師、木の間の「ギャップ」に潜り込みたかったのです。 私は他の選択肢を思いつきませんでした。地元の「グリッド」を作り、それに沿って歩くことができ、同時に、ある時点または別の時点にいることの危険性と有用性を計算することにしました。


ゲームカードのレイアウト。 敵の基地（上/下/中車線）を攻撃する価値のある線は、森によって互いに分離されています。

金曜日と週末は、それが価値があるかどうかにかかわらず、このビジネスに関与するかどうかを熟考するために過ぎました...しかし、それでも、日曜日の夕方までに、動きのある何かが実現しました。 グリッドの最初のバージョンは、401 * 301ポイント（バトルラインに沿って前方に600、側面に300、後方に200の距離）を測定する2単位でした。 このグリッドの各ポイントでスコアが計算されました-「発見の有用性」から「存在する危険」を差し引いたものです。 最終バージョンでは、グリッドセルは多くのフィールドで構成され、手下からの危険、魔術師からの危険、建物からの危険、敵を攻撃できるゾーンにいることの有用性を考慮しました（それぞれ、最高の価値のみが考慮されました）、障害のある敵の周りのエリアにいることの有用性（殺すための経験を得るため）と追加の2つの変数otherDangerとotherBonusは、ボーナスを集める、場所に危険なゾーンを作成するなどのケースの松葉杖を実装するため e忍び寄る敵の出現、森への不必要な出発の防止、地図の隅への運転など。 私はそのような行列を移動するたびに再作成したくなかったので、その座標を更新すると（マジシャンと一緒に移動した）、これらの値はすべてリセットされました。


マトリックスの元のバージョン。 マトリックスの前端までの距離は600「ピクセル」です。 右と左-300、後ろ-200。ポイント間の距離-2.マトリックスが大きすぎることが判明しました。 マトリックス自体のポイントの数は401 * 301です。これは、メイジの向きに関係なく、常にバトルラインに沿って方向付けられます。

ローカルランナーでの起動は、私のアプローチの動作が遅すぎることを示していました...競争の状況に応じて、戦略の各ティックに10ミリ秒が割り当てられ、ローカルマシンでの測定によると、大幅に多くなりました。 世界を必要な最小限にフィルターしました：私のローカルグリッド、ツリーまで600の距離にあるリビングユニットとタワー-計算ではそれらを障害物として考慮しましたが、「余分な」ツリーはできるだけ追加しませんでした。 さらに、グリッドのステップを3に増やし、必要なパフォーマンスに近いパフォーマンスを得ました。 最適化は依然として必要でしたが、私は初めてそれで十分だと判断しました 。 それにもかかわらず、ほぼ一週間がすでに過ぎていて、私は自分の何かを戦場に投げ入れたかった。 彼が移動していたポイントは、スコアの値によって、マトリックス上のポイントの中で単に最良のものとして選択されました。 リブの重量は距離ではなく（2番目の要因として考慮されていましたが）、優先ラインの検索を手配しましたが、そこにいることの有用性を考慮せずに、敵チームから顔を叩く危険性がありました。 このアプローチでは、短いものの、ボットがマトリックスのポイントに沿ってしか歩くことができなかった場合、壊れてしまい、急速な動きを大きく妨げるようなパスが見つかります。 パス全体に沿ったバイナリ検索によってこの問題を解決し、ポイントから目的の場所に移動する機能を確認しました（ビン検索を開始する前に、パスのエンドポイントの到達可能性を確認しました）。 T.O. 途中に障害物がない場合、ボットは単に目的地に直行しました。

まあ、私たちは歩くことができます、私たちは敵の魔術師と手先を少し恐れることができます...しかし、戦いはどうですか？ うーん...目標リストを作成し、それらがフィルタリングされて木が射撃の妨げにならないようにしました（目標がツリーのすぐ後ろにある場合は明らかに十分ではないため、危険グリッド上の障害物としてカウントされるように木がフィルタリングされたことを忘れてしまいます）、目標に依存する優先順位を設定します残りの％hp目標から。 初めて、魔術師と塔の優先度は手先の優先度の5倍と6倍でした。 次に、ボットにショットのために回転するように教えます-現在の位置から撃つことができ、リロードする前のティックの数がすでにターゲットに「回す」ことができる寸前にある場合-ターゲットに向くか、そうでなければ移動の方向に回します

ローカルランナーでのテスト。

ロケールランナーと協力して、私は悲しみに気づきました-すべて同じですが、パスオプションはあまり適していません...「危険な」ゾーンを離れるとき、私たちはすぐに最適なポイントまで走ろうとしますが、あなたは単純にミニオンの影響から逃げることができます（ミニオンの速度は魔法使いの裏面の速度に等しいそして横向き）、あなたが彼から厳密に走る場合。 敵の手下から逃げることを学ぶ-今、私たちは直線ではなく終点までではなく、経路上のそのような中間点まで走ろうとしています。その危険は、私の魔術師の現在の点の危険よりも顕著に小さいです。 移動先のポイントの検索を変更しました-すぐには選択されませんが、ターゲットポイントスコアに加えて、途中で直面する危険性を考慮して、マトリックス全体でパスが検索されます。 この段階では、すべての危険の合計* 0.02でした（最初から最後までのすべての係数は目で選択され、ほとんど変更されませんでした）。

ランナーロケールで新しいパスの選択とより詳細なテストを実装した後、 悲しいことに悪い考え（RAIC）を残すと思いますが、コードが再び時間枠に収まらないことに気付きました。 Javaコードプロファイラーをオンにすると、パスの検索は非常に多くの労力を費やしますが、主な負荷はマトリックスの各ポイントのスコアを計算していることです。 確かに、マトリックスの各ポイントについて、このユニットからの距離が計算され、すべてのユニットに対してチェックが実行されます。この距離がこのユニットが私のマトリックスに影響を与える距離よりもはるかに大きい場合でも...うーん。 彼は、グリッド座標の更新とは別のサイクルで危険の計算を取り出し、グリッドポイントのスコアにユニットの影響を適用するための構造を作成しました。 ユニットからマトリックスの次の行の各ポイントまでの距離を計算する前に、ユニットから、この線の端であるセグメントまでの距離を確認し始めました。 ユニットがハザードマトリックスの特定の行のポイントスコアに影響を与えないことが保証されている場合、単に行全体をスキップします。 そして、この最適化により、ローカルでの制限へのかなりの投資がすでに許可されました。 これはすべてひどく曲がっているように見えましたが、どういうわけかうまくいきました...

それでも、おそらく、ボットは最初の戦いの準備ができていません。 近接戦闘では、メイジはスタッフとの試合を選ぶことができず 、木は乗り越えられない障害物であり、敵の魔術師と手下は絶えず私を森から追い出しました...近くに誰かまたはぶつかることができるものがあるかどうか、そして今すぐショットを回す必要はありません-スタッフで打ちましょう。 木をまったく撮影したくないという問題を修正します（ただし、ショットの優先順位は0に設定されていますが、他のターゲットがない場合）。 行の中心から離れるとペナルティが追加されます。ポイントをカウントするマトリックスを大幅に削減し（前方351、後方および150の距離になりました。サイズは動作にあまり影響を与えなかったようです）、最初のバージョンは戦闘に入りました！

悲惨な光景、悲痛な光景...魔道士は敵の魔道士が近づくと硬くなり（検索マトリックス全体が危険になりすぎるため）、手先が彼をつまむと、立ち往生し、地図の端を越えて逃げようとし、地図の隅に逃げ出します。 1.2kティック後のベース（リバイバルタイム）...マップの端に近いポイントにいることに対するペナルティを追加することでこれらの欠点をすべて修正し、マップの端を障害物として追加し、どこでも非常に危険な場合にumb然としたものを削除します（危険の合計は魔術師のHPよりも大きい）。 これはすべて少し助けになり、今では、効果はまだあまり良くありませんが、どうにか生きることができます。 それまでの間、トップはすでにボーナスのために走り回っています。

必要なことではなく、何かをするためにボーナスを求めてボットに教える方法。

まあ、私はボーナスのために実行することを学ぶ必要があります...彼らのために多くのポイントを与えます。 しかし、それはどのように明確ではありません。 そもそも、スピードを最大限に活用する方法を学ぶことにしました...同時に、私は未来をつかむことができました-私たちはすべてのオーラとパッシブスキル、HASTENEDステータス（加速）を考慮することを学んでいます-そして今、ミニオンが突然私をボーナスに押し込んだ場合、私はより速く走ります！ その後、他のライバルとの戦いを見た後、私は常に敵の塔に落ちていることに気づきました...そして、彼らのショットの1つはHPマジシャンの3分の1以上です。 世界での位置を追加し、次のショットまでの時間を思い出しました。 同時に、彼はタワーをリロードするとき、私の魔術師が少し近づいたようにそれを作りました。 私たちはまだ手下からひどく逃げています、なぜなら グリッドに従って厳密に実行します。その方向は、ミニオンから逃げるべき方向とほとんど一致しません。 その結果、私のボットは「わずかに斜めに」ミニオンから逃げ出し、後者は厳密に私に向かっているので、ギャップは絶えず減少しています。 解決策-ボットが移動する価値があると考えている方向（1つのステップのいくつかの方向の局所検査を追加しました（追加で考慮できるウェイ+角度の最も近いポイントへの方向）。これは、ポイントでポイントを計算するための構造が役立ちます。 まず、このセットからポイントを選択します。まず、自分自身で見つけるのが非常に有用であり、次に、目的の移動方向に近くなります。通常は、「一歩前進-横に一歩」という原則にとらわれることなく、美しい円に沿って危険なエリアを歩くことができます、そして今、あなたは一直線にずっと効率的にミニオンから逃げることができます。 また、敵のミニオンが出現する前に一定の時間、敵のミニオンが出現するゾーンからの危険性をマトリックスに追加します。これにより、敵のミニオンが環境内にいなくてもそこから離れることができます...

（クリック可能なgif内）


ビジュアライザーのスクリーンショット。 装飾された長方形の中央の端から少し離れたところにある緑色の円（踏み込めない「白い」ゾーンがない）は、戦略によって制御される魔術師です。 赤は敵で、緑は敵です。 私の魔術師の中心からの青いギザギザの線は、私たちが今進んでいる方法です。 魔術師の中心からの黒い縞-最適なステップを選択しようとするときに考慮される角度。 ピンクは現在取られる可能性が最も高い方向です。 赤-次のステップで選択された方向。

Neo mod。

土曜日の朝に目を覚ますと、彼はボーナスを用意することに決めましたが、ボットがトップ100に達したことがわかりました。そこで、彼らは突然、中心ではなく、私のメイジの端で、ほぼすべての格付けバトルで残酷で自信を持って撃ち始めました彼が何かに答えるまで彼をhimりました。 しかし、私もこれをやりたくありませんでした。 彼らはまだ回避する方法を知らないが、彼らはすぐそこにいるだろうが、私はそこに行きたい...計画は私の心にシンプルで同時に複雑に思いついた-しかし、私はそれを同じようにしないだろう、私はちょうど飛ぶそれらの12ティックの利点を試す発射体、あなたはかなり自分自身を残すことができます...彼らが中心で撃つならば、魔術師の速度は十分ではありませんが、それはそのような問題から助けることができます。

最初に、すべてのシェルの外観の目盛りを覚えておく必要があります。これにより、後で各シェルが最大値に達する場所を計算できます。 最終的には、全体として、同盟国からのすべてのショットを無視することが可能になりますが、最初の2ラウンドでは、あまり同盟していない魔術師のショットを無視する価値はありません。 なぜなら ポイントでの競争も同じチーム内で機能し、「同盟」した魔術師もしばしば自分たちで仕上げるのが好きです（燃えるような挨拶mortido ）。 次に、静止している場合に発射物が私と交差するかどうかを確認します（発射物の飛行間隔までの距離は、魔術師と発射物の半径の合計よりも小さく、これに追加の距離が追加され、誤って発射物の下に踏み込まないようになります） 。 少なくとも1つのシェルが私を襲う場合は、かわすようにしてください。 まず、ボットが静止している場合にボットがどれだけ「キャッチ」されるかを計算します（シェルを踏むのが怖い場合のオプション）。 この基本的なダメージを最初のダメージとして、横向きまたは後ろ向きに移動するかのように、あらゆる方向に高速で移動しようとします。 これはまた、回避中に通過するポイントの合計ポイント数を考慮します（静止している場合は、同じポイントに必要なティック数を追加します）。 この段階で発射物をかわすことができなかった場合、可能な限り最高の速度（選択した方向に回転）ですべての方向に走ろうとします。 発射体から離れようとするか、逃げようとするとき、すべてのミニオンが常に直線で動き、魔術師、建物、木が静止していると仮定して、障害物にぶつからないことも確認します。 現在のティックで障害物にぶつかった場合、次のティックでステップを繰り返します。 突然、誰かが手放した...あなたはシェルをかわしましたか？ パスの検索をブロックし、ダメージが少なく安全な方向に移動します。 また、特定の方向への別の方向転換が逃げるのに役立った場合、このティックでのボットの回転の制御をブロックし、実行している方向にそれをねじります（ショットを計算した後、最後に私の方向を変えます）。

ダッジアルゴリズムの記述に加えて、中心部での撮影は最良の選択肢ではないという認識に至りました。魔術師の中心部のすぐ前の位置で撮影する方が良いでしょう。 この知識を将来のために残すことにしました。

そしてまだ-ボーナス。

だから、ボットとのカップルに嫌いだったこれらの木をいつ切るかを決定する方法の次の改善を含む）改善の束を段階的に書いて、私はまだボーナスのための旅行を書くために座った。 その時までに、彼らのために本当の戦いがトップで始まりました、そして、穏やかに、そして免責でどんなボーナスも拾うことがしばしば可能でありませんでした。 敵の魔術師が最後に見られた場所を思い出し始めました。そうすることで、高い確率で彼らが私の前でそれを拾うことができるなら、ボーナスの方向に行かないように。 2500の倍数のティックでは、その場所でボーナスを見つける確率が1に設定されました。見えない時間に見えない敵のメイジがボーナスに到達できる場合、ポイントでボーナスを見つける確率は徐々に低下しました。 そして、マジシャンが最後に見られる前にボーナスに近づいたほど、ボーナスがまだ適所にある可能性が低下しました。 彼は敵の手下の位置を覚え始めたので、あなたはあなたのショットの距離で彼らの動きのライン上のポイントに戻ることができました。 4番目の「行」がコードに追加されました-それは単に私が行きたい方向を設定します。 また、この行をアクティブにすると、ハザードマトリックスで、ターゲットに近いポイントが追加のボーナスを獲得しました。 現在、ボットはその方​​向に動いており、敵の手先、魔術師、または塔を完成させるのにあまりにも固執していません。

（クリック可能なgif内）


4番目の「疑似」行に切り替えます。 彼女は、行列の方向を、行く必要があるポイントに厳密に設定しました。 この場合、魔術師は少し前に森を通って最も近いボーナスに行きました。

ボーナスのためのキャンペーンを書くことに加えて、彼は死の時を除いて攻撃ラインを変更する機能を追加しました（元の実装は他の状況ではそのような可能性を意味しませんでした）。 なぜなら 視界内にあるすべてのユニットの位置にデータを保存したので、ボットは、防衛線が攻撃者よりも弱いラインをよりよく理解し始めました（これは、敵のマジシャンやミニオンの視界からの一時的な出口の影響を受けなくなりました）。 一般的に、この瞬間からラウンド2の終わりまで、ラインの選択は「敵が多く、魔術師が少ない場所に行く」ように見えました。

最後の仕上げとして、まだ少し切り離された状態で、最適な位置とパスを見つけるためのアルゴリズムを3度目に書き直しました。 最後と最後の反復で、最高のポイントは、途中の平均スコアとポイント自体のスコアの合計が最大であるポイントと見なされました。 これを行うには、まず、優先度として、マトリックスに沿ったパスを検索しました。この検索のスコアが最大値だけ減少したスコアです（正の「ループ」を避けるため）。 ボットの歩行のこのような変更の後、深刻な欠陥が明らかになりました-彼は敵の手先や建物の周りを走り回るのが好きになり、しばしばそれらの後ろに行き、敵の魔術師から退くために彼自身の道を切りました。 ミニオンからの危険フィールドを2つの部分に分割しました：現在、攻撃ゾーンに加えて、ミニオンが私を攻撃する追加のゾーンがありました（少なくとも視界と私に最も近いユニットまでの距離から）。 これにより、私はこの問題を取り除くことができ、ボットによって選択されたパスは以前よりもかなり論理的に見え始めました。

（クリック可能なgif内）


ビジュアライザーのスクリーンショット。 この場合、ドッジアルゴリズムはマジシャンの回転の制御をブロックし、マジシャン自身が走る側になります（ステータスRUN_FROM_PROJECTILE）。 また、ボットは敵の魔術師の1人の最後の位置を記憶していることがわかります。 さらに、与えられたメイジが逃げることができるおおよその最大距離が描かれます。

その瞬間から最初のラウンドまで、それ以上の特別な改善は行われませんでした。 係数のバグと重大な欠陥が修正されました。 徐々に、ボットの評価はトップ10に落ち着くまで上昇しました。 この段階では、私のボットでの勝利の割合は、サンドボックスの上部にいる他の参加者と比較して非常に小さいことに注意できます。 ボーナスに対する慎重な態度では、最大ポイント数を獲得することはできなかったようですが、マジシャンの生存は多かれ少なかれ許容レベルであり、そのため彼は一貫してポイントを獲得しました。

最初のラウンドの後。

最初のラウンドの結果、ランキングで8位になりました。これは私にとって嬉しい驚きでした。ラウンド2のルールは、スキルを学習して適用する能力がラウンド1のルールと異なりました。ラウンド2のルールに従ってサンドボックスでゲームを開始する前の最後の日に、氷の矢を発射する可能性がボルトで固定されました。初日の夕方、スキルの使用方法と回避方法を知っている戦略がほとんどないという事実の中で、非常に印象的でした。しかし...わずか1日後、最初のultとして火の玉を選んだボットと戦うのは良くないことが明らかになりました。これを係数で修正し、爆発の半径を火の玉から覆い焼きアルゴリズムに追加する試みは失敗しました。敵を倒すことはできません-リードしてください。次のステップは、火の玉射撃の執筆でした。一般に、（火の玉の端と爆発の端で最後を傷つけるために）所定の位置にいるミニオンの周りでショットを試すよりも良いことはありません。オプションはまさにそのようなバストになりました。現在のキャスト半径でできるショットオプションのみが考慮されました。しかし... ...一時的なものほど永続的なものはありません。敵の魔術師が私のファイアボールから脱出できるかどうかを明確にすることを除いて、最後まで検索アルゴリズムはまったく同じままでした。後者は常に最適な方法で爆発から逃げようとしているということです）すぐに思いつきませんでした。そして、そのような消耗は一時的な選択肢としてなされました。現在のキャスト半径でできるショットオプションのみが考慮されました。しかし... ...一時的なものほど永続的なものはありません。敵の魔術師が私のファイアボールから脱出できるかどうかを明確にすることを除いて、最後まで検索アルゴリズムはまったく同じままでした。後者は常に最適な方法で爆発から脱出しようとしていること）がすぐに思いつきませんでした。そして、そのような消耗は一時的なオプションとして行われました。現在のキャスト半径でできるショットオプションのみが考慮されました。しかし... ...一時的なものほど永続的なものはありません。敵の魔術師が私のファイアボールから脱出できるかどうかを明確にすることを除いて、最後まで検索アルゴリズムはまったく同じままでした。
戦場での火の玉の使用のテストが非常に成功した後、私はサンドボックスで1位になり、すでに書かれた内容の改善を開始することにしました。彼はWizardsInfoクラスを作成しました。このクラスには、魔術師のオーラに作用する受動的スキル、ultsに関する情報が含まれていました。同様の情報を使用して新しいクラスを使用するコードを切り替えました。そして、1週間後に判明したように、彼は真剣に回避を破りました。加速状態がない場合、ボットは、回避の試みをシミュレートするときの実際の速度よりも30％低い速度でこれを実行しようとしました。一般的に彼らは働いていたので、私はこれにすぐに気づきませんでしたが、彼らはもっと悪い仕事をし始めました。

攻撃的な戦略がしばしば私を殺したサイトでの戦闘を見た結果に基づいて、退却を改善するために、彼らは私だけであることが判明しました、180度のターン検索マトリックスが追加されました（つまり、この場合、前方よりも後方の距離が長いと考えられました）、ボットが危険にさらされていると判断した場合（たとえば、2人の敵の魔術師のところに行き、近くに味方がいない場合）。彼は不滅の建物への攻撃を修正しました（ルールによれば、ラインの2番目のタワーを破壊することなく最初のタワーを傷つけることはできませんでしたが、隣接するラインの2番目のタワーはボットが気を散らすほど近くにありました）。マトリックスのスコアに対する敵の影響を変更することにより、状況を改善するための多くの試みがありました。明らかに前向きな変化から-敵の魔術師から危険な領域を計算するとき、彼らの回転の角度が考慮され始めました、敵の魔術師のスキルのクールダウンに加えて、マナの存在と回復の時間が考慮され始めました。ターゲットシステムは完全に書き直されたため、マジシャンは次に使用するスペルをより慎重に選択します（たとえば、火の玉があり、マナが残っていない場合、基本的な魔法のロケットにマナを費やすのはなぜですか？ただ傍観します）。私のショットから敵の魔術師をかわす可能性の説明を追加しました。ベーススペルと敵の魔術師のための氷の矢の助けを借りてショットを計算する際に、彼は2つのポイントで射撃を開始しました-ターゲットの中心と、側面から射撃するときのポイントを等しく長く、前後に動かします（このポイントは魔術師の中心のわずかに前方にあります） 。ここでは、覆い焼きアルゴリズムを書く際に得た知識を使用しました。そして、評価はすべて溶けて溶けました。なぜそれが悲しくなったのか。

それでも、回避アルゴリズムの失敗から1週間後、ビジュアライザーで次の戦いを見ると、ボットが回避ロジックを起動し、「オープンフィールドで」発射体から落ち着いて正確に移動することで、突然回避していると思い始めました。彼は砲弾から逃げることができず、ダメージの一部を捕らえたものが何もなかったかのように戦いを続けました。これにより、この特定の状況を再確認しました。毎週の悲しみと悲しみの原因となったバグは、局所化され、厳しく処罰されました。

ラウンドの準備2。

覆い焼きアルゴリズムの問​​題を修正した後、評価は再び大きくなり始め、決勝に進まないことを恐れることをやめました。ただし、第2ラウンドの準備に必要な時間に、すべてのultを使用して最終版で使用できるようにする方法を学びたいと思います。しかし最初に...私の魔術師はまだ非常に消極的であり、特に距離を保つ敵の魔術師を攻撃しようとはしていません。そして、私はそれを修正したいと思います。ターゲティングシステムは先週書き直され、今ではこの松葉杖を挿入するのは多少簡単になりました与えられた改善。ボットに実行されたショットがショットポイントまでの道のりで多少のリスクをブロックする場合、ボットに目的のターゲットに直接実行するように教えました。ボットは著しく攻撃的にプレイし始め、敵が回復するために戦闘ラインから退却することが非常に多くなり、ほとんど生きていない敵を手放すことはほとんどありません。

そして...フィナーレルールがサンドボックスに含まれるまでの残りの時間、私はマジシャンに加速呪文とシールド呪文の使用を教え、フロストボルトのようなすべての戦闘呪文の使用を調整し、立ち往生した木の別の問題を修正しました（ラウンド2の直前に発見されました）、そして...ボットライン上の敵の数が味方の数よりも多い場合、ボット自体に与えられたスキルブランチの調査が含まれ、これが走行速度の原因となります。そして、バグが発見され、その修正が0:00:01に送信されました。 1秒遅れます。つまり-ラウンド2の少し前に、私はボットに仲間に加速呪文を唱えることを教えることにしましたが、この呪文を自分に課すことを打ち破りました。そして、ラインで2対3の戦闘があった場合、すべてがうまくいきました（ルールによれば、加速呪文を味方に唱えるとき、それを課す魔術師も自分自身に呪文のコピーを受け取ります）、1対2の戦いでは、この問題は依然として非常に重大でした。この問題は、第2ラウンドの前半の最初の戦いで文字通り感じられました。これまでのボットの行の選択は、ラウンド1に実装されたアルゴリズムに従って機能しました。彼は自分の中で最も少ないラインを選びました。しかし、これは、第2ラウンドの第1部の結果によると、彼がトップラインに立つことを止めるものではありませんでした。少なくとも自分の場所。しかし、これは、第2ラウンドの第1部の結果によると、彼がトップラインに立つことを止めるものではありませんでした。少なくとも自分の場所。しかし、これは、第2ラウンドの第1部の結果によると、彼がトップラインに立つことを止めるものではありませんでした。

ラウンドの2番目の部分には、メイジのキャストのゾーンの背後にある火の玉のターゲットを検索するロジックが追加されました（使用時のショットのランプアップのロジックが洗練されたのと同時に）、次に気づいた木のスタックの問題は修正されました（そう、ツリーはまだボットを倒しました）。呪文を適用するロジックは、次の呪文のために必要な量のマナが回復したときに考慮するのがはるかに良くなりました。ラウンド2の2番目の部分の打ち上げ後、手先はわずかに修正されました（今は前端、つまり手先が見ている場所で撃ちました。中心で撃つとき、手先は私たちに逃げると発射体から逃げることができました）。

決勝戦の準備。

最終的には、ルールが異なり、一方の側のすべての魔術師が一人の戦略によって制御され、チームプレーのための新しいスペースが開かれました。私が最初にやろうとしたことは、ラウンド2のソースをコピーし、ゲームがラウンド2のルールに従っている場合にそれらを起動するために次に置くことでした。ロジックを複雑にし、ゲームの現在のルールに依存することをまったく望んでいませんでした。しかし...システムは、彼女がこれ以上私の決定をしたくないと判断し、理由の検索に数時間を費やしました。なぜシステムが「不正なアーカイブ」を送信しているというエラーを出しましたか？一般的なチャットではない場合、理由の検索が遅れる可能性がありますそしてずっと長い間。しかし、判明したのは、システムがソースを受け入れたくないということです。これは、展開されたバージョンでは、ディスク上で1メガバイト以上を占有します。どうやってもっと書いたのかメガバイトごとよりも???一般的にスクラップとある種の母親の助けを借りて、活発に開発されていないソースをミニファイナーで絞って、最初の2ラウンドでビジュアライザーを破棄し、必要なメガバイトを達成しました。その後、システムはソースを2MBに送信する機能を拡張し、この項目はルールに反映されましたが、その夜、戦略の試用版を決勝戦に送信するために（彼らの魔術師は全員中心線に行きました）、多くの時間を費やす必要がありました。その結果、彼は未確認のバージョンを送信し、スリープ状態になりました。このバージョンでは、すべてのマジシャンが異なるスキルブランチを習得し、1つの中央ライン（いわゆる「プッシュミッド」）を介して攻撃する必要がありました。そして朝、私はそのような戦術が、2晩でバグのあるバージョンをアップロードし、私のマジシャンがまったくスキルを習得したくないという事実を考慮しても、非常にうまくいくことを発見しました。

スキルの問題を修正し、ボーナスのためにグループウォーキングを削除したので（今では最も近いマジシャンのみがボーナスを獲得しました）、グループインタラクションの記述を開始しました。他のラウンドと比較して、割り当てられる時間は大幅に少なく（1週間）、本質的にまったく新しいものを書く必要がありました。第1ラウンドと第2ラウンドの同盟国間の相互作用は、戦略の大きな違いのために非常に困難であったため、私はフィナーレ専用に個別に書きました。

「真ん中に押し込む」が直面した最初の問題は、敵の安全な距離への逃げ道をしばしば妨害し、しばしば敵の殻から逃れることを妨げる同盟の魔術師によるラインの混雑でした。解決策は非常にシンプルで明白でした-彼は同盟のマジシャンと近すぎるために罰金を追加しましたが、現在のマジシャン自身が危険にさらされている場合は無視されました。今、私の魔術師は互いの回避を妨げませんでした、そして、もし私の誰かがより安全な場所に退却したいなら、彼は他を「押し」ました。この編集に加えて、もう1つが追加されました-各同盟マジシャンから600の距離に追加の正のフィールドが作成されました。これにより、ボットの動作に十分な自由がありましたが、互いに離れすぎないようになりました。

（クリック可能、gif内） 2 * 5をプレイするときの味方の魔術師の周りの危険


なぜなら 私たちが「危険な」ゾーンにいた場合、彼女は切断しました-時々彼女は、彼女の魔術師を「押して」退却するのを助けました。gifの最後に、「アトラクション」ゾーンがあります。あなたの魔術師に。

「プッシュミッドウェイ」が直面した次の完全に解決可能な問題は、4人で防御に戻ったIvan Tyamgin tyamginからの適応戦略で、5人がセンターを攻撃しました。しかし、当初、彼女は、4人の魔術師全員がそれぞれ自分の側で戦いに加わり、まるで私の周りを取り巻くようにそれを行いました。このような環境では、ボットが失われ、最初に勝つべき相手を見つけることができませんでした。そして混乱の間、彼の魔術師の1人は傍観者のままで、しばしば私の基地に到達してそれを破壊することができました。

このような問題を解決するために、私は攻撃のために魔術師の「クラスター」の外見を選び出しました-互いに近い（座標の算術平均から約350ピクセル以内）ほぼすべてのユニットで構成されるアクティブなアクションのグループが形成されようとしていました。それらが3つ以上ある場合-平均範囲（〜900ピクセル）で、塔の下にいない魔術師を探していましたが、近くに魔術師はいません（最大1つですが、そのようなサポートがない目的では、優先順位が高くなりました）。パッシブスキルが選択された速度または加速状態のターゲットは無視されました。それらを追いかけることはより高価でした。適切なターゲットがあった場合、私の魔術師は群衆全体で貧しい仲間に走り、非常に効果的に経験を積んで、失われた魔術師を次の世界に送り、一般的な魔術師のグループからボディシェルの離脱を奪います。このために、4番目の「疑似回線」が使用されました。これは、もともとボーナスを収集して回線を変更するために作成されました。以前は、メイジが「正しい方向に進む」ための十分に強力なボーナスを提供していましたが、これは単に取得したい座標によって設定されていました。単一の敵の攻撃的な攻撃は、その後、頑なに森の中を歩き、あらゆる方法で私の主要な軍隊を取り囲もうとした戦略との戦いで非常に役立ちました。

次の問題は、敵の基地へのダメージが十分に高いことであり、完全に中央の線を壊したので、私はしばしばあえて攻撃しませんでした。だから彼らは他の線に沿って敵が私の基地に到着し、私が戦うことを決める前にそれを破壊するまで待つことができました。一般的に、敵の基地は本当に危険な場所であるため、優柔不断を削除したくありませんでしたが、1つの条件が追加されました-数に圧倒的な優位性があるか、2番目の塔が側線のいずれかで破壊された場合、基地からの危険は無視され、すべての魔術師が命令されますこの攻撃をさらに刺激した同じ4番目の「擬似ライン」を使用して、より便利な側から敵の基地に進入する（アカデミーでプレイする場合、この側は敵基地の少し右側にあります。 AZEタワーはあまり干渉し）ではありません。

これらの改善後、2 * 5の戦闘で実質的に損失はなく、センターでの攻撃の選択肢が実際に多数勝ち始めた場合に備えて、代替の戦術を書くことに集中しました。しかし、私の戦略は決勝戦の当初の戦術に抵抗するのがあまり得意ではなく、このトピックに関する実験があまり多くなかった後、私はまだこの考えを拒否しました。

ファイナル

金曜日に到着-フィナーレの最初の部分の前日。仕事で休みが取られ、すべてが順調に進み、災害を予感させるものはありませんでした。木曜日の夜、私の戦略は最も近い追跡者の戦略よりもはるかに安定しており、金曜日にはリラックスすることを考えていましたが、そこにはありませんでした。アントン・チュマチェンコ（Antmsu）、この間ずっと夜寝るのがあまり好きではないようで、私の睡眠中、彼は彼の戦略のいくつかの欠点を修正し、彼の戦略はほとんどいつも私を打ち負かし始めました。道徳的にリラックスすることはもはや不可能であり、私は公正な戦いでこの特定の戦略を破る方法へのアプローチを探し始めました。夕方になると、小さな変更の助けを借りてこれを成功させることはできず、ほとんどすべてのファイナリストでテストした戦略を破りたくありませんでした。さらに、昼食後、NightTursもほとんど常に私を打ち負かし始め、状況は木曜日の夕方に比べて非常に憂鬱に見え始めました...一般的に、その日の気分は言葉よりも画像を通して伝える方がはるかに簡単です。


Git . 4.30 PM, , .


決勝の最初の部分の前の最後の数時間でライバルの行動を注意深く見て、私は勇気を出し、私の観察に基づいてボットのマイクロコントロールの何かを変更しようとしました。変更は取るに足りないものであり、私の戦略にさらなる積極性を与えましたが、すべての参加者に対してファイナルへの未検証の変更を開始しませんでした。その結果、対戦相手のニックネームを確認する機会を得ました。AntmsuとNighTursについてのみ、最新の更新を含めました。とにかく、戦闘で負けるものは何もないように見えました。

誰もが（私も含めて）シリルボロンキン（core2duo）、決勝戦の最初の部分で私に6敗のうち6敗を負わせたが、ナイツツアーの6試合すべてを失い、それにより朝のように、少なくともトップ2のポジションに戻ることができるという点で私にほとんどコントロールの打撃を与えた。 、私は奇跡を待つ意味はないと判断しました。朝に結果を確認する方が良いでしょう。私は3位位が私を待っていたと思っていましたが、より悪い選択肢のために精神的に準備していました。ロシアのaiカップ2016の決勝戦の最初の部分の最高の参加者の結果。P-勝利の数、G-ゲームの数。ロシアのAi Cupでの私のニックネームはCommandosです。


クリック可能。

最後のスタンド。

第1部の後に決勝の中間結果を検討した結果、私を含む全員が、トップ2の参加者が「自分たちの中で」物事を整理することに同意し、私は3番目の位置を維持します。 ある程度、それは私を慰めた、なぜなら 結果によると、少なくとも3位はすでに比較的失うのが難しいことは明らかでしたが、... iPadですか？ なぜiPadが必要なのですか？ MacBookが欲しい！ 少なくともAir ...一般に、金曜日は比較的落ち込んだ状態で過ごしたので、決勝戦の第2部の前日の最終日には、次に何が起こるかについての期待を失うべきではないと判断しました。 そして私は絶対に絶対に高くなりたいです。 それにも関わらず、望ましい結果を得る方法を考えるのに数時間を費やしました。 現在の2人の最終リーダーによって失われたゲームは12試合と13試合のみであり、私はそれぞれ12試合と11試合に遅れをとっていました。 私が100％のチャンスで彼らを倒し始めたとしても、それはありそうに見えませんでしたが、これは彼らに追いつくのに十分ではなく、追い越すのにそれ以上です。 そして、私はすべてのプレイヤーとの損失を見て修正することにしました。 ほぼ100％の結果が必要でした。 まあ、それは不可能です、多分企業のパーティーに行きます。

もちろん、最初のcore2duo戦略が注目を集めました。 ミクロレベルでのマジシャンのコントロールはかなり弱く、ほぼ100％の勝利を保証して彼を正面から攻撃することが可能でした。 私の意見では、これはこの場合の理想的な戦術ですが、この戦略のクローンが登場した場合に備えて、より普遍的なものが必要でした。 解決策は簡単でした-中央以外のラインに敵のマジシャンが多すぎる場合、ダメージを与える可能性のあるポイントでマジシャンを見つけるためのボーナスを大幅に増やしました。 このアプローチでは、core2duoを使用してプレイする場合、私の戦略はほぼ常に勝ちましたが、安全性を高めるために後者からの新しいトリックを待って、チェックを追加しました：if（ "core2duo .equals（playerName））-どこにいても、最も近い敵の魔術師に直接攻撃します。 現在の戦略での勝利の約100％の確率に加えて、これは彼が私に悪いことをすることができないというさらなる自信をもたらしました。

2番目のポイントは、GreenTea参加者の戦略に対する私の唯一の損失でした。 このゲームでは、私の魔術師は非常に頑固に、同じ数で最後の攻撃に行きたくはありませんでしたが、はるかに多くの敵を攻撃しました。 デバッグの助けを借りてこのゲームをより詳しく調べると、もう1つのバグがありました。攻撃グループを作成するために私のマジシャンの「クラスター」を検索するときに、1人のマジシャンでも遠すぎる場合、平均を更新する問題のためにグループが見つかりませんでした「クラスター」のマジシャンの算術的位置。ただし、最も遠いものは除きます。 このバグを修正し、防御側の敵のヒットポイントの数がはるかに少ない場合に敵の基地に攻撃を強制するロジックを追加して、次の問題を検討しました。

その後、TonyKとtyamginの参加者に損失がありました。 当時の最新バージョンのTonyKでのテストでは、多数の敗北は明らかにならず、彼の戦略で何かが壊れていると思いました。 念のため、フィナーレの最初のパートでAntmsuとNighTursだけでプレイしたのと同じ少し攻撃的な戦術もテストしました。 なぜなら 目に見える問題はありませんでした-そのままにしておきました。 同じ小さな変更が、tyamginとの戦闘にも適用されました。 視覚的には、小さなプラスの効果があり、検査の結果によると、そのまま残されていました。

ファイナルの前半で負けた残りの4人の参加者は、私と同じように5人の魔術師全員が中心線に沿って歩いているという事実によって、一般的なヒープから際立っていました。 これは私の敗北の大部分を占めています（もちろん、core2duo戦略を忘れてしまった場合）、そしてこれをマジシャンのマイクロコントロールの係数の選択とマイナーな修正で解決することは、先日金曜日にAntmsuに対してこれをやろうとしていたので、とてもありそうにないようでした。 core2duoから得た経験に触発され、私は彼らのために何か特別なことをしようとすることにしました。 ファイナルの最初の部分（およびファイナルの2番目の部分の前に、これら4つの戦略のうち4つのうち3つすべてが私を大いに助けてくれました）は、近接戦闘まで停止することなく、敵の最初のタワーへの攻撃に行ったことに気づくのは非常に簡単でした。 計画は単純でしたが、攻撃者のグループ全体を2つに分割しようとするとどうなりますか？ さらに、彼らが私の塔に駆け寄るとき、彼らは側面からの接近に対して脆弱になります...計画によると、それらのすべてが一方向に後退する機会を持たず、敵の魔術師の一部を森に押し付けようとする最速の攻撃は、理論的にはもたらすことができます望ましい結果。


側面攻撃計画。 赤い矢印は私の計画された動きを示し、青い矢印は敵の予想される動作を示します。 クリック可能。

この理論をテストするために、最初に最初の塔からの危険を無視して攻撃するようにバージョンを変更しました。 その後、ローカルランナーを使用して自分のバージョンに対して変更された戦略が開始されました。これは、このケースの側面から呼び出しを行う方法を既に知っていました。 結果は非常に説得力がありました-塔の形での損失、時には1人の魔道士でさえありましたが、側面からの無謀な攻撃はしばしばゲームの開始時に明白な利点をもたらし、これは十分であることが判明し、戦闘の残りはすでにほぼ安定していました新鮮な更新を支持します。 地元の成功に触発され、私はこのアイデアがmortidoとud1の戦闘条件でどのように機能するかを確認することにしました。 私の仮定によれば、彼らは私のアプローチを破るような何かを書くための真剣な試みに時間を無駄にしないでしょう。 戦闘条件でのテストも正常に完了し、上位2人の参加者が驚きの可能性を高めるために、この戦略を以前のオプションに置き換えました。詳細は、ローカルランナーを使用して午前4時頃までに行われました。完了しました。

上位2人の参加者を確認するために、11.39に更新バージョンをアップロードしました。 決勝の第2部の開始の21分前。 トップ2のテストは成功し（4ゲームで1敗でしたが、結局、私の勝利の可能性はさらに高くなりました）、この形で戦略は最後まで残りました。

ゲームを始めた後、私はすでにレモンを絞った状態にあり、昼寝をするために去りました。 少し休んだ後、2つのニュースが待っていました。 Pleasant-私の戦略は、敗北なしで本当に行きました（2波で1敗、これは118ゲームです）。 不快な-テストは最初の日よりも著しく遅く、前の波と同じくらいの波があるかどうかはかなり疑わしかった...そして最初の波の結果によると、最初の2人の参加者の1人を追い越すことはほとんど不可能に思えた。 それにもかかわらず、幸運の多い5ウェーブでも、私の戦略は最終結果で2位になりました。



ロシアのaiカップ2016の決勝戦の第2部の最高の参加者の結果。クリック可能。



ロシアのaiカップ2016の決勝戦の最優秀参加者の最終結果。クリック可能。

一ヶ月半の命の損失にもかかわらず、私は間違いなく最初にその考えを放棄しなかったことを後悔していません。 タスクは非常に膨大であることが判明し、実装されたときに、ルールのどの機能、どのケースを考慮し、どの機能を無視するかを常に選択する必要がありました。 最終的な実装のすべてのニュアンスを考慮することは事実上不可能であり、おそらく最終的なアルゴリズムは不完全な感覚を残していましたが、競争ではさらに面白くて難しい瞬間でした。 このような大規模で魅力的な競技会を開催してくれたRAICの主催者に感謝の意を表します。また、ほぼ伝統的に、多くの参加者が有用な情報、非常に有益なテーブルを見つけた一般的なチャットを作成したRoman Udovichenko（ Romka ）に特別な感謝を表明したいと思います中間結果（上記のスクリーンショットで見ることができます）、最終版の最後の部分、およびこの投稿の最初の校正の準備に役立ちました。

UPD。 リポジトリを部分的に復元しました。 最初のいくつかのコミットを削除する必要がありました。 また、すべての死んだブランチは生き返りませんでした。