最近完了したAIチャレンジの勝者のメモの翻訳があなたの注意を喚起し、アルゴリズムの一般的なポイントといくつかの技術的な詳細を明らかにします。 ソースコードを自分で検査することもできます。



勝ったとは信じられません。

そしてさらに、私が決定的に勝ったとは信じられません。



私はプログラミング競技が大好きで、私にとってこれまでで最大かつ最も刺激的なものでした。 数ヶ月間のコンテストの主催者、アシスタント、tcpサーバーホスト、およびすべてのプレイヤーに感謝します。



これは私のゲームの例です： aichallenge.org/visualizer.php?game=346288&user=4513 （ これは著者が彼の記事で引用したゲームではありません。著者のサーバーに直接保存されているため、リンクを付けることはできません。 -約Transl。 ） 。 この記事では、私のコードが何をするのか、そしてそれがどのように成功するのかを説明したいと思います。 多くの技術的なポイントがあり、一般にこの記事は戦略そのものに関するものではありませんが、より簡単に説明しようとします。

コードについて

Javaスターターパックをダウンロードし、ファイルの名前を変更し、不要なものをすべて削除し、新しいStrategy



クラスを追加することから始め、すぐにアリを表すクラスも必要になることに気付きました。 私はすべてのコードをStrategy



クラスで作成しました。その結果、約1800行のコードが作成されました。 また、興味深いのはAnt.java



とTile.java



、どちらもTile.java



のフィールドを持つ値オブジェクトです。



私はスターターパックからアイデアを残しました。このパックでは、不明な領域がデフォルトで地面と見なされていました。 ボットの視野を計算しなかったため、どの細胞が実際に地球であり、今まで見たことのない細胞であるかさえ知りませんでした。



マップの各セルには、ゲーム全体で使用されるタイルのインスタンスが1つだけあります。 アリは、すべての私のアリと敵のアリの各ターンの開始時に作成されます。



自分でソースコードを見たい場合は、知っておく必要があります。govnokodaでいっぱいであり、私は特に誇りに思っていません。 ただし、おそらく何らかの形で見たいので、 ここからダウンロードできます。

戦略の実施

多くの人がいくつかの一般的な戦略について話しましたが、残念ながら、私はそれを持っていません。 私は、アリの数や占領地の割合に基づいて決定を下しません。 ボットは勝ち負けても戦術を変えません。 彼はそれについて全く知りません。 さらに、私は今の動きを見ていないし、最初はすべてが999番目とまったく同じように起こる。 私は、戦闘中であっても敵を区別せず、蟻塚の性質を保存しません。 ミッションの助けを借りて蟻塚からアリを送ることに加えて、各動きはアリのローカル環境のみに依存します。



では、毎ターン正確に何が起こるのでしょうか？ すべての初期化と事前計算の後、次のメソッドをこの順序で呼び出します。

• initMissions（）;
• enemyHills（）;
• 食品（）;
• initExplore（）;
• createAreas（）;
• 戦う（）;
• 防衛（）;
• approachEnemies（）;
• attackDetachedEnemies（）;
• escapeEnemies（）;
• 配布（true）;
• 探索（）;
• doMissions（）;
• createMissions（）;
• 配布（false）;
• cleanAreas（）;

以下では、これらすべての方法が何をするのかを説明しますが、要するに、特定の基準に適合するアリを単に移動させるだけです。 アリが移動すると、これに関する情報が即座にサーバーに送信され、アクションを取り消すことはできなくなります。

ワイド検索

ここでは、一般にBFSを取得する方法について説明します。 パフォーマンス上の理由から、各タイルには隣接するセル（水を除く）があるため、2次元配列にアクセスして、rowsおよびcolsプロパティを使用する必要はありません。 （ これにより、パフォーマンスが大幅に向上することは疑わしい-およそTransl。 ）典型的なBFS（およびそれらの多くを使用）は、次のようになります。

 LinkedList<Tile> openList = new LinkedList<Tile>(); LinkedList<Tile> changedTiles = new LinkedList<Tile>(); openList.add(foodTile); foodTile.dist = 0; foodTile.isReached = true; changedTiles.add(foodTile); while (!openList.isEmpty()) { Tile tile = openList.removeFirst(); if (tile.dist >= 10) break; for (Tile n : tile.neighbors) { if (n.isReached) continue; if (n.type == Type.MY_ANT) { // found one of my ants at the tile n } n.isReached = true; n.dist = tile.dist + 1; changedTiles.add(n); openList.add(n); } } for (Tile tile : changedTiles) tile.isReached = false;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

この例では、foodTileから始めて、10ステップで到達可能なアリを探します。 HashMapを使用して既にアクセスしたセルを保存する方が効率的である場合は、最後にループを取り除くことができます。

コースの初期化

各移動の開始時に、近くにいる「友人」の数や近くの敵のリストとそれらまでの距離など、アリのあらゆる種類の比率をカウントします。 ここでの距離はユークリッドとマンハッタンの両方であり、BFSのステップ数によって考慮されるため、これは少しわかりにくいです。



敵までの距離に応じて、アリには（間接的な可能性がある）危険があるかどうかを示すフラグがあります。 敵の場合、孤立しているかどうか（つまり、近くに他の敵アリがあるかどうか）を確認しました。



初期化中に実行される別のタスクは、数回の移動で移動していない敵アリを識別することです。 そのような動きの数が5に達した場合、さらに次の動きに立つと想定されました。

研究とミッション

蟻を蟻塚から遠ざけ、新しい領域を探索し、実装で可視領域を最大化することは、互いに非常に密接に関連しており、おそらくこれが私のボットの動作で最も重要な部分です。

リサーチ

ExploreValueは、マップ上の各セルに保存されます。このセルは、少なくとも1つのアリと10ターンでBFSで到達できない場合、1ターンごとに増加します。 セルに到達できる場合、カウンターはゼロにリセットされます。 したがって、exploreValueは、セルで何が起こっているのかわからなかった時間の尺度です。



したがって、探索方法では、別のタスクに使用されなかったすべてのアリから、最大深さ11ステップでBFSが起動されますが、最後のステップのみに関心があります（最初の10個のexploreValueは0であることが保証されているため）。 ステップ11で到達可能なすべてのセルのexploreValueがゼロの場合、これはアリが「自分自身」または水に囲まれていることを意味します。 それ以外の場合、ステップ11のexploreValue合計が最大になる方向にアリを移動します（つまり、10ステップで入力するセルから到達可能なすべてのセルのexploreValue合計）。 2つの異なる最初のステップを実行することで11ステップで任意のセルに到達できるため、BFSでは1つまたは2つの最初の動きのリストが保存されます。

このようにして、地図を探索し、すべてのサイトを表示します。

ミッション

では、アリが自分のアリに囲まれているとしたらどうでしょうか？ もちろん、境界線に移動します！ 境界線のより正確な定義はcreateAreasメソッドにあり、これについては後で詳しく説明します。 国境に移動することをミッションと呼びます。 ミッションは、アリと国境の標的細胞の2つだけで構成されています。 ミッションは、移動の間に保存されるいくつかのデータの例ですが、目標へのパスは毎回A *でカウントされます。 アリがすでにミッションを持っている場合、それはそれを実現し続けます。そうでなければ、新しいものが作成されます。 アリにミッションがあったが、それが他の目的（食物収集、戦闘、防衛）に使用された場合、ミッションはキャンセルされます。

土地と国境

createAreasメソッドは、マップをセクションに分割します。 今回は別のBFSを実行しますが、今回はすべてのアリ（敵を含む）から同時に実行します。 開始時に、各アリには独自のプロットがあり、ラウンドトリップ中に到達したすべてのセルがそれに結合します。 しかし、1人のプレーヤーに属するセクションが衝突すると、それらは1つの大きなセクションにマージされ、その後、何度もマージできます。 BFSの後、自分のエリア内のすべてのセルを調べ、少なくとも1つの隣接セルが別のエリアに属している各セルを境界セルと見なします。 このBFSでは、私は20の動きよりも深くは行かないため、39歩の距離にある2つのアリは、それらの間に霧がかかっていても同じエリアにいます。 これにより、明らかに自分に属している領域に突然の境界線がないことが保証されます。 境界セルは、アリと敵から等距離にあるか、アリから20歩離れたセルであり、敵が見えないことがわかります。 2番目のケースでは、境界セルが今まで見たことのない水の上にあることが判明する場合があり、水を検出するとすぐにミッションを削除します。



ミッションを作成するとき、境界セルの1つをターゲットとして選択する必要があります。 アリが私の蟻塚の上に立たない場合、境界セルが選択され、そこへ行くのが最も速くなります（BFSを使用して決定されます）。 それ以外の場合、ターゲットセルは、このセルの近くにある自分のアリと敵のアリの数の比率、敵の蟻塚までの推定距離、近くのセルに行くミッションをすでに持っているアリの数、およびそこに着くまでにかかる時間を使用する複雑な式によって決定されますそこに着く...さあ、冗談です:)これは偶然に決定されます。 絶対に偶然。 このように：

 target = area.border.get(turnRandom.nextInt(area.border.size()));
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

これは私の最初の実装であり、非常にうまく機能したため、変更することはありませんでした。 ミッションが他のタスク（食料の収集など）によって中断された場合、新しいものが決定的に選択されたため、動作はまだ完全にランダムではなかったことに注意してください。 さらに、各ターンの境界は異なるため、ミッションは随時更新する必要があります。 これは、十分な時間があれば、すべての移動ごとに行われ、常に少なくとも10回の移動ごとに行われます。

雑多

セルは10回の移動で到達可能であると発言することができます- セルまでの距離が77以下であると正確に同じではありませんが、かなり近いので、問題はありませんでした。



かなりの時間、アリが行き来することがよくあります。 たとえば、彼が水に囲まれた洞窟に一人でいて、出口が1つしかない場合。 この場合、アリは11ターンの距離にあるケージを調べる必要があるため、1ターンごとにアリは洞窟に足を踏み入れます。 そして、次の動きで、調査するものが何もないことが判明したため、アリは国境に行き、次の動きで物語が繰り返されます。 ミッションの作成は安価な操作なので、これはそれほど怖いことではありません。 （ まあ、はい、しかし明らかにアイドルなアリはそれよりも悪いです。-約transl。 ）

食べ物

ここで特に興味深いものはありません。 目に見えるすべての食物からBFSを起動し、彼女の方向で見つかった最も近いアリを送ります。 私は食べ物の場所を保存せず 、1つのアリが互いに近い2つの食べ物を収集できるとは思わない 。 しかし、食べ物の近くに敵がいる場合に行動する特別な論理があります。 通常、私はアリの交換を避けようとしますが、食べ物の隣にまだアリがいる場合、敵が食べ物を集めようと決めたら、私はアリを犠牲にする準備ができています。



McLeopoldは、これが彼にどのように起こったのかについて語った良い投稿を書きました。

敵の蟻塚

食べ物と同様に、敵の蟻塚から始めてBFSを作ります。 敵の蟻塚から20歩以内の距離にある4匹以下のアリを襲撃します。 10個以下のアリがある場合、敵の蟻塚が互いに非常に近いマップでゲームの最初の降伏で問題を回避するために1つだけを送信します。 蟻塚に直接4匹以上の蟻を送ることはありませんが、敵の蟻が近くにいることが多く、非常に積極的にプレイするので、そこにたくさんの蟻がいます。

戦う

さて、楽しみが始まりました！ 間違いなく、戦いの論理が最も議論された問題でした。



私のアプローチはこれです。戦闘機をグループに分けて、次のターンに何が起こるか見てみましょう。 これを行うには、バージョン2以降のすべてではなく、アリが実行できるすべての動きをシミュレートします。すべての組み合わせについて、相手の考えられる動きを調べ、状況を評価して、最も有利なオプションを選択します。敵は私がどのように見えるかを知っており、私にとって最も危険な方法のように聞こえます。

これはミニマックスおよびアルファベータクリッピングに非常に似ており、いくつかの最大ノード（アリ用）および敵用の最小ノードが必要です。

例

以下の状況を見てみましょう。 アリA、B、Cは地雷（緑）、敵はアリXとY（青）です。 （ パーセント-水、ポイント-土地-約transl。 ）

 % % % % % % % % A % % % % % . B % % % % . . C % % X . . . % % % Y . . % % % % % % %
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

私は何が起こっているかを示す小さな図を描くのが面倒ではありませんでした：

N / E / S / Wはそれぞれ北/東/南/西に移動することを意味し、「-」はその場に留まることを意味します。



ツリーは、DFSを使用してオンザフライで生成されます。 アリAの可能な動きを検討することから始め、この動きをシミュレートし、アリBについて続行します。最後の敵のアリが移動した後、単純な式を使用して状況を評価します：（死んだ敵アリの数）-（死んだ蟻の数my）。 敵のノード（最小）は常に結果が最小になる動きを選択し、ノード（最大）はこの式の値が最大になる値を選択します。 A、B、Cを南（左のサブツリー）に移動すると、両方の敵がどこに移動しても死ぬため、値は+2です。 しかし、AをそのままにしてBとCだけを移動すると、両方の敵が東に移動でき、その結果、全員が死亡し、最終的な値は2-2 = 0になります。これは素晴らしいオプションです。 2の結果につながる可能性のある組み合わせがあることは既に知られているため、茶色のフレームの他の部分を見てはいけませんが、敵は常に私たちにとって最も有益ではない動きを選択するため、この茶色のフレームでは0を超えない値が選択されます。



ご覧のとおり、サブツリーを描画しませんでした。 さらに、可能な動きの数は非常に少なく、アリは5つしかないため、この場合、ツリーはアリの数から指数関数的にはるかに強くなります。



擬似コードでの実装は次のようになります。

 List myAnts List enemyAnts bestValue = -Infinity void max(antIndex) { if antIndex < myAnts.size myAnt = myAnts[antIndex] for each possible move of myAnt simulate move max(antIndex+1) undo move else value = min(0) if value > bestValue bestValue = value save the current simulated moves of all my ants } int min(antIndex) { if antIndex < enemyAnts.size minValue = +Infinity enemyAnt = enemyAnts[antIndex] for each possible move of enemyAnt simulate move value = min(antIndex+1) undo move if value < bestValue return -Infinity // cut! if value < minValue minValue = value return minValue else return evaluate() }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

アリのリストを埋めてから、最適な動きのリストを取得した結果として、max（0）を呼び出す必要があります。

最適化

移動しない隣接する2つのアリは、場所を切り替える場合と同じであるため、2番目のオプションは無視できます。 これを達成するために、戦闘前に各アリの位置を維持します。



最初のバージョンでは、8つまでが数百ミリ秒必要だったため、7つ以下のアリでバトルアルゴリズムを使用しました。 同時にいくつかの戦いがある可能性があるため、これは明らかに多すぎます。

チェックされた動きのリスト

2番目のバージョンでは、さまざまな最適化を試しました。これにより、多くの状況で著しく大きなグループをサポートできました。 今度は水なしの別の例を見てみましょう。各アリには、移動のための5つの異なるオプションがあります（2つのアリが同じセルに行くときはカウントしません）。

 . . . . . . . . A . . . . . . B . . . . . . C . . . . . . . . XY . . . . . . . . .
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

アリAはどうなりますか？ 彼が南に行けば、彼は戦いに参加できますが、彼がその場に留まるなら、彼は戦いから離れます。 もちろん、攻撃する意味があるかどうかはまだわからないので、両方のケースを考慮する必要があります。 しかし、Aが西、北、または東に行くのはどうですか？ したがって、彼は間違いなく戦いに参加することはなく、評価は彼がその場に留まる場合とまったく同じになり、これらの動きは重要ではなく、考慮する必要はありません。 しかし、BとCが所定の位置に残っている場合、Yはそれらを攻撃し、北に向かって歩きます。 また、BとCについては、北向きの動きの推定値が東向きの動きの推定値に等しいことに気付くことができますが、私はこれを考慮しませんでした。 そのため、アリごとに、チェックする必要がある動きのリストを計算できます。 ネストされたサイクルは多数あります。グループ内の各アリと近くにいるすべての敵の近くのセルをすべてチェックする必要があるためです。



敵に対しては、似たようなことをすることができますが、わずかに異なります。 Aをそのままにして、BとCを北に向けます。 XとYはアクセスゾーンの外にあります。何をするにしても、この評価はあなたがその場に留まるのと同じだからです。 Bがまだ北に行かず、同じ場所に残っている場合、Yは北への移動を考慮する必要があります。これは、これが戦闘につながるためです。 敵が動きを考慮する必要があるかどうかを知るためには、私のアリが特定のセルにいるかどうかを知る必要があることがわかります。 したがって、各敵には、セル（私のアリがいる可能性がある）からチェックする必要がある動きのリストへの対応があります。 これらの通信は、ネストされたループのより大きなクラウドで構築されています...

ここでは行と列の番号（行/列が示されています）を使用して依存関係テーブルを表示する別の例があるため、例を気に入っていただければ幸いです。

  0 1 2 3 4 5 0 . . . . . . 1 . . , A . . 2 . . . , B . 3 . . . . , . 4 . X . . . . 5 . . . . . .
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

（1/2）にアリがある場合、ant Xは（3/1）を確認する必要があります。 （2/3）がオンの場合、（3/1）および（4/2）を確認します。 （3/4）の場合、（4/2）をチェックします。 テーブルは次のようになります。

 (1/2) => [ (3/1) ] (2/3) => [ (3/1), (4/2) ] (3/1) => [ (4/2) ]
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

これらのリストはツリーの分岐を大幅に削減しますが、残念ながら、計算にかかる時間を見積もることは困難です。 私はアリの数に基づいてグループを切り離しませんが、考慮する必要がある動きの数と敵の数に制限を課します。



グループを構成するとき、私は任意に最初のアリを選択し、その後、彼と彼らが移動した場合に戦闘に参加できるすべての敵アリをグループに追加します。 次に、これらの敵が攻撃できるアリを近くに持っているかどうかを確認します。 そのようなものが複数ある場合、最初に最初のアリに近い方を追加し、彼のために敵を探しています。 このプロセスは、制限に達するか、追加できる人がなくなるまで繰り返されます。 私のアリのそれぞれにとって、彼のグループにはすべての敵がいることが重要です。 同時に、私のアリは1つのグループにしか所属できませんが、敵は一度に複数のグループに所属する可能性があります。

格付け

評価関数は、殺された人と見知らぬ人の数だけでなく、私とアリの敵との距離も考慮します。 ここにあります：

 if (beAgressive) return enemyDeadCount * 300 - myDeadCount * 180 - distValue; else return enemyDeadCount * 512 - myDeadCount * (512+256) - distValue;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

beAgressiveフラグが設定されている場合、死んだ敵のコストは300ポイントになり、死んだ敵は180ペナルティを科せられます。したがって、1人のアリを殺して1人の敵を殺し、3人のアリを殺して2人を殺します。 非アグレッシブモードでは、ボットは同等の交換を行いませんが、3対2を与える準備ができています。distValue-各アリから最も近い敵までの距離の合計。敵に近い方が良いため、この量を差し引きます。



beAgressiveがtrueに設定されるのはいつですか？これは、アリの総数や位置的優位性とは関係ありません。バトルに近いアリの数にのみ依存します。より正確には、私のアリの隣のバトル（グループではなく、バトル）のアリの最大数が14以上の場合にフラグが設定されます。なぜですか？主に42が14で割られているためです！

接近する敵

approachEnemiesメソッドは、戦闘の直後に呼び出され、敵の近くにいる私のアリの方向を送信します。アリごとに、最初にA *を起動します。これは、フリーセルのみに沿って移動します（つまり、他のアリがいるセルはチェックしません）。この方法でパスが見つかった場合、このパスの最初の移動が実行されました。この理由で、ボットは一列に並んでいることがよくあります。なぜなら、前線にボイドが形成されると、2行目の誰かがすぐにそこに行ったからです。



また、ベータ版の残りの部分であるattackDetachedEnemiesメソッドもあり、最初に孤立した敵にアプローチする必要がありました。

保護

最初のバージョンでは保護がまったくありませんでしたが、2番目のバージョンでは、多くのアリを含むカードの人気が高まったときに、それを追加しました。蟻塚を保護するのは、4頭以下の場合のみです。それが理にかなっているかどうかはわかりませんが、たくさんあるときはあまり好きではありません。私は蟻塚の近くで敵を探しています-信じられないでしょう-幅優先探索！次に、これらの敵を距離で並べ替え、それぞれに対して1人のディフェンダーを見つけようとします。最初に、私は敵が蟻塚に到達するために行かなければならない経路に近い人々の中から検索します。このパスは簡単に取得できます。BFS中に保存されている情報については、前のセルに戻るだけです。防御者がいない場合、別のBFSを起動します。これは、その敵の進路の1/4に最も近いアリを探しています。このzashitnikを1/2の方法で送信します。アリを1対1で交換することは、アリを失うことよりも怖くないため、これが安全かどうかはチェックしません。

敵の回避

一般的に、私は1対1のやり取りを避けようとするため、1人以上の敵の目で私だけのアリが逃げます。私はアリの可能なすべての動きを考慮し、安全なものを見つけようとしています。そうでない場合は、敵が私の方向に行けば、少なくとも敵を殺す動きをします。

ほとんどの場合、いくつかの安全な動きをすることができます。選択するために、バージョン3で最後に追加された急いで変更されたロジックの1つであることが判明しました。迷路マップ。ESCAPE_CHECK_DISTの最大深度（8に等しい）でBFSを起動し、すべての安全な動きの値を合計することで、これを回避しました。

 int addValue = (ESCAPE_CHECK_DIST+1-tile.dist); if (tile.type == Type.MY_ANT) addValue *= 3; else if (tile.type.isEnemy()) addValue *= -3;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

配布

また、これはほとんどの場合、ベータ版のエコーであり、これを取り除くことはできませんでした。ベータ版では、蟻塚の破壊はありませんでしたので、誰もが最初に食べ物に到達するために、達成ゾーンにできるだけ多くの細胞を保持しようとしました。

私はアリと彼の近くにいるすべての人からBFSを開始します。考えられるすべての動きについて、値を合計し、最小の動きで到達できるセルの数を最大にする動きを探します。（私は理解するためにこのフレーズを5回読み直しました！-約翻訳）。

ボットの最終バージョンでは、これはめったに使用されませんでした。一部の状況で、私のアリの1人が敵の隣にいたときだけです。

さて、それだけです！

私が説明しなかった多くの小さな詳細があると確信していますが、全体像が表示されるはずです。あなたがこれを読んだという事実からあなたがいくらかの感覚を持っていることを願っています、そして、私はより急なアルゴリズムを使用しないことを謝罪します。

IRCには引き続き参加できます。おそらく次のコンテストに参加しますが、再び多くの時間を費やすことはできないでしょう。

翻訳者から

正直なところ、この記事を読んだときはとても驚きました。勝者のアルゴリズムには非常に多くの欠陥がありました。天井から取った定数や係数を覚えておくか、多くの非常に重要な要素を考慮しないだけです。それにもかかわらず、勝者を批判することは困難です。なぜなら、彼らが言うように、「最初にそれを手に入れよう！」。最も成功したのはバトルアルゴリズムでした。非常にシンプルですが、明らかに非常に効果的です。直接の戦いでは、xathisが明確なリーダーだったからです。彼の考えに基づいて、係数の動的選択を備えたより一般的なシステムがまもなく作成され、TCPサーバーで非常に壮大な戦いが起こると考えられています。



あなたが興味を持っていたことを願っています。