Продолжаем разбираться в правилах проходящего сейчас турнира Google AI Challenge. Дальше вы можете прочитать перевод официальных правил расчета результатов муравьиных боев.
Исход битвы определяется с двух различных ракурсов:
Муравей погибает, если враг, находящийся на расстоянии атаки, окружен меньшим (или таким же) количеством его собственных врагов.
или
Наш муравей убивает врага, если враг, находящийся на расстоянии атаки, окружен большим (или таким же) количеством врагов, чем его цель.
Если это пока не понятно, не отчаивайтесь, дальше будут подробные объяснения.
Первая — создать нового муравья из еды, к которой он подобрался достаточно близко. Это действие, конечно, достаточно сложно для муравья, требующее точной и кропотливой работы (именно поэтому к еде надо подобраться вплотную). Хотя результат совершенно прост — если еда достаточно близко, появляется еще один муравей того же цвета. Исключением является случай, когда несколько муравьев разных цветов приблизятся к еде вплотную одновременно; еда уничтожается при их попытке собрать ее.
Вторая — атаковать вражеских муравьев. Это гораздо проще рождения и может происходить на гораздо большей дистанции (хотя детали достоверно неизвестны, но приходится быстро перебирать лапками). Результаты могут быть несколько сложнее для понимания, чем при рождении.
В простейшем случае, когда два отдельных муравья различных цветов сближаются друг с другом настолько, что вступают в бой, все их внимание сконцентрировано на противнике. Уделяя равное количество внимания, противники убивают друг друга.
Когда одинокий муравей сталкивается с двумя противниками одновременно, ему приходится разделять внимание между врагами. Враги при этом полностью сосредоточены на муравье. Это значит, что одинокий муравей придет в растерянность и погибнет, а двое других выживут. Вы видите, что для выживания концентрация внимания у муравья должна быть выше, чем у противника. Если внимание муравья равно или меньше, чем у кого-либо из противников, муравей погибает.
Муравьи не различают врагов по цветам. Если муравьи трех разных цветов, скажем, зеленый, красный и синий одновременно окажутся на расстоянии атаки друг друга, внимание каждого муравья будет разделено между двумя врагами, и все три муравья погибнут. Но если у зеленого муравья с одной стороны будет красный, а с другой стороны синий, причем красный и синий слишком далеко для атаки друг друга, тогда только зеленый погибнет. Ведь его внимание будет рассредоточено между двумя противниками, в то время как каждый из врагов буден сконцентрирован только на зеленом.
Будем надеяться, что это описание помогло вам понять принцип расчета исхода битвы. Для закрепления понимания рассмотрим более сложный пример боя.
Два синих муравья Сид и Сэм, и два красных муравья Кент и Кайт исследовали мир. И вот, после очередного хода Сэм вышел на расстояние атаки обоих красных муравьев, в то время как Сид может атаковать только Кента. Теперь вопрос к вам. Кто погибнет, а кто выживет?
Не подлгядывайте ответ, пока вы не ответите на вопрос.
Вы уже получили ответ? Не продолжайте пока не получите.
В этой ситуации у синего муравья Сэма и красного муравья Кента внимание разделено между двумя врагами. Сид и Кайт сконцентрированы каждый на своем единственном враге, внимание которого разделено. Поэтому в этой битве погибнут Сэм и Кент, а Сид и Кайт выживут, для того чтобы сразиться в будущем.
Довольно просто, так ведь? Конечно. Каждая битва протекает таким же образом. Если внимание муравья делится между меньшим количеством противников, чем внимание каждого из его противников, он выживает. Теперь вы готовы к тому, чтобы углубиться в этот документ, чтобы найти описание некоторых технических деталей и дополнительные примеры.
Чтобы попробовать посчитать битву вручную, достаточно подсчитать количество врагов, окружающих каждого муравья:
Затем, если рядом с муравьем есть враг с меньшим или равным числом — муравей погибает.
Во всех случаях квадрат радиуса атаки равен 5, и дистанция атаки имеет форму как на рисунке (с подсчитанными квадратами радиусов)
Погибают оба
A погибает
Все погибли
Муравей посередине погибает. A и C выживают.
B и C погибают
Много полегло
Муравей B выживает потому, что его атакуют только 3 центральных муравья A, каждый из которых занят гораздо больше. В свою очередь он влияет на смерть этих трех центральных муравьев A.
Муравьи A с краю выживают потому, что их атакует единственный муравей B который занят гораздо больше.
Сид и Сэм против Кента и Кайта:
Верхний и нижний муравьи не достают друг друга.
По одной смерти с каждой стороны
Для положения муравья x, зададим функцию enemies(x), равную количеству врагов находящихся на расстоянии атаки от x.
Для положения муравья a, a выживает если
Аналогично, для положения муравья a, a погибает если
Основное правило результата боя
Исход битвы определяется с двух различных ракурсов:
Муравей погибает, если враг, находящийся на расстоянии атаки, окружен меньшим (или таким же) количеством его собственных врагов.
или
Наш муравей убивает врага, если враг, находящийся на расстоянии атаки, окружен большим (или таким же) количеством врагов, чем его цель.
Если это пока не понятно, не отчаивайтесь, дальше будут подробные объяснения.
Очевидные факты о мире муравьев
Муравей — это очень простое существо. По сути он может делать самостоятельно только две вещи.Первая — создать нового муравья из еды, к которой он подобрался достаточно близко. Это действие, конечно, достаточно сложно для муравья, требующее точной и кропотливой работы (именно поэтому к еде надо подобраться вплотную). Хотя результат совершенно прост — если еда достаточно близко, появляется еще один муравей того же цвета. Исключением является случай, когда несколько муравьев разных цветов приблизятся к еде вплотную одновременно; еда уничтожается при их попытке собрать ее.
Вторая — атаковать вражеских муравьев. Это гораздо проще рождения и может происходить на гораздо большей дистанции (хотя детали достоверно неизвестны, но приходится быстро перебирать лапками). Результаты могут быть несколько сложнее для понимания, чем при рождении.
В простейшем случае, когда два отдельных муравья различных цветов сближаются друг с другом настолько, что вступают в бой, все их внимание сконцентрировано на противнике. Уделяя равное количество внимания, противники убивают друг друга.
Когда одинокий муравей сталкивается с двумя противниками одновременно, ему приходится разделять внимание между врагами. Враги при этом полностью сосредоточены на муравье. Это значит, что одинокий муравей придет в растерянность и погибнет, а двое других выживут. Вы видите, что для выживания концентрация внимания у муравья должна быть выше, чем у противника. Если внимание муравья равно или меньше, чем у кого-либо из противников, муравей погибает.
Муравьи не различают врагов по цветам. Если муравьи трех разных цветов, скажем, зеленый, красный и синий одновременно окажутся на расстоянии атаки друг друга, внимание каждого муравья будет разделено между двумя врагами, и все три муравья погибнут. Но если у зеленого муравья с одной стороны будет красный, а с другой стороны синий, причем красный и синий слишком далеко для атаки друг друга, тогда только зеленый погибнет. Ведь его внимание будет рассредоточено между двумя противниками, в то время как каждый из врагов буден сконцентрирован только на зеленом.
Будем надеяться, что это описание помогло вам понять принцип расчета исхода битвы. Для закрепления понимания рассмотрим более сложный пример боя.
Два синих муравья Сид и Сэм, и два красных муравья Кент и Кайт исследовали мир. И вот, после очередного хода Сэм вышел на расстояние атаки обоих красных муравьев, в то время как Сид может атаковать только Кента. Теперь вопрос к вам. Кто погибнет, а кто выживет?
Не подлгядывайте ответ, пока вы не ответите на вопрос.
Сид -> С..
...
Сэм -> С.К <- Кент
...
..К <- КайтВы уже получили ответ? Не продолжайте пока не получите.
В этой ситуации у синего муравья Сэма и красного муравья Кента внимание разделено между двумя врагами. Сид и Кайт сконцентрированы каждый на своем единственном враге, внимание которого разделено. Поэтому в этой битве погибнут Сэм и Кент, а Сид и Кайт выживут, для того чтобы сразиться в будущем.
Довольно просто, так ведь? Конечно. Каждая битва протекает таким же образом. Если внимание муравья делится между меньшим количеством противников, чем внимание каждого из его противников, он выживает. Теперь вы готовы к тому, чтобы углубиться в этот документ, чтобы найти описание некоторых технических деталей и дополнительные примеры.
Некоторые технические детали
У каждого муравья на дистанции атаки может быть несколько противников. Считается, что он «занят» сражением с этими муравьями. У каждого муравья может быть свое количество врагов, которые «занимают» его внимание. Муравьи, которые заняты меньшим количеством врагов, более сфокусированы на убийстве этих врагов, чем муравьи, которые которые сражаются с большим количеством врагов. Одинаково занятые муравьи могут убить друг друга.......C
C.A.B.C
......C- муравей A на расстоянии атаки от муравья B
- муравей A занят (или сражается с) 2-я противниками
- муравей B занят (или сражается с) 4-я противниками
- муравью B приходится отслеживать и отвлекаться на большее число противников, поэтому он менее эффективно сражается, чем муравей A
- поэтому муравей A может убить муравья B
- если учесть муравьев C, то ситуация изменится, но мы пока рассматривали только A и B
- муравьи C убьют и A и B, даже если бы A и B были не так близко друг к другу
Чтобы попробовать посчитать битву вручную, достаточно подсчитать количество врагов, окружающих каждого муравья:
......1
1 2 4 1
......1Затем, если рядом с муравьем есть враг с меньшим или равным числом — муравей погибает.
......C
C.x.x.C
......CВарианты
Во всех случаях квадрат радиуса атаки равен 5, и дистанция атаки имеет форму как на рисунке (с подсчитанными квадратами радиусов)
....... ...9...
..xxx.. .85458.
.xxxxx. .52125.
.xxAxx. 9410149
.xxxxx. .52125.
..xxx.. .85458.
....... ...9...Один на один
Погибают оба
..... ..... .....
.A.B. -> .1.1. -> .x.x.
..... ..... .....Двое на одного
A погибает
...B. ...1. ...B.
.A... -> .2... -> .x...
...B. ...1. ...B.Сошлись 3 бойца
Все погибли
...B. ...2. ...x.
.A... -> .2... -> .x...
...C. ...2. ...x.Муравьиный сандвич
Муравей посередине погибает. A и C выживают.
..... ..... .....
A.B.C -> 1.2.1 -> A.x.C
..... ..... .....Пара против двух одиночек
B и C погибают
...B. ...3. ...x.
.A.A. -> .2.2. -> .A.A.
...C. ...3. ...x.Пробивание стены
Много полегло
AAAAAAAAA 013565310 AAxxxxxAA
...BBB... -> ...555... -> ...xxx...
...BBB... ...333... ...xBx...Муравей B выживает потому, что его атакуют только 3 центральных муравья A, каждый из которых занят гораздо больше. В свою очередь он влияет на смерть этих трех центральных муравьев A.
???AAA??? ???565??? AAxxxxxAA
...???... -> ...???... -> ...xxx...
...?B?... ...?3?... ...xBx...Муравьи A с краю выживают потому, что их атакует единственный муравей B который занят гораздо больше.
?A??????? ?1??????? AAxxxxxAA
...B??... -> ...5??... -> ...xxx...
...???... ...???... ...xBx...Сид и Сэм против Кента и Кайта:
Верхний и нижний муравьи не достают друг друга.
По одной смерти с каждой стороны
..С.... ..1.... ..С....
..С.К.. -> ..2.2.. -> ..x.x..
....К.. ....1.. ....К..Математика
Для положения муравья x, зададим функцию enemies(x), равную количеству врагов находящихся на расстоянии атаки от x.
Для положения муравья a, a выживает если
Аналогично, для положения муравья a, a погибает если
Псевдокод:
// Как проверить погибнет ли муравей
для каждого муравья:
для каждого врага на расстоянии атаки от муравья:
если (врагов в атаке на муравья) >= (врагов в атаке на врага) тогда
муравей погибает
прерывание цикла по врагамПитон
# предварительно подсчитаем количество врагов рядом с каждым муравьем для ускорения
# отобразим муравьев на ближайших врагов
nearby_enemies = {}
for ant in self.current_ants.values():
nearby_enemies[ant] = self.nearby_ants(ant.loc, self.attackradius, ant.owner)
# зададим каких муравьев убить
ants_to_kill = []
for ant in self.current_ants.values():
# зададим слабость у муравьев (1/power)
weakness = len(nearby_enemies[ant])
# муравей, рядом с которым нет врагов не может быть атакован
if weakness == 0:
continue
# определим самого сильного ближайшего врага
min_enemy_weakness = min(len(nearby_enemies[enemy]) for enemy in nearby_enemies[ant])
# муравей погибает, если его слабость больше или равна слабости врага
if min_enemy_weakness <= weakness:
ants_to_kill.append(ant)