Ants AI Challenge. Учебник начинающего ботовода

Стратегии реализованные в стартовом пакете — это только точка отсчёта для создания вашего собственного бота, по сути — это одни из худших стратегий. В то же время, в стартовый пакет включены полезные функции, помогающие вам разработать лучшую стратегию. Эта статья проведёт вас через серию улучшений пакета. С каждым завершённым шагом, ваш бот будет становиться умнее, а ваш рейтинг начнёт расти.

Предпосылки

Для данной статьи будем использовать стартовый пакет на Java (прим. переводчика: также нам потребуется Python, поскольку инструменты — тестер бота и набор полезных скриптов написаны на нём, ссылки в конце статьи). Также вам пригодятся инструменты.

Устанавливаем

Создайте директорию, в которой будете работать со стартовым пакетом(ботом) и инструментами. У вас должно получиться что-то вроде этого:

C:\aichallenge>tree
Folder PATH listing
C:.
+----tools
+---mapgen
+---maps
| +---maze
| +---multi_hill_maze
| +---symmetric_random_walk
+---sample_bots
| +---csharp
| +---java
| +---php
| | +---tests
| +---python
+---submission_test
+---visualizer
+---data
| +---img
+---js

C:\aichallenge>dir /b
AbstractSystemInputParser.java
AbstractSystemInputReader.java
Aim.java
Ants.java
Bot.java
Ilk.java
make.cmd
Makefile
Manifest.txt
MyBot.java
Order.java
Tile.java
tools

Проверяем

Убедимся, что всё работает как надо запустив тестовую игру (используем шелл-скрипт play_one_game.cmd или play_one_game.sh в зависимости от вашей ОС). Среди инструментов есть утилита «playgame.py», которая поможет нам тестировать нашего бота. Её использование наглядно показано в шелл-скрипте play_one_game.cmd (play_one_game.sh).

Создаём шелл-скрипт для тестирования бота

Теперь сделаем свой шелл-скрипт, который будет использовать новую карту и нашего бота.

Для Windows: создаём tutorial.cmd

C:\aichallenge>notepad tutorial.cmd

Для Linux: создаём tutorial.sh

user@localhost:~$ gedit tutorial.sh

после чего назначаем права

user@localhost:~$ chmod u+x tutorial.sh

В нём прописываем:

python tools/playgame.py "java -jar MyBot.jar" "python tools/sample_bots/python/HunterBot.py" --map_file tools/maps/example/tutorial1.map --log_dir game_logs --turns 60 --scenario --food none --player_seed 7 --verbose -e

• Первые две опции — боты, которые запускаем. Используем нашего бота и HunterBot в качестве оппонента.
• Опция --map_file устанавливает используемую карту. Выберем карту с 2-мя муравейниками.
• Опция --log_dir устанавливает место, куда будут сохраняться файл просмотра и, опционально, логи ввода/вывода бота и его ошибки.
• Опция --turns устанавливает максимальное количество ходов для игры. Поскольку дополнительные данные не требуются — остановимся на 60 шагах.
• Опция --scenario позволяет располагать начальные точки с едой на карте. Специфицируем размещение еды для данного учебника.
• Опция --food none позволяет выключить появление пищи во время игры. Опять же, эта опция используется в рамках учебника.
• Опция --player_seed гарантирует, что вы сможете получить тот же результат, что и в данном учебнике. HunterBot использует это значение для инициализации генератора случайных чисел, так что он всегда будет делать одни и те же шаги. (Примечание: если вы хотите использовать реплеи игры для отладки вашего бота, то вам так же стоит применить данную стратегию).
• Опция --verbose будет выводить общую статистику по игре, что позволяет наблюдать за прогрессом игры.
• Опция --e направляет все ошибки бота на консоль, так что, если вы сделаете ошибку при изучении — сможете увидеть сообщение о ней.

Не забываем о том, что бота на Java надо скомпилировать. Оба бота — и HunterBot и бот, воспроизводимый в учебнике будут детерминированы, т.е. при одинаковом вводе они будут производить одинаковые ходы. Это значит, что если вы будете полностью следовать инструкции, вы получите точно тот же результат, что и в учебнике.

Давайте запустим наших ботов с помощью шелл-скрпита и посмотрим, как работает бот из стартового пакета.
Вы должны увидеть подобный вывод:

    running for 60 turns
                      ant_count c_turns climb? cutoff food r_turn ranking_bots s_alive s_hills score  w_turn winning
    turn    0 stats:   [1,1,0]     0    [1,1]    -     18    0        None      [1,1]   [1,1]  [1,1]   0     None
    turn    1 stats:   [1,1,0]     0    [1,1]    -     16    1       [0,0]      [1,1]   [1,1]  [1,1]   1     [0,1]
    turn    2 stats:   [2,1,0]     0    [1,1]    -     16    1       [0,0]      [1,1]   [1,1]  [1,1]   1     [0,1]
    turn    3 stats:   [2,2,0]     0    [1,1]    -     15    1       [0,0]      [1,1]   [1,1]  [1,1]   1     [0,1]
    turn    4 stats:   [2,3,0]     0    [1,1]    -     14    1       [0,0]      [1,1]   [1,1]  [1,1]   1     [0,1]
    turn    5 stats:   [2,4,0]     0    [1,1]    -     14    1       [0,0]      [1,1]   [1,1]  [1,1]   1     [0,1]
    turn    6 stats:   [2,4,0]     0    [1,1]    -     14    1       [0,0]      [1,1]   [1,1]  [1,1]   1     [0,1]
    turn    7 stats:   [2,4,0]     0    [1,1]    -     14    1       [0,0]      [1,1]   [1,1]  [1,1]   1     [0,1]
    turn    8 bot 0 eliminated
    turn    8 stats:   [0,4,0]     0    [0,1]    -     14    1       [0,0]      [0,1]   [1,1]  [1,1]   1     [0,1]
    score 1 3
    status eliminated survived
    playerturns 8 8

Игра продолжалась всего 8 шагов, что подозрительно быстро. Похоже на то, что игрок 0 (наш бот) был уничтожен. После окончания игры должен запуститься браузер, чтобы показать в визуализаторе, что же произошло.


Вы можете увидеть, что стратегия изначального бота ужасна — он уничтожил сам себя столкнув двух муравьёв. Что ж, это будет нашим первым улучшением.

Шаг 1. Избегаем столкновений

План

Чтобы предотвратить столкновения, нужно сделать следующее:

• Запретить муравьям двигаться на других муравьёв.
• Запретить 2м муравьям передвигаться в одну точку.
• Отслеживать информацию о всех наших муравьях.

Реализация

Чтобы отслеживать информацию, где наши муравьи, эффективно использовать структуру HashMap. Данная структура данных будет хранить положением муравьёв и позволит проверять, не используется ли такое положение уже. Каждое ключевое значение HashMap`а будет содержать объект Tile. Tile — объект с положением объекта на карте. Ключём будет положение предполагаемого шага, а значением — текущее положение. Таким образом мы сможем проверять HashMap перед тем, как делать шаг, чтобы убедиться, что два муравья не пойдут в одну точку. При каждом движении будем обновлять HashMap.
Поскольку эта проверка пригодится позже в учебнике, сделаем функцию, проверяющую возможен ли заданный шаг. Она будет возвращать булево значение (true или false).

Код

Мы опустим комментарии в изначальном боте и разместим новый код:

   public boolean doMoveDirection(Ants ants, HashMap<Tile, Tile> orders, Tile antLoc, Aim direction) {
        // Track all moves, prevent collisions
        Tile newLoc = ants.getTile(antLoc, direction);
        if (ants.getIlk(newLoc).isUnoccupied() && !orders.containsKey(newLoc)) {
            ants.issueOrder(antLoc, direction);
            orders.put(newLoc, antLoc);
            return true;
        } else {
            return false;
        }
    }

    @Override
    public void doTurn() {
        HashMap<Tile, Tile> orders = new HashMap<Tile, Tile>();
        Ants ants = getAnts();
        for (Tile myAnt : ants.getMyAnts()) {
            for (Aim direction : Aim.values()) {
                if (doMoveDirection(ants, orders, myAnt, direction)) {
                    break;
                }
            }
        }
    }

Функция doMoveDirection получает положение муравья (объект Tile), и направление (объект Aim — N|E|S|W) и пытается выполнить шаг. Данная функция расположена вне функции doTurn, так что мы должны передать ей объект Ants и HashMap с нашими приказами. Будем использовать некоторые предопределённые функции из бота, которые могут нам помочь:
— ants.getTile(Tile, Aim) примает положение (объект Tile) и направление (объект Aim) и возвращает новое положение (объект Tile). Она позаботится о замыкании карты, так что нам нет необходимости волноваться об этом.
— ants.getIlk(Tile) — принимает положение (объект Tile) и возвращает объект Ilk (тип точки карты в заданном положении). Далее вызываем функцию isUnoccupied() объекта Ilk, чтобы убедиться, что есть возможность сделать ход.
— Ilk.isUnoccupied принимает положение и даёт нам знать, возможен ли данный ход. Это лучше, чем раннее Ilk.isPassable, поскольку не позволит сходить на еду или на других муравьёв.
— HashMap с приказами используется для отслеживания запланированных шагов. В выражении if условие !orders.containsKey(newLoc) проверяет на существование указанного ключа и помогает избежать столкновений.

Результаты

Наконец запустим нашего бота снова и посмотрим, что у нас получилось.

C:\aichallenge>tutorial.cmd
running for 60 turns
                  ant_count c_turns climb? cutoff food r_turn ranking_bots s_alive s_hills score  w_turn winning
turn    0 stats:   [1,1,0]     0    [1,1]    -     18    0        None      [1,1]   [1,1]  [1,1]   0     None
turn    1 stats:   [1,1,0]     0    [1,1]    -     16    1       [0,0]      [1,1]   [1,1]  [1,1]   1     [0,1]
turn    2 stats:   [2,1,0]     0    [1,1]    -     16    1       [0,0]      [1,1]   [1,1]  [1,1]   1     [0,1]
...
turn   60 stats:   [1,5,0]     0    [1,1]    -     12    1       [0,0]      [1,1]   [1,1]  [1,1]   1     [0,1]
score 1 1
status survived survived
playerturns 60 60

Лучше, но до сих пор — плохо. Только один муравей выходит и дерётся с HunterBot, впрочем мы избежали суицида, а это — уже улучшение. К тому же, мы создали вспомогательную функцию, которая нам пригодится в дальнейшем.

Ссылки

Стартовый пакет можно подобрать тут.
Инструменты для Windows, для Linux/MacOS.
Переведённые статьи: Ants Tutorial, Step 1: Avoiding collisions.

PS на сайте только начали появляться примеры для Java (сейчас завершились на 1ом шаге), поэтому пока довёл перевод только до конца первого шага.
PPS Если перевод понравился — буду переводить и дальше по мере добавления в следующие шаги примеров на Java.
PPPS Спасибо неизвестному хабра-другу за инвайт и возможность вынести статью на общее обозрение.