6年間、毎年恒例のロシアAIカップ大会が開催されています。 この期間中、チャンピオンシップは一定の聴衆で生い茂り、多くの熱心な参加者が彼らの開発に役立つツールとトリックの小さなセットを持っています。 私はこのコンペティションに3回参加し、いくつかの空白とスクリプトも手に入れました。これらについては、この記事で説明します。

コードの品質に関する小さな余談。 競争は戦略を書くための厳しい時間枠を設定し、多くの参加者は勉強や仕事を続ける必要があります。誰かが競争を使用して新しいプログラミング言語を学習します。 私のコードも例外ではありません。これが、この記事でツールの組み立て方法を説明する理由の1つですが、完全に既製のソリューションは提供しません。 だから...

ベクトルクラス

2012年の受賞者の記事では 、Smile氏は、ゲーム世界の物理をシミュレートするコードのために、別のプロジェクトからベクトルクラスを取得したと書いています。 彼はその時は知っていましたが、参加者の間では、昨年のコンテストのコードからプロジェクトにベクタークラスを追加するという半冗談半伝統がありました（初めて参加する場合は、見知らぬ人からもできます）。

なぜこのクラスはとても便利で便利なのでしょうか？ ゲームマップ上のオブジェクトの位置、速度、力（摩擦など）を想像できます。 正規化されたベクトルは、方向や角度などとして使用できます。 物理学または運動をシミュレートする場合、このクラスは多くの力と神経を節約します。

クラスの基礎として、参加者の1人のコードを取得し、パブリックドメインに投稿しました（残念ながら、誰が正確に覚えていないのか...）。 それから彼は私に必要な方法で拡張し、古いものを更新しました：

• フィールドを公開し、 getX
  
  
  
  およびgetY
  
  
  
  を削除しました（これにより、コードがより簡潔に記述されます。追加の関数呼び出しについて心配する必要はありません）。
• 数値の乗算、別のベクトルの減算などの操作中に、新しいベクトルの作成を削除しました。 作成される中間オブジェクトが少ないほど、すべてが高速に動作します。新しいオブジェクトが必要な場合は、 copy
  
  
  
  メソッドが追加されました。 コードの記述はより困難になります-すべきでないオブジェクトの変更を開始しないように、常に監視する必要があります。
• ベクトル間の二乗距離を計算する方法を追加し、長さの計算を変更しました（これについては記事の次の段落で詳しく説明します）。
• ほとんどのメソッドはベクトル自体を返します。これにより、たとえば次のように、チェーンで呼び出すことができます。
  
  

   double speed = ... Vec2D oldPosition = ... Vec2D position = new Vec2D(1.0d, 0.0d).mul(speed).mul(stepsCount).rotate(unit.getAngle()).add(oldPosition);
        
        
  
          
          
          
        
  
      
          
          
          
        
        
  
          
          
          
        
  
      
       

 import static java.lang.Math.*; public class Vec2D { public double x; public double y; public Vec2D() { x = 0; y = 0; } public Vec2D(double x, double y) { this.x = x; this.y = y; } public Vec2D(Vec2D v) { this.x = vx; this.y = vy; } public Vec2D(double angle) { this.x = cos(angle); this.y = sin(angle); } public Vec2D copy() { return new Vec2D(this); } public Vec2D add(Vec2D v) { x += vx; y += vy; return this; } public Vec2D sub(Vec2D v) { x -= vx; y -= vy; return this; } public Vec2D add(double dx, double dy) { x += dx; y += dy; return this; } public Vec2D sub(double dx, double dy) { x -= dx; y -= dy; return this; } public Vec2D mul(double f) { x *= f; y *= f; return this; } public double length() { // return hypot(x, y); return FastMath.hypot(x, y); } public double distance(Vec2D v) { // return hypot(x - vx, y - vy); return FastMath.hypot(x - vx, y - vy); } public double squareDistance(Vec2D v) { double tx = x - vx; double ty = y - vy; return tx * tx + ty * ty; } public double squareDistance(double x, double y) { double tx = this.x - x; double ty = this.y - y; return tx * tx + ty * ty; } public double squareLength() { return x * x + y * y; } public Vec2D reverse() { x = -x; y = -y; return this; } public Vec2D normalize() { double length = this.length(); if (length == 0.0D) { throw new IllegalStateException("Can\'t set angle of zero-width vector."); } else { x /= length; y /= length; return this; } } public Vec2D length(double length) { double currentLength = this.length(); if (currentLength == 0.0D) { throw new IllegalStateException("Can\'t resize zero-width vector."); } else { return this.mul(length / currentLength); } } public Vec2D perpendicular() { double a = y; y = -x; x = a; return this; } public double dotProduct(Vec2D vector) { return x * vector.x + y * vector.y; } public double angle() { return atan2(y, x); } public boolean nearlyEqual(Vec2D potentialIntersectionPoint, double epsilon) { return abs(x - potentialIntersectionPoint.x) < epsilon && abs(y - potentialIntersectionPoint.y) < epsilon; } public Vec2D rotate(Vec2D angle) { double newX = angle.x * x - angle.y * y; double newY = angle.y * x + angle.x * y; x = newX; y = newY; return this; } public Vec2D rotateBack(Vec2D angle) { double newX = angle.x * x + angle.y * y; double newY = angle.x * y - angle.y * x; x = newX; y = newY; return this; } @Override public String toString() { return "Vector (" + String.valueOf(x) + "; " + String.valueOf(y) + ")"; } public Vec2D div(double f) { x /= f; y /= f; return this; } public Vec2D copyFrom(Vec2D position) { this.x = position.x; this.y = position.y; return this; } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

2点間の距離

ロシアAIカップのほぼすべての戦略では、2つのポイント間の距離（射撃できる距離、オブジェクトの衝突、ターゲットまでの距離など）が何らかの形で考慮されます。 問題は、ティックごとに数十万または数百万のそのようなティックをカウントする必要があるときに始まります。 プロファイラーを実行すると、 hypot



、 sqrt



メソッド、およびいくつかの戦略sin



およびcos



計算に多くの時間が費やされていることがhypot



ます。

（このスクリーンショットでは、FastMath.hypotメソッドを変更してMath.hypotを呼び出した結果を返します）

この問題を解決するにはさまざまな方法があります。

ポイント間の二乗距離

その計算では、座標差の平方和の根をとる必要はありません。これにより、計算が大幅に高速化されます。 ただし、結果は、たとえば、ショットの範囲の2乗（危険ゾーンでチェックしている場合）または半径の2乗（円との衝突をチェックしている場合）と比較する必要があります。

残念ながら、距離の2乗を常に使用できるとは限らず、潜在的なフィールドを計算するための数式など、一部の計算では距離だけが必要です。

おおよその計算

ポイント間の距離を計算するために、正確ではないが（十分な）正確な方法を使用できます。 これがFastMath （hypotメソッド）などでどのように実装されるか。 プログラミング言語の既製のソリューションを探すだけです。

値表

より高い精度を必要とせず、メモリ制限が高すぎない場合は、特定の手順で事前に関数値を計算できます。 このアプローチは、 sin



とcos



適していsin



。

ビジュアライザー

戦略をデバッグするプロセスは非常に骨が折れ、複雑であり、競技場に追加の要素を描く能力が重要です。 残念ながら、これは主催者が提供する標準のビジュアライザーを使用して行うのはそれほど簡単ではありません。 そして、Repeaterユーティリティを使用すると、すべてを盲目的に見る必要があります。 さらに、独自のビジュアライザーは多くの場合、巻き戻し機能をサポートして、戦略の異常な動作を簡単に学習できるようにします。

コンテスト中、ビジュアライザーを作成するための2つの主なアプローチがありました。

外部

ビジュアライザーは、ソケットまたはファイルを介して描画する必要があるものに関する情報を受け取る別個のアプリケーションです。

長所：汎用性。 1つのビジュアライザーをさまざまなプログラミング言語に使用できます。

短所：機能を拡張することは困難です（APIを更新する必要があります）

電報ユーザー@kswaldemarは、オープンソースのopenGLオープンソースビジュアライザーを作成しました。 githubからダウンロードできます。 ビジュアライザーは巻き戻しをサポートし、かなり多数のオブジェクトを描画できます。 他のユーザーは、C ++、C＃、Java、Python、Ruby、Rust、Swift用のクライアント（API上のラッパー）を作成しました。

作り付け

戦略自体と統合するビジュアライザー。

長所：簡単に新しいものを描くことができます。 戦略が使用して保存するデータ構造のレンダリングに特化することができます。

短所：単一の戦略の一部としてのみ機能し、他のプロジェクトに移行することは非常に困難です。

言語を変更するときは、ゼロから作成する必要があります。

最後のビジュアライザーを2番目の方法で書くことにしました。 それは私にはもっと簡単で速いように思えました。 現時点では、ソースコードをアップロードしません。 彼は私の戦略に強く結びついており、参加者がどのように機能するかを理解しようとする競争から気を散らされてほしくありません。

この場合、レンダリングは非常にシンプルであり、JPanelの上で実行されますが、すべてが常にうまく機能するとは限りません。

Romkaのレビューに触発されて、昨年のコンテスト開始の数週間前に、外部のJavaScriptビジュアライザーを作成しました。 ブラウザーで開きました（巻き戻しとレイヤー化の機能を備えているため、かなりうまくいきました）。 実行時の戦略は、ビジュアライザーにロードされるはずのjsonログファイルを生成することでした。 しかし、現実には、ゲームに含まれるオブジェクトが多すぎて20,000ティック持続し、ブラウザがクラッシュした巨大なログファイルが生成されることが判明しました。

したがって、すでに再生された試合をログで描画するビジュアライザーを作成する場合は、リプレイデータを保存する形式と苦痛に値するかどうかを検討する必要があります。 私は価値がないと自分で決めました。

ビジュアライザーのプロキシ

私にとっての主な発見は、戦略によって送信され、世界の州のローカルランナー/リピーターユーティリティによって返される動きをインターセプトするプロキシクラスでした。 彼のおかげで、テスト中に戦略の異常な動作を確認するために巻き戻すことができるだけでなく、戦略にブレークポイントを設定してゲームを最初に見たときとまったく同じ状態にディベースするために適切なタイミングで巻き戻すことができます。 かっこいいですね。

これがどのように機能するかを理解するために、Javaを例として使用して言語パッケージがどのように機能するかを見てみましょう。 アプリケーションへのエントリポイントはRunnerクラスです。 起動時に、Local Runnerによって送信された世界の状態を読み取り、ストラテジー（クラスMyStrategy ）によって実行されたアクションを送り返すRemoteProcessClientオブジェクトが作成されます。 サーバーからのすべてのメッセージをインターセプトするには、RemoteProcessClientクラスから継承し、 readPlayerContextMessage



およびwriteMoveMessage



をオーバーライドするreadPlayerContextMessage



ありwriteMoveMessage



。 RemoteProcessClientクラスはfinalとして宣言されていますが、何でも変更できます。 サーバーでは、このファイルは元のファイルで上書きされます（主なことは、戦略を作成するときに忘れないことです）。

 public class VisualizerProxy extends RemoteProcessClient { private static final int[] FPS_LIMITS = new int[]{1, 5, 10, 15, 20, 30, 60, 120, 0}; private int fpsLimitIndex = 6; private long startTime = 0; private int currentFrame = 0; private int endGameFrame = Integer.MAX_VALUE; private boolean isRunning = true; private boolean processOneFrame = false; private final Object runningLock = new Object(); private List<PlayerContext> frames = new ArrayList<>(); private void setFrame(int value) { synchronized (this.runningLock) { this.pause(); this.currentFrame = Integer.max(Integer.min(value, this.frames.size()), 0); this.runningLock.notifyAll(); } } private void play() { this.isRunning = true; this.processOneFrame = false; } private void pause() { this.isRunning = false; this.processOneFrame = true; } private void toggle() { synchronized (runningLock) { if (isRunning) { this.pause(); } else { this.play(); runningLock.notifyAll(); } } } private VisualizerProxy(String host, int port) throws IOException { super(host, port); this.createControls(); this.addEventsListeners(); } private void createControls() { } private void addEventsListeners() { } @Override public PlayerContext readPlayerContextMessage() throws IOException { this.startTime = System.nanoTime(); PlayerContext frame = null; while (frame == null) { // Wait until not paused synchronized (this.runningLock) { while (!this.isRunning && !this.processOneFrame) { try { this.runningLock.wait(); } catch (InterruptedException e) { e.printStackTrace(); } } this.processOneFrame = false; } if (this.currentFrame >= this.endGameFrame) { // GAME END message show... this.isRunning = false; } else if (this.currentFrame == this.frames.size()) { frame = super.readPlayerContextMessage(); if (frame != null) { this.frames.add(frame); } else { this.endGameFrame = this.currentFrame; } } else { frame = this.frames.get(this.currentFrame); } } assert this.currentFrame < this.frames.size(); return frame; } @Override public void writeMoveMessage(Move move) throws IOException { this.drawer.finishFrame(); this.currentFrame++; if (this.currentFrame == this.frames.size() && this.currentFrame < this.endGameFrame) { super.writeMoveMessage(move); } long endTime = System.nanoTime(); if (FPS_LIMITS[this.fpsLimitIndex] > 0) { double diff = (1000.0 / FPS_LIMITS[this.fpsLimitIndex]) - (endTime - startTime) / 1000000.0; if (diff > 0) { try { Thread.sleep((long) diff); } catch (InterruptedException e) { e.printStackTrace(); } } } } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

UIコードからコンポーネントと一部の機能を削除して、わかりやすくしました。

この場合のボタンとスライダーは、 setFrame



メソッドを使用して巻き戻し、 fpsLimitIndex



を使用して1秒あたりのフレーム数の制限を設定します。 基本的な考え方は単純です：フレームを順番に返しますが、そうでない場合はこれでゲームは終了します。以前に保存しなかった場合はローカルランナーに次のフレームを要求します。 一時停止があり、巻き戻しを開始すると自動的に設定されます。

この場合、すべてのフレームを保存しても安全です。なぜなら、 十分なメモリがある場合にのみ、RemoteProcessClientがすべてのオブジェクトを新しい方法で作成します（ -Xmx1024M



フラグを使用して戦略を実行し、これまで問題はありませんでした）。

さて、世界の状態が任意のティックに戻ると、最大の問題が残ります-このティックの戦略の状態です。 多くの参加者の決定には、以前のティックで蓄積された世界に関する情報が保存されます。 これは、最後のティックで世界の状態を受け取った後、戦略が前回とまったく同じように動作しないことを意味します。

これは深刻な問題であり、その解決策として、ティック間で保持する必要がある戦略のすべての状態を別のクラスに入れることを提案します。 また、そこにcopy



メソッドを追加する必要があります。これにより、過去の各ティックの戦略の状態を保存できます。 以下に、乱数ジェネレーターを保存し、同じフレームを巻き戻すたびに乱数も同じになるように、その乱数コピーを作成するクラスの例を紹介します（たとえば、ソリューションで遺伝的アルゴリズムを使用する場合）。

 import model.*; // TODO: REMOVE START import java.lang.reflect.Field; import java.util.concurrent.atomic.AtomicLong; // TODO: REMOVE END class GameState { Random random; GameState(Game game, World world) { random = new Random(game.getRandomSeed()); ... } void update(World world) { ... } // TODO: REMOVE START GameState(long randomSeed) { random = new Random(randomSeed); } GameState copy() { long theSeed = 0L; try { Field field = Random.class.getDeclaredField("seed"); field.setAccessible(true); AtomicLong scrambledSeed = (AtomicLong) field.get(random); //this needs to be XOR'd with 0x5DEECE66DL theSeed = scrambledSeed.get(); } catch (Exception e) { //handle exception } return new GameState(theSeed ^ 0x5DEECE66DL); } // TODO: REMOVE END }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

戦略自体のステータスを監視することをお勧めします（大量のコードを書かないようにするため）。 現在のティックの状態があるかどうかを確認し、それを取得します。 そこにない場合、または現在のティックの後に次のティックがある場合、この時点で再び戻った場合に備えて、古いオブジェクトを残して保存します。

 public final class MyStrategy implements Strategy { private boolean initializationRequired = true; private GameState state = null; @Override public void move(Player me, World world, Game game, Move move) { if (initializationRequired) { initialize(me, world, game); initializationRequired = false; } // TODO: REMOVE START loadState(world.getTickIndex()); // TODO: REMOVE END state.update(world); // MAIN LOGIC HERE // TODO: REMOVE START saveState(world.getTickIndex() + 1); // TODO: REMOVE END } private void initialize(Player me, World world, Game game) { state = new GameState(game, world); // TODO: REMOVE START states = new GameState[world.getTickCount() + 1]; saveState(world.getTickIndex()); // 0 tick. // TODO: REMOVE END } // TODO: REMOVE START private int prevTick = -1; private int maxTick = -1; private GameState[] states; private void saveState(int tick) { if (tick > maxTick) { maxTick = tick; states[tick] = state.copy(); } prevTick = tick; } private void loadState(int tick) { if (prevTick > tick) { state = states[tick].copy(); return; } // RAIC 2016 has 'frozen' strategies, so we should handle cases when we were frozen for some ticks. GameState loadState = null; int statesBetween = 0; for (int i = prevTick + 1; i <= tick; i++) { if (states[i] != null) { statesBetween++; loadState = states[i]; } } if (statesBetween > 1) { state = loadState.copy(); } } // TODO: REMOVE END }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

それだけです。GameStateクラスのcopy



メソッドをサポートして、戦略の状態をコピーするだけです。 これは、この決定のマイナスの最大値です。 ティック間で転送する必要があるデータが大量にある場合、このメソッドのサイズは大幅に増加する可能性があり、メンテナンスが非常に難しくなります。

気配りのある読者は、コード// TODO: REMOVE START



および// TODO: REMOVE END



コメントに気付きました。 戦略をサーバーに送信する前に、コードの一部に削除のマークを付けました。 各ティックのすべての状態をコピーして保存すると、決定が大幅に遅くなります。 もちろん、私たちはこれを手で行いません。

パッケージアセンブリ

素晴らしいIFDEFがあるC ++で戦略を書かない場合、何らかの方法でコードの一部を削除する必要があります。 これらの目的のために、小さなpythonスクリプトが作成されました。

• 必要なファイルのみをコードとともに一時フォルダーにコピーし、
• マークされた領域を削除します
• zipアーカイブに日付と時刻をパックし、
• クリーニングされたファイルを2番目のプロジェクトにコピーします（ビジュアライザーなしでテストに使用されます）。
• 一時フォルダーをクリーンアップします。
  
  zipアーカイブをサイトにアップロードし、ボットが最高の権利を得るためにどのように戦っているのかを見るだけです。

 import os from shutil import copyfile, rmtree import zipfile from datetime import datetime root_dir = os.path.dirname(__file__) root_path = os.path.join(root_dir, '..\\src\\main\\java') temp_path = os.path.join(root_dir, '..\\temp') out_path = os.path.join(root_dir, '..\\..\\zipped') for_optimization_path = os.path.join(root_dir, '..\\..\\zipped\\java-cgdk-ru-master\src\main\java') if not os.path.exists(out_path): os.mkdir(out_path) zip_name = 'strategy_{}.zip'.format(datetime.now().strftime("%Y%m%d_%H-%M")) with zipfile.ZipFile(os.path.join(out_path, zip_name), 'w', zipfile.ZIP_DEFLATED) as zipf: queue = [''] while queue: cur_path = queue.pop(0) if cur_path.startswith('model'): continue for entity in os.scandir(os.path.join(root_path, cur_path)): # Filter some files. if entity.name in ['Strategy.java', 'Runner.java', 'Visualizer.java', 'VisualizerProxy.java', 'RemoteProcessClient.java']: continue if entity.is_dir(): queue.append(os.path.join(cur_path, entity.name)) else: new_path = os.path.join(temp_path, cur_path) if not os.path.exists(new_path): os.mkdir(new_path) new_full_path = os.path.join(new_path, entity.name) with open(os.path.join(root_path, cur_path, entity.name), 'r', encoding="utf8") as rd, \ open(new_full_path, 'w', encoding="utf8") as wt, \ open(os.path.join(os.path.join(for_optimization_path, cur_path), entity.name), 'w', encoding="utf8") as wtopt: filter_flag = True for line in rd.readlines(): if "TODO: REMOVE START" in line: assert filter_flag == True, "No clossing remove tag" filter_flag = False elif "TODO: REMOVE END" in line: assert filter_flag == False, "No open remove tag" filter_flag = True elif filter_flag: wt.write(line) # Copy clean files to another project wtopt.write(line) assert filter_flag == True, "No clossing remove tag" zipf.write(new_full_path, arcname=os.path.join(cur_path, entity.name)) rmtree(temp_path)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

多くの戦略を実行する

上記では、ビジュアライザーのコードをクリアしたプロジェクトについて言及しました。 テストに加えて、たとえばp2-startup-command



パラメーターを使用して、Local Runnerで敵として実行できるjarファイルを生成するためにも使用されます。 または、次のようなpythonスクリプトを使用できます。

 import subprocess def run_strategy(filename, port, args=None): params = ['java', '-jar', filename, "127.0.0.1", str(port), "0000000000000000"] if args: params.extend(map(str, args)) return subprocess.Popen(params)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

この場合、ホスト、ポート、およびsidに加えて、追加のパラメーターが開始時に戦略に転送されます。 これを使用して、さまざまなパラメーターで戦略を自動的に起動し、結果を確認できます（ローカルランナーはデフォルトでresults.txtファイルを生成しますが、名前は設定で変更できます）。 もちろん、この関数が呼び出されるまでにローカルランナーは既に実行されているはずです。

ストラテジーとそれ自体の自動バトル、およびこれらのバトルに基づいた定数の選択は別の記事に値しますが、今度はストラテジー内でこのようにパラメーターを送信する方法を考えてみましょう。 Runnerクラスを微調整する必要があること、つまり、2つ以上の入力パラメーターを受け入れるように2つのメソッドを更新する必要があることを既に推測している場合があります。

 public static void main(String[] args) throws IOException { if (args.length >= 3) { new Runner(args).run(); } else { new Runner(new String[]{"127.0.0.1", "31001", "0000000000000000"}).run(); } } private Runner(String[] args) throws IOException { remoteProcessClient = new VisualizerProxy(args[0], Integer.parseInt(args[1])); token = args[2]; if (args.length > 3) { Params.INSTANCE.setValues(Arrays.copyOfRange(args, 3, args.length)); } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

この場合のParams



は、デフォルト値を更新するメソッドを持つシングルトンです。

 public enum Params { INSTANCE; private Params() { } public double c1 = 1.0d; public double c2 = 2.0d; public void setValues(String[] args) { c1 = Double.parseDouble(args[0]); c2 = Double.parseDouble(args[1]); } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

だから

上記のツールボックスは完全なものではありません。 生活を楽にするために、競技者は多くのユーティリティ、補助スクリプト、電報ボットなどを作成します。 もちろん、これは勝利の前提条件ではありませんが、多くの場合、戦略を迅速かつ効率的に開発することができ、最終的に多くの人が大好きなボットの壮大な戦いの回数を増やします。

コンテストにご関心をお寄せいただきありがとうございます。