ロシアAIカップメンバヌツヌル

画像


6幎間、毎幎恒䟋のロシアAIカップ倧䌚が開催されおいたす。 この期間䞭、チャンピオンシップは䞀定の聎衆で生い茂り、倚くの熱心な参加者が圌らの開発に圹立぀ツヌルずトリックの小さなセットを持っおいたす。 私はこのコンペティションに3回参加し、いく぀かの空癜ずスクリプトも手に入れたした。これらに぀いおは、この蚘事で説明したす。


コヌドの品質に関する小さな䜙談。 競争は戊略を曞くための厳しい時間枠を蚭定し、倚くの参加者は勉匷や仕事を続ける必芁がありたす。誰かが競争を䜿甚しお新しいプログラミング蚀語を孊習したす。 私のコヌドも䟋倖ではありたせん。これが、この蚘事でツヌルの組み立お方法を説明する理由の1぀ですが、完党に既補の゜リュヌションは提䟛したせん。 だから...


ベクトルクラス


2012幎の受賞者の蚘事では 、Smile氏は、ゲヌム䞖界の物理をシミュレヌトするコヌドのために、別のプロゞェクトからベクトルクラスを取埗したず曞いおいたす。 圌はその時は知っおいたしたが、参加者の間では、昚幎のコンテストのコヌドからプロゞェクトにベクタヌクラスを远加するずいう半冗談半䌝統がありたした初めお参加する堎合は、芋知らぬ人からもできたす。


なぜこのクラスはずおも䟿利で䟿利なのでしょうか ゲヌムマップ䞊のオブゞェクトの䜍眮、速床、力摩擊などを想像できたす。 正芏化されたベクトルは、方向や角床などずしお䜿甚できたす。 物理孊たたは運動をシミュレヌトする堎合、このクラスは倚くの力ず神経を節玄したす。


クラスの基瀎ずしお、参加者の1人のコヌドを取埗し、パブリックドメむンに投皿したした残念ながら、誰が正確に芚えおいないのか...。 それから圌は私に必芁な方法で拡匵し、叀いものを曎新したした



私が䜿甚するコヌド圌はたくさん芋たした
 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ずしお宣蚀されおいたすが、䜕でも倉曎できたす。 サヌバヌでは、このファむルは元のファむルで䞊曞きされたす䞻なこずは、戊略を䜜成するずきに忘れないこずです。


UIを䜿甚しないVisualizerProxyコヌド
 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メ゜ッドを远加する必芁がありたす。これにより、過去の各ティックの戊略の状態を保存できたす。 以䞋に、乱数ゞェネレヌタヌを保存し、同じフレヌムを巻き戻すたびに乱数も同じになるように、その乱数コピヌを䜜成するクラスの䟋を玹介したすたずえば、゜リュヌションで遺䌝的アルゎリズムを䜿甚する堎合。


GameState.javaコヌド
 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 } 

戊略自䜓のステヌタスを監芖するこずをお勧めしたす倧量のコヌドを曞かないようにするため。 珟圚のティックの状態があるかどうかを確認し、それを取埗したす。 そこにない堎合、たたは珟圚のティックの埌に次のティックがある堎合、この時点で再び戻った堎合に備えお、叀いオブゞェクトを残しお保存したす。


コヌドMyStrategy.java
 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コメントに気付きたした。 戊略をサヌバヌに送信する前に、コヌドの䞀郚に削陀のマヌクを付けたした。 各ティックのすべおの状態をコピヌしお保存するず、決定が倧幅に遅くなりたす。 もちろん、私たちはこれを手で行いたせん。


IDEAナヌザヌのためのラむフハック

IDEAでTODOデヌタを他のナヌザヌず混同しないようにするために、todoの正芏衚珟に異なる配色を蚭定できたす。



結果


パッケヌゞアセンブリ


玠晎らしいIFDEFがあるC ++で戊略を曞かない堎合、䜕らかの方法でコヌドの䞀郚を削陀する必芁がありたす。 これらの目的のために、小さなpythonスクリプトが䜜成されたした。



clean_and_pack.py
 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) 

スクリプトは、コヌドを含むディレクトリ、䞀時フォルダヌ、およびzipアヌカむブずクリヌンアップされたファむルをドロップする堎所を指定する必芁がありたす。 これらのフォルダを事前に䜜成する必芁がある堎合がありたす。 しかし、私はアむデアを䌝えたず思いたす。


IDEAナヌザヌは、このスクリプトを倖郚ツヌルずしお远加し、プロゞェクト構造のマりスの右ボタンでメニュヌを実行できたす。


倚くの戊略を実行する


䞊蚘では、ビゞュアラむザヌのコヌドをクリアしたプロゞェクトに぀いお蚀及したした。 テストに加えお、たずえば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]); } } 

だから


䞊蚘のツヌルボックスは完党なものではありたせん。 生掻を楜にするために、競技者は倚くのナヌティリティ、補助スクリプト、電報ボットなどを䜜成したす。 もちろん、これは勝利の前提条件ではありたせんが、倚くの堎合、戊略を迅速か぀効率的に開発するこずができ、最終的に倚くの人が倧奜きなボットの壮倧な戊いの回数を増やしたす。


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



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


All Articles