Этот топик — перевод первых двух частей руководства по написанию своего бота для Google AI Challenge.
Весь код написан на языке Python.
Шаг 1: Как избежать столкновений
План
Чтобы муравьи не сталкивались надо:
1) Предотвратить перемещение одного муравья на другого;
2) Предотвратить перемещение двух муравьев в одну и ту же точку;
3) отслеживать информацию о местонахождении всех наших муравьёв.
Реализация
Для отслеживания информации о том, где муравьи находятся, мы будем использовать словарь (он же HashMap, ассоциативный массив, JavaScript-объект). Каждый ключ массива будет позицией, а значение — муравей, который движется в эту точку. Местоположение будет кортежом (списоком, массивом) из двух значений — строк и столбцов на карте. Затем мы можем проверить список, прежде чем двигаться, чтобы 2 муравья не двигались на одно и то же место. Каждый раз, когда мы перемещаем муравья, мы должны обновить список.
Эта проверка будет пригодится в дальнейшем в руководстве, так что мы сделаем функцию, которая проверяет, возможен ли данный шаг. Она возвращает логическое (истина или ложь) значение.
Код
Вырежем комментарии из кода из примера и вставим новый код новый код:
def do_turn(self, ants):
# track all moves, prevent collisions
orders = {}
def do_move_direction(loc, direction):
new_loc = ants.destination(loc, direction)
if (ants.unoccupied(new_loc) and new_loc not in orders):
ants.issue_order((loc, direction))
orders[new_loc] = loc
return True
else:
return False
# default move
for ant_loc in ants.my_ants():
directions = ('n','e','s','w')
for direction in directions:
if do_move_direction(ant_loc, direction):
break
(Примечание: Убедитесь, что отступы правильные. В Python отступы определяют блоки кода и области видимости, поэтому отступы должны быть правильными)
Функция Do_move_direction принимает позицию муравья (кортеж (строка, столбец)) и направление ('N', 'е', 'S' или 'W') и пытается выполнить движение. Эта функция находится внутри метода класса (который также является функцией) и это нормально в Python. (Если вы пишете на другом языке, то, возможно, потребуется поставить функцию в другом месте) Мы используем некоторые предопределенные функции из начального бота:
ants.destination принимает местоположение и направление и возвращается место назначения для нас. Эта функция обрабатывает перемещение муравья через край карты, нам не нужно думать об этом
ants.unoccupied принимает местоположение и определяет, можно ли переместить туда муравья. Это лучше, чем ants.passable, которая не позволит нам переместится на еду или другич муравьёв.
Ассоциативный массив orders используется для отслеживания текущих движений. Проверка занятости new_loc и её отсутствие в массиве orders поможет предотвратить столкновения.
Результат
Давайте запустим бота снова и посмотрим:
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Повтор: http://aichallenge.org/ants_tutorial_step_1.php
Уже лучше, но все еще не очень хорошо. Один одинокий муравей вышел и сразился с HunterBot. Это не самоубийство, а улучшение. Кроме того, мы создали вспомогательную функцию, которая пригодится позже.
Шаг 2: Сбор еды
План
Нам нужно более двух муравьёв чтобы победить, и есть еда недалеко от стартовой позиции муравья! Давайте попробуем собрать её. Мы должны переместить муравья к еде чтобы собрать её. Мы также хотим сделать это эффективно. Вы заметили, что HunterBot послал половину всех его муравьёв за едой в последней игре? Кажется, что это может быть неэффективно.
Мы собираемся реализовать нечто похожее на приоритетную очередь. Мы сделаем список всех наших муравьев, а затем посмотрим, как далеко он находится от каждой еды. Затем мы отсортируем список и отправить каждого муравья к ближайшей пищи, но только по одному муравью к одной еде. Другие муравьи будут свободны и будут заниматься другими важными делами. Мы также избавимся от глупых движений по умолчанию, которые остались от стартового бота.
Реализация
Чтобы отслеживать информацию о еде, за которой уже идут муравьи, нам нужен еще один массив. Он будет хранить расположение целевой пищи как ключ, и расположение муравьев, которые идут за ней в качестве значения. Мы можем проверять ключ цели, чтобы убедиться что мы не отправляем два муравья к одной и той же пищи. Мы создадим другую вспомогательную функцию, чтобы сделать несколько иной тип движения. Вместо расположения муравьев и направления, мы сделаем расположение муравьев и целевое расположение, и функция будет выяснять направление.
Код
Создайте следующие функции после функции do_move_direction:
targets = {}
def do_move_location(loc, dest):
directions = ants.direction(loc, dest)
for direction in directions:
if do_move_direction(loc, direction):
targets[dest] = loc
return True
break
else:
return False Массив targets отслеживает муравьёв и их цель — еду. Мы используем другую стандартную функцию бота, чтобы помочь нам:
ants.direction принимает текущее место и цель, и возвращает список ближайших направлении «по прямой». Если цель вверху слева, то он вернет ['N', 'W'], и мы должны затем попытаться переместить нашего муравья в одно из этих двух направлений. Если цель прямо внизу, то он вернет ['S'] — список из одного элемента.
Заменим функцию move этим:
# find close food
ant_dist = []
for food_loc in ants.food():
for ant_loc in ants.my_ants():
dist = ants.distance(ant_loc, food_loc)
ant_dist.append((dist, ant_loc, food_loc))
ant_dist.sort()
for dist, ant_loc, food_loc in ant_dist:
if food_loc not in targets and ant_loc not in targets.values():
do_move_location(ant_loc, food_loc) Здесь у нас есть список — ant_dist — который будет хранить для каждого муравья сочетание пищи и расстояния как кортеж (расстояние, ant_loc, food_loc). Список строится вложенным циклом чтобы дать нам каждую комбинацию. Далее мы сортируем список. Python-списки имеют несколько полезных функций для сортировки. Чтобы отсортировать кортеж, питон будет сравнить первые значения каждого кортежа, а затем, если они такие же, перейдем к второму значению и так далее. Именно поэтому мы сохранили расстояние как первое значение, чтобы убедиться, что кратчайшее расстояние являются первыми в списке.
Далее мы в цикле по отсортированному списку проверяем есть ли у нас любые свободные муравьи которые могут собирать пищу. Food_loc not in targets проверяет, имеет ли пища муравья который уже идёт за ней. Ant_loc not in targets.values() проверяет что муравью еще не было дано задание. Если муравей будет найден, мы вызываем do_move_location.
Результат
Давайте запустим бота снова и посмотрим:
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: [1,1,0] 0 [1,1] - 16 1 [0,0] [1,1] [1,1] [1,1] 1 [0,1]
...
turn 60 stats: [4,6,0] 0 [1,1] - 6 1 [0,0] [1,1] [1,1] [1,1] 1 [0,1]
score 1 1
status survived survived
playerturns 60 60Повтор: http://aichallenge.org/ants_tutorial_step_2.php
Вся пища, которую мы могли видеть, была захвачена. Если вы внимательно посмотрите на повтор, вы можете увидеть у нас еще есть 3 муравья у муравейника которые не могут появиться. В будущем лучше позаботиться об этом. Если муравьи не могут выйти, они не могут помочь нам победить.
Оригинал:
P.S. пока эта статья проходила через песочницу, webkumo опубликовал похожую статью. Его статья содержит Ants Tutorial и Step 1: Avoiding collisions, эта — Step 1: Avoiding collisions и Step 2: Gathering Food.