Geekly Articles each Day

2週間後のGoogle AIチャレンジ

多くの人が既に知っているように、 Google AIチャレンジは最近開始されました。これは、ウォータールー大学が開催し、Googleが支援するゲームPlanet Warsのボットを作成するための競争です。 昨日は公式発表から2週目（9週目）が終わりました。 競争はますます軍拡競争に似てきており、最初にボットがトップ50に入るのに十分だった場合、ほとんどの場合、スターターキットの例を打ち負かし、今すぐ試してみる必要があります。 これをどのように行うことができるかについて、また、現在行われているトーナメントのニュースについて。

コミュニティ

最初の数週間は、オーガナイザーの問題によって特徴付けられました。これはサーバーのパフォーマンス、「ダーティ」ゲームのケース、開始セットとユーザーの作業環境の間のさまざまな競合、12〜13日にコードを送信する問題です。 しかし、彼らの名誉のために、すべては十分に迅速に決定されました。 まあ、またはほとんどすべて...これまで、すべてのボットは平均で1時間に1回再生されます。つまり、コードの変更が評価にどのように影響するかを理解するには、1〜2日待つ必要があります（来週はおそらく別のサーバーが追加されるでしょう）。 この問題の一部は、コンピューターから直接ボットに接続できる非公式のTCPサーバーによって解決されます。 ゲームの頻度が大幅に増加し、プラスとして、デバッグデータを保存することが可能になります。 主な欠点は、サーバーにほとんどのトップボットがないため、結果はコードのテストまたは処理の時間にのみ意味があることです。 そして最新のニュース：この間、待望のLisp、Haskell、OCaml、CoffeeScript、およびあまり知られていないエキゾチックなもの：PHP、Perl、Javascript、Ruby（またはそれとは逆ですか？） が 、サポートされているC ++、C＃、Java、Pythonのリストに追加されました。

参加者によって作成されたユーティリティについて少し説明します。 これはLinuxユーザーの側からの見方であり、ここではWindowsに固有のことは何もないことを予約します。 だから：

ボット開発について

次に、参加中に得た経験を共有したいと思います。 彼は絶対的な真理の役割を装うのではなく、むしろ思考の糧です。 では、ボットは何ができるはずですか？

シミュレーション

成長と飛行船を考慮に入れて、いくつかの動きで惑星に何が起こるかを知る必要があります。 これがなければ、防御または攻撃のコストを正しく評価することは不可能です。 単純化された形式（中立惑星への同時攻撃の規則を除く）では、次のようになります。
public void Simulate （）{
// <Fleet>艦隊のリスト-ターゲット惑星に飛んでいる艦隊
if （フリートサイズ （） == 0 ）
帰る
sortFleets （ ） ;

//現在の計算状態の変数
int owner =ターゲット。 所有者 ;
int shipCount =ターゲット。 shipCount ;
//現在処理された動きを保存して結果を蓄積します
int lastGrowth = 0 ;

for （ int i = 0 ; i <フリートサイズ （ ） ; i ++ ） {
//移動の結果が計算される場合、状態を保存します
if （ lastGrowth < fleets。get （ i ） 。turnsRemaining ） {
if （ i > 0 ）
状態。 add （ new PlanetState （ shipCount、owner、lastGrowth ） ） ;
//プレイヤー惑星でのみ成長
if （ target。owner > 0 ）
shipCount + =ターゲット。 growthRate *
（艦隊。get （ i ） .turnsRemaining -lastGrowth ） ;
//この動きはさらに計算されます
lastGrowth =フリート。 get （ i ） 。 turnsRemaining ;
}
if （ owner ！ = fleets。get （ i ） 。owner ）
shipCount-=フリート。 get （ i ） 。 numShips ;
他に
shipCount + =フリート。 get （ i ） 。 numShips ;
//所有権の変更
if （ shipCount < 0 ） {
shipCount * = -1 ;
所有者=フリート。 get （ i ） 。 所有者 ;
}
if （ i ==フリートサイズ （ ） -1 ）
状態。 add （ new PlanetState （ shipCount、owner、lastGrowth ） ） ;
}
}
ちなみに、キリル文字のコメントを含むコードはサーバー上でコンパイルされないため、送信する前に注意してください。 状態の変化が計算された後、移動の予測を取得するのは非常に簡単です。
public PlanetState getInfoForTurn （ int turn ） {
int growth = target。 growthRate ;
//入ってくる艦隊がなかった場合と
//最初のフリートが到着する前にリクエストが移動する場合
if （ states。size （ ） == 0 || states。get （ 0 ） 。turn > turn ） {
//中立惑星にはゲインがありません
if （ target。owner == 0 ）
成長= 0 ;
新しい PlanetStateを返します（ターゲット。shipCount + turn * growth、
ターゲット。 所有者 、ターン） ;
}
int last =状態。 サイズ （ ） -1 ;
//最後の艦隊の到着後に移動する
if （ turn > = states。get （ last ） 。turn ） {
if （ states。get （ last ） 。owner == 0 ）
成長= 0 ;
新しい PlanetStateを返す（ states.get （ last ） .shipCount +
（ターンステート。get （ last ） 。turn ） *成長、
状態。 get （最後） 。 所有者 、ターン） ;
}
//最初と最後の艦隊の到着間を移動します
for （ int i = 1 ; i < = last ; i ++ ）
if （ states。get （ i ） 。turn > turn ） {
if （ states。get （ i- 1 ） 。owner == 0 ）
成長= 0 ;
新しい PlanetStateを返す（ states。get （ i- 1 ） 。shipCount +
（ターンステート。get （ i- 1 ） 。 ターン ） *成長、
状態。 get （ i- 1 ） 。 所有者 、ターン） ;
}
nullを 返し ます 。
}

ロギング

まず、これはデバッグ情報を取得する方法の1つであり、「正しい」ログはプレーヤーでの視覚化よりも分析に便利です（ただし、相互に排他的ではありません：公式フォーラムでスキップされたプレーヤーでデバッグ情報を表示できるパッチへのリンク）。 また、ログを使用すると、ゲームの結果をバッチで確認できます。 一般に、テストの自動化により、時間と労力が大幅に節約されます。

ゲームスタイルの切り替え

すでに異議を聞いています。 実際、あなたは正しい、あなたはそれを行うことができます...しかし、ルールはゲームの継続時間（200の動き）を規制するという事実、オープニングでブルートフォースが容易であるという事実、そしてカードのサイズの違いがスタイルの変更を強制します。 例：
if （ myPlanets。 サイズ （ ） < 4 ）
モード= BotMode。 bmStart ;
else if （ myPower > enemyPower * 3 && turn > 50 ）
モード= BotMode。 bmFinishHim ;
else if （ターン> 180 || myPower * 5 < enemyPower * 4 ）
モード= BotMode。 bmRegenerate ;
他に
モード= BotMode。 bmNormal ;

評価関数

問題を解決するためのアプローチが何であれ、見つかったものの中からより好ましいアクションのオプションを選択する必要があります。 これは、攻撃のターゲットの選択、それが実行される惑星、艦隊を移動するための目標（これについては以下で詳しく説明します）などに関係します。 このために、他のコードから分離できる評価関数が必要です。 おそらくハードコーディングされたパラメーターがあり、テスト中にボット起動コマンドラインを介して送信できるため、多くの組み合わせを自動的に実行し、最適な組み合わせを選択できます。

標準的なトリック

明らかに攻撃に加えて、次のような標準的な手法を実装することをお勧めします。

スターターキットの変更

ゲームオブジェクトを使用した簡単な操作を解析および実行するために、主催者が提供するコードを書き換えることをお勧めします。 Javaから判断すると、スターターキットは非常に曲がって書かれています。 言語が最速ではないことを考えると、それを終了することをお勧めします。 ところで、多くの言語では、これらの問題が解決されたスターターキットが既に修正されています

次は？

上記のリストは、（今のところ）上位50に入るには十分です。さらに、独自のアプローチと数学的な装置の使用は有用です。 ボットを開発できる主な分野のうち、次の点に注意してください。
  1. 物語。 過去の動きの結果を考慮することで、フローを監視し、原則に従ってトラフィックの集中と実際の成長の場所を特定できます
    realGrowth = growthRate +（fleetsInMy-fleetsInEnemy-fleetsOut）/ historySize
  2. マップ分析。 最も単純なケースでは、この問題は、自身と異星の惑星までの平均距離と最小距離、成長、それらの船の数を考慮した評価関数を導入することで解決されます。 より複雑なケースでは、グラフ内の最適なパスと最大フローを見つける問題が発生します。
  3. 可能な動きの分析。 ターゲットを選択した後、それぞれに対して攻撃を実行できる最も成功した惑星のセットをいくつか生成できます。 同時に、各セットについて、有効性と、捕獲または保護のために送られる必要がある船の数の評価があります（さらに、この数は惑星間で再分配できます）。 このような一連の移動を選択する際に、利用可能な数の船を送信すると最大の利益が得られるという問題があります。 これはわずかに変更されたパッケージングタスクです。
  4. 待っています。 毎ターン、すべての惑星からのすべての成長を最も優先度の高いエリアに送るボットがあります。 彼らはすべて「働く」という感覚がありますが、そうですか？ 送信された艦隊は、相手にとって計算がはるかに簡単です。待機中の艦隊とは異なり、すでに目標を持っています。 同時に、あなたが確実に（まあ、またはほぼ確実に）捕まえるか、逆に守備に留まることができるような目標を待つことが可能になります。 したがって、総質量が特定のマークを超えるまで結果を達成できないため、小さな部分での攻撃は悪意がある可能性が高いことを理解することが重要です。 この質量があなたの中に蓄積される瞬間まで待ってみませんか。 そしてもう1つの事実：派遣された艦隊は目標に到達するまでゲームから除外されるため、一掃されるまでに優れた部隊による攻撃が目標に到達する状況が発生しないように距離を考慮することが重要です。
  5. 移動間の計算。 ルールによると、移動のタイムアウトは1000ミリ秒であり、ボットはスレッドを使用できません。 しかし、コースの完了後、エンジンがそれらを処理する瞬間に考慮することができます。 これらの瞬間に、履歴を操作し、ほとんど変化しない値（たとえば、惑星間の距離、流れ、中立惑星の優先順位など）を計算してキャッシュできます。

おわりに

そしてタイトルの「AI」について。 ニューラルネットワークまたは遺伝的アルゴリズムを使用して共通の作業ロジックを実装することはほとんど意味がありません（このため、手続き主義またはマルチエージェントシステムの方がはるかに優れています）が、パス/フローの発見、目標の認識と評価、およびパッケージング問題の顕著なタスクを解決するために使用できます。 現時点では誰もAIアプローチを使用していないか、大きな利点をもたらしていないか、これまでのブルートフォースのヒューリスティック検索がタイムアウトに収まり、勝つことができます。 いずれにせよ、さらに興味深いものになります。 名前が1か月か2か月で正当化されるかどうかを見てみましょう。 出版後、ロシア語を話す参加者の数が増えることを願っています。

Source: https://habr.com/ru/post/J104861/

More articles:


All Articles