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

Ответ 1

ИЗМЕНИТЬ ОТ ОП:

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

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

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

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

Проблема здесь заключается в поиске хорошей эвристической функции, которая оценивает "насколько хорошо состояние"

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

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

Ответ 2

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

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

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

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

Ответ 3

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

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

Ответ 4

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

Точно!

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

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

BTW: вы можете увидеть блог текущего лидера, и его стратегия на удивление проста.