Russian AI Cup

Расширенный поиск  
Страницы: 1 [2] 3

Автор Тема: Здесь шарим свои наработки после окончания песочницы!  (Прочитано 24425 раз)

olexiyo

  • Newbie
  • *
  • Сообщений: 21

Эх, собирался я написать здоровенную статью как в прошлом году, и выложить на хабр, да так толком и не собрался =(
Кароч вот код
https://github.com/Hohol/HoholTroopers

Я посмотрел одним глазом код, в истории коммитов там куча-куча небольших изменений. А Вы не помните какие именно фичи давали наибольший прирост в рейтинге?
Записан

Hohol

  • Full Member
  • ***
  • Сообщений: 101

В порядке появления. Фичи разного размера и важности, просто которые мне запомнились.
-ходить кучей
-изменять стойку для нанесения большего дамага
-перебор всех действий одного юнита в бою со сложной оценкой финальной позиции (ну это, разумеется, постепенно улучшалось на всем протяжении)
-ЮНИТ ТЕСТЫ для предыдущего
-не блочить путь тиммейтам в драке (особенно важно было на карте cheeser)
-находить, какой дамаг может нанести нам враг. При этом предполагается, что враг действует максимально просто, чтобы не расширять дерево перебора. Максимизировать величину "нанесенный нами дамаг минус нанесенный врагом дамаг".
-запоминать положение врага, предполагать, что отошел недалеко, если исчез. Стрелять в туман, делать выводы по изменению очков.
-уменьшать предполагаемый нанесенный врагом нашему юниту дамаг, если сейчас враг этого юнита не видит
-разведка - и в драке, и без драки стараться увидеть как можно больше клеток. Клетки, как у мегабайта, трехмерные. Клетки близкие к врагу более ценны.
-учитывать порядок ходов. Считать, что юнит А врага не может продамажить нашего юнита Б, если Б точно будет ходить раньше А (при этом я не пытаюсь определить, какой из двух (для финального режима) возможных вариантов порядка ходов правилен, а выбираю худший для меня)
-предполагать, что у врага где-то есть снайпер и бояться его
-если стреляем в туман, предпочитать стрелять в того, который точно не ходил с тех пор как его последний раз видели
-располагаться так, чтобы врагу было как можно сложнее избежать нашего выстрела (актуально для снайпера - он всегда либо делает один выстрел, либо долго бегает, выбирая позицию)
-если ходящего юнита в любом случае могут убить, убежать в такое место, чтобы враг мог увидеть его лишь сделав как можно больше шагов (без этого он у меня отчаянно бежал в атаку)
-предполагать, что у врага где-то есть ВСЯ тима и бояться ее
-по нанесенному дамагу определять, откуда он был нанесен. При этом делать различные выводы по величине дамага (дамаг медика делится на три, дамаг от гранаты равен 60 или 80, и тому подобное). Все равно довольно часто не угадывают, но это все же намного лучше, чем ничего.
-ВНЕЗАПНО в самый последний день - двигаться всей командой к бонусам, а не просто подбирать те, мимо которых проходили
Записан

Megabyte

  • Jr. Member
  • **
  • Сообщений: 27

На счет бонусов. Тоже добавил это в последние дни. Шел только к нужным бонусам, включая те, про которые знаем за счет зеркализации уровня.
Много с этим пропарился. Случались ситуации, когда труперы перекрывали бонус тому, кому он нужен, и команда топталась до бесконечности на месте. Пришлось долго отлаживать код, защищающий от таких блокировок.
Записан

access_denied

  • Sr. Member
  • ****
  • Сообщений: 282

На счет бонусов. Тоже добавил это в последние дни. Шел только к нужным бонусам, включая те, про которые знаем за счет зеркализации уровня.
Много с этим пропарился. Случались ситуации, когда труперы перекрывали бонус тому, кому он нужен, и команда топталась до бесконечности на месте. Пришлось долго отлаживать код, защищающий от таких блокировок.
Тысяча чертей! Еще одна идея, которая не пришла в мою голову :-) Совершенно не использовал симметрию уровня в отношении обнаружения бонусов, а ведь можно было сбегать при необходимости, знал бы, куда.
Записан

pivizz

  • Newbie
  • *
  • Сообщений: 4

Вот моя последняя версия: http://yadi.sk/d/2WiV1WT9ET5Ae (версия 42 - с ней шел в финал и в итоге с ней же завершал песочницу, правда уже под другим номером). Код получился ужасный, но уж какой есть =). По скорости оптимизировал только узкие места, которые показывал профайлер.

У меня, видимо, все получилось похоже на большинство остальных стратегий из топа:

  • Каждый боец просчитывает только свой текущий ход до конца
  • В начале игры подсчитываются некоторые полезные вещи, такие как наименьшее расстояние между любыми двумя парами клеток
  • Перед обсчетом каждого хода смотрим что есть вокруг и записываем сведения об окружающем мире. Самое главное - бойцы противника и клетки, которые видят мои бойцы и где противника нет. Для каждого вражьего бойца сохраняется каждая встреча с ним: на каком ходу какой мой боец его видел, что тот держал в руке, сколько хитпоинтов было и т.п.
  • Просчитывается очередность ходов и определяется мог ли сдвинуться с места тот или иной боец противника.
  • Если есть хотя бы один боец противника, про которого известно либо точное положение, либо что он могу сделать не более 1 хода с того положения, в котором мои бойцы его видели, то все такие противники объявляются потенциальными мишенями и при просчета хода используется режим атаки.
  • При просчете хода учитывается какие клетки окажутся видимыми, нанесем ли мы урон противнику, полечимся ли, подберем ли бонусы, выставимся ли сильно перед предполагаемым противником или нет.
  • Алгоритм передвижения в неатакующем режиме мне самому не очень нравится, но лучше сделать не получилось. Мои бойцы смотрят кто остался в живых и выбиряют себе лидера (если есть разведчик, то он лидер, если нет разведчика, то командир, потом медик, потом солдат, наконец если жив только снайпер, то он сам себе лидер). Лидер старается открывать побольше клеток, которые мы не видели раньше и приближаться к "цели" - случайно выбранной точке на карте. Остальные бойцы хотят не отставать от лидера сильно. В случае если настоящий лидер слишком далеко, боец может выбрать лидером близкого к нему бойца "старше по званию". Еще бойцы стараются не запирать командира по возможности.
Записан

santa324

  • Full Member
  • ***
  • Сообщений: 142

А я очень старался от всех этих эвристик избавиться, у меня и правда по сравнению с тем что тут описывают эвристик очень мало. Но не довел до ума...
Записан

santa324

  • Full Member
  • ***
  • Сообщений: 142

А я очень старался от всех этих эвристик избавиться, у меня и правда по сравнению с тем что тут описывают эвристик мало. Но не довел до ума...
Записан

oparin

  • Full Member
  • ***
  • Сообщений: 59

У меня делиться нечем. Занял 500+ место и это был мой дебют в java, что какбэ намекает на качество кода, но могу поведать ход мыслей:
1. Определяем лидера (по еще живым в порядке приоритета)
2. Если это лидер и у него нет маршрута - строит маршрут по часовой стрелке (в угол)
3. Лидер делает не более 5 ходов (чтобы кучкой ходить)
4. Остальные строят оптимальный маршрут к лидеру с приоритетом точек - доктор напр. старается встать сзади)
5. Если у кого-то здоровье меньше 100% - идти к нему на помощь и занимать точки в порядке приоритета.
6. Действия в порядке приоритетов: Гранату, Стрелять, Идти на помощь, Лечиться, Ждать помощи, Следовать по маршруту. (у доктора приоритет №1 - Лечить)
Это костяк. Потом дописывал еще всякое, что породило только глюков:
Напр.: уходить от обстрела, если остался один ход и есть клетка на расстоянии одного хода в которую враг не может стрелять - отходить.
Записан

CyberWo1f

  • Full Member
  • ***
  • Сообщений: 105

У меня тоже был дебют, только на python. Посмотрел быстрый старт на него и давай ваять стратегию.
А я с одной и той же стратегией болтался от 220 до 400 места =) Сейчас на ~300 месте.
Начинал я с простой стратегии, которую предлагали в быстром старте, т.е. идти в центр и стрелять =)
Тогда было много пустышек, поэтому я даже немного поднялся, мешалась только карта, где труперы начинают за ограждениями =)
Потом прикрутил Алгоритм Ли для поиска пути (Не знаю почему, но он мне показался проще, хотя наверно почти все использовали алгоритм a*)
А траекторию выбрал простую - движение по углам, но с промежуточными точками, которые ближе к центру (например начинаем в {1, 1}, затем идем в {7, 10}, затем в {1, 19}, ну и так далее). Причем каждый бой направление было разное. Где бы ни начинали, сначала идем в противоположный по вертикали угол. НУ и потом дальше по ходу. Этим я добился того, что достигал самой ближней точки респауна врагов.
Потом прикрутил сбор бонусов и лечение, бросок гранаты. После первого раунда для броска гранаты выбирал клетку с максимальным дамагом (сначала вообще кидал просто так =), хоть и глупо, зато позволяло поначалу получать преимущество над соперниками моего уровня на карте Чизера, где я бросал через стены =))

Ну потом сделал лидерство (командир, медик, разведчик, пулеметчик, снайпер)
потом сделал так, чтобы лидер не тратил все ходы на передвижение, и не убегал от группы.

По сути, больше ничего у меня и не было. Что не помешало мне достигнуть апогея в лице 220 места =) Хоть это и мало, но футболку я все таки получу =)

Не сделал: Кайтинг(ну тоесть стрельба - прятки), прятанье за препятствиями(хотя нет - вру, сделал приседание у солдата, если он не рядом с командиром, т.к. в этом случае у него после 2 выстрелов оставалось 2 очка действия), приоритет врагов (тоесть стрелял во всех подряд), Просчет ходов своих, запоминание порядка ходов и вычисление невидимых врагов, которые не могли никуда уйти ну и так далее =)
Записан

amurushkin

  • Sr. Member
  • ****
  • Сообщений: 189

Удивительно то, что моя стратегия на словах делает то же самое что и у лидеров фактически, но только на словах ))) В реализации все нюансы проявляются
Записан

acherednychenko

  • Newbie
  • *
  • Сообщений: 14

моя самая большая проблема - отсутствие тестов. решение к концу второго раунда стало очень сложным и неуправляемым - прототипы новых фич реализовывались быстро и часто коряво. Рефакторинг был редкостью. В итоге включение\выключение одной фичи производилось в нескольких местах. чтото можно было забыть на этапе прототипов.

Главный вывод - код писать в след раз так же как и на работе - с юнит и интеграционными тестами и рефакторингом когда надо.

Перед всеми не попавшими в ловушку сложности решения снимаю шляпу.
Записан

darkstone

  • Jr. Member
  • **
  • Сообщений: 22

1 раунд 440, максимальное место 135+ (ночью достиг и свалился, на утро было 140  :) ) к закрытию 199, но тут даже не перезаливал ошибочные, поэтому свалился.
Код тут: https://github.com/darksotnea/RussianAICup2013.git

Всё было очень быстро, так как хоть и проводился чемпионат месяц, к сожалению времени было только вечером и в выходные. Начал только где-то за 5 дней до начала раунда.

К сожалению, про тестирование подумал поздно, хотя львиную долю времени как раз убил на поиск и исправление ошибок в коде после обновлений.
Причём Repeater стал использовать почему-то только после 1 раунда..

Спасибо организаторам за localrunner, так как кто-то умеет его сделать со своими картами и стратегиями, а кто-то нет.. Так было бы ещё больше преимущество у имеющих.

Реализовано:
-Обновление глобальных целей по углам, в начале глобальная точка в центре (шёл медленно, так что боёв когда между нескольких врагов не так много), использование локальный целей (последний видимый противник).
-Использование абилки командора.
-Командир и разведчик идут первыми, за ними солдат, снайпер и медик.
-При отсутствии перестрелки во время хода, используются ограничения по радиусу от некоторых юнитов, чтобы не разбегались.
-Поиск кратчайшего пути (волновой алгоритм, lee, с учётом труперов и без).
-Медик привязан изначально к снайперу.
-Атака и отбегание из видимости юнита или из радиуса досягаемости, если нет возможности уйти из радиуса видимости.
-Стрельба по ранее видимым целям.
-Использование гранат , нахождение лучшей точки с максимальным кол-вом повреждаемых юнитов с учётом AP и проверка имеет ли смысл бросать гранату.
-Передвижение с использованием карты опасности, использование по возможности безопасных мест.
-Реагирование на падение стратегии оппонента.
-Хиляние медиком (когда, кого и т. п.)
-Уход из битвы при значительном повреждении.
-Обранужение атаки из "ниоткуда", только что не успел добавить реакцию на это поэтому после такой атаки юниты просто игнорируют её и бегут дальше.
-Подбор бонусов в мирное время
-Использование бонусов: лечение, расчёт броска гранаты с учётом FIELD_RATION и т. п.
-Понижение и повышение положения юнита для лучшей стрельбы. Для скрытия от врага сделать не успел, хотя вещь очень и очень полезная.
-Обход своих стоящих юнитов
-Учёт действий юнитов от кол-ва юнитов соперника при атаке. Тут тоже ещё много идей, широкое поле для улучшения.
-Выбор целей для атаки исходя из дистанции, статуса юнита (разведчик, командир, снайпер и т. д.), его здоровья.

Многое чего хотел переделать, что-то переписал заново, что-то так и не решил делать из-за лимита времени, например переписать код отвечающий за ходилку в нормальный вид. Тест шёл в ручную, начальный в локалранере, дальнейшее после заливки на сервер.

Много времени потрачено на реализацию нормальной "ходилки-бродилки". Сначала при начале боя юниты ложились или садились и стрелялись. Потом посмотрев на Alchemist и Hohol понял, что убегать тоже надо и только кайтить тоже мало. После того как вообще потонул в дебрях кода первой бродилки, заново переписал её с учётом кайтинга правда сейчас она опять страшная какая-то стала :)).
Очень вовремя познакомился с работой изменчивости рейтинга. Перед вторым раундом находясь в районе 380 места (а к 300 уже прошедших добавлялись 60 с песочницы, то есть нужно было быть примерно в первых 340-355, так как новых игроков примкнуло не так уж много, разница в очках между 340 и мной была что-то около ~70 очков) и залив доделанную стратегию и протестив её неплохо, заметил, что она занимает 1-2 места в ~70-80% случаев и зная, что за 1-2 места обычно дают в плюс решил не ждать обычных боёв, а ускорить процесс чтобы побыстрее вылезти вверх. В первом же бое занял 2 место и получил -200. Понял что 2 раунд уже будет без меня  >:(
« Последнее редактирование: Декабря 17, 2013, 04:40:24 pm от darkstone »
Записан

darkstone

  • Jr. Member
  • **
  • Сообщений: 22

Цитировать
Много с этим пропарился. Случались ситуации, когда труперы перекрывали бонус тому, кому он нужен, и команда топталась до бесконечности на месте. Пришлось долго отлаживать код, защищающий от таких блокировок.
Хм, а я просто не шёл к бонусу, если на нём кто-то стоял. А когда пехотинец с него убегал, тут то и подбирался он. :)Затыков не было, правда и кому нужно брать тоже не рассматривал, брал тот, кто доходил в свой текущий ход. Какие-то пропускались, но в основном разбирались все бонусы.
Записан

acherednychenko

  • Newbie
  • *
  • Сообщений: 14

Цитировать
Много с этим пропарился. Случались ситуации, когда труперы перекрывали бонус тому, кому он нужен, и команда топталась до бесконечности на месте. Пришлось долго отлаживать код, защищающий от таких блокировок.
Хм, а я просто не шёл к бонусу, если на нём кто-то стоял. А когда пехотинец с него убегал, тут то и подбирался он. :)Затыков не было, правда и кому нужно брать тоже не рассматривал, брал тот, кто доходил в свой текущий ход. Какие-то пропускались, но в основном разбирались все бонусы.
я при расстоянии лидера к бонусу меньше 2 сменял цель на следующий бонус. ктото обязательно подбирал. шел к бонусу конечно только если он был нужен
Записан

Megabyte

  • Jr. Member
  • **
  • Сообщений: 27

На открытах картах проблем с затыком на бонусах небыло. Проблемы были только тогда, когда бонус лежал в узком корридоре, где при всем желании, с бонуса не уйдешь, если впереди и позади стоят чуваки которым этот бонус нужен : )
Записан

noop

  • Full Member
  • ***
  • Сообщений: 73

Запланировал код с зеркальными бонусами с самого начала, но подключил лишь к финалу, и то кое-как. Собственно, это только в финале и имело смысл, т.к. там всегда было 2 угла с неразобранными бонусами. Бойцы умели убегать за аптечками, если знали, где они еще остались, но я даже толком не протестировал эту фичу. Проблему блокирования своими попросту проигнорировал - не до того было.
Записан

acherednychenko

  • Newbie
  • *
  • Сообщений: 14

я боролся с блокированием симуляцией хода остальных юнитов из каждого просчитываемого конечного состояния. симуляция - поиск наилучшего состояния с ограничением по глубине для каждого юнита в порядке очереди хода. собственно и симуляция деятельности противника делалась так же, но с очень простой оценочной функцией
Записан

noop

  • Full Member
  • ***
  • Сообщений: 73

я боролся с блокированием симуляцией хода остальных юнитов из каждого просчитываемого конечного состояния. симуляция - поиск наилучшего состояния с ограничением по глубине для каждого юнита в порядке очереди хода. собственно и симуляция деятельности противника делалась так же, но с очень простой оценочной функцией
У меня был запланирован перебор за второго юнита, с запоминанием возможных координат ходов и маски выстрелов по врагам, благо что скорости, благодаря оптимизации кода, хватало с запасом. Но не сделал к финалу, а для песочницы было уже просто лень. За врагов у меня, как и у многих, кэшировался возможный урон в разные клетки, но, как теперь понимаю, стоило сделать его вычисление посложнее того, что написал еще до 2-го раунда.

На открытах картах проблем с затыком на бонусах небыло. Проблемы были только тогда, когда бонус лежал в узком корридоре, где при всем желании, с бонуса не уйдешь, если впереди и позади стоят чуваки которым этот бонус нужен : )
У меня на бонусы стоял вес намного больше штрафов за убегание от группы или попадание в неисследованные клетки, поэтому мои бойцы, у которых бонусов не было, отрывались от команды и бежали за ними в одиночку. Где их временами могли убить даже смартгаи :)
« Последнее редактирование: Декабря 17, 2013, 08:19:08 pm от noop »
Записан

darkstone

  • Jr. Member
  • **
  • Сообщений: 22

А с какими вообще сложностями значимыми для себя или на которые убили много времени вы сталкивались?
Я вот с "ходилкой" влип) или вместе не держались, или держались но разбредались и затык находили.
Записан

acherednychenko

  • Newbie
  • *
  • Сообщений: 14

я боролся с блокированием симуляцией хода остальных юнитов из каждого просчитываемого конечного состояния. симуляция - поиск наилучшего состояния с ограничением по глубине для каждого юнита в порядке очереди хода. собственно и симуляция деятельности противника делалась так же, но с очень простой оценочной функцией
У меня был запланирован перебор за второго юнита, с запоминанием возможных координат ходов и маски выстрелов по врагам, благо что скорости, благодаря оптимизации кода, хватало с запасом. Но не сделал к финалу, а для песочницы было уже просто лень. За врагов у меня, как и у многих, кэшировался возможный урон в разные клетки, но, как теперь понимаю, стоило сделать его вычисление посложнее того, что написал еще до 2-го раунда.

у меня скорости как правило хватало чтобы просчитать ходы\смену стоек 5 юнитов соперника на глубину 3 и стрельба\граната до конца экшнпойнтов. это для каждого возможного листа дерева текущего юнита (конечного состояния). знаю как еще значительно улучшить.

планирую для експериментов с reinforcement learning многое переписать и сделать конфетку )
Записан

noop

  • Full Member
  • ***
  • Сообщений: 73

А с какими вообще сложностями значимыми для себя или на которые убили много времени вы сталкивались?
Я вот с "ходилкой" влип) или вместе не держались, или держались но разбредались и затык находили.
Если использовать манхэттенское расстояние до центра, определенного через то же манхэттенское расстояние, проблем вроде не должно быть, и не было. Хотя я запямятовал, у меня была специальная заливка, штрафующая не за расстояние до центра всей группы, а за расстояние до ближайшего, с минимальным пределом, чтобы не старались подойти вплотную. И своя отдельная цель для медика, которого выгодно держать как можно ближе .
У меня была куча багов, связанных с гранатами. И попытки набрать очки на своих, и перемешивание списка перебираемых юнитов, которые могли бы быть гранатой убиты, из за чего свой командир попадал в список врагов…
Одной из самых неприятных вещей была подстройка весов обследованных "опасных" клеток под разные карты. Неприятной, потому что это куча макарон и ты не понимаешь полностью, почему какая-то комбинация в одном уровне работает, а в другом нет. А когда понимаешь - становится вообще стыдно. Видишь, что благодаря некоторой конкретной комбинации весов стратегия застревала в некоторой выгодной кемперской позиции, а если веса другие, то либо до нее не доходила, либо уходила слишком рано. Не люблю эвристики и ручную модификацию магических констант, а именно через них и лежал путь к победе :)
« Последнее редактирование: Декабря 17, 2013, 08:49:33 pm от noop »
Записан

tyamgin

  • Sr. Member
  • ****
  • Сообщений: 182
Записан

olexiyo

  • Newbie
  • *
  • Сообщений: 21

Цитировать
А с какими вообще сложностями значимыми для себя или на которые убили много времени вы сталкивались?

Моей самой большой проблемой было научить юнитов не заканчивать ход на "плохих" клетках (клетка А плохая, если есть много клеток Б, таких, что Б видит А, но А НЕ видит Б).

В некоторый момент, приблизительно 75 процентов моих поражений начинались с того, что первый солдат так подставлялся.
К сожалению, времени на контест было мало -- так что я повозился часок с подбором коэффициентов, солдаты постоянно застревали где-то, и я просто выключил эту фичу
Записан

santa324

  • Full Member
  • ***
  • Сообщений: 142

А с какими вообще сложностями значимыми для себя или на которые убили много времени вы сталкивались?
Я вот с "ходилкой" влип) или вместе не держались, или держались но разбредались и затык находили.
1) Моя альфабета увидев первого противника считала что раз он один (других не видит) а нас много надо бежать вплотную чтобы не убежал :) Боролся с этим долго и упорно, кое как победил - кривыми костылями. Сделал заливку поля опасности на начало расчетов и убедительно настаивал альфабете что идти вперед в неизвестность очень невыгодно. Стала проигрывать моей же более агрессивной альфабете, но в песочнице пошла вверх.
2) Еще альфабета не старалась убить противников быстро. Бывало солдат мог пристрелить противника сразу, но вместо этого просто перемещался в более безопасную позицию, рассчитывая что его пристрелит снайпер, ходящий следом (тоже до врага). Но оказывалось что сзади за врагом стоит невидимый медик, подбегает лечит и убить уже не можем. Или сзади снайпер и он убивает моего снайпера до того как он выстрелит. Так и не победил, подкрутил коэффициенты и вроде  стало реже.
3) Еще одна проблема: расчеты не учитывали что противник может быть потерян из виду. Мой боец мог пойти занимать более выгодную позицию вместо того чтобы стрелять во врага, рассчитывая что местность открытая, спрятаться врагу некуда - потом пристрелим. Но враг уходил из виду и мы про него тут же забывали - все расчеты летели в трубу. И я сам тоже не особо старался прятаться, а на тот момент топы только и делали что выстрелят и прячутся. Тоже не победил, было несколько экспериментов но не удачных.
Был эксперимент где я запрещал стрелять по врагам, которые на данный момент по расчетам невидимы (был ход этого бойца после того как его последний раз видели), но стало хуже. Видимо из-за того что при таком подходе алгоритм точно знал где находится враг и считал что всегда может пару ходов сделать, войти в зону видимости и получить право стрелять.
Потом додумался до честного способа, надо расчеты альфабеты вести для каждого хода с собственным списком видимых юнитов (у меня один общий для всех расчетов), чтобы не знала о тех врагах что ушли по расчетам из виду, не угадывала где они, не пыталась их атаковать и получала с этого большой негатив - но сделать уже не успел.
« Последнее редактирование: Декабря 17, 2013, 11:39:30 pm от santa324 »
Записан

amurushkin

  • Sr. Member
  • ****
  • Сообщений: 189

Стыдно признаться что я не смог догадаться, что для того чтобы скаут бежал впереди надо сравнить его расстояние до цели с другим юнитом. Сейчас добавил это в стратегию, а также включаю систему предсказания, когда очков действия становится немного меньше чем полные, для того чтобы боялись меньше, и все стало сразу по-другому прямо
Записан

acherednychenko

  • Newbie
  • *
  • Сообщений: 14

1) Моя альфабета увидев...
Скажите, какая у Вас глубина поиска?
Записан

santa324

  • Full Member
  • ***
  • Сообщений: 142

1) Моя альфабета увидев...
Скажите, какая у Вас глубина поиска?
Глубина поиска плавающая, от1 до 10 ходов при удачном стечении обстоятельств. (разные ходы на разную глубину)
Вот 2 компаратора, ответственные за выбор позиции для дальнейшего разложения и выбор лучшего хода для "всплывани" вверх оценки:
            new Comparator<WorldBox>() {
                @Override
                public int compare(WorldBox b1, WorldBox b2) {
                    return Double.compare(b2.getBestScore()*(10+b1.getDeep()), b1.getBestScore()*(10+b2.getDeep()));
                }
            };
            new Comparator<WorldBox>() {
                @Override
                public int compare(WorldBox b1, WorldBox b2) {
                    if (b2.getDeep() == b1.getDeep())
                        return Double.compare(b2.getBestScore(), b1.getBestScore());

                    return b2.getDeep() - b1.getDeep();
                }
            };

getBestScore() - текущая оценка позиции
getDeep() - количество разложений (примерно пропорционально времени потраченному на исследование этой позиции)

Кстати изменеие второго компаратора на такой (был просто выбор позиции с максимальным getBestScore()) привел к резкому скачку в рейтинге с 60х мест до, примерно, 18го :). А я долго не мог до этого додуматься хотя теперь все очевидно.

Вообще я очень доволен практикой применения альфабеты, хотя и не победитель.
« Последнее редактирование: Декабря 18, 2013, 12:06:36 am от santa324 »
Записан

acherednychenko

  • Newbie
  • *
  • Сообщений: 14

1) Моя альфабета увидев...
Скажите, какая у Вас глубина поиска?
Глубина поиска плавающая, от1 до 10 ходов при удачном стечении обстоятельств.

Спасибо, я сразу не увидел что Вы также выложили исходники. Изучу.

Александр, 10 ходов это впечатляет. 10 ходов - это больших итераций, верно? Интересно - примерно сколько это вариантов конечных состояний в результате?
Записан

santa324

  • Full Member
  • ***
  • Сообщений: 142

1) Моя альфабета увидев...
Скажите, какая у Вас глубина поиска?
Глубина поиска плавающая, от1 до 10 ходов при удачном стечении обстоятельств.

Спасибо, я сразу не увидел что Вы также выложили исходники. Изучу.

Александр, 10 ходов это впечатляет. 10 ходов - это больших итераций, верно? Интересно - примерно сколько это вариантов конечных состояний в результате?
Возможно вы не поняли, лишь немногие ходы рассматриваются так глубоко, большинство так и остаются рассмотренными только на 1 ход.
30000-50000 конечных состояний рассматривается за тик (один вызов move()).
Это не совсем альфабета, это модификация на ее основе
« Последнее редактирование: Декабря 18, 2013, 12:17:55 am от santa324 »
Записан

acherednychenko

  • Newbie
  • *
  • Сообщений: 14

Александр, спасибо!
Записан

darkstone

  • Jr. Member
  • **
  • Сообщений: 22

2santa324 Планируешь в песочнице доработать? :) Чтобы посмотреть, что получилось?
Записан

maskit

  • Newbie
  • *
  • Сообщений: 2

Мои оболтусы:  v.9, финал - 23-и, в песочке - 34-е
https://www.dropbox.com/s/bprqgk1ut9ymoa9/v9.zip,  копия последней отосланной стратегии, со всеми недоработками и намётками
Но, по мне - код простой

Ход мыслей такой - хотя стратегия вызывается несколько раз до окончания ОД, мир статичен.
Карту мы знаем изначально. Что нового может случится за время действия одного бойца?
1) может появится враг
2) может появится бонус
Поэтому лучший вариант - просчитать все возможные действия бойца за его имеющиеся ОД, составив набор планов, состоящий из мувов,  и выбрать самый лучший.
Если ни врагов, ни бонусов не появилось, боец действует по плану, не жрёт процессор, всё гут (потом пригодится, если вдруг).
Если появился враг или бонус - пересчитываем.

Создается копия мира с бонусами, врагами и тиммейтами
Рекурсивно составляются планы на очки действия бойца, каждый мув в которых изменяет копию мира.
Поскольку урон отлично просчитывается, в конце получаем  кучу конечных 100% точных состояний мира (по кол-ву планов), которые остается отсортировать, и выбрать лучший.

Нужно убить как можно больше врагов? Пожалуйста - сортируем по кол-ву оставшихся после просчета противников. (меньше - лучше)
Хочется нанести как можно больше урона - не проблема, сортируем по кол-ву оставшегося у врагов здоровья (опять же, меньше - лучше)
Не хочешь, чтобы боец загораживал лидеру дорогу? Выбери план, в котором он этого не делает
Ну и т.п.

И так последовательно разными компараторами сравниваем состояния, потом выбирая первый план из списка

Практически никаких переменных, брутфорс.

Пробемы: для уменьшения кол-ва планов можно считать лечения одного трупера за один экшн (так и не успел сделать)
Ну и Field Ration. Если трупер видел рационов так 6-8, то он становился таким довольным, что выжирал доступные 6.5 гигов памяти на просчеты и падал
с OutOfMemoryException. Поэтому аппетиты пришлось ограничить, быстрый фикс, пришедший в голову - ограничение кол-ва планов.

А так планы составлялись, боты носились,
За ботами интересно было наблюдать, пару раз в голову приходила мысль - "а фиг бы я такое заскриптовал"
Хотя и тупили местами, ясен перец

Вначале тактика была: "бей-беги". Т.е по максимому нанесение урона. И неплохо работало. Потом все стали осторожничать,
благо, мне для осторожности нужно было местами поменять две строчки.

А потом на работе напрягли так, что на моих оболтусов не оставалось времени. Ибо я работаю в финансовой организации,
а до введения евро в Латвии оставался месяц...  (это я пожаловался и попытался себя отмазать)

По вечерам и выходным, когда не отсыпался, ковырял, конечно, но уже без энтузиазма.

Из нереализованного:
Просчет действий врагов (благо, механизм есть и запас по скорости большой)
Атака по приоритету
Разведка! По сути лидером у меня был боец с самым большим радиусом обзора, а остальные толпились сзади.А могут ведь выбежать - и назад.
Анализ опасностей (куда лучше не вставать, а куда вставать лучше)

Если бы всё это реализовал, думаю, в десятку бы мог войти
Ну и ладно, я и так доволен, отличная разминка для мозга
Записан

Cooler

  • Full Member
  • ***
  • Сообщений: 98

А с какими вообще сложностями значимыми для себя или на которые убили много времени вы сталкивались?
Я вот с "ходилкой" влип) или вместе не держались, или держались но разбредались и затык находили.
Я влип с реализацией углубленного перебора - задача оказалась чрезвычайно сложной, с массой неочевидных нюансов и потенциально забагованных мест: чем дальше продвигался - тем больше понимал, как много еще предстоит сделать, чтобы это заработало как надо. Потратил на это 3 дня на неделе подготовки к финалу, тогда как надо было делать другие фичи.
Записан

santa324

  • Full Member
  • ***
  • Сообщений: 142

Поделитесь своим опытом кто использовал что-нибудь искусственно интеллектуальное или алгоритмы применяемые в игровом AI.
А то что-то все топы на эвристиках :) Такое ощущения что я один попытался пойти в эту сторону.
Записан

AdmiralShadow

  • Jr. Member
  • **
  • Сообщений: 21

Мои оболтусы:  v.9, финал - 23-и, в песочке - 34-е
https://www.dropbox.com/s/bprqgk1ut9ymoa9/v9.zip,  копия последней отосланной стратегии, со всеми недоработками и намётками
Но, по мне - код простой


Если бы всё это реализовал, думаю, в десятку бы мог войти
Ну и ладно, я и так доволен, отличная разминка для мозга

Понравился ваш код. Строгий и понятный. Есть большой потенциал расширения поведения.
Также использовал перебор, мой подход очень близок к Вашем.

В своей стратегии изначально тоже использовал рекурсию, для открытия узлов возможностей. Но очень простая идея позволило мне вырезать это, так как часто не хватало лимита времени или памяти на просчет одного хода (а хотелось то чтобы варианты возможности были полнее :) ). Чаще это было с медиком, если рядом были и враги и подраненные из твоего отряда, тут тебе и пострелять и подлечить, во общем мрак.
Идея очень проста описывается всего тремя полями:
    private List<SimNode> simLayerPrev;
    private List<SimNode> simLayer;
    private List<SimNode> positionEnding;

Соответственно рекурсия выродилась в цикл с контролем над глубиной:

while (currentStep < (startStep + depth) && this.simLayer.size() > 0) {
            this.simLayerPrev = this.simLayer;
            this.simLayer = getNewSimLayer();

            generateNewPositionsLayer(brain.getWorld(), simLayerPrev, simLayer, onlyMoving);

            // применяем действия
            applyActions(simLayer);
            // удаляем убитый, забираем бонусы
            solveActions(simLayer);
            // Если это конечная позиция (закончились очки действий),
            // переносим данную позицию в окончательные и убираем из симуляции
            adjActions(simLayer);

            currentStep++;
        }
Записан

santa324

  • Full Member
  • ***
  • Сообщений: 142

В своей стратегии изначально тоже использовал рекурсию, для открытия узлов возможностей. Но очень простая идея позволило мне вырезать это, так как часто не хватало лимита времени или памяти на просчет одного хода.
Я без проблем пересчитывал все возможные действия любого бойца сотни раз за вызов move(). Рекурсия работает плохо, лучше использовать алгоритм Дейкстры (состояние игрового мира-узел, расстояние между узлами = стоимость действия в од) - отсекается множество вариантов хождения туда-сюда.
Записан

AdmiralShadow

  • Jr. Member
  • **
  • Сообщений: 21

В своей стратегии изначально тоже использовал рекурсию, для открытия узлов возможностей. Но очень простая идея позволило мне вырезать это, так как часто не хватало лимита времени или памяти на просчет одного хода.
Я без проблем пересчитывал все возможные действия любого бойца сотни раз за вызов move(). Рекурсия работает плохо, лучше использовать алгоритм Дейкстры (состояние игрового мира-узел, расстояние между узлами = стоимость действия в од) - отсекается множество вариантов хождения туда-сюда.

:) Ну поначалу я тоже запретил ходить туда-сюда, встать-присесть. Но как показала игра  грамотная разведка  сыграла большую роль для победы. А для нее следовало как раз бегать туда сюда, ну и вставать, чтобы увидеть за препятствиями.
А с алгоритмом познакомлюсь, спасибо Вам.
Записан

santa324

  • Full Member
  • ***
  • Сообщений: 142

:) Ну поначалу я тоже запретил ходить туда-сюда, встать-присесть. Но как показала игра  грамотная разведка  сыграла большую роль для победы. А для нее следовало как раз бегать туда сюда, ну и вставать, чтобы увидеть за препятствиями.
А с алгоритмом познакомлюсь, спасибо Вам.
Множество разведанных клеток тоже входит в состояние мира ;) Есть куча вариантов ходить туда-сюда и при этом ни одной новой клетки не разведать.
У меня было 2 версии, один не учитывал разведку - использовался в бою для большей глубины просчета.
Второй с контролем разведанных позиций - использовался во время перемещения.
Второй работал медленнее, но все равно намного быстрее рекурсии - примерно сотню раз успевал перебрать все возможные ходы против 300-700 по первому варианту.
« Последнее редактирование: Декабря 18, 2013, 02:07:45 pm от santa324 »
Записан

amurushkin

  • Sr. Member
  • ****
  • Сообщений: 189

планирую для експериментов с reinforcement learning многое переписать и сделать конфетку )

у меня возникало желание попробовать это использовать но я так и не придумал в какой момент выполнять обновление коэффициентов. По сути мы оцениваем трансформации одной позиции в другую, вот какие брать для этой оценки я так и не понял
Записан

acherednychenko

  • Newbie
  • *
  • Сообщений: 14

планирую для експериментов с reinforcement learning многое переписать и сделать конфетку )

у меня возникало желание попробовать это использовать но я так и не придумал в какой момент выполнять обновление коэффициентов. По сути мы оцениваем трансформации одной позиции в другую, вот какие брать для этой оценки я так и не понял

один из вариантов это Approximate Q-Learning:
https://www.youtube.com/watch?v=8IakYZnMdIk

и у многих из нас почти все для этого есть :-)
Записан

noop

  • Full Member
  • ***
  • Сообщений: 73

Хмм.. У меня с перебором можно было лечить соседних солдат по очереди и брать несколько рационов, при этом укладываясь в таймлимит. Но, вероятно, поиск "в ширину" действительно мог бы сработать лучше в данной игре. Задумался..
Записан

noop

  • Full Member
  • ***
  • Сообщений: 73

Хмм.. У меня с перебором можно было лечить соседних солдат по очереди и брать несколько рационов, при этом укладываясь в таймлимит. При этом всегда работало обновление трехуровневой карты видимости при перемещениях/вставаниях. Но, вероятно, поиск "в ширину" действительно мог бы сработать лучше в данной игре. Задумался..
Записан

baho

  • Newbie
  • *
  • Сообщений: 19

У меня перебор поиском в ширину без рекурсии с отсечением заведомо худших ветвей. Выставил ограничение на 50000 цепочек ходов, очень редко до него добираются. Да и с рекурсией вроде времени хватало, это уж я так, по привычке, сразу же оптимизировать начинаю. Вообще посмотрел, очень все похоже у нас получается. Дело, как уже выше писали, в нюансах.
Правда у меня выбор лучшего хода сделан простой "лексикографической" сортировкой получившегося набора цепочек. Так и не придумал, как можно получше выбирать. Надо бы в математике на этот предмет покопаться.
Записан

noop

  • Full Member
  • ***
  • Сообщений: 73

Хммм.. Оказывается, рекурсия многим не по нраву пришлась… А в чем, собственно, оптимизация, если считать все равно один ход и времени хватает? Лишние варианты-то отсекаются, но генерация каждого варианта становится намного медленнее. Да и разве рекурсия не проще по коду даже "с наворотами"?

P.S. Модераторы, удалите моё сообщение выше, случайно намусорил.
Записан

santa324

  • Full Member
  • ***
  • Сообщений: 142

Хммм.. Оказывается, рекурсия многим не по нраву пришлась… А в чем, собственно, оптимизация, если считать все равно один ход и времени хватает? Лишние варианты-то отсекаются, но генерация каждого варианта становится намного медленнее. Да и разве рекурсия не проще по коду даже "с наворотами"?

P.S. Модераторы, удалите моё сообщение выше, случайно намусорил.
Так у меня минимакс/альфабета, мне не один ход а сотни обсчитать надо успеть.
Рекурсия проще конечно, но в моем случае не подходила. Большинство на ней и остановились - им было достаточно.
А почему генерация каждого варианта медленнее? этого я не понял
Записан

santa324

  • Full Member
  • ***
  • Сообщений: 142

У меня перебор поиском в ширину без рекурсии с отсечением заведомо худших ветвей. Выставил ограничение на 50000 цепочек ходов.
Что-то я не понал как вы поиском в ширину перебираете, я Дейкстрой делал. И у меня более 5000 вариантов на одного бойца не получалось никак.
Записан

AdmiralShadow

  • Jr. Member
  • **
  • Сообщений: 21

Хммм.. Оказывается, рекурсия многим не по нраву пришлась… А в чем, собственно, оптимизация, если считать все равно один ход и времени хватает? Лишние варианты-то отсекаются, но генерация каждого варианта становится намного медленнее. Да и разве рекурсия не проще по коду даже "с наворотами"?

P.S. Модераторы, удалите моё сообщение выше, случайно намусорил.

Если хватало , то нет проблем. Но у меня точно были проблемы с количеством вариантов, особенно для медика. Как отсекать заведомо худшие я не понял. Отсекал только варианты приводящие к одинаковой позиции с одинаковым количеством потраченных очков действия, но и с этим были проблемки. Ну еще тупые действия конечно отсекались, типа съесть сухой поёк, если очков действия слишком много.

Конечно было бы интересно увидеть Вашу  реализацию, по полному перебору вариантов действий десантника.
Записан

baho

  • Newbie
  • *
  • Сообщений: 19

У меня всегда генерятся все возможные варианты, так что разницы между "в ширину" и "в глубину" по скорости особой нету. Но вот возможность раньше отсечь заведомо ненужные ветки мне показалось неплохой мыслью. Да и при просмотре списка вариантов вручную, лучше, когда мусорных веток не будет вообще (бег из одной клетки в другую и обратно или цикл встал-лег-встал). При генерации в ширину они отсекаются раньше.
Записан

AdmiralShadow

  • Jr. Member
  • **
  • Сообщений: 21

У меня всегда генерятся все возможные варианты, так что разницы между "в ширину" и "в глубину" по скорости особой нету. Но вот возможность раньше отсечь заведомо ненужные ветки мне показалось неплохой мыслью. Да и при просмотре списка вариантов вручную, лучше, когда мусорных веток не будет вообще (бег из одной клетки в другую и обратно или цикл встал-лег-встал). При генерации в ширину они отсекаются раньше.

А как же разведка ? Мои как раз и бегали вперед назад, на радость снайперу :). Или вставали и ложились (особенно мои любили карту икс ), когда на задних линиях стоял снайпер.
Записан

baho

  • Newbie
  • *
  • Сообщений: 19

Медик по, кол-ву вариантов, конечно лидировал. Особенно, если есть еда, есть кого полечить и есть куда гранаты покидать (все возможные клетки).
Отсечение сделал очень просто. Для каждой клетки (с учетом стойки) на поле сохраняю лучшую, здесь уже проходившую, цепочку. Если считающаяся цепочка не может стать в чем-то лучше (заведомо хуже по параметрам и осталось меньше AP), то ее в дальнейшем не просчитываем. Вот сейчас описывал и понял, что у меня здесь баг есть :) Но вроде не критичный, посколько я перед заливкой тестировал верссии без отсечений, она играла не лучше.
Записан
Страницы: 1 [2] 3