сложно сказать наверняка, но на глаз видно что топовые боты лучше организуют контроль (и защиту) территорий, расставляя «часовых» в «узких» местах. если сравнивать качество обхода карты, то за равное время они собирают не большее количество еды, чем при описанном в моей заметке обходе — хотя, это и не критерий, но это то что легко может видеть человек.
я бы сказал, что писать синтетические алгоритмы на языке, отличном от С++ — уже заведомый проигрыш. Но кроме синтетических, есть еще и конструктивные алгоритмы, в которых описано большее количество человеко-понимаемых правил, а перебора по сути меньше, вот в таких случаях С++ не так удобен.
явно реализовано только описанное, и «дежурные» муравьи для того чтобы не терять свой муравейник из вида. атака вражеских муравейников есть, это первое правило. групповой атаки в явном виде нет, но когда один из муравьев получает цель — вражеский муравейник, и ему на пути (в пределах видимости) встречаются враги, то соседние свои муравьи начинают «подтягиваться» (правило поддержки). отступление реализуется проверкой на «бессмысленность» смерти (в пункте о блокировках), но это даже не полноценное отступление, а выбор из всех возможных направлений того, которое имеет смысл, и не приводит к смерти.
это синтетический алгоритм, он и не должен быть очень сложным. и да, достаточно, более того, реализация без технических ошибок попала бы в двадцатку (в моей версии есть ошибки).
увы, правилами это запрещено — была бы возможность создавать потоки, было бы разумно ей воспользоваться пока другие игроки считают свой ход, но во-первых возможно это помешает им (загрузка процессора еще ладно, но обращения к памяти), а во вторых сделает разное и не очень предсказуемое время на ход. так что posix-овские хедера с сервера порезали.
Вообще волновой алгоритм это и есть частный случай Дейкстры для графа представляющего собой сетку вершин. Волновой алгоритм перепроверяет вершины, только если число, стоящее в ней больше, чем число вершины из которой мы пришли, но это соответствует маркировке «вычеркнутых вершин» Дейкстры. Проблемы с производительностью, думаю на PHP будут. На плюсах достаточно тупой вариант обхода без каких-либо кеширований отрабатывает едва ли за секунду для 100 муравьев. А на кеширование нужно до (200x200)^4 байт памяти (для каждой точки «откуда» идти, сохраняем всю карту расстояний от нее == результат одного прогона волнового алгоритма). Но это как раз влезает в отведенные 1.5Гб памяти.
захожу я и вижу такое (текст последнего комментария):
в контексте топика было особенно интересно, что за вид рекламы, который настойчиво не советует покупать товар :)
я писал нахождение пути через волновой алгоритм + кеширование результатов (по сути для каждой пары клеток куда-откуда записывается направление для кратчайшего пути).
в этой версии правда вообще никак не сделана battle resolution и защита hill, но на какой-то момент она была в десятке лучших, aichallenge.org/visualizer.php?game=11045&user=682
кстати в C++ started package очень медленно сделано updateVisibility, на карте 150x150 при 1000 муравьев этот код одъедает бОльшую часть лимита (до 300мс), пришлось переписывать :)
вот как раз про battle resolution было бы круто поговорить, когда я последний раз смотрел было только «Это самая веселая часть игры!», теперь добавили спецификацию. Вроде буквы понятные, но не понятно «within the attack radius of» — имеется в виду меньше или меньше-равно attackradius. и что значит «ant dies», влияет ли это на текущий обсчет боя, или же при расчете enemies(a) для остальных участников схватки муравей все еще «жив» до окончания этого обсчета (потому как в примерах выше, вроде как порядок вычисления важен)? Но правда и без понимания этого пока удалось попасть в двадцатку =)
Регистрироваться лень, но 3 минуты это на звонок или переписку?
Если на переписку то очень сомнительная идея, не у всех скорость печати over 9000 знаков в минуту, даже в час, хех.
только тогда еще нужно объяснить почему P(d)=1/2, у меня нигде значение P(d) не используется. Но к сожалению на вопрос «зачем?» кроме как, «а почему бы и нет», не могу ответить )
А вот другое рассуждение, тоже попробуйте найти ошибку.
Вытянули одну золотую, вероятность что вторая золотая == вероятности выбора «нужного» ящика т.к. выбор монетки — однозначное соответствие с выбором ящика, и т.к. только в одном из трех есть две золотые. P = нужный ящик / количество допустимых выборов == 1/2.
в целом очень похоже, даже изначальное заполнение клеток тоже зависит от lastSeen — меньше операций поиска пути, зато больше вещественных операций с полем.
сложно сказать наверняка, но на глаз видно что топовые боты лучше организуют контроль (и защиту) территорий, расставляя «часовых» в «узких» местах. если сравнивать качество обхода карты, то за равное время они собирают не большее количество еды, чем при описанном в моей заметке обходе — хотя, это и не критерий, но это то что легко может видеть человек.
это синтетический алгоритм, он и не должен быть очень сложным. и да, достаточно, более того, реализация без технических ошибок попала бы в двадцатку (в моей версии есть ошибки).
в контексте топика было особенно интересно, что за вид рекламы, который настойчиво не советует покупать товар :)
в этой версии правда вообще никак не сделана battle resolution и защита hill, но на какой-то момент она была в десятке лучших, aichallenge.org/visualizer.php?game=11045&user=682
Если на переписку то очень сомнительная идея, не у всех скорость печати over 9000 знаков в минуту, даже в час, хех.
P(a) = монета вытащена из первого ящика
P(b) = монета вытащена из второго ящика
P© = монета вытащена из третьего ящика
P(d) = вытащена золотая монета
P(d|a)= 1 (обе золотых)
P(d|b) = 0 (нет там золотых)
P(d|c) = 1/2
вероятность что мы вытянем вторую золотую = вероятности выбора нужного (первого) ящика = P(a|d) = (по ф.Байеса) = P(a)P(d|a) / ( P(a)P(d|a) + P(b)|P(d|b) + P©|P(d|c) ) = 1/3*1 / ( 1/3*1 + 1/3*0 + 1/3*1/2) = 1 / (1+1/2) = 2/3.
Вытянули одну золотую, вероятность что вторая золотая == вероятности выбора «нужного» ящика т.к. выбор монетки — однозначное соответствие с выбором ящика, и т.к. только в одном из трех есть две золотые. P = нужный ящик / количество допустимых выборов == 1/2.