Очередной конкурс играющих программ проводится на нашем сайте с 11 марта по 31 марта (включительно). Информация о конкурсе тут. Регистрироваться на контест можно здесь.
Для тех, кто соберётся участвовать в первый раз (да и в целом для порядка), я написал небольшой manual, вот здесь.
Контест начался, информацию об ходе контеста и материалы к нему (условие задачи, комплект для локального запуска, визуализатор), можено скачать здесь. Текущие результаты можно смотреть здесь.
Контест завершился, всем большое спасибо за участие.
Финальные результаты конкурса доступны тут. Задача добавлена в архив игровых задач, интересующиеся могут подорешивать её и задачи с прошлых конкурсов.
Опертивно контест состряпал :) Здорово, надеюсь будет время поучаствовать!
Вопрос снят, прошу прощения за беспокойство.
Как-то у вас не всё логично на сайте... Киньте что-ли ссылку со страницы http://acm.petrsu.ru/site/article/608 туда где можно зарегаться и войти в соревнование, чтобы сдавать задачи.
Добавил, спасибо
А экзешники player1, player2 это скомпилированный sample.cpp или что-то другое?
Именно они
В очередной раз на конкурсе для программистов сайт подразуметвает, что программист использует windows -- на ссылке для скачивания даже не указано для какой ОС скомпилированы лежание в ней бинарники (хотя, конечно, можно догадаться по расширению)
Ага, ещё в прошлый раз немного опечалило отсутствие комплекта для других ОС. Пожелание ftc — может, лучше делать комплект для локального запуска на чём-нибудь кроссплатформенном, например, на java?
Можно наверное и так, правда не очень понятно, как без использования некроссплатформенных библиотек мерять время и память, использованные процессом.
Подразумевается, что программист необязательно использует windows, но может запустить бинарник, скомпилированный для неё :-)
А вообще написать аналог под linux я уже давно хочу, но всё руки не доходят. Как только — так сразу
а есть ли ограничения на размер заливаемого решения?
Да, максимальный размер файла — 1МБ
Что-то никак не пойму из условия — "Тогда с вероятностью a/(a+b) погибает один из жуков второго игрока, а с вероятностью b/(a+b) погибает один из жуков первого" — эти события независимые? Или взаимоисключающие? Т.е. если a = b = 1, то с вероятностью 1/4 умрут все жуки, или с вероятностью 1/2 останется только первый, а с вероятностью 1/2 — только второй?
Это взаимоисключающие события. То есть если a=b=1, то с вероятностью 1/2 останется только первый и с вероятностью 1/2 — только второй.
Если же жуков несколько, то после гибели одного, этот процесс продолжается, пока в клетке не останутся жуки только одного игрока
Ещё вопрос — из условия следует, что обязательно надо отдать приказ каждому жуку; из "формата выходного файла" — что необязательно: "Перед обработкой приказов будет проверено, что в каждой клетке (ip; jp) жуков не меньше, чем сумма количеств жуков во всех приказах, исходящих из этой клетки", т.е. больше может быть. Как правильно?
Некоторые жуки могут остаться без приказов. В таком случае они не двигаются.
Условие поправлю.
А что, если для какой-то клетки команд будет отдано больше, чем в ней есть жуков, как поведёт себя система?
Проигнорирует все команды, отданные из этой клетки (это поведение описано в формате вывода в условии)
Что-то участников совсем мало...4 ( Присоединяйтесь, предложенная игра реально интересна с точки зрения написания AI для нее!
Начальная расстановка фиксированная или случайная?
Карты фиксированные. Три штуки, все можно посмотреть, меняя в конфиге game_run.cfg параметр GameNumber соответственно на "1", "2" и "3"
Посмотрите что случилось с парой 107466. У чекера IL.
UPD Еще IL : 107480,107481
Проблему локализовал, работаю, спасибо.
Недавно была проблема с Idleness Limit exceeded у чекера. Она поправлена.
Напоминаю, что Ваше решение должно читать ходы в бесконечном цикле, а не работать по принципу "прочитал ввод, что-то поделал, написал ходы, вышел". Это отражено в частности здесь.
Что-то народ неактивно участвует :-(
ИМХО, народ бы участвовал намного активнее, если хотя бы за первые три места(или первое) давались какие-нибудь мелкие призы(майки, кружки......)
Понятное дело. Надо будет над чем-нибудь подобным подумать
Какие-то уникальные майки замутить — и народу будет более чем достаточно.
Кстати, с кружками идея не ахти в том плане, что суровая почтовая система вечно добивается того, что их присылают битыми (2 раза был такой опыт уже).
В последнее время много других контестов, да и может в универе завал.. госы через 3 недели, а там диплом...
(Под Linux) Программа для проверки ваших ботов. Сырая. Проверка на затрачиваемую память не производится. Только Time Limit в 1 секунду на ход. http://code.google.com/p/war-bug-emulator/
В папке trunc/src readme.txt
Соревнование закончилось, хотел поблагодарить ftc за организацию всего этого веселья ) Может, и были какие-то технические проблемы, но их удавалось преодолеть. Надеюсь на проведение других турниров стратегий
Контест завершился.
В первую очередь, хочется поблагодарить ftc за организацию очень интересного конкурса! Лично я был бы очень рад, если традиция проведения таких соревнований продолжится :)
Жаль, что так мало народу (всего семь человек) приняли участие в контесте. Поэтому хотелось бы призвать остальных принимать участие в подобных мероприятиях. Да, это требует немалого времени, как на обдумывание, так и на реализацию, но сам процесс не менее интересен (и, я думаю, не менее полезен), чем решение олимпиадных задач. Если у вас иногда появляется свободное время, а вы тратите его сугубо на олимпиадный кодинг, не гнушайтесь иногда внести разнообразие в предмет, на который направлены ваши усилия! Кроме того, чем больше людей примут участие в соревновании, тем больше разных стратегий будет предложено, тем больше обострится борьба в таблице.
К тем, кто всё же участвовал: поделитесь, пожалуйста, вашими идеями, соображениями, стратегиями.
Собственно, мой ответ на мой же вопрос, если кого-нибудь заинтересует, что писал я:
Идея №1. Для каждой группы наших юнитов жадно будем выбирать, куда пойти. Для этого вначале запретим посещать те клетки, в которых стоят более сильные враги, и те, где на следующем ходе противника его юнитов может стать меньше, чем наших. А теперь запустим bfs и найдём ближайшую к нашей клетку, на которой находится либо нейтральное гнездо, либо группа врагов с меньшей численностью, чем текущая наша.
Идея №2. Если нейтральных гнёзд не осталось, посчитаем, сколько очков наберёт каждый игрок к концу игры, в предположении, что гнёзда так и останутся у того, кто ими сейчас владеет. Если мы набираем больше очков, то отправим всех юнитов, находящихся не на гнёздах, оборонять их.
Идея №3. Будем оценивать каждый ход юнита в каждую из доступных клеток. Для этого заведём вещественные коэффициенты: первый будет соответствовать ходу в наше гнездо, второй — ходу в нейтральное, третий — во вражеское, четвёртый — нападению на более слабого врага. У меня ещё был пятый, соответствующий вероятности нападения более сильного врага в этой клетке, но сейчас мне кажется, что это было лишним, поэтому в подробности углубляться не буду. Для каждой достижимой (изначально запретив часть клеткок: см. идею №1) клетки, в которой что-нибудь/кто-нибудь есть, посчитаем значение функции как произведение соответствующего коэффициента на величину, обратную расстоянию до этой клетки из текущего положения. Выберем цель с наибольшим значением функции, восстановим путь до неё и сделаем ход вдоль этого пути. Задача свелась к подбору коэффициентов. Приходят в голову два подхода: нейросеть (которую можно было бы обучать, играя с алгоритмами, основанными на предыдущих идеях) или генетический алгоритм. Я выбрал второй вариант просто потому, что мне ещё с июля (с прекрасного спецкурса Romka, посвящённого генетическим алгоритмам, в ЛКШ) хотелось реализовать что-нибудь подобное, да задачи подходящей не попадалось, а идеи в голову не приходили. Когда я начинал писать, я явно не рассчитывал на то, что игры происходят долго. Поэтому всего при 10 особях в поколении и турнире по круговой системе между ними, в котором каждый с каждым проводит по 6 поединков (3 карты * 2 "цвета"), мне удалось за три дня запуска программы на 10-12 часов дойти только лишь до 13-го поколения. Существенного улучшения это не принесло и лишь в комбинации с двумя предыдущими идеями чуть-чуть увеличило количество очков. Тем не менее, оно того стоило: во-первых, понравился сам процесс написания (в минувшую субботу), во-вторых, было забавно, приходя домой вечером, разглядывать результаты турниров — таблички в формате html, которые служили логом работы генетического алгоритма.
Понятно, что всё это можно и нужно было бы улучшать и улучшать. Как минимум, я нигде не использую возможность разбить группу, находящуюся в одной клетке, а, наверняка, это может принести свои дивиденды, понять бы только, как и когда разбивать. Кроме того, я никак не учитываю действия противника и оцениваю то, где его юниты могут оказаться, только на один ход вперёд.
Резюмируя, хочется ещё раз сказать СПАСИБО за такую замечательную задачу, при написании решения которой появляется столь большое количество идей!
Тут можно подорешивать. Там еще есть интересные задачи.
Спасибо за ссылку! Обязательно попробую свои силы и в других конкурсах.
У меня всё проще, по сути я скомбинировал несколько несложных эвристик: 1) Вначале смотрим, до каких ульев успеваем раньше противника, и посылаем туда по 1 жуку 2) Если рядом есть наш улей и вокруг него противников больше, то идет к нему для зашиты 3) Если по плану нам следующим ходом нужно атаковать улей, а там в const раз больше жуков, чем нас, то не делаем этого 4) Сбор в 1 точке. Если вокруг много противников, и есть несколько отрядов наших, то группируем их в 1 точке 5) Если все хитрые планы использованы, а у нашего отряда жуков остался ход, то идем им к одному из ближайших не наших ульев Может, что-то забыл, так как код был написан уже давно
я сдал программу перед закрытием. будет ли она принята?
Да, будет конечно.