Комментарии 14
Читаю уже вторую статью в которой упоминается симулятор.
Можете, пожалуйста, поподробнее разъяснить почему это так важно? Я пользовался batch mode предоставленного локального раннера чтобы тестировать стратегии друг с другом и, в целом, остался доволен. Что я упускаю?
Без симулятора приходится действовать только эвристикой, а это значительно менее эффективно.
Хм, а не слишком ли это затратно в плане ресурсов? Для своего бота я рассчитывал траектории пуль и радиусы зон поражения взрыва с помощью простой геометрии. Для поиска пути и траектории движения игроков я строил граф возможных положений игрока ( при этом одни и те же координаты отражаются в разные вершины графа для падающего игрока и летящего вверх) и строил путь дейкстрой.
Для прицеливания я просто анализировал несколько возможных траекторий (опять же чисто геометрически) и выбирал из них наиболее эффективную.
Все же не очень понимаю, к чему здесь полный симулятор.
Второй вопрос про симулятор: как его валидировать? Ведь, будет довольно мало толку, если он, к примеру, рассчитывает столкновения отличным от настоящей игры образом. Как проверить совпадение симуляции с настоящей игровой механикой?
И еще из вашего описания я не до конца понял как вы строите граф возможных положений, хочется подробней про это услышать.
Насчет симуляции: для принятия правильного решения боту нужна оценка возможных действий, симулятор дает точный прогноз, все остальные методы дают приблизительный. Точней прогноз — эффективней действия. Тем не менее, всё зависит от задачи. Чем сложней игровая механика, тем сложней для нее написать эвристику и тем эффективней симуляция.
Для проверки симулятора я с помощью отладочной отрисовки выводил путь полученный моим симулятором и проверял, совпадает ли он с путем которым движется бот в раннере.
russianaicup.ru/profile/uf.darxy
Про граф положений:
Первым делом я выбираю размерность сетки. От размерности сетки зависит количество вершин графа, которые нужно анализировать, поэтому, в условиях ограниченых ресурсов я остановился на размерности 1х1 игровой единицы расстояния. Пробовал с размерностью 0.1, но большой разницы не увидел.
Затем я строю граф из начальной позиции игрока. При этом граф направленный и вершины различаются не только координатами, но и внутренним состоянием игрока.
Попытаюсь объяснить на примере:
Допустим у нас есть клетка с инексом [18,20], которая находится над поверхностью. В ней игрок может оказаться либо подпрыгнув с поверхности, либо падая сверху.
Соответственно эта клетка будет отражаться в несколько разных верщин графа:
- [x:18, y:20, fallingState:y, jumpingStateCancellabe:n] — юнит пролетает клетку падая
- [x:18, y:20, fallingState:n, jumpingStateCancellabe:y] — юнит пролетает клетку прыгая
Допустим, есть JumpPad неподалеку. Тогда мы получим еще одну вершину графа:
- [x:18, y:20, fallingState:n, jumpingStateCancellabe:n] — юнит пролетает клетку, прыгнув с джамппада
Ребра между вершинами графа означают возможно ли перейти из одного состояния в другое. Например из вершины [x:18, y:20, fallingState:n, jumpingStateCancellabe:y] можно перейти в вершину [x:18, y:20, fallingState:y, jumpingStateCancellabe:n] если остановить прыжок и начать падать.
Затем я присваиваю каждой вершине вес. Например, для клеток с аптечками присваивается положительный вес, для клеток в которых ожидается пуля/взрыв — вес отрицательный. Также вершины графа с большим количеством степеней свободы получают положительный вес. Учитывается и положение относительно вражеских/дружественных юнитов в зависимости от оружий и здоровья. Затем дейкствой ищу наилучший путь.
Насчет симулятора:
симулятор дает точный прогноз только на определенное количество тиков (ресурс же ограничен). Т.е. если надо посчитать положение на 50 тиков вперед, нужно провести 50 расчетов, что дает o(n). В случае с простым геометрическим расчетом посчитать можно любой момент времени за константу. Кроме того, симулятор дает точный прогноз только в случае если вы уверены, что он совпадает на 100% с игровой механикой. Таким образом, что в случае симуляции, что в случае геометрического расчета вопрос сводится к валидации результата.
В этом году игровая механика, на мой взгляд, была довольно простая, т.е. движение пуль легко просчитывалось геометрически, а все остальное недетерминировано, т.е. толку от любой симуляции мало.
Я не хочу спорить с предложенным вами подходом, просто хочу понять, могло бы это помочь мне добиться лучшего результата.
Симуляция — это перебор возможных действий в различных ситуациях. Вы можете даже не знать что ищете, пробовать и смотреть что получается. У меня в 15м году бот таким образом сам придумывал трюки которые я ему специально не программировал (вроде разворота шиной). Ваш же подход только находит способ сделать то что Вы его просите.
В случаях, когда тактическое преимущество критично, да, наверно это имеет како-то смысл. Но не очень понятно, в каком месте провести границу между честной симуляцией и аппроксимацией.
Почему выбор ЯП пал на c++, а не тот же питон? Есть ли какие-то подводные камни, если использовать питон на соревновании?
Какие ещё бывают чемпионаты по данной дисциплине?
Мой бот для Russian AI Cup 2019