Боевая стратегия для муравьев

Question

Этот вопрос относится к спонсируемому Google AI Challenge , конкурсу, который проводится каждые несколько месяцев и в котором претенденты должны представить бота, способного автономно играть в игру против других игроков-роботов.Конкурс, который только что завершился, назывался "муравьи", и вы можете прочитать все его спецификации здесь , если вам интересно.

Мой вопрос относится к одному аспекту муравьев : боевая стратегия .

Задача

Учитывая сетку дискретных координат [как на шахматной доске] и учитывая, что у каждого игрока есть количество муравьев, которые на каждом ходу могут либо:

1. стоять на месте
2. двигаться на восток / север / запад / юг,

... муравей будет убит вражеским муравьем, если вражеский муравей в радиусе действия будет окружен меньшим количеством (или то же самое) своих врагов, чем муравей [эквивалентно: «Муравей убьет муравья-врага, если враг, находящийся на расстоянии, окружен большим (или тем же) врагом, чем его цель»]

Aвизуальный пример:

В этом случае желтые муравьи собираются двигаться на запад, а у оранжевого муравья, не способного отойти [синие плитки блокируют], будет дважелтые муравьи «в пределах досягаемости» и умрут (если объяснение все еще неясно, я приглашаю вас посетить ссылку выше , чтобы увидеть больше примеров и объясненных сценариев).

Вопрос

Мой вопрос по существу о сложности.Я много думал об этой проблеме, но все равно не смог придумать приемлемый способ расчета оптимального набора ходов за разумное время .Мне кажется, что для нахождения наилучшего возможного набора ходов для моих муравьев я должен оценить результат для каждого возможного сценария, но поскольку битвы могут быть довольно переполнены муравьями, это будет означать, что время вычислений будет расти в геометрической прогрессии (5^nгде n - число задействованных муравьев).

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

Я подозреваю, что хорошее решение может быть найдено по некоторым геометрическим соображениям в сочетании с линейной алгеброй (возможно, вычисление некоторых "центров тяжести" для группмуравьев?) но я не мог пройти уровень «интуиции» на этом ...

Итак, мой вопрос действительно сводится к:

Как решить эту проблемунайти [почти] оптимальные решения за время вычисления ~ 50-100 мс на современном компьютере (эта цифра получена из официальных правил конкурса)?

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

Answer 1

Действительно сложно. Вы можете найти некоторые подсказки в Алгоритмах пчел . Это набор алгоритмов, которые используют кооперацию роя и «разумное время вычислений». Например, алгоритмы пчел могут быть использованы, чтобы примерно (!) Решить проблему коммивояжера. Я ожидаю, что эти алгоритмы могут предоставить вам лучшее решение с учетом вычислительного времени.

Конечно, проблему можно упростить, используя геометрию: относительные положения муравьев в окрестности важнее абсолютных позиций. А также решение light_303 дополняет шаблон поиска, который я предлагаю.

Answer 2

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

• + 1 для места сохранения
• + 2 дляместо, в результате которого враг умирает
• -1 очко за позицию с определенной смертью

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

Возможно, стоит попробовать:)

Answer 3

РЕДАКТИРОВАТЬ С ОП:

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

---

. Для такого рода проблем алгоритм MinMax с альфа-бета-отсечкой обычноиспользуемый.(*) [простое объяснение minmax и alpa beta prunning в конце, но для более подробной информации, страницу википедии также следует прочитать].

Чтобы преодолеть проблему, которую вы упомянули о чрезвычайно большом количестве возможных ходов, общее улучшение заключается в том, что алгоритм minmax выполняется итеративно.Сначала вы исследуете все узлы до глубины 1 и находите лучшее решение.Если у вас еще есть время: исследуйте все узлы до глубины 2, а теперь выберите новое, более информированное, лучшее решение и т. Д. ...
Когда не вовремя: дает лучшее решение, которое вы можете найти, на последнем уровневы исследовали.

Чтобы еще больше улучшить свое решение, вы можете изменить порядок разрабатываемых вами узлов: для итерации i сортируйте узлы в итерации (i-1) [по их эвристическому значению для каждой вершины] и исследуйтекаждая возможность согласно заказу.Идея заключается в том, что вы с большей вероятностью обрежете больше вершин, если сначала исследуете «лучшие» решения.

Здесь остается проблема поиска хорошей эвристической функции, которая оценивает «насколько хорошо состояние».

(*) Алгоритм MinMax прост: вы исследуете игровое дерево и решаете, что вы будете делать для каждого состояния, и что ваш оппонент, скорее всего, сделает для каждого действия.Это делается до глубины k, где алгоритму присваивается значение k.

Альфа-бета-отсечение является дополнением к minmax, которое говорит вам, «какие узлы больше не нужно исследовать, так как яне собираюсь выбирать их, потому что у меня есть лучшее решение "

Answer 4

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

Точно!

Это соревнование AI .ИИ имеет дело с проблемами, которые слишком сложны , чтобы их можно было решить с помощью оптимальных алгоритмов.

Таким образом, вы должны попробовать "вещи", такие как ваше представление о центрах тяжести.Еще лучше были бы некоторые генетические алгоритмы, в которых лучшие стратегии находят путем естественного отбора (но для этого сложно создать какую-то развивающуюся «основу»).

Кстати: вы можете увидеть блог нынешнего лидера и его стратегии на удивление просто.