Pull to refresh

Старт в Google AI Challenge на Java

Sport programming *
Меня очень давно заинтересовала тема программирования поведения объектов в виртуальном мире. Но практические знания в этой области оставляют желать лучшего, поэтому недавно начал искать небольшой проект для вложения сил. В итоге я его нашел, благодарен гуглу и ideas4ru за анонс.

Язык и стартовый пакет


Организаторы проекта предлагают больше десятка языков для разработки бота, я выбрал Java. Не могу сказать, что хорошо знаю Java, но так получилось (С++ — многословен, PHP — не круто, C# — слишком мягкотело, JavaScript — долго разбираться с V8, Lua — не нравится синтаксис, Pascal — слишком по-школьному, Python — немного пугает). Стартовый пакет для Java можно скачать с официального сайта или по этой прямой ссылке.

О том, как начал


Возможно я тормоз или плохо знаю Java, но в начале я не смог понять, как работает код в основном классе:
public void doTurn() {
    Ants ants = getAnts();
    for (Tile myAnt : ants.getMyAnts()) {
        for (Aim direction : Aim.values()) {
            if (ants.getIlk(myAnt, direction).isPassable()) {
                ants.issueOrder(myAnt, direction);
                break;
            }
        }
    }
}

У меня ушло около часа, чтобы разобрать по косточкам весь код стартового пакета (тоже самое советую сделать всем, а не читать статьи о том, как быстро начать). В итоге оказалось, что первый цикл пробегает по ячейкам с дружественными муравьями, а второй пытается переместить муравья в одном из четырех направлений (последовательный перебор перечисления Aim).

На самом первом шаге я столкнулся с одним очень милым правилом — при перемещении двух муравьев на одну ячейку, они оба умирают. Для решения этой проблемы была внесена правка в класс Ants.

Я добавил список занятых ячеек:
public class Ants
{
     private final Set<Tile> employed = new HashSet<Tile>();
     //...

При очистке позиций дружественных муравьев, добавил чистку занятых позиций:
public void clearMyAnts()
{
     employed.clear();
     //...

И, наконец, почти полностью переписал метод issueOrder:
public boolean issueOrder(Tile myAnt, Aim direction)
{
     Order order = new Order(myAnt, direction);
     Tile newPosition = getTile(myAnt, direction);

     if(getIlk(myAnt, direction).isPassable() && !employed.contains(newPosition))
     {
          orders.add(order); //Особо не задумывался зачем этот список, но кажется он безполезен
          employed.add(newPosition);

          System.out.println(order);
          System.out.flush();

          return true;
     }

     return false;
}

Код в основном классе немного уменьшиться:
public void doTurn()
{
    Ants ants = getAnts();

    for (Tile myAnt : ants.getMyAnts())
    {
        for (Aim direction : Aim.values())
        {
            if (ants.issueOrder(myAnt, direction))
                break;
        }
    }
}

Немного индивидуальности


Немного помечтаем и представим, что в будущем каждый наш муравей будет индивидуальностью и обладателем некоторых параметров. Продолжением подобных раздумий будет класс Ant:
public class Ant
{
    protected Ants ants;
    protected Tile tile;

    protected int waitStep = 0;

    public Ant(Ants ants, Tile tile)
    {
        this.tile = tile;
        this.ants = ants;
    }

    public Tile getTile()
    {
        return tile;
    }

    //При перемещении нужно обновить текущее положение (долго искал эту ошибку!)
    public boolean issueOrder(Aim direction)
    {
        if(ants.issueOrder(tile, direction))
        {
            tile = ants.getTile(tile, direction);
            return true;
        }
        else
            return false;
    }

    //Иногда нужно подождать пару шагов, это метод для будущих стратегий
    public boolean waiting()
    {
        return waitStep-- > 0;
    }

    //Элементарное размышление
    public void think()
    {
        for(Aim direction : Aim.values())
        {
            if(ants.issueOrder(direction))
                break;
        }
    }
}

Дальше нужно внести довольно много мелких правок, чтобы этот класс начал работать. Это довольно скучно и монотонно, но все же… начнем с метода MyBot:
    public void doTurn()
    {
        getAnts().think(); //Просим сообщество дружественных муравьев подумать
    }

Добавим недостающий метод в Ants и изменим тип содержимого списка myAnts:
    private final Set<Ant> myAnts = new HashSet<Ant>();
    //...

    public void think()
    {
        for(Ant ant : myAnts)
        {
            if(ant.waiting()) //Пропускаем шаг, если это необходимо
                continue;

            ant.think(); //Просим подумать отдельного муравья
        }
    }

Теперь нужно внимательно следить за добавлением и удалением муравьиных объектов. Те, кто разбирался с кодом скорей всего видели в классе Ants метод update, в котором можно отследить появление дружественного муравья и смерть (но смерть общая для всех муравьев). Такую общую смерть можно исправить несколькими способами… я решил добавить два вида смерти.

Внесем правки в класс-перечисление Ilk:
public enum Ilk
{
    MY_DEAD, ENEMY_DEAD, // вместо DEAD,
    //...
    public boolean isUnoccupied()
    {
        return this == LAND || this == MY_DEAD || this == ENEMY_DEAD;
    }
}

Откорректируем метод removeAnt в классе Bot:
    public void removeAnt(int row, int col, int owner)
    {
        ants.update(owner > 0 ? Ilk.ENEMY_DEAD : Ilk.MY_DEAD, new Tile(row, col));
    }

Теперь все готово, чтобы сделать «наблюдение» за муравьями, правим метод update в классе Atns:
    public void update(Ilk ilk, Tile tile)
    {
        map[tile.getRow()][tile.getCol()] = ilk;

        switch (ilk)
        {
            case FOOD:
                foodTiles.add(tile);
                break;
            
            case MY_ANT:
                myAnts.add(new Ant(this, tile));
                break;
            
            case ENEMY_ANT:
                enemyAnts.add(tile);
                break;
            
            case MY_DEAD:
                myAnts.remove(new Ant(this, tile));
        }
    }

Еда и фигня — немного мозга


Далее нет смысла пытаться расписывать все шаги, просто приведу код с комментариями. Изменим поведения муравья, внеся изменение в код класса Ant:
public class Ant
{
    //...

    public void think()
    {
         if(!doFood())  //Если не видит пищу,
            doRandom(); //То движемся случайно
    }

    protected boolean doRandom()
    {
        while(!issueOrder(Aim.getRandom())); //Перебираем случайные направления до удачного
        return true;
    }

    protected boolean doFood()
    {
        return moveToObject(ants.getFoodTiles());
    }

    //вспомогательный метод для перемещения к ближайшему из объектов
    protected boolean moveToObject(Set<Tile> objects)
    {
        Tile object = findObject(objects);

        if(object != null)
        {
            issueOrder(ants.getDirections(object, tile).get(0));
            return true;
        }

        return false;
    }

    //вспомогательный метод для поиска ближайшего из объектов
    protected Tile findObject(Set<Tile> objects)
    {
        Tile find = null;

        int distance = 0;
        int minDistance = ants.MAX_MAP_SIZE;

        for(Tile aspt : objects)
        {
            distance = ants.getDistance(aspt, tile);

            if(minDistance > distance)
            {
                find = aspt;
                minDistance = distance;
            }
        }

        return find;
    }
}

При написании этого кода, я добавил в класс-перечисление Aim статический метод, который возвращает случайное направление:
public enum Aim
{
    private static final Random random = new Random();
    //...

    public static Aim getRandom()
    {
        return values()[random.nextInt(values().length)];
    }
}

Ошибочка


Возможно я где-то напутал в коде, но кажется в методе getDirections класса Ants закралась ошибка:
    public List<Aim> getDirections(Tile t1, Tile t2)
    {
        List<Aim> directions = new ArrayList<Aim>();
        if (t1.getRow() < t2.getRow()) {
            if (t2.getRow() - t1.getRow() >= rows / 2) {
                directions.add(Aim.SOUTH); //Было Aim.NORTH
            } else {
                directions.add(Aim.NORTH); //Было Aim.SOUTH
            }
        } else if (t1.getRow() > t2.getRow()) {
            if (t1.getRow() - t2.getRow() >= rows / 2) {
                directions.add(Aim.NORTH); //Аналогично нужно было поменять...
            } else {
                directions.add(Aim.SOUTH); //...местами с этим значением (сейчас правильно написано)
            }
        }
        if (t1.getCol() < t2.getCol()) {
            if (t2.getCol() - t1.getCol() >= cols / 2) {
                directions.add(Aim.EAST); //Аналогично нужно было поменять...
            } else {
                directions.add(Aim.WEST); //...местами с этим значением (сейчас правильно написано)
            }
        } else if (t1.getCol() > t2.getCol()) {
            if (t1.getCol() - t2.getCol() >= cols / 2) {
                directions.add(Aim.WEST); //Аналогично нужно было поменять...
            } else {
                directions.add(Aim.EAST); //...местами с этим значением (сейчас правильно написано)
            }
        }
        return directions;
    }

Долго не мог понять, что не так… муравей искал еду как-то не так… оказалось дело в этом.

Заключение


Я не считаю, что в подобной игре нужно самообучение. Возможно лучше будет набор стратегий + их небольшая корректировка (размер группы, текущая стратегия… остальные параметры пока не раскрою). Пока не уверен, насколько эффективны будут такие муравьи, но постараюсь написать об этом во второй статье.

P.S. Самообучение не нужно, т.к. это закрытая система, в которой не появляются новые факторы. А пока самообучающийся противник учится, можно захватить вражеские холмы :)
Tags:
Hubs:
Total votes 41: ↑28 and ↓13 +15
Views 1.5K
Comments Comments 47