Clever Geek Handbook

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か月で正圓化されるかどうかを芋おみたしょう。 出版埌、ロシア語を話す参加者の数が増えるこずを願っおいたす。


More articles:


All Articles