Уже 6 лет проводится ежегодное соревнование Russian AI Cup. За это время чемпионат оброс постоянной аудиторией и у многих заядлых участников появился небольшой набор инструментов и хитростей, которые помогают им в разработке. Я участвовал в этом соревновании 3 раза и также обзавелся рядом заготовок и скриптов, о которых и хочу рассказать в данной статье.
Небольшое отступление о качестве кода. Соревнование ставит жесткие временные рамки для написания стратегии, многим участникам нужно продолжать учится или работать, кто-то использует соревнование для изучения новых языков программирования — все это крайне негативно влияет на читаемость кода. Мой код не исключение, и это одна из причин, почему в статье я расскажу как собрать свой инструментарий, но не буду давать полностью готовых решений. Итак...
Класс вектора
Еще в статье победителя 2012 года Mr.Smile писал, что взял класс вектора из другого проекта, для кода симулирующего физику игрового мира. Знал он тогда или нет, но среди участников зародилась полу шутка полу традиция, что класс вектора надо добавить в проект из кода прошлогоднего соревнования (можно из чужого, если участвуете первый раз).
Чем же так хорош и полезен этот класс? Им можно представить положение объекта на игровой карте, скорость, силы (например трение). Нормированный вектор может использоваться как направление или угол и т.д. При симуляции физики или движения этот класс сэкономит вам много сил и нервов.
За основу своего класса я взял код одного из участников, который выложил его в открытый доступ (к сожалению, не помню у кого и именно...). После чего расширил необходимыми мне методами и обновил старые:
- Сделал поля публичными и удалил функции
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 = v.x;
this.y = v.y;
}
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 += v.x;
y += v.y;
return this;
}
public Vec2D sub(Vec2D v) {
x -= v.x;
y -= v.y;
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 - v.x, y - v.y);
return FastMath.hypot(x - v.x, y - v.y);
}
public double squareDistance(Vec2D v) {
double tx = x - v.x;
double ty = y - v.y;
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;
}
}
Расстояние между двумя точками
Практически любая стратегия в Russian AI Cup так или иначе считает расстояние между двумя точками (расстояние на котором можно выстрелить, столкновение объектов, расстояние до цели и т.д.). Проблемы начинаются, когда таких расстояний надо посчитать сотни тысяч или миллионы за 1 тик. Если запустить профайлер, то можно увидеть, что очень много времени тратится на вычисление методов hypot, sqrt, а в некоторых стратегиях sin и cos.
(Для данного скриншота я изменил метод FastMath.hypot чтобы он возвращал результат вызова Math.hypot)
Для решения этой проблемы есть разные способы.
Квадрат расстояния между точками
Для его расчета не нужно брать корень от суммы квадратов разностей координат, что значительно ускоряет вычисления. Но тогда результат нужно сравнивать, например, с квадратом дальности выстрела (если мы проверяем в опасной ли мы зоне) или квадратом радиуса (если проверяем столкновение с окружностью).
К сожалению не всегда можно использовать квадрат расстояния, и некоторые расчеты требуют именно расстояния, например, в некоторых формулах расчета потенциальных полей.
Приближенные вычисления
Можно использовать не совсем (но достаточно) точные методы вычисления расстояния между точками. Как это реализовано, например, в FastMath (метод hypot). Нужно только поискать готовые решения под ваш язык программирования.
Таблицы значений
В случаях, когда не нужна большая точность, а ограничения на память не слишком велики, то можно просчитать заранее значения функции с определенным шагом. Такой подход хорошо работает для sin и cos.
Визуализатор
Процесс отладки стратегии достаточно кропотливый и сложный, и возможность отрисовать дополнительные элементы на игровом поле является критически важной. К сожалению, это не так просто сделать с помощью стандартного визуализатора, предоставляемого организаторами. А с утилитой Repeater приходится и вовсе все просматривать вслепую. Кроме того, самописные визуализаторы часто поддерживают возможность перемотки назад, чтобы легче изучить нестандартное поведение стратегии.
За время проведения конкурса сложилось 2 основных подхода к написанию визуализатора.
Внешний
Визуализатор представляет из себя отдельное приложение, которое через сокеты или файл получает информацию о том, что надо отрисовать.
Плюсы: Универсальность. Можно использовать один визуализатор для разных языков программирования.
Минусы: Сложно расширять функционал (нужно обновлять API)
Пользователь телеграма @kswaldemar написал опенсорсный внешний визуализатор на OpenGL. Скачать его можно с github’a. Визуализатор поддерживает перемотку назад и способен отрисовывать достаточно большое количество объектов. Другие пользователи создали под него клиенты (обертка над API) для С++, С#, Java, Python, Ruby, Rust, Swift.
Встроенный
Визуализатор, который встраивается в саму стратегию.
Плюсы: Легко дописать отрисовку новых вещей. Можно быстро специализировать его под отрисовку структур данных, которые использует и хранит стратегия.
Минусы: Работает только в рамках отдельно взятой стратегии и очень сложно переносится в другие проекты.
При смене языка надо писать с нуля.
Свой последний визуализатор я решил написать вторым способом, т.к. он показался мне более простым и быстрым. На данный момент, я не буду выкладывать его исходный код, т.к. он сильно завязан на моей стратегии, и я также не хочу, чтобы участники отвлекались от соревнования пытаясь разбираться как он устроен.
В данном случае отрисовка достаточна простая и выполнена поверх JPanel, но не всегда все работает хорошо и быстро.
Вдохновленный обзором от Romka, в прошлом году за пару недель до начала соревнования я написал внешний визуализатор на JavaScript. Он открывался в браузере (получилось достаточно неплохо, с возможностью перемотки и слоями). Стратегия в ходе выполнения должна была генерировать json файл с логами, который предполагалось загружать в визуализатор. Но реальность оказалось такой, что игра содержала слишком много объектов и длилась 20000 тиков, что порождало колоссальных размеров файл с логами, который крешил браузер.
Поэтому, если вы решите создать визуализатор, отрисовывающий уже отыгранные матчи по логам, то стоит задуматься о том, в каком формате хранить данные реплея и стоит ли это ваших мучений. Я для себя решил, что не стоит.
Прокси для визуализатора
Главной находкой для меня стал прокси класс, перехватывающий отсылаемые стратегией ходы и возвращаемые утилитой Local Runner/Repeater состояния мира. Благодаря ему можно не просто перематывать назад, чтобы пересмотреть необычное поведение стратегии при тестировании, но и отмотав на нужный момент поставить в стратегии брекпоинт и дебажить ее в точно таком же состоянии в каком она была, когда первый раз просматривали игру. Звучит круто, не правда ли?
Чтобы понять, как это работает разберем как устроен языковой пакет на примере Java. Точкой входа в приложение является класс Runner. При старте создается объект RemoteProcessClient который считывает состояние мира посланное Local Runner’ом и отсылает обратно действия, предпринятые стратегией ( класс MyStrategy ). Для того, чтобы перехватывать все сообщения от сервера, нам необходимо унаследовать от класса RemoteProcessClient и переопределить методы 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 чтобы выставить ограничение на количество кадров в секунду. Основная идея простая: мы возвращаем фреймы по порядку, пока они есть, если их нет, то это либо конец игры, либо мы запрашиваем следующий кадр у Local Runner’a если мы его не сохранили прежде. Есть пауза, которая еще и автоматически ставится, если начать перематывать.
Отмечу, то в данном случае хранить все фреймы безопасно, т.к. 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
}Вот и все, останется только поддерживать метод copy у GameState класса, чтобы копировать состояние стратегии. Это наибольший из минусов данного решения, т.к. если у вас очень много данных, которые должны передаваться между тиками, то размер этого метода может сильно разрастаться и его становится очень сложно поддерживать.
Внимательный читатель заметил комментарии в коде // TODO: REMOVE START и // TODO: REMOVE END. Ими я пометил куски кода для удаления перед отправкой стратегии на сервер, т.к. копирование и хранение всех состояний за каждый тик сильно замедляет решение. Делать это руками мы, конечно же, не будем.
Чтобы не путать данные TODO с другими, в IDEA можно задавать разные цветовые схемы по регулярному выражению для todo.
Результат:
Сборка посылки
Если вы не пишите стратегию на С++, где есть чудесные IFDEF, то вам придется как-то удалять куски кода. Для этих целей и был написан небольшой python скрипт, который:
- копирует только необходимые файлы с кодом во временную папку,
- удаляет помеченные участки,
- запаковывает в zip архив с датой и временем,
- копирует очищенные файлы во второй проект (он используется для тестирования без визуализатора),
- чистит временную папку.
Останется только загрузить 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)
Скрипту нужно будет указать каталог с кодом, временную папку и место куда скидывать zip архив и очищенные файлы. Вероятно, придется создать эти папки заранее. Но, надеюсь, идею я передал.
Пользователи IDEA могут добавить этот скрипт как External Tool и запускать через меню на правую кнопку мыши в структуре проекта.
Запуск множества стратегий
Выше я упоминал проект с очищенным от визуализатора кодом. Кроме тестирования, он используется и для генерации jar файла, который можно запускать как противника в Local Runner’e, например, используя параметр p2-startup-command. А можно и используя 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)В данном случае, кроме хоста, порта и сида, в стратегию на старте передаются дополнительные параметры. Это можно использовать для автоматического запуска стратегий с разными параметрами и проверкой результата (Local Runner генерирует файл results.txt по умолчанию, но имя можно поменять в настройках). Разумеется Local Runner должен быть уже запущен к моменту вызова этой функции.
Автоматическое сражение стратегии самой с собой и подбор констант на основе этих сражений заслуживают отдельной статьи, а сейчас давайте разберемся, как внутри стратегии получать посланные таким образом параметры. Возможно, вы уже догадались, что снова придется слегка подправить Runner класс, а именно, обновить два метода, чтобы он мог принимать больше 3х параметров на вход:
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]);
}
}
Итак
Описанный выше набор инструментов не исчерпывающий. Для облегчения жизни, участники конкурса пишут много утилит, вспомогательных скриптов, телеграм-ботов и тому подобных вещей. Разумеется, это не является обязательным условием для победы, но часто позволяет быстрее и эффективнее разрабатывать свою стратегию, что в конечном счете увеличивает количество зрелищных сражений ботов, которые многие так любят.
Спасибо за внимание и успехов в конкурсе!