Пользователь
0,0
рейтинг
26 декабря 2011 в 16:14

Алгоритм победителя AI Challenge 2011 (Ants) перевод

Вашему вниманию представляется перевод заметки победителя недавно закончившегося AI Challenge, в которой раскрываются общие моменты алгоритма, а так же некоторые технические детали. Также есть возможность осмотреть исходники самостоятельно.

Не могу поверить в то, что я выиграл.
И тем более не могу поверить в то, что выиграл решительно.

Я очень люблю соревнования по программированию, и это для меня было пока самым крупным и захватывающим. Мои благодарности организаторам соревнования, помощникам, хостерам tcp-серверов и всем игрокам за несколько замечательных месяцев.

Вот пример одной из моих игр: aichallenge.org/visualizer.php?game=346288&user=4513 (это не та игра, которую привёл автор в своей статье. Я не могу дать ссылку именно на неё, поскольку она хранится прямо на сервере автора. — прим. перев.). В этой заметке я хочу объяснить, что делает мой код, и как именно у него получается это делать. Есть много технических моментов, и в общем-то статья не о самой стратегии, но я постараюсь объяснять попроще.

О коде

Я начал с того, что скачал стартовый пакет Java, попереименовывал файлы, удалил всё лишнее, добавил новый класс Strategy, а вскоре понял, что понадобится ещё и класс, представляющий муравья. Весь свой код я писал в классе Strategy, в котором в результате оказалось около 1800 строк кода. Также представляют интерес Ant.java и Tile.java, оба они являются value object-ами с кучей полей.

Я оставил идею из стартового пакета, по которой неизвестная область по умолчанию считалась землёй. Я не вычислял поле зрения бота, и потому даже не знал, какие клетки действительно земля, а какие я просто пока не видел.

Для каждой клетки карты есть ровно один экземпляр Tile, который используется в течение всей игры. Ant'ы создаются в начале каждого хода для всех моих муравьёв и муравьёв противника.

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

Реализация стратегии

Многие говорили о каких-то общих стратегиях, но у меня, к сожалению, такой нет. Я не принимаю решений, основываясь на числе моих муравьёв или на доле занимаемой территории. Мой бот не меняет тактику, когда он выигрывает или проигрывает; он об этом вообще не знает. Кроме того, я не смотрю на то, какой сейчас ход, и на первом всё происходит точно так же, как и на 999-м. Я никак не различаю врагов, даже во время боя, и не храню расположений муравейников. Не считая отправления муравьёв от муравейников с помощью миссий, каждое движение зависит лишь от локального окружения муравья.

Итак, что же именно происходит каждый ход? После всяких инициализаций и предподсчётов я вызываю следующие методы в таком порядке:
  • initMissions();
  • enemyHills();
  • food();
  • initExplore();
  • createAreas();
  • fight();
  • defence();
  • approachEnemies();
  • attackDetachedEnemies();
  • escapeEnemies();
  • distribute(true);
  • explore();
  • doMissions();
  • createMissions();
  • distribute(false);
  • cleanAreas();
Ниже я постараюсь объяснить, что все эти методы делают, но если вкратце, то они просто двигают муравьёв, которые подходят под определённые критерии. Если какой-то муравей подвинут, информация об этом моментально отправляется на сервер, и отменить действие уже нельзя.

Поиски в ширину

Тут я расскажу о том, как у меня вообще происходит BFS. Из соображений производительности, каждая Tile имеет ссылки соседние к ним клетки (кроме воды), и таким образом нет необходимости обращаться к двумерному массиву и использовать свойства rows и cols. (Сомневаюсь, что это дало ощутимый прирост производительности — прим. перев.) Типичный BFS (а я их использую МНОГО) выглядит примерно так:
LinkedList<Tile> openList = new LinkedList<Tile>();
LinkedList<Tile> changedTiles = new LinkedList<Tile>();
openList.add(foodTile);
foodTile.dist = 0;
foodTile.isReached = true;
changedTiles.add(foodTile);
while (!openList.isEmpty()) {
    Tile tile = openList.removeFirst();
    if (tile.dist >= 10) break;
    for (Tile n : tile.neighbors) {
            if (n.isReached) continue;
            if (n.type == Type.MY_ANT) {
                    // found one of my ants at the tile n
            }
            n.isReached = true;
            n.dist = tile.dist + 1;
            changedTiles.add(n);
            openList.add(n);
    }
}
for (Tile tile : changedTiles) tile.isReached = false;

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

Инициализация хода

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

В зависимости от расстояния до врагов, у моих муравьёв есть флаги, показывающие, находятся ли они в (возможно, косвенной) опасности. Для врагов проверялось, не обособлены ли они (то есть, есть ли у них рядом ещё вражеские муравьи).

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

Исследования и миссии

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

Исследование

Для каждой клетки на карте хранится exploreValue, которое увеличивается на 1 каждый ход, если эта клетка не достижима с помощью BFS за 10 ходов хотя бы одним моим муравьём. Если клетка достижима, то счётчик сбрасывается в ноль. Таким образом, exploreValue — мера того, как долго я не знал, что происходит в клетке.

Итак, в методе explore от всех муравьёв, которые не были использованы для другого задания, запускается BFS с максимальной глубиной в 11 шагов, при этом интересует нас только последний шаг (поскольку на первых 10 exploreValue гарантированно 0). Если все клетки, достижимые на 11 шаге, имеют exploreValue равным нулю, это значит, что муравей окружён «своими» или водой. Иначе, я двигаю муравья в направлении, где сумма exploreValue на 11 шаге максимальна(то есть, сумма exploreValue всех клеток, достижимых из клетки, в которую я перейду, за 10 шагов). Поскольку до любой клетки за 11 шагов можно дойти, сделав до двух различных первых шагов, при BFS хранится список из одного или двух первых ходов.
Таким образом я исследую карту и обеспечиваю видимость всех участков.

Миссии

Так, а что делать, если муравей окружён своими? Двигать его к границе, конечно же! Более точное определение границы есть в методе createAreas, об этом чуть позже. Перемещение к границе и есть то, что я называю миссиями. Миссия состоит лишь из двух вещей: муравья и целевой клетки на границе. Миссии — пример тех немногих данных, которые хранятся между ходами, хотя путь к цели пересчитывается каждый раз с помощью A*. Если у муравья уже есть миссия, он продолжает её выполнять, иначе создаётся новая. Если у муравья была миссия, но он использовался для других целей (сбор еды, сражение, защита), миссия отменяется.

Участки и граница

Метод createAreas разделяет карту на участки. Я запускаю очередной BFS, на этот раз от всех муравьёв (включая вражеских) одновременно. На старте у каждого муравья есть свой участок, к которому присоединяются все клетки, достигнутые при обходе в ширину. Но когда сталкиваются участки, принадлежащие одному игроку, они сливаются в один большой участок, который затем может быть слит ещё и ещё. После BFS, я смотрю на все клетки в моих участках, и каждую клетку, у которой хотя бы один сосед принадлежит другому участку, считаю граничной клеткой. В этом BFS я иду не глубже, чем на 20 ходов, и таким образом два муравья, находящиеся на расстоянии 39 шагов, окажутся на одном участке, даже если между ними есть туман войны. Это гарантирует отсутствие внезапно появившихся границ в областях, явно принадлежащих мне. Получается, что граничные клетки — это те клетки, которые либо равноудалены от моего уравья и от вражеского, либо находятся в 20 шагах от моих муравьёв, а в поле зрения нет врагов. Во втором случае может оказаться так, что граничная клетка находится на воде, которую я ранее не видел, и тогда я удаляю миссию как только обнаруживаю воду.

При создании миссии необходимо выбрать одну из граничных клеток в качестве цели. Если муравей не стоит на моём муравейнике, для него выбирается граничная клетка, до которой идти быстрее всего (определяется с помощью BFS). В противном случае, целевая клетка определяется некоторой сложной формулой, использующей соотношение числа своих и вражеских муравьёв поблизости к этой клетке, вероятное расстояние до вражеских муравейников, число муравьёв, у которых уже есть миссия идти в близлежащие клетки, и сколько им потребуется времени, чтобы дотуда дойти… Да ладно, шучу :) Это определяется случайно. Абсолютно случайно. Вот так:
target = area.border.get(turnRandom.nextInt(area.border.size()));

Это была моя первая реализация, и она работала весьма хорошо, так что я не стал утруждаться менять. Обратите внимание, что поведение было всё-таки не совсем случайное, поскольку когда миссия прерывалась другими задачами (сбор еды и тому подобное), новая затем выбиралась уже детерминированно. Кроме того, поскольку границы на каждом ходу разные, миссии необходимо время от времени обновлять. Это делается каждый ход, если хватает времени, и обязательно хотя бы раз в 10 ходов.

Ещё разное

Можно сделать замечание, что клетка достижима за 10 ходов — не совсем то же самое, что расстояние до клетки не более 77, но они довольно близки, и с этим у меня проблем никогда не возникало.

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

Еда

Тут нет ничего особо интересного. Я запускаю BFS от всей видимой еды, и ближайшего найденного муравья отправляю в её сторону. Я не храню местоположение еды и не думаю о том, что один муравей может собрать две еды, находящиеся близко друг к другу. Впрочем, есть особая логика, по которой я действую, если рядом с едой есть враг. Обычно я стараюсь избегать размена муравьёв, но если рядом с едой есть ещё свой муравей, то я готов пожертвовать одним, если враг решит попытаться собрать еду.

McLeopold написал хороший пост, в котором он рассказывал, как это происходило у него.

Вражеские муравейники

Как и с едой, я делаю BFS, стартуя от вражеских муравейников. Я отправляю на штурм не более четырёх муравьёв, находящихся на расстоянии не более 20 шагов от вражеского муравейника. Если у меня 10 или менее муравьёв, я отправляю только одного, чтобы избежать проблем на начальных сдадиях игры на картах, где муравейники врагов очень близко друг от друга. Я никогда не отправляю прямо на муравейник более 4 муравьёв, но поскольку там часто поблихости вражеские муравьи, а я играю весьма агрессивно, у меня там всё равно будет куча муравьёв.

Бой

Ну вот и началось самое интересное! Несомненно, самым обсуждаемым вопросом была именно логика ведения боя.

Мой подход такой: разделить сражающихся на группы, а затем посмотреть, что может произойти на следующем ходу. Я это делаю, симулируя все (не совсем все, начиная с версии 2, об этом чуть ниже) возможные ходы, которые могут сделать мои муравьи, и для всех комбинаций смотрю на возможные ходы противника, затем оцениваю ситуацию и выбираю наиболее выгодный вариант, предполагая, что противник знает, как я похожу, и походит наиболее опасным для меня способом.
Это довольно похоже на minimax и альфа-бета отсечение, просто нужно иметь несколько max-узлов подряд (для моих муравьёв) и min-узлов для противника.

Пример

Давайте рассмотрим ситуацию ниже. Муравьи A, B и C — мои (зелёные), а враги — муравьи X и Y (синие). (проценты — вода, точки — земля — прим. перев.)
% % % % % %
% % A % % %
% % . B % %
% % . . C %
% X . . . %
% % Y . . %
% % % % % %

Я даже не поленился нарисовать небольшую диаграмму, показывающую, что происходит:
N/E/S/W означает подвинуться на Север/Восток/Юг/Запад соответственно, а "-" означает остаться на месте.

Дерево генерируется на лету с использованием DFS. Мы начинаем, рассматривая возможное движение для муравья A, симулируем это движение и продолжаем для муравья B. После того, как двинулся последний вражеский муравей, мы оцениваем ситуацию, используя простую формулу: (число мёртвых вражеских муравьёв) минус (число мёртвых моих муравьёв). Вражеские узлы (min) всегда выбирают ходы, приводящие к наименьшму результату, наши же узлы (max) выбирают значения, у которых значение этой формулы максимально. Если мы подвинем A, B и C на юг (левое поддерево), оба врага погибнут вне зависимости от того, куда они двинутся, так что значение получается +2. Но если мы оставим A на месте, и подвинем только B и C, то оба врага могут пойти на восток, в результате чего все умрут, и итоговое значение будет 2 — 2 = 0. Это здорово, потому что мы можем отсечь часть вариантов и не смотреть больше ни на что, находящееся в коричневой рамке, ведь уже известно, что есть комбинация, которая может привести к результату в 2, но поскольку враг всегда выбирает наименее выгодные для нас движения, в этой коричневой рамке будет выбрано значение, не превышающее нуля.

Как вы можете заметить, я не стал рисовать некоторые поддеревья. К тому же, число возможных движений очень маленькое, и муравьёв всего пять, потому в настоящих случая дерево растёт куда сильнее, экспоненциально от числа муравьёв.

Реализация в псевдокоде выглядит примерно так:
List myAnts
List enemyAnts
bestValue = -Infinity
void max(antIndex) {
        if antIndex < myAnts.size
                myAnt = myAnts[antIndex]
                for each possible move of myAnt
                        simulate move
                        max(antIndex+1)
                        undo move
        
else
        value = min(0)
        if value > bestValue
                bestValue = value
                save the current simulated moves of all my ants
}
int min(antIndex) {
        if antIndex < enemyAnts.size
                minValue = +Infinity
                enemyAnt = enemyAnts[antIndex]
                for each possible move of enemyAnt
                        simulate move
                        value = min(antIndex+1)
                        undo move
                        if value < bestValue
                                return -Infinity  // cut!
                        if value < minValue
                                minValue = value
                return minValue
        
else
        return evaluate()
}

Нужно заполнить списки муравьёв, а затем вызвать max(0), в результате получая список оптимальных движений.

Оптимизации

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

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

Списки проверяемых движений

Ко второй версии я поэкспериментировал с разными оптимизациями, что позволило мне во многих ситуациях поддерживать заметно бОльшие группы. Давайте рассмотрим другой пример, на этот раз без воды, где для каждого муравья есть 5 различных вариантов хода (не считая тех, когда два муравья идут на одну клетку):
. . . . . .
. . A . . .
. . . B . .
. . . . C .
. . . . . .
. X Y . . .
. . . . . .

Что может случиться с муравьём А? Если он пойдёт на юг, он может вступить в бой, но если останется на месте, то будет вдали от сражения. Рассмотреть, конечно, нужно оба случая, так как мы пока не знаем, имеет ли смысл атаковать. Но как насчёт того, чтобы A пошёл на запад, север или восток? Так он точно не попадёт в бой, и оценка будет точно такой же, как если он останется на месте, значит эти движения не значимы, и рассматривать их не нужно. А вот если B и C останутся на месте, то на них может напасть Y, шагнув на север. Ещё можно заметить, что для B и C оценка движения на север равна оценке движения на восток, но я это не учитывал. Итак, для каждого муравья можно предподсчитать список движений, которые следует проверить. Тут есть много вложенных циклов, поскольку нужно проверить все близлежащии клетки для всех врагов, находящихся поблизости с каждым своим муравьём в группе.

Для врагов можно сделать что-то похожее, но слегка иначе. Пусть A останется на месте, а B и C отправятся на север. Теперь X и Y вне зоны доступа, потому что бы они не делали, оценка у этого будет такая же, как если остаться на месте. Если B всё же на север не пойдёт, а останется на прежнем месте, Y придётся рассмотреть ход на север, поскольку теперь это приведёт к бою. Получается, что чтобы враг знал, нужно ли рассматривать движение, нужно знать, есть ли на некоторой конкретнйо клетке мой муравей, или нет. Таким образом, для каждого врага есть соответствие из клетки (где может быть мой муравей) в список движений, которые необходимо проверить. Эти соответствия строятся ещё бОльшей тучей вложенных циклов…
Надеюсь, вы любите примеры, потому что вот ещё один, который показывает таблицу зависимости, на этот раз с указанием номеров строк и столбцов (обозначается строка/столбец):
  0 1 2 3 4 5
0 . . . . . .
1 . . , A . .
2 . . . , B .
3 . . . . , .
4 . X . . . .
5 . . . . . .

Если есть муравей на (1/2), муравей X должен проверить (3/1). Если есть на (2/3), то проверять следует (3/1) и (4/2). Для (3/4) нужно проверить (4/2). Вот так выглядит таблица:
(1/2) => [ (3/1) ]
(2/3) => [ (3/1), (4/2) ]
(3/1) => [ (4/2) ]


Эти списки очень сильно уменьшают ветвистость дерева, но теперь, к сожалению, сложно оценить, сколько времени могут занять вычисления. Я не отсекаю группы, основываясь на числе муравьёв, но ввожу ограничение на число собственных ходов, которые нужно рассмотреть, и на число врагов.

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

Оценка

Оценочная функция рассматривает не только число убитых своих и чужих, но ещё и расстояние между моими и вражескеми муравьями. Вот она:
if (beAgressive) return enemyDeadCount * 300 - myDeadCount * 180 - distValue;
else return enemyDeadCount * 512 - myDeadCount * (512+256) - distValue;

Если установлен флаг beAgressive, то мёртвый враг стоит 300 очков, а мёртвый свой муравей штрафует на 180. Таким образом, я пожертвую одного муравья, чтобы убить одного противника, трёх муравьёв, чтобы убить двух, но не двух, чтобы убить одного. В неагрессивном режиме бот не делает равных разменов, но вполне готов отдать двоих за трёх. distValue — сумма расстояний от каждого моего муравья до ближайшего вражеского, мы эту сумму вычитаем, поскольку лучше находиться ближе к врагу.

Так когда же beAgressive устанавливается в true? Это никак не связано с общим числом муравьёв или позиционным преимуществом, это зависит лишь от числа муравьёв, находящихся близко к бою. Более точно, флаг устанавливается если максимум от числа муравьёв в бою (именно в бою, а не в группе) пососедству с моим муравьём больше или равен 14. Почему? В основном потому что 42 делится на 14!

Приближение к врагам

Метод approachEnemies вызывается прямо после сражений, и отправляет тех моих муравьёв, что находятся близко к врагам, в их направлении. Для каждого своего муравья я сначала запускаю A*, который идёт только по свободным клеткам (т.е. не проверяет клетки, на которых есть другие сви муравьи), и ограничен по глубине трёхкратным манхэттоновским расстоянием до ближайшего противника. Если таким образом находился путь, выполнялось первое движение этого пути. Именно по этой причине мой бот часто выстраивался в шеренгу, так как если на передовой образовывалась пустота, туда сразу же шёл кто-то со второй линии.

Есть ещё метод attackDetachedEnemies, остаток от бета-версии, который заставлял приближаться сначала к обособленным врагам.

Защита

В первой версии защиты не было вовсе, но ко второй версии, когда карты с множеством муравейнико стали более популярными, я её всё же добавил. Я защищаю свои муравейники только когда у меня их не более четырёх. Не уверен, что это звучит разумно, но мне не особо нравится, когда их много. Я ищу врагов поблизости от моих муравейников с помощью — вы не поверите — поиска в ширину! Затем я этих врагов сортирую по расстоянию, и для каждого из них стараюсь найти одного защитника. Сначала я ищу среди тех, которые близко к пути, который должен пройти враг, чтобы дойти до муравейника. Этот путь получить легко, достаточно только пробежать обратно по предыдущим клеткам, информация о которых хранится при BFS. Если так защитник не находится, я запускаю ещё один BFS, который ищет моего муравья, находящегося ближе всех на 1/4 пути того врага. Этого зашитника я посылаю на 1/2 пути. Я не проверяю, безопасно ли это, поскольку обменять муравья 1 на 1 менее страшно, чем потерять муравейник.

Избегание врагов

В общем случае я страюсь избегать обменов 1 на 1, поэтому мои одинокии муравьи сбегают при виде одного или более врагов. Я рассматриваю все возможные движения моего муравья, пытаясь найти безопасное. Если такого нет, я делаю движение, которое хотя бы убьёт противника, если тот пойдёт в мою сторону.
Большую часть времени возможно сделать несколько безопасных движений, так что для того, чтобы выбрать, я добавил логику, которая оказалась одним из последних добавленных впопыхах изменений в версии 3. До того мои муравьи часто убегали в тупики, где они были лёгкой добычей, особенно на картах-лабиринтах. От этого я спасся, запуская BFS с максимальной глубиной в ESCAPE_CHECK_DIST (равна восьми) и складывая значения для всех безопасных движений, при этом близкие клетки имели больший вес, свои муравьи — хорошо, а вражеские --плохо:
int addValue = (ESCAPE_CHECK_DIST+1-tile.dist);
if (tile.type == Type.MY_ANT) addValue *= 3;
else if (tile.type.isEnemy()) addValue *= -3;


Распределение


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

Ну вот и всё!


Я уверен, что есть много мелких деталей, которые я не объяснил, но общая картина у вас должна появиться. Надеюсь, что вам был какой-то толк от того, что вы это прочитали, и извиняюсь за то, что не использовал более крутые алгоритмы.
Я ещё буду доступен в IRC, и наверняка поучаствую в следующих контестах, но вряд ли смогу снова уделить так много времени.

От переводчика


Честно сказать, я был сильно удивлён, когда прочитал эту заметку. В алгоритме победителя было огромное число изъянов: стоит только вспомнить про взятые с потолка константы и коэффициенты или не учитывание многих очень важных факторов. Тем не менее, сложно критиковать победителя, ведь, как говорится, «сперва добейся!». Наболее успешным был алгоритм ведения боя: довольно простой, но, по всей видимости крайне эффективный, ведь в непосредственном поединке xathis был явным лидером. Стоит полагать, что на основе его идей вскоре будет создана более общая система с динамическим подбором коэффициентов, и тогда на TCP-серверах будут крайне эпичные побоища.

Надеюсь, вам было интересно.
Перевод: Mathis [xathis] Lichtenberger
Глеб Смирнов @gvsmirnov
карма
103,5
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое

Комментарии (20)

  • +26
    Даже как-то обидно, что бот победил без стратегического мышления. Хотя, с другой стороны, это ведь муравьи и было бы неправдоподобно руководствоваться идеей коллективного разума, а не идеально выверенными природой рефлексами.

    Почему-то вспомнилось примечание к одной настольной игре, в которой один игрок играет за большое количество медлительных зомби, а другие игроки за людей. Так вот там, в правилах, была такая строчка
    «Зомби должны вести себя как зомби, а не как отряд специального назначения, умеющий устраивать засады, обходить и вообще действовать разумно» :)
    • +4
      Да, у xathis не был самый лучший стратегический алгоритм (хотя он очень сильный), но вот тактический алгоритм (атака/защита/уход) был самый лучший. Именно это и позволило ему быть самым первым, т.к. количество муравьев, которое остается после битвы, определяет контроль зоны и победу в конечном счете.
    • +4
      Требую название настолки!
      • +2
        пнп Zombie Plague :) Играли в расширенную версию, там таких замечаний не было, а вот в оригинале нашлись.
    • +4
      Ну тут вы не совсем правы. У бота есть вполне себе стратегическое мышление, и даже подобие hive-mind.
      Возьмите те же «миссии» для муравьев, логику «не посылать в атаку на муравейник больше 4-х муравьев, или если их меньше 10, то только одного»; расчет того, как двигаться при каком перевесе сил и т.п.
      Тут скорее стоит право внести ремарку, что это не стратегическое, а тактическое мышление (это всё же разные вещи), но согласитесь что при столь значительном рандоме (карты, еды, противников и т.п.), гораздо эффективнее сосредотачиваться именно на тактике, нежели длительной стратегии, что собственно данный бот и доказал.

      А так конечно можно доводить к идеалу до бесконечности (засады, удары в тыл, фланговые атаки и т.п.), но это уже на мой взгляд отняло бы значительно больше времени, особенно у одного человека.
      • +1
        Вы, по большому счету, сами ответили за меня :) «Стратегия это не тактика», никто и не ставит под сомнение его заслуги и правильность расстановки акцентов.
  • +7
    Очень интересно! Удивительно что победил алгоритм, который почти ничего не запоминает от хода к ходу и действует почти всегда на основе локальных данных.
    Он наверно победил потмоу, что его бот был ближе всего по духу к муравьям :)
    • +1
      У меня был точно такой же алгоритм: каждый раз заново все обсчитывалось. Прикол в том, что очень сложно было следить за муравьями, т.к. на вход подавался вектор из муравьев, который каждый раз пересоздавался заново. Плюс надо учитывать, что ты не видишь всего, что происходит, есть «туман войны». Плюс муравьи могут погибнуть в любой момент (их убьют или они самоликвидируются), плюс иногда передвигаешь муравья, а он может не передвинуться (например, когда ты идешь на еду, тогда этот ход игнорируется). Все это сильно усложняет логику по сохранению состояния, поэтому проще все время пересчитывать с нуля.
      • +1
        Мой бот оказался самым сильным среди PHP-ботов.

        Могу сказать, что для такого медленного языка, как PHP, слежение за муравьями и накопление информации от хода к ходу — необходимое условие, т.к. время на вычисления очень мало.
        Так, найдя вражеский муравейник, я делал BFS (волновой поиск) для него для всей открытой карты (чтобы можно было потом быстро послать к муравейнику любое количество муравьёв). Этот поиск растягивался у меня на 2-5, а то и больше ходов — смотря чем ещё был занят бот. В то время как ребята С++ писали, что делают сотню BFS за ход ).

        Для всех уже отправленных на маршрут муравьёв этот самый маршрут приходилось кэшировать. Поэтому нельзя было «терять» муравья ни в каком случае — даже если прямо перед ним появлялась еда, мешая ходить.

        Могу сказать, что достаточно невысокое место — это моя проблема, а не самого PHP. У последней версии бота оставалось всё ещё много времени для реализации кучи вещей, которые я задумал — но у меня самого его не было. Кроме того, закоммитил бота с глупой и смешной ошибкой: при определённых обстоятельствах муравьи-патрульные бросали патрулирование и убегали на другой конец карты помогать разведчику. Муравейник, ясное дело, тут же захватывали )

        Поэтому думал о том, чтобы написать оптимистическую статью о этих и других нюансах написания бота на медленном языке )
      • +1
        на самом деле в логике сохранения состояния ничего сложного нет, можно просто привязывать муравьев к сетке, при перемещении соответственно менять указатели. мне теперь стыдно советовать, т.к. даже в сотню не попал, ибо забил на minmax вообще и оценивал успешность атаки тупо по количеству муравьев. но все-таки код с полным сохранением состояний, обсчетом «тумана войны» и хорошим кешированием BFS (ну точнее у меня wavemap) легко уложился в 1500 строчек.

        хотя причину провала теперь осознаю, упор надо было делать на экономный расход муравьев, а не на хороший контроль территории, что в случае сильных соперников дает большие потери (много муравьев по одному рассеяны на карте).
  • –6
    random() — наше всё!
    • +5
      К сожалению, такой алгоритм не вошел в 100-ку.
      • +8
        к сожалению, это не алгоритм)
        • +3
          к сожалению, это не «к сожалению».
  • +4
    > (ну да, а вот очевидно простаивающий муравей — это уже страшнее. — прим. перев.)
    этот муравей вовсе не простаивает — он контролирует территорию
  • +5
    brunneng.blogspot.com/ Блог GreenTea — второе место
  • +2
    Пособие по борьбе с гопотой =)
  • НЛО прилетело и опубликовало эту надпись здесь
  • +1
    Только у меня страница xathis не доступна? Можете перевыложить исходники, пожалуйста?
  • 0
    В общем, победа была за счет того, что строились деревья переборов для каждого муравья на шаг (или несколько шагов) вперед. Такой алгоритм применяется, например, в шахматных программах. То есть, для движения муравья обсчитываются все возможные ситуации по принципу «а что будет если». Решение о направлении движения принимается с помощью альфа-бета отсечения по какому-нибудь критерию.

    Впринципе такой подход очень эффективен, гораздо эффиктивен всяких стратегий, построенных на основе анализа игры. Я думаю, что такой подход наверно станет стендартом де-факто при написании программ в подобных конкурсах.

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.