Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 36
Впрочем это бесконечный сабж.
Хорошо что он работает на локалке и ни куда не денется.
Вообще алгоритмы тут можно придумывать очень разные.
Начиная от группирования мурашей, заканчивая равномерным распределением по карте.
Вот на счет распределения по карте. Видел как кто-то запустил этот алгоритм, так он всех выиграл за 400 турнов.
Из-за того что все мураши были равномерно распределены по карте, то большая часть еды была его и даже большие группы ложились хоть и весьма долговато.
Всем удачи в соревнованиях!
Хорошо что он работает на локалке и ни куда не денется.
Вообще алгоритмы тут можно придумывать очень разные.
Начиная от группирования мурашей, заканчивая равномерным распределением по карте.
Вот на счет распределения по карте. Видел как кто-то запустил этот алгоритм, так он всех выиграл за 400 турнов.
Из-за того что все мураши были равномерно распределены по карте, то большая часть еды была его и даже большие группы ложились хоть и весьма долговато.
Всем удачи в соревнованиях!
Возможно ли параллельность работы алгоритма. Допустим, один поток вычисляет пути, второй поток управляет сбором еды, а третий — атакой на муравейники и т.д? Насколько я помню, сервера там с core i7.
увы, правилами это запрещено — была бы возможность создавать потоки, было бы разумно ей воспользоваться пока другие игроки считают свой ход, но во-первых возможно это помешает им (загрузка процессора еще ладно, но обращения к памяти), а во вторых сделает разное и не очень предсказуемое время на ход. так что posix-овские хедера с сервера порезали.
Несколько вопросов:
1. Является ли карта полностью обозримой? Те. в любой момент времени мы имеем положение всех объектов на карте? Как вообще работает видимость, можно подробнее?
2. Как быстро в среднем растет количество муравьев у сильного противника? Те. реально ли ходить большими боевыми группами, чтобы муравьи противника гарантированно погибали? (Я не видел алгоритмов, где они ходят сплошным блоком).
1. Является ли карта полностью обозримой? Те. в любой момент времени мы имеем положение всех объектов на карте? Как вообще работает видимость, можно подробнее?
2. Как быстро в среднем растет количество муравьев у сильного противника? Те. реально ли ходить большими боевыми группами, чтобы муравьи противника гарантированно погибали? (Я не видел алгоритмов, где они ходят сплошным блоком).
3. Можно ли сохранять результаты обучения между боями? Те. учиться по ходу тестирования скрипта.
1. Изначально вся карта заполнена землей (в Java версии так) потом игровой движок каждый ход присылает список клеток, который в данный момент видимы вашим муравьям, и отличаются от земли (муравей, еда, вода, муравейник, враг)
2. Как сильно растут не отвечу, но тут есть компромисс — ходить раздельно — собирать больше еды, ходить вместе.
3. Писать в файлы на сервере нельзя, но если на локальном компьютере тестируете, то почему нет.
2. Как сильно растут не отвечу, но тут есть компромисс — ходить раздельно — собирать больше еды, ходить вместе.
3. Писать в файлы на сервере нельзя, но если на локальном компьютере тестируете, то почему нет.
Я видел несколько ботов где муравьи передвигаются группами.
Спасибо за статью, почерпнул для себя 4-5 интересных момента, именно в деталях. Основной функционал уже реализован.
> В этой заметке я расскажу как написать бота для Google AI Challenge, который без труда попадет в 50 лучших из 6500 участников (на текущий момент).
Интригующее вступление, но что-то мне подсказывает, что этого всего не достаточно, чтоб попасть в топ 50. Основные алгоритмы, которые гарантируют попадает в топ — это атака вражеских муравейников, защита своих, атака чужих муравьев, группирование своих муравьев, отступление при возможном поражении. У вас, действительно, это все не реализовано, или вы решили не раскрывать секретов?
> В этой заметке я расскажу как написать бота для Google AI Challenge, который без труда попадет в 50 лучших из 6500 участников (на текущий момент).
Интригующее вступление, но что-то мне подсказывает, что этого всего не достаточно, чтоб попасть в топ 50. Основные алгоритмы, которые гарантируют попадает в топ — это атака вражеских муравейников, защита своих, атака чужих муравьев, группирование своих муравьев, отступление при возможном поражении. У вас, действительно, это все не реализовано, или вы решили не раскрывать секретов?
явно реализовано только описанное, и «дежурные» муравьи для того чтобы не терять свой муравейник из вида. атака вражеских муравейников есть, это первое правило. групповой атаки в явном виде нет, но когда один из муравьев получает цель — вражеский муравейник, и ему на пути (в пределах видимости) встречаются враги, то соседние свои муравьи начинают «подтягиваться» (правило поддержки). отступление реализуется проверкой на «бессмысленность» смерти (в пункте о блокировках), но это даже не полноценное отступление, а выбор из всех возможных направлений того, которое имеет смысл, и не приводит к смерти.
это синтетический алгоритм, он и не должен быть очень сложным. и да, достаточно, более того, реализация без технических ошибок попала бы в двадцатку (в моей версии есть ошибки).
это синтетический алгоритм, он и не должен быть очень сложным. и да, достаточно, более того, реализация без технических ошибок попала бы в двадцатку (в моей версии есть ошибки).
А что вы подразумевает под «синтетический алгоритм», что-то википедия ничего не находит по этому поводу.
> и да, достаточно, более того, реализация без технических ошибок попала бы в двадцатку (в моей версии есть ошибки).
Вообще это удивительно, потому что, как я понимаю, ничего особенно гениального реализовано не было…
> и да, достаточно, более того, реализация без технических ошибок попала бы в двадцатку (в моей версии есть ошибки).
Вообще это удивительно, потому что, как я понимаю, ничего особенно гениального реализовано не было…
возможно не самое общеупотребительное выражение, но я имел в виду, что этот алгоритм не пытается эмулировать какое-либо человеко-подобное поведение, а просто решает задачу исходя из условия.
на самом деле это не так удивительно, если приглядеться к таблице лидеров, то только у первого десятка достаточно большое отличие skill, остальные идут «ровненько», то есть если и есть что-то «гениальное», то оно очень немногочисленно.
на самом деле я примерно представляю, что необходимо для создания действительно мощного алгоритма — расчет вероятности успеха для каждого действия, которая, конечно, зависит от возможных действий противника. скажем, вероятность ухватить еду, лежащую ближе к муравейнику противника менее вероятно, чем на нейтральной территории, но это все достаточно сложно формализуется. когда формализация заканчивается, начинаются подгонки, а по предыдущему контесту я уже понял что это тупиковый путь.
у меня было две версии бота, один с «подгонками», другой generic. первый почти всегда выигрывал у второго, но в финальных рейтингах их места отличались почти на сотню, generic версия лучше. подгонки в принципе существенно снижают вероятность выиграть у «черного ящика».
мое мнение — «гениальное» здесь может быть на уровне деталей реализации, а не на уровне стратегических особенностей.
на самом деле это не так удивительно, если приглядеться к таблице лидеров, то только у первого десятка достаточно большое отличие skill, остальные идут «ровненько», то есть если и есть что-то «гениальное», то оно очень немногочисленно.
на самом деле я примерно представляю, что необходимо для создания действительно мощного алгоритма — расчет вероятности успеха для каждого действия, которая, конечно, зависит от возможных действий противника. скажем, вероятность ухватить еду, лежащую ближе к муравейнику противника менее вероятно, чем на нейтральной территории, но это все достаточно сложно формализуется. когда формализация заканчивается, начинаются подгонки, а по предыдущему контесту я уже понял что это тупиковый путь.
у меня было две версии бота, один с «подгонками», другой generic. первый почти всегда выигрывал у второго, но в финальных рейтингах их места отличались почти на сотню, generic версия лучше. подгонки в принципе существенно снижают вероятность выиграть у «черного ящика».
мое мнение — «гениальное» здесь может быть на уровне деталей реализации, а не на уровне стратегических особенностей.
Я посмотрел ваши игры. Мне кажется, если улучшить алгоритм атаки и более активно атаковать муравейники, то вы можете значительно сильнее продвинуться. Мой текущий алгоритм не может защищать муравейник, зато более агресивно атакует чужой и старается атаковать муравьев с выигрышем (по крайней мере без проигрыша). Это позволяет выступать успешнее, хотя часто я проигрываю муравейник.
попробую пойти по другому пути — улучшил защиту и контроль территории, посмотрим как будет играть против реальных ботов (главное в реализации просто — два новых правила: не «размениваться» муравьями вообще, и при отсутствии своей цели муравьи сопровождают тех у кого есть цель). в большинстве случаев противник «гоняясь» за моими муравьями попадает в области, где моих муравьев больше чем его. но, конечно, против массового и целенаправленного «удара» это не спасает.
не хочу покидать предел в 1000 строк на программу =)
не хочу покидать предел в 1000 строк на программу =)
А можно поинтересоваться, под каким ником вы зарегистрированы в AI Challenge? Это для того, чтобы посмотреть игры, которые используют приведенный алгоритм. Очень интересно.
«Почему тогда вообще выбран такой алгоритм? Для начала надо заметить, что теоретически за меньшее число действий без какой-либо промежуточной информации путь и не проложить, по крайней мере можно сконструировать пример, обходящийся за O(cols*rows) шагов («спираль» во все поле). „
Во тут вы не правы. Алгоритм A* позволяет ускорить процесс расчета путей, однако длинные пути и ему не под силу, так что я использую что то похожее на вашу карту низкого разрешения + кэширование результатов.
А так все супер.
Огромное спасибо за статью!
Подчерпнул для себя пару интересных идей.
Во тут вы не правы. Алгоритм A* позволяет ускорить процесс расчета путей, однако длинные пути и ему не под силу, так что я использую что то похожее на вашу карту низкого разрешения + кэширование результатов.
А так все супер.
Огромное спасибо за статью!
Подчерпнул для себя пару интересных идей.
> так что я использую что то похожее на вашу карту низкого разрешения + кэширование результатов.
Тоже так делаю. Вы уже пробовали запускать своего бота на картах 256х256, я еще нет, но опасаюсь, что по памяти не выдержит.
Тоже так делаю. Вы уже пробовали запускать своего бота на картах 256х256, я еще нет, но опасаюсь, что по памяти не выдержит.
Ну, максимум какие карты будут — это 200 на 200.
Но сейчас, даже на более маленьких картах при определенном количестве муравьев он у меня начинает тормозить.
Но во-первых мне еще есть куда двигаться в сторону кэширования — пока у меня кэш не очень умный. И я думаю, что лимита в 1,5 Гб мне хватит.
А во-вторых, меня сейчас больше волнует идея разведки карты. Причем не с помощью поиска неизведанных клеток и затем поиска пути к ним, а с помощью построения карты с числами, по которой затем будут двигаться муравьи разведчики, просто выбирая меньшее число из тех, что рядом. Немного инфы есть тут
Называется это collaborative diffusion, и мне кажется топовые боты используют что то похожее.
Первые опыты показывают, что нагрузка на процессор снижается в разы.
Но сейчас, даже на более маленьких картах при определенном количестве муравьев он у меня начинает тормозить.
Но во-первых мне еще есть куда двигаться в сторону кэширования — пока у меня кэш не очень умный. И я думаю, что лимита в 1,5 Гб мне хватит.
А во-вторых, меня сейчас больше волнует идея разведки карты. Причем не с помощью поиска неизведанных клеток и затем поиска пути к ним, а с помощью построения карты с числами, по которой затем будут двигаться муравьи разведчики, просто выбирая меньшее число из тех, что рядом. Немного инфы есть тут
Называется это collaborative diffusion, и мне кажется топовые боты используют что то похожее.
Первые опыты показывают, что нагрузка на процессор снижается в разы.
Интересная идея, но смущает обновление каждой клетки карты на каждом ходе, да еще и с делением. А так для исследования карты реализовать очень удобно будет.
Посмотрел оригинал, benjamin-meyer.blogspot.com/2011/11/using-collaborative-diffusion-rather.html
в целом очень похоже, даже изначальное заполнение клеток тоже зависит от lastSeen — меньше операций поиска пути, зато больше вещественных операций с полем.
сложно сказать наверняка, но на глаз видно что топовые боты лучше организуют контроль (и защиту) территорий, расставляя «часовых» в «узких» местах. если сравнивать качество обхода карты, то за равное время они собирают не большее количество еды, чем при описанном в моей заметке обходе — хотя, это и не критерий, но это то что легко может видеть человек.
в целом очень похоже, даже изначальное заполнение клеток тоже зависит от lastSeen — меньше операций поиска пути, зато больше вещественных операций с полем.
сложно сказать наверняка, но на глаз видно что топовые боты лучше организуют контроль (и защиту) территорий, расставляя «часовых» в «узких» местах. если сравнивать качество обхода карты, то за равное время они собирают не большее количество еды, чем при описанном в моей заметке обходе — хотя, это и не критерий, но это то что легко может видеть человек.
У вас есть какие-либо идеи по тому, как выявлять эти самые узкие места?
идеи — конечно! на практике версия с «часовыми» играла хуже против «слабых» игроков. интересная особенность, что некоторые игроки принципиально не хотят размениваться муравьями, за счет этого, расставив «часовых» по контуру области мы почти гарантируем что никто туда не войдет. а вот некоторые даже не запаривались с battle resolution.
алгоритмически определить узкие места тривиально — это те точки, которые не являются водой, однако в направлении слева-справа или сверху-снизу есть близкие точки с водой. близость (то есть сколько именно клеток нужно просматривать) определяется исходя из среднего расстояния от клетки до ближайшей клетки с водой (т.е. зависит от карты).
сколько именно туда ставить муравьев, пока никак не формализовано.
алгоритмически определить узкие места тривиально — это те точки, которые не являются водой, однако в направлении слева-справа или сверху-снизу есть близкие точки с водой. близость (то есть сколько именно клеток нужно просматривать) определяется исходя из среднего расстояния от клетки до ближайшей клетки с водой (т.е. зависит от карты).
сколько именно туда ставить муравьев, пока никак не формализовано.
Вы предлагаете для каждой точки карты устраивать такой тест? Дороговато будет
очень большой запас производительности (по крайней мере для C++), но после проверки этой идей я от нее отказался. смысла маловато — вместо потенциального нахождения еды муравьи ждут противника, который возможно и не пройдет через «ловушку». эффективнее «размазывать» врагов по стенке, когда возможного отхода у них нет, а не ждать.
Получается писать на языке, отличном от C++ — заведомый проигрыш?
Посмотрите на каком языке пишет лидер.
я бы сказал, что писать синтетические алгоритмы на языке, отличном от С++ — уже заведомый проигрыш. Но кроме синтетических, есть еще и конструктивные алгоритмы, в которых описано большее количество человеко-понимаемых правил, а перебора по сути меньше, вот в таких случаях С++ не так удобен.
Хотел бы подкорректировать пару вещей, которые подробно обсуждались на родном для игры форуме.
Причина не в этом, так как, во-первых, разумно предположить, что новая версия всё-таки лучше старой, а, во-вторых, если версия и хуже, она просто скатится вниз.
Необнуление же skill повзволило бы новой версии сразу соревноваться с равными по уровню ботами, а не ждать этого 3-5 дней.
Так вот, организаторы называют такую причину. Если skill не сбрасывать, то новая версия бота автоматически «проскочит» средненьких ботов. Но может оказаться, что ваш бот хорошо играет против классных ботов, и хреново — против средненьких. У вас же нет шанса встретиться со средними ботами, если не обнулять skill.
И вот, наступает время сосбственно соревнования — 18 декабря, когда skill обнулится у всех. Тут-то и окажется, что ваш бот не может пройти средних ботов, чтобы соревноваться с сильными. Облом.
Организаторы говорят, что в предыдущем соревнованиии были именно такие ситуации.
Не совсем понимаю, что вы подразумеваете под проблемами из-за буферизации ввода-вывода, поэтому расскажу о причинах забавных штук, которые выяснили на оф. форуме. Их две:
1) В стартовом пакете java для чтения входных данных использовался Scanner. Его замена на StringTokenizer практически полностью устраняла проблему, буквально на порядок увеличивая скорость чтения.
2) Ошибка в начале отсчёта времени хода. Время следует отсчитывать не от команды «go» от сервера, а от первой переданной в начале хода строки.
3) Похоже, изредка сами сервера испытывают проблемы с производительностью.
Совокупность первых двух проблем часто приводила к таймауту java-ботов на первом же ходу на картах с несколькими муравейниками у каждого, т.к. на первом ходу передавалось слишком много строк с водой.
Если что, спрашивайте :)
>>цифра Skill является относительной величиной, и после каждой загрузки версии на сервер сбрасывается в ноль (т.к. не известно, будет ли новая версия лучше предыдущей).
Причина не в этом, так как, во-первых, разумно предположить, что новая версия всё-таки лучше старой, а, во-вторых, если версия и хуже, она просто скатится вниз.
Необнуление же skill повзволило бы новой версии сразу соревноваться с равными по уровню ботами, а не ждать этого 3-5 дней.
Так вот, организаторы называют такую причину. Если skill не сбрасывать, то новая версия бота автоматически «проскочит» средненьких ботов. Но может оказаться, что ваш бот хорошо играет против классных ботов, и хреново — против средненьких. У вас же нет шанса встретиться со средними ботами, если не обнулять skill.
И вот, наступает время сосбственно соревнования — 18 декабря, когда skill обнулится у всех. Тут-то и окажется, что ваш бот не может пройти средних ботов, чтобы соревноваться с сильными. Облом.
Организаторы говорят, что в предыдущем соревнованиии были именно такие ситуации.
>>Однако крайне желательно завершить выполнение алгоритма быстрее этого порога хотя бы на 50 мс, иначе велика вероятность получить timeout из-за буферизации ввода-вывода (вся передача игровых данных ведется через pipes), а то иногда получаются забавные штуки
Не совсем понимаю, что вы подразумеваете под проблемами из-за буферизации ввода-вывода, поэтому расскажу о причинах забавных штук, которые выяснили на оф. форуме. Их две:
1) В стартовом пакете java для чтения входных данных использовался Scanner. Его замена на StringTokenizer практически полностью устраняла проблему, буквально на порядок увеличивая скорость чтения.
2) Ошибка в начале отсчёта времени хода. Время следует отсчитывать не от команды «go» от сервера, а от первой переданной в начале хода строки.
3) Похоже, изредка сами сервера испытывают проблемы с производительностью.
Совокупность первых двух проблем часто приводила к таймауту java-ботов на первом же ходу на картах с несколькими муравейниками у каждого, т.к. на первом ходу передавалось слишком много строк с водой.
Если что, спрашивайте :)
>> Итого 200^2*1000*100, это 4 миллиарда итераций, по большей части записи в память.
А зачем для каждой пары (муравей, цель) запускать отдельный поиск в ширину? Можно просто запустить поиск в ширину от каждого муравья, после чего мы получим кратчайшие пути до каждой клетки поля (в том числе и до всех целей). В итоге получится около 40 млн. операций, что уже в 500мс укладывается.
А зачем для каждой пары (муравей, цель) запускать отдельный поиск в ширину? Можно просто запустить поиск в ширину от каждого муравья, после чего мы получим кратчайшие пути до каждой клетки поля (в том числе и до всех целей). В итоге получится около 40 млн. операций, что уже в 500мс укладывается.
Есть еще вариант поиграть своим боттом на не оффициальных серверах — www.tcpants.com/howto
Лучше на этом — там намного больше активных ботов.
ants.fluxid.pl/howto
ants.fluxid.pl/howto
спасибо
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
AI Challenge: Ants AI Challenge: оживляем «муравьев»