リーダーが使用するアルゴリズムはほぼ同じで、基本的なものは2つでした-幅優先探索（ BFS ）で、近接戦闘で遠方のターゲットとミニマックスに最も近い経路を決定しました。 悪魔は、目標を選択して詳細を微調整する正しい方法に隠れていました。
複数のソースのBFS図（著者BenJackson）：
結果に影響する詳細を見つけるには、多くの理論的および実験的作業を行う必要がありました。
迅速な実装のために、シンプルで簡単に変更可能なコアアルゴリズムを用意します。
迅速かつ正確なテストをセットアップして、イノベーションの有用性を判断しました（一見有用な変更の70％が悪影響を及ぼしました）。
しかし、ローンチの時点で、私はこれをすべて知らなかったので、フォーラムの簡単な分析に基づいて、制限時間に苦労し始めました。 その結果、迅速でありながら扱いにくく、実験に便利ではない幅広い検索オプションが生まれました。 最初のバージョンは数日で準備が整い、食べ物を集める方法を知っていましたが、公式サーバーのトップ100に簡単に登りました。
相手の衝突アルゴリズム
大きくてきれいなものが欲しかったのですが、最終的には、切り捨てられたミニマックスによって実現され、非常にうまく機能しました。
毎ターン、5枚のカードは、敵がすべてのアリと共に一方向に移動するか、静止することを想定して計算されました。 さらに、マップは5×5セルの正方形に分割され、私のアリは攻撃ゾーン（最大5個）に落ち、あらゆる方法で移動しました。 結果はミニマックスによって評価に集められ、最も好ましい動きの組み合わせが選ばれました。 ジョイントをより正確に処理するために、5 * 5グリッド自体もターンごとにわずかにシフトしました。
ヒールに最も近い敵のアリを食物と同等にすることが可能になりました。残りの攻撃アルゴリズムはそれ自体で行われました。
ゲームの大幅な改善を可能にした詳細は非常に些細なものに見えました。
- 他にやるべきことがない場合や攻撃を受けている場合は、自分で治癒しないでください
- 互いに押しつぶさないでください
- あなたの子供に退く
- 攻撃されたセルをバイパスする
- ヒールに近すぎる敵の攻撃を優先する
- 攻撃中に、食料に移動します（そうでなければ、敵の反対側にぶら下がってしまいます）
- 1対1のゲームでは、より積極的に行動します。
締め切りの2週間前
Memetixが提案したスキームを実装しようとしました （最終10位）
アルゴリズムによると、マップ上の各セルは、ターゲットからの距離に応じて値を与えることが提案されました。 それは攻撃アルゴリズムに私に素晴らしくフィットするでしょう-私は単に全体的なスコアに値を追加し、ミニマックスとの最良の組み合わせを取得します。 しかし、すぐに良いことは何も起こりませんでした。食べ物の収集は現在のバージョンよりも悪く、反発のあるさまざまなダンスの後でも、「フィールド」の交差点でアリの群れを倒すことはできませんでした。 メソッドを完了する時間はありませんでした。 そのままにして、既存のコードを思い出すことにしました。
締め切りの前日
最新の係数が選択されます。 TCPサーバーでは、2つの異なる定数セットを持つ8（4 + 4）のコピーが24時間ハングアップします。 ただし、誰が優れているかを判断することは役に立たない-多数のプレーヤーによる一定のタイムアウト、または200アリの制限に近づいたとき（チームが長時間サーバーに行く）。 さらに、ボットクラスの分散により、評価アルゴリズムが評価を正しく決定できません。 カードのテストセットにも矛盾する結果が示されているため、少し攻撃的なバージョン（攻撃の計算時にマスクを5ずつずらすテクニックにより）が決勝戦に進みます。 また、最後の瞬間に、攻撃時に食物に向かって運転するためのボーナスがボルトで固定されます。 テストは満場一致でそれが有用であると誓った。
カオスの公式サーバー、主な参加者のほとんどは最新の変更で再送信します。
決勝
初日
驚きのない4ゲーム。 ライバルの選択はランダムです。
ゲームは非常に遅いです。
二日目
5回目から、主催者はTrueSkill評価評価アルゴリズムを組み込みました。評価は2つの係数で構成されています。mu-評価自体とシグマ-評価におけるシステムの信頼性を反映しています。 総合評価はmu-3 * sigmaです。 対戦相手は、近い評価と低いシグマで選択されます。 実際には、これは、大きなシグマのためにトップボットが他のボットよりもはるかに頻繁にプレイしないという事実につながりました。
Murashkaにとって、5番目のゲームは、戦争の霧の覆いの下を通り、小さな貧しいマップ上で、最初の200になかったボットが1つのヒールを盗んだという事実で終わりました。 合計-4からムーおよび500分の1の場所。 カジノはシックでオープンしています。
一部のプレーヤーの評価は誤っていると見なされます。 エラーが再び修正され、サーバーが再起動されます。
ゲームはさらに遅くなります。
3日目
スターターパックは20のゲームを喜んでプレイし、リーダーはアセットで6つのゲームをen望の目で見ました。 主催者は、対戦相手を選択するためのアルゴリズムを変更してゲーム数を均等にし、その後、5000位までのクリッピングを含めます。 そして、夕方には3000日まで、1日半の競争を延長します。 ハレルヤ！
4日目
2000および1000の場所でのカットオフ。
ロシアのティーポットヘドロンチームは、xathisから1ゲーム離れており、すべてリーダーの交代を期待しています...運命ではありません。
20日に静かにガサガサと音がします。
5日目-最終
500クリッピング。
ティーポットヘドロンが下がる（5位で終了）。
しかし、前日のシナリオはウクライナのGreenTeaで繰り返されます。 今回は成功しました。リーダーの交代は、サーバーが停止する2時間前に起こりました。 さらに、ライバルの選択アルゴリズムは再び失敗し、500のカットオフ制限外の参加者を選択し、彼がプレイしなかったゲームを補うためにすべてのサーバー電源を割り当てました-上位30分全体が慎重に足を吸います。
しかし、奇跡は起こりませんでした。xathisは自信を持って、当然のことながらその最初の場所を取り戻しました。
決勝の数時間前に14位を占めたグースバンプは、フルタイムの会議の最後の試合で日本の小牧をリードしていました。 同時に、ロシアのSDil_とmeduzによって可決されました。 再度カジノ、しかしそれはより悪いかもしれない-このカードのセットのための15位はよい結果である。
間違い
高速でありながら扱いにくいコードが変更を複雑にし、空想的な飛行を実現しました。
ミニマックスなしで戦いを解決しようとして多くの時間が無駄になりました。
目標の有能な定義とそれらの間のアリの分布にはほとんど注意が払われていません。 アリは敵のいない場所に行って地図をつかむのではなく、敵のグループの反対側の山に山積みする傾向がありました。
一列に並んで歩くことは間違いなく利点をもたらしますが、それを適切かつ迅速に実装する方法は私には決してありませんでした。
初期配布は効果的ではありませんでした。 癒しに近づくほど、アリがどこに行けばいいのか分からずに痙攣する結果、遠くのターゲットが頻繁に変わる可能性があります。
今後の注意事項
数か月で相手を有利にスタートさせるのは、思ったより難しいです。
ユーティリティを決定するテストシステムは非常に重要です。
最終日には、すべてが劇的に変化し、最終的な競争はテストとは大きく異なります。
あなたはすぐに小さなエラーを取り除く必要があります-それらは蓄積し、良い戦略が機能しなくなり、テスト中に破棄されるという事実につながる可能性があります。
組織
アイデアは素晴らしいです、仕事は巨大です、主催者はすべての感謝に値します。 エラーがなかったわけではありませんが、私たちは不完全な世界に住んでいます。
論争の的になった決定は、競争でスターターパックからボットを残すことでした。 主催者は理解できます-私は質量を宣言したかったです。 しかし、控えめな計算能力を備えているため、実際の参加者にとっては不便でした。 ただし、エラーは認識され、将来のフィルタリングを約束しました。
TrueSkillが修正する必要がある十分なエラーがあることは明らかであるため、非常に不安定な結果のカードのセットも完全に明確ではありません。
格付けの急激な上昇と下降は、おそらくカードのセットと選択アルゴリズムの機能によるもので、ランダムではありませんでした。 私のバージョンでは、最終的なマップの共通セット内で、一部のボットには非常に有益であり、他のボットには有益ではないクラスターが形成されています。 TrueSkillによって評価された評価システムが平衡状態になるとすぐに、マップ選択アルゴリズムが次のそのような組み合わせに遭遇し、5〜10ゲームのテーブルを混合しました。 端近くのシグマは最小限に縮小し、もはや何の影響も受けず、バーストを補正できませんでした。
最終評価
勝者レポート
最後に、Goosebumpsによる小さなAnt-Artが行われました。
競技会で今後の幸運を祈ります！