Clever Geek Handbook

Google AIチャレンジ（Ants）の説明

画像

ハブにはすでにこのコンテストに関する多くの情報がありますが、すべては全体像ではなく、実装の特定の瞬間を照らします。 この状況をできるだけ簡単に修正しようとしますが、一般的にはそうします。

この説明は、このイベントについて何かを聞いたことがある人を対象としていますが、何かをしたいという願望は、実装の複雑さを理解する必要性を思いとどまらせます。 投稿は、一部は公式サイトからの資料の翻訳、一部は他のボットの戦略と純粋なロジックの分析で構成されています。 また、投稿の最後にPHPボットへのリンクがあり（スターターパックよりも少し複雑）、既存のコードを追加してみてください。 公式コンテストウェブサイト： aichallenge.org





アリのコロニー戦略の主なコンポーネントは次のとおりです。



1.パッシブ


1.1。 フードコレクションとコロニーの補充（スポーン）






1.2。 アリ丘防衛






1.3。 領土の偵察と管理


スコープメカニズムは条件（以下を参照）で実装されるため、ボットはどのマップがその前にあるかを認識せず、アリのスコープに入るオブジェクトに関する情報のみを受け取ります。 ほとんどの場合、敵の蟻塚への接近を除き、領土の管理は必要ありません。 アリの理想的な配置は、最大の可視領域を開き、すべての未使用のアリを「ミッション」に送り、敵の蟻塚を破壊する（プッシュ）アルゴリズムです。 したがって、オープンカードを維持することは、範囲内にあるすべての食物の偵察を収集することを主な目的としています。



2.アクティブ


2.1。 敵アリの駆除


「攻撃」の計算は、単純なルールに従って全体として発生します。

敵が等しい場合は、敵の強さと自分自身の強さとの差と見なされます。すべてが死に、それ以外の場合は弱く死に、強いものは生き残ります。

「力」とは、攻撃範囲内でこのセル（アリがいる場所）を持っているアリの数を意味します。 簡単に言えば、1つのアリが2の攻撃半径内にいる場合、彼は死にますが、彼らは死にません。 2x2-すべてが死ぬなど。 アリは、攻撃範囲内のすべてのセルのすべてのアリを一度に攻撃することがわかります。



注意：水はまずまずのセルではありませんが、水を介した攻撃も考慮されます。つまり、水セルの異なる側にいる2つのアリは互いに殺します。

技術面：

敵のアリに関する情報は毎ターンボットに送信されますが、入力からの敵のアリの消失は死の状況を意味する可能性があり、視界からの消失の状況を意味します。 最初の状況は、死者に関するデータを分析することによって監視される場合がありますが、アリは別のアリと視野の境界で死ぬ可能性があります。 これにより、個々の敵アリの行動を追跡する実装が複雑になり、敵のおおよその行動を計算する上でいくらかの利点が得られますが、その実装はそれほど優先されません。



2.2。 敵の蟻塚の駆除


それは勝利を達成する主な方法の1つです。 蟻塚がなければ、コロニーは新しい蟻を生産しませんが、生きている人は戦い続けます。

技術面：

敵の蟻に関する情報だけでなく、すべての（あなたを含む）蟻塚に関する情報が毎ターン送信されます。 つまり、この蟻塚が視野から消えたり消去されたりした場合、この蟻塚に関する情報を受け取れない場合もあります。 ただし、蟻塚は移動できず、枯れた丸太には反映されません。 したがって、発見された蟻塚についての情報を保存することは理にかなっていますが、次のログで発見されず、可視領域にある場合は、それらを破壊済みとしてマークします。

したがって、これにより、たとえアリが視界から消えたとしても、アリを敵の蟻塚に向けることができます。

ほとんどのボットでは、アリの丘の保護が実装されていないため、「空飛ぶ」アリが無防備なアリの丘を単に破壊し、それによってボットを補強せずに本質的に敗北に至ることは珍しくありません。



コースの段階（ステップ）


すべての計算は、次の順序で実行されます。

  1. ムーブメント
  2. 攻撃
  3. 蟻塚の破壊（レイズ）
  4. 食べ物を集める
  5. 新しいアリと食物の出現（スポーン）




このロジックに基づくいくつかの注意：



各移動で、次の情報がボットに送信されます（水、アリ、蟻塚、死んだアリ、食物、移動番号）。 これらはすべて、ボットの入力ログで見つけることができます。



範囲と追跡


蟻塚自体にはスコープがありません。つまり、蟻の隣に蟻がいない場合、蟻の丘の上の敵の出現は、あなたにとって不愉快な驚きです。

ボットが起動すると、現在のマップの構成が送信されます。これは、スコープ、攻撃、およびスポーンも示します。 これは、2つのセル間のHippotenusesの正方形です（整数値を維持するために正方形が選択されます）。

標準パラメーター：

可視性-55（半径約7セル）、

攻撃-5（約2セルの半径）。

spawn-1（現在のセル）。

着信データは指定された移動の状況（変更）のみを反映するため、次のアプローチが実践として採用されます。





敗北条件


  1. ボットアリはすべて死んでいます。
  2. ボットがクラッシュしました。
  3. ボットがフリーズします（タイムアウト）。
  4. ボットは、競争の規則で禁止されているコードを実行しようとします。


繰り返しますが、すべての蟻塚の損失は敗北ではなく、すべての蟻の損失までボットは戦い続けます。

重要なポイント：

敵ボットがクラッシュまたはフリーズした場合、そのアリは戦場に残りますが、コマンドを受け取りません。 これは、同じ形式で情報を受信し続ける他のプレーヤーには報告されません。 この点で、「クラッシュした」プレイヤーを追跡するアルゴリズムを実装することも可能です（これはまれですが、発生します）。



ゲームごとのポイントの計算


各ボットは、各蟻塚の最初のポイントから始まります。

敵の蟻塚の破壊+2ポイント。

蟻塚の損失-1ポイント。

ボットが1つだけ残っていて、すべての敵の蟻塚が破壊されていない場合（ただし、すべての敵の蟻が殺されるか、他のボットが「スタック」または「ドロップ」）、残りの敵の蟻塚ごとに、ボットはそれを破壊したかのようにポイントを受け取ります、つまりそれ自体に+2そして、蟻塚の所有者に-1。



戦略の要素


1.動き、ポイントへの道を見つけ、目標を選択する


目標の通常の優先順位：最初の食べ物、次に敵の蟻塚、そして敵。

最も単純な経路探索アルゴリズムは、幅優先探索 、またはやや複雑なA *です。 最も原始的で最速の方法は、座標の違いを減らすことに基づいて移動方向を選択することと考えることができます（このようなメカニズムはスターターパックに実装されます）が、もちろん、多くの障害が発生します（たとえば、ターゲットが反対側にある場合）。

パスを見つけることは、コースを計算する上で最もリソースを消費する操作の1つです（アクションの分析でも平均して簡単です）。そのため、アルゴリズムの選択と実装は、ボットの最終結果に大きく影響します。 したがって、パフォーマンスの高いボットはより能力があります（正しく理解されているように、トップ全体はC、C ++、およびJavaで記述されています）。

近くにターゲットが存在しない場合の主な優先事項は、見えないエリアを考慮することです。これにより、アリがマップ上で「クリープ」します。 敵の蟻塚が発見されるとすぐに、すべての新しい蟻（またはその割合）をチェーンで送ってそれを襲撃し、再び偵察のために送ることができます。 スコープと未発見の領域への移動を制御することで、敵のプッシュ時にのみ必要な集合を配置することなく、アリをマップスペースに均等に分散できます。

便利な手法は、3つの側面に水があるセルの通過をブロックすることです（このようなセルにはほとんど実用的な意味はありません）。これは、マップを分析し、そのようなセルをメモリに保存することで実行できます。

同じことは、行き止まりの「単細胞」トンネルにも当てはまりますが、ターゲット（たとえば、食物）が見つかった場合は例外となります。

有用な要素は、ボットがすべての障害を発生させずにコースを維持するように、最初の機会にサイドの1つに移動することを好む場合の「最後の優先順位」の保持です。



3.防御と攻撃


一般的に、攻撃のメカニズムは非常に明白です。 敵のおおよその動きが計算され（たとえば、彼の優先目標があなたのものと同じ場合：食べ物、他の蟻塚、敵）、次に敵の「パワーマップ」が計算され、次に敵のパワーマップと優先度を考慮してアリの動きが計算されます目標、つまり、あなたのアリがターゲットに最も近いセルを提供し、あなたの方向のセル内の「力」の利点を提供します。 いくつかのアリの動きのさまざまな組み合わせを同時に計算する必要があるため、これはかなり複雑なアルゴリズムですが、大きな「前線」は非常にまれであり、ほとんどの場合これらは個々の衝突です。

その結果、アリは「可能な限り慎重に」あたかもターゲット（蟻塚または敵）に向かって移動し、それにより、できるだけ早く敵を破壊します。

ほとんどの場合はあいまいで、「ランダム」でさえあるため、理想的なソリューションはありませんが、これはすでに損失を最小限に抑えるのに十分です。

また、すでに述べたように、あなた自身の蟻塚を保護することを忘れないでください。ここでは、斜めのセルに2〜4個の「ガード」を置くことができます。



同様の戦略の例は、競争のトップにあります。


緑茶

モモボット

フラッグキャッパー

一部のゲームは、特にこれらがボットであることを知っているので、見るのが非常に面白いです。



シード用のPHPボット


ボットは、OOP形式でほぼゼロから書き直されます。 さまざまな行動戦略がはるかに便利に試されます（たとえば、各アリは個別のオブジェクトに保存されます）。したがって、$ ant-> stay（）または$ ant-> doMove（）を実行できます。 コードにはコメントがほとんどなく、未使用のテスト関数がいくつかありますが、非常に読みやすくなっています。

ボットの一般的な戦略：マップをさまよい、食べ物を集め、敵を避け、最初の機会に敵の蟻塚をco病に破壊します。 約50〜60ポジションのランキングに留まるのに十分です（最大スキル49）。 したがって、彼はスターターパックのボットを簡単に倒します。 さらにあなたの裁量ですでに。 ただ楽しみのために。

Yandexからボットをダウンロードする



ボットのデバッグ


公式サイトでは、ボットをデバッグする方が正確にどのように書かれているかはわかりません。

標準パック（ツール）は、ファイルplay_one_game_live.shを使用してボットゲームを表示します

ここで、ボットのアドレスを指定する必要があります。 これについては、トピックで詳しく説明していますが、Google AIチャレンジ用のボットを作成しています。 クイックスタート。 。 これに加えて、ボットが失敗（クラッシュ）した理由に関するメッセージがコンソールとログに表示されないことを追加する価値があります。 これを行うには、ファイルplay_one_game_live.shをわずかに変更して、スクリプトを実行するキーを追加する必要があります（ SoをSoeEIOに置き換えます ）。

./playgame.py -SoeEIO --player_seed 42 --end_wait=0.25 --verbose --log_dir game_logs .....







これで、ゲーム中に発生することに関するすべての情報（1つのアリのダブル移動などのボットのアクションのエラーを含む）がコンソールとgame_logsディレクトリのログに表示されます。 この情報は、ボットを分析するのに十分なはずです。

技術的な側面（仕様）をよりよく理解するには、興味のある言語のスタートパックを「掘り下げる」ことをお勧めします。 一般に、最初はそれらで十分です。



結論として


提案されたボットの「戦場」は、アルゴリズムを練習したい人にとって非常に興味深いことが判明しました。 もちろん、このコンペティションのトップにもっと多くのプレイヤーが参加したいと思っています。それがこの記事が書かれた理由です。 独自の人工蟻塚を作成して頑張ってください。


More articles:


All Articles