Already 6 years, the annual competition is held Russian AI Cup. During this time, the championship has become a regular audience and many avid participants have a small set of tools and tricks that help them develop. I participated in this competition 3 times and also got a number of blanks and scripts, which I want to talk about in this article.

A small digression about the quality of the code. Competition sets a tough time frame for writing a strategy, many participants need to continue learning or working, someone uses a competition to learn new programming languages ​​- all of this has an extremely negative effect on the readability of the code. My code is not an exception, and this is one of the reasons why in the article I will explain how to assemble my toolkit, but I will not give you complete solutions. So...

Class vector

Even in the 2012 winner’s article , Mr.Smile wrote that he had taken a vector class from another project, which simulates the physics of the game world for code. He knew then or not, but among the participants a half joke was born on the half tradition that a vector class should be added to the project from the code of last year’s competition (it is possible from someone else’s, if you participate for the first time).

What is so good and useful this class? They can imagine the position of the object on the game map, speed, force (for example, friction). The normalized vector can be used as a direction or angle, etc. When simulating physics or movement, this class will save you a lot of energy and nerves.

For the basis of my class, I took the code of one of the participants, who put it in open access (unfortunately, I don’t remember who and exactly ...). After that, I expanded the methods I needed and updated the old ones:

• I made the fields public and deleted the getX and getY (this is how the code is written more concisely, and I don’t worry about the extra function calls).
• Removed the creation of a new vector, with the operations of multiplying by a number, subtracting another vector and the like. The less intermediate objects are created, the faster everything works, and if you need a new object, then for this you add the copy method. Writing code becomes more difficult - you need to constantly monitor, so as not to start changing the object that should not be.
• Added methods for calculating the square of the distance between vectors and changed the calculation of the length (more on this in the next paragraph of the article).
• Most methods return the vector itself, this allows you to call them in a chain, for example, like this:
  

   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; } } 

Distance between two points

Virtually any strategy in the Russian AI Cup somehow counts the distance between two points (the distance at which you can shoot, the collision of objects, the distance to the target, etc.). Problems begin when such distances must be calculated hundreds of thousands or millions for 1 tick. If you run the profiler, you can see that a lot of time is spent on calculating the methods of hypot , sqrt , and in some strategies, sin and cos .

(For this screenshot, I changed the FastMath.hypot method so that it returns the result of the Math.hypot call)

There are various ways to solve this problem.

Square distance between points

To calculate it, it is not necessary to take the root of the sum of squares of the differences of coordinates, which significantly speeds up the calculations. But then the result must be compared, for example, with the square of the range of the shot (if we check in a dangerous zone) or with the square of the radius (if we check for a collision with a circle).

Unfortunately, it is not always possible to use the squared distance, and some calculations require exactly the distance, for example, in some formulas for calculating potential fields.

Approximate calculations

You can use not quite (but sufficiently) accurate methods for calculating the distance between points. How this is implemented, for example, in FastMath (hypot method). You only need to look for ready-made solutions for your programming language.

Value tables

In cases where there is no need for greater accuracy, and the limitations on memory are not too great, then it is possible to calculate in advance the function values ​​with a certain step. This approach works well for sin and cos .

Visualizer

The process of debugging a strategy is quite laborious and complicated, and the ability to draw additional elements on the playing field is crucial. Unfortunately, this is not so easy to do with the standard visualizer provided by the organizers. And with the utility, Repeater has to do everything blindly. In addition, self-written visualizers often support the ability to rewind to make it easier to learn non-standard strategy behavior.

During the competition there are 2 main approaches to writing a visualizer.

External

A visualizer is a separate application that receives information about what needs to be drawn through sockets or a file.
Pros: Versatility. You can use one visualizer for different programming languages.
Cons: Difficult to expand functionality (need to update the API)

Telegraph user @kswaldemar wrote an openGL open-source external visualizer. You can download it from github'a . The visualizer supports rewinding and is able to draw a sufficiently large number of objects. Other users created clients for it (wrapper over API) for C ++, C #, Java, Python, Ruby, Rust, Swift.

Built

A visualizer that is embedded in the strategy itself.
Pros: It is easy to add a drawing of new things. You can quickly specialize it in drawing data structures that strategy uses and stores.
Cons: It works only within the framework of a single strategy and is very difficult to transfer to other projects.
When changing language, you need to write from scratch.

I decided to write my last visualizer in the second way, since it seemed simpler and faster to me. At the moment, I will not post its source code, because he is strongly tied to my strategy, and I also do not want participants to distract from the competition trying to figure out how it works.

In this case, the drawing is simple enough and performed on top of JPanel, but not everything always works well and quickly.

Inspired by the review from Romka, last year, a couple of weeks before the competition, I wrote an external JavaScript visualizer. It opened in the browser (it turned out quite well, with the ability to rewind and layers). The strategy in the course of execution was supposed to generate a json file with logs that was supposed to be loaded into the visualizer. But the reality turned out to be that the game contained too many objects and lasted 20,000 ticks, which created a huge file with logs that crashed the browser.

Therefore, if you decide to create a visualizer that renders the games already played by the logs, then you should think about the format in which to store the replay data and whether it is worth your torment. I decided for myself that it was not worth it.

Proxy for visualizer

The main find for me was a proxy class, intercepting the moves sent by the strategy and returned by the Local Runner / Repeater utility of the state of the world. Thanks to him, you can not just rewind to review the unusual behavior of the strategy during testing, but also rewind the strategy breakpoint at the right time and debug it in the exact same state it was in when you first viewed the game. That sounds cool, doesn't it?

To understand how this works, let's analyze how the language pack is arranged using the example of Java. The entry point to the application is the Runner class. At the start, a RemoteProcessClient object is created that reads the state of the world sent by the Local Runner and sends back the actions taken by the strategy ( MyStrategy class). In order to intercept all messages from the server, we need to inherit from the RemoteProcessClient class and override the readPlayerContextMessage and writeMoveMessage . I note that the class RemoteProcessClient is declared final, but we can change anything, since On the server, this file will be overwritten by the original (the main thing is not to forget about it while writing the strategy).

 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(); } } } } } 

I removed components and some features from the UI code to make it more understandable.
Buttons and slider in this case use the setFrame method for rewinding and fpsLimitIndex to set the limit on the number of frames per second. The basic idea is simple: we return the frames in order, while they are there, if not, then this is either the end of the game, or we request the next frame from Local Runner if we have not saved it before. There is a pause, which is also automatically set if you start rewinding.

I will note that in this case it is safe to store all frames, since RemoteProcessClient each time creates all the objects in a new way, as long as there is enough memory (I run the strategy with the -Xmx1024M flag and there were no problems yet).

Now, when the state of the world returns to an arbitrary tick, the biggest problem remains - the state of the strategy for this tick. Many of the decisions of the participants store information about the world, accumulated over the previous tics. This means that if you receive the state of the world for the last tick, the strategy will not behave exactly the same as last time.

This is a serious problem, and to solve it, I propose all the states of the strategy, which should be preserved between ticks, to be put into a separate class. Also, you should add the copy method there, thanks to which we can save the state of the strategy in each of the previous ticks. Below I greet an example of such a class that stores a random number generator and makes an exact copy of it, so that even random numbers will be the same for each rewind of the same frame (for example, if you use genetic algorithms in the solution).

 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 } 

I suggest monitoring the state of the strategy itself (in order not to write a lot of code). We will check if we have a state for the current tick, and take it. If it is not there, or we have received the next tick after the current one, then we leave the old object and save it, in case we return again at this point in time.

 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 } 

That's all, it will be necessary only to support the copy method of the GameState class to copy the state of the strategy. This is the largest of the disadvantages of this decision, because if you have a lot of data that must be transferred between ticks, then the size of this method can grow greatly and it becomes very difficult to maintain.

The attentive reader has noticed comments in the code // TODO: REMOVE START and // TODO: REMOVE END . I marked them with pieces of code for deletion before sending the strategy to the server, since copying and storing all states for each tick slows down the solution. Of course, we will not do this with our hands.

Build Package

If you do not write a strategy in C ++, where there are wonderful IFDEFs, then you will have to somehow remove pieces of code. For these purposes, a small python script was written, which:

• copies only necessary files with code to a temporary folder,
• removes marked areas
• zip archive with date and time
• copies the cleaned files to the second project (it is used for testing without a visualizer),
• cleans the temporary folder.
  It will only download the zip archive to the site and watch how your bot fights for the right to be the best.

 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) 

Run a variety of strategies

Above, I mentioned a project with code cleared of a visualizer. In addition to testing, it is also used to generate a jar file that can be run as an adversary in a local runner, for example, using the p2-startup-command parameter. Or you can use the python script, like this:

 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) 

In this case, in addition to the host, port and side, additional parameters are passed to the strategy at the start. This can be used to automatically launch strategies with different parameters and check the result (Local Runner generates the file results.txt by default, but the name can be changed in the settings). Of course, the Local Runner should already be running by the time this function is called.

The automatic battle of the strategy with itself and the selection of constants on the basis of these battles deserve a separate article, and now let's see how inside the strategy to receive the parameters sent in this way. You may have already guessed that once again you have to slightly tweak the Runner class, namely, update two methods so that it can take more than 3 parameters per input:

 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 , in this case, is a singleton with a method for updating default values.

 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]); } } 

so

The toolkit described above is not exhaustive. To make life easier, the participants write many utilities, auxiliary scripts, telegram bots and the like. Of course, this is not a prerequisite for victory, but often allows you to develop your strategy faster and more efficiently, which ultimately increases the number of spectacular bots battles that so many people love.

Thank you for your attention and success in the competition!