Или старое доброе динамическое программирование без этих ваших нейросетей.
Полтора года назад мне довелось поучаствовать в корпоративном конкурсе (с целью развлечения) по написанию бота для игры Lode Runner.
20 лет назад я старательно решал все задачи динамического программирования на соответствующем курсе, но практически все забыл и не имел опыта программирования игровых ботов.
Времени было выделено мало, приходилось вспоминать, экспериментировать на ходу и самому наступать на грабли.
Но, вдруг, все сложилось очень хорошо, поэтому я решил как-то систематизировать материал, не топя читателя матом.
ЭИгровой сборщик с сервера проекта Codenjoy
Для начала немного опишем правила.
игры : Игрок перемещается горизонтально по полу или по трубам, может подниматься и спускаться по лестнице и падает, если под ним нет пола.
Он также может прорезать дыру слева или справа от себя, но не каждую поверхность можно прорезать – условно «деревянный» пол возможен, а бетонный – нет. Монстры бегут за игроком, падают в вырезанные ямы и умирают в них.
Но самое главное, что игрок должен собирать золото, за первое собранное золото он получает 1 очко прибыли, за N-е он получает N очков.
После смерти общая прибыль сохраняется, но за первое золото снова дают 1 очко.
Это говорит о том, что главное – как можно дольше остаться в живых, а сбор золота как-то второстепенен.
Поскольку на карте есть места, из которых игрок не может выбраться самостоятельно, в игру был введен бесплатный суицид, который случайным образом помещал игрока куда-то, но по сути ломал всю игру - суицид не прерывал увеличение стоимость найденного золота.
Но мы не будем злоупотреблять этой особенностью.
Все примеры из игры будут приведены в упрощенном виде, который использовался в логах программы: 
Немного теории
Чтобы реализовать бота с использованием какой-то математики, нам нужно задать некую целевую функцию, описывающую достижения бота, и найти для нее действия, максимизирующие ее.Например, за сбор золота мы получим +100, за смерть -100500, таким образом, никакой сбор золота не превзойдет возможную смерть.
Отдельный вопрос, что именно мы используем для определения целевой функции, т. е.
каково именно состояние игры? В простейшем случае достаточно координат игрока, но в нашем случае все гораздо сложнее:
- координаты самого игрока
- координаты всех лунок, сделанных всеми игроками
- координаты всего золота на карте (или координаты недавно съеденного золота)
- координаты всех остальных игроков
Поэтому давайте немного упростим задачу и пока мы не будем запоминать съеденное нами золото (к этому мы еще вернемся), мы также не будем запоминать координаты других игроков и монстров.
Итак, текущее состояние игры следующее:
- координаты самого игрока
- координаты всех ям
- Команды движения изменяют одну из соответствующих координат.
- Команда «Выкопка ямы» добавляет одну новую яму.
- Падающий без поддержки игрок уменьшает вертикальную координату
- Бездействие игрока, стоящего на опоре, не меняет состояние
Одним из почтенных классических методов, позволяющих просчитать количество ходов игры вперед, является динамическое программирование.
Совсем без формул обойтись невозможно, поэтому приведу их в упрощенном виде.
Сначала придется ввести много обозначений.
Для простоты мы будем рассчитывать время от текущего хода, т.е.
текущий ход t=0.
Обозначим состояние игры на ходу t через 
.
Куча 
будет обозначать все допустимые действия бота (при определенном состоянии, но для простоты мы не будем писать индекс состояния), через
обозначим конкретное действие на ходу t (индекс опускаем).
Состояние
Под влиянием
переходит в состояние 
.
Выигрыш при выполнении действия а в состоянии
давайте обозначим это как 
.
При его расчете будем считать, что если мы ели золото, то оно равно G=100, если мы умерли, то D=-100500, иначе 0.
Позволять 
это функция выигрыша оптимальный игра бота, находящегося в состоянии x в момент времени t. Тогда нам просто нужно найти действие, которое максимизирует 
.
Теперь запишем первую формулу, очень важную и в то же время почти правильную: 
Или для произвольного момента времени 
Выглядит это довольно коряво, но смысл прост – оптимальное решение для текущего хода состоит из оптимального решения для следующего хода и выигрыша для текущего хода.
Это кривая формулировка принципа оптимальности Беллмана.
Мы пока ничего не знаем об оптимальных значениях на шаге 1, но если бы мы их знали, мы бы нашли действие, максимизирующее функцию, простым перебором всех действий бота.
Красота рекуррентных отношений в том, что мы можем найти 
, применив к нему принцип оптимальности, выразив его точно такой же формулой через 
.
Мы можем так же легко выразить функцию выигрыша на любом этапе.
Казалось бы, проблема решена, но здесь мы столкнулись с проблемой: если на каждом шаге нам приходилось перебирать 6 действий игрока, то на N шаге рекурсии нам придется перебирать 6^N вариантов.
, что для N=8 уже вполне приличная цифра ~1,6 млн случаев.
С другой стороны, у нас есть гигагерцовые микропроцессоры, которым делать нечего и вроде бы они вполне справляются с задачей, но мы ограничиваем их глубину поиска ровно 8 ходами.
Итак, наш горизонт планирования — 8 ходов, но где мы возьмем значения? 
? И тут нам просто приходит в голову мысль, что мы можем как-то проанализировать перспективность позиции, и приписываем ей некую ценность, исходя из своих высших соображений.
Позволять 
, Где 
это функция стратегии, в самом простом варианте это просто матрица, из которой мы выбираем значение исходя из геометрических координат бота.
Можно сказать, что первые 8 ходов были тактикой, а потом начинается стратегия.
На самом деле нас никто не ограничивает в выборе стратегии, и этим мы займемся позже, а пока, чтобы не уподобиться сове в анекдоте про зайцев и ежиков, перейдем к тактике.
Общая схема
И вот, мы определились с алгоритмом.На каждом шаге мы решаем оптимизационную задачу, находим оптимальное действие для шага, выполняем его, после чего игра переходит к следующему шагу.
На каждом этапе необходимо решать новую задачу, потому что с каждым ходом игры задача немного меняется, появляется новое золото, кто-то кого-то съедает, игроки перемещаются.
Но не думайте, что наш блестящий алгоритм сможет предусмотреть всё.
После решения задачи оптимизации необходимо добавить обработчик, который будет проверять неприятные ситуации:
- Бот долго стоит на месте
- Постоянно двигаясь влево и вправо
- Нет дохода слишком долго
Характер этих ситуаций может быть разным.
Иногда противоречия между стратегией и тактикой приводят к тому, что бот зависает на месте в точке, которая кажется ему стратегически важной, что было обнаружено древними писателями-ботами под названием «Осел Буриданова».
Ваши противники могут околачиваться и преграждать вам короткий путь к заветному золоту – все это мы рассмотрим позже.
Борьба с прокрастинацией
Рассмотрим простой случай, когда справа от бота есть одно золото и в радиусе 8 ячеек золота больше нет. Какой шаг сделает бот по нашей формуле? На самом деле абсолютно любой.Например, все перечисленные решения даже после трех ходов дают совершенно одинаковый результат:
- шаг влево – шаг вправо – шаг вправо
- шаг вправо - бездействие - бездействие
- бездействие – бездействие – шаг вправо
И стоять на месте вечно.
Нам нужно изменить формулу победы, чтобы побудить бота действовать как можно раньше: 
будущий выигрыш на следующем этапе мы умножили на «коэффициент инфляции» Е, который необходимо выбрать меньше 1. Можно смело экспериментировать со значениями 0,95 или 0,9. Но не выбирайте его слишком маленьким, например, при значении Е=0,5 съеденное на 8-м ходу золото принесет всего 0,39 очка.
Итак, мы заново открыли для себя принцип «Не откладывай на завтра то, что можно съесть сегодня».
Безопасность
Собирать золото – это конечно хорошо, но нужно подумать и о безопасности.У нас есть две задачи:
- Научите бота рыть ямы, если монстр находится в подходящей позиции
- Научите своего бота убегать от монстров
Отдельная проблема в том, что мы не просчитываем, где именно монстр может оказаться в тот или иной ход. Поэтому для простоты будем считать, что монстры стоят на месте, и нам просто не нужно к ним приближаться.
Если они начнут к нам приближаться, бот сам начнет от них убегать, потому что его оштрафуют за слишком близкое к ним расположение (своего рода самоизоляция).
Итак, вводим два правила:
- Если подойти к монстру на расстояние d и d<=3, then we are subject to a fine of 100500*(4-d)/4
- Если монстр подойдет достаточно близко, окажется на одной линии с нами и между нами будет дыра, то мы получим некоторую прибыль P
Обходим графики
Математически проблема оптимального обращения золота — это давно решенная задача коммивояжера, решение которой не доставляет удовольствия.Но прежде чем решать подобные задачи, нужно задуматься над простым вопросом – как найти расстояние между двумя точками в игре? Или в чуть более полезной форме: по заданному золоту и для любой точки карты найти минимальное количество ходов, за которое игрок доберется от точки до золота.
Забудем на время о рытье ям и прыжках в них, оставим только естественные движения в 1 клетку.
Только пойдем мы в обратном направлении – подальше от золота и через всю карту.
На первом шаге мы выбираем все ячейки, из которых можно за один ход попасть в золото, и присваиваем им 1. На втором шаге мы выбираем все ячейки, из которых за один шаг попадаем в 1, и присваиваем им 2. На картинке показан случай для 3 шагов.
Теперь попробуем записать все это формально, в форме, удобной для программирования.
Нам понадобится:
- Двумерный числовой массив distance [x,y], в котором мы будем хранить результат. Изначально для золотых координат оно содержит 0, для остальных точек -1.
- Массив oldBorder, в котором мы будем хранить точки, от которых будем двигаться, изначально содержит одну точку с координатами золота
- Массив newBorder, в котором мы будем хранить точки, найденные на текущем шаге.
- Для каждой точки p из oldBorder находим все точки p_a, из которых мы можем достичь p за один шаг (точнее, мы просто сделаем все возможные шаги от p в обратном направлении, например, полетев вверх при отсутствии поддержки ) и расстояние [p_a]=-1
- Разместим каждую такую точку p_a в массиве newBorder, запишем номер итерации на расстоянии [p_a]
- После прохождения всех пунктов:
- Мы меняем местами массивы oldBorder и newBorder, а затем очищаем массив newBorder.
- Если oldBorder пуст, то завершаем алгоритм, иначе переходим к шагу 1.
iter=1;
newBorder.clear();
distance.fill(-1);
distance[gold]=0;
oldBorder.push(gold);
while(oldBorder.isNotEmpty()) {
for (p: oldBorder){
for (p_a: backMove(p)) {
if (distance[p_a]==-1) {
newBorder.push(p_a);
distance[p_a]=iter;
}
}
}
Swap(newBorder, oldBorder);
newBorder.clear();
iter++;
}
На выходе алгоритма мы будем иметь карту расстояний со значением расстояния от каждой точки всего игрового поля до золота.
При этом для точек, из которых золото недостижимо, значение расстояния равно -1. Такой обход игрового поля (образующий граф с вершинами в точках поля и ребрами, соединяющими доступные за один ход вершины) математики называют «обходом графа в ширину».
Если бы мы реализовали рекурсию, а не два массива границ, это бы называлось «обход графа в глубину», но поскольку глубина может быть довольно большой (несколько сотен), советую избегать рекурсивных алгоритмов при обходе графов.
Реальный алгоритм будет немного сложнее за счет выкапывания ямы и прыжка в нее - получается, что за 4 хода мы перемещаем одну клетку вбок и две вниз (так как двигаемся в обратную сторону, то вверх), но небольшая модификация алгоритм решает проблему.
Дополнил картинку цифрами, в том числе выкопал яму и прыгнул в нее: 
Что это нам напоминает? 
Запах золота! И наш бот будет следовать за этим запахом, как Рокки - за сыром (но при этом он не потеряет мозгов и уворачивается от монстров, и даже роет для них ямы).
Давайте создадим для него простую жадную стратегию:
- Для каждого золота мы построим карту расстояний и найдем расстояние до игрока.
- Выберем ближайшее к игроку золото и возьмем его карту для расчета стратегии.
- Для каждой клетки карты обозначим через d ее расстояние до золота, затем стратегическую ценность
это некая мнимая стоимость золота, желательно, чтобы она оценивалась в несколько раз меньше реальной, и
Это фактор инфляции.
<1 because the further away the imaginary gold is, the cheaper it is. The ratio of coefficients E and
представляет собой нерешенную проблему тысячелетия и оставляет простор для творчества.
Не думайте, что наш бот всегда будет бежать к ближайшему золоту.
Допустим, слева на расстоянии 5 клеток у нас одно золото и далее пустое место, а справа два золота на расстоянии 6 и 7. Так как настоящее золото более ценно, чем мнимое, то бот пойдет Направо.
Прежде чем перейти к более интересным стратегиям, сделаем еще одно усовершенствование.
В игре гравитация тянет игрока вниз, и подняться он может только по лестнице.
Это означает, что золото, которое расположено выше, должно цениться выше.
Если высота от верхней строки вниз, то вы можете умножить значение золота (с вертикальной координатой y) на значение 
.
Для коэффициента 
был придуман новый термин «коэффициент вертикальной инфляции», по крайней мере, он не используется экономистами и хорошо отражает суть.
Усложняем стратегии
Одно золото мы разобрали, надо со всем золотом что-то делать, а тяжелую математику затягивать не хочется.Есть очень изящное, простое и неправильное (в строгом смысле) решение - если одно золото создает вокруг себя «поле» значения, то давайте просто сложим все поля значений из всех ячеек с золотом в одну матрицу и будем использовать ее как стратегия.
Да, это не оптимальное решение, но несколько единиц золота на средней дистанции могут быть более ценными, чем одна вблизи.
Однако новое решение порождает новые проблемы – новая матрица значений может содержать локальные максимумы, вблизи которых нет золота.
Поэтому наш бот может в них попасть и не захочет уходить — а значит, нам нужно добавить обработчик, который проверяет, что бот находится в локальном максимуме стратегии и остается на месте в конце хода.
И теперь у нас есть инструмент борьбы с зависаниями — отменить эту стратегию на N ходов и временно вернуться к стратегии ближайшего золота.
Довольно забавно наблюдать, как застрявший бот меняет стратегию и начинает непрерывно идти вниз, съедая все находящееся поблизости золото; на нижних этажах карты бот приходит в себя и пытается подняться наверх.
«Такие доктор Джекил и мистер Хайд.
Стратегия противоречит тактике
Вот наш бот приближается к золоту под полом:
Оно уже попадает в оптимизирующий алгоритм, остаётся сделать 3 шага вправо, прорезать дыру справа и прыгнуть в неё, а дальше гравитация всё сделает сама.
Что-то вроде этого: 
Но бот зависает на месте.
Отладка показала, что ошибки нет: бот решил, что оптимальная стратегия — подождать один ход, а затем следовать по указанному маршруту и забрать золото на последнем анализируемом шаге.
В первом случае он получает выигрыш от полученного золота и выигрыш от мнимого золота (на последней анализируемой итерации он находится именно в той ячейке, где было золото), а во втором - только от реального золота (пусть и ход ранее), но для выигрыша там уже нет необходимости в стратегии, потому что место для золота гнилое и неперспективное.
Ну, а следующим ходом он снова решает передохнуть на один ход; мы уже сталкивались с подобными проблемами.
Пришлось доработать стратегию - так как мы помнили все съеденное золото на этапе анализа, то из общей матрицы стратегического значения мы вычитали карты стоимости съеденного золота, тем самым стратегия учитывала достижение тактики (можно было вычислить значение и иначе - складывая матрицы только для целого золота, но это вычислительно сложнее, ведь золота на карте гораздо больше, чем мы можем съесть за 8 ходов).
Но на этом наши мучения не закончились.
Предположим, что матрица стратегических ценностей имеет локальный максимум и бот приближается к нему за 7 ходов.
Пойдёт ли бот на него зависать? Нет, потому что для любого маршрута, в котором бот доберется до локального максимума за 8 ходов, выигрыш будет одинаковым.
Старая добрая прокрастинация.
Причина этого в том, что стратегический выигрыш никак не зависит от того, в какой момент мы окажемся в клетке.
Первое, что приходит на ум — оштрафовать бота за простой, но от бессмысленного хождения влево/вправо это никак не помогает.
Необходимо лечить первопричину — учитывать стратегический выигрыш на каждом ходу (как разницу между стратегической ценностью нового и текущего состояния), уменьшая его с течением времени на множитель.
Те.
ввести дополнительный член в выигрышное выражение: 
значение целевой функции при последнем обычно принимается равным нулю: 
.
Поскольку выигрыш обесценивается с каждым ходом путем умножения на коэффициент, это заставит нашего бота быстрее накапливать стратегический выигрыш и устранит наблюдаемую проблему.
Непроверенная стратегия
Я не проверял эту стратегию на практике, но она выглядит многообещающе.
- Поскольку мы знаем все расстояния между золотыми точками и расстояния между золотом и игроком, мы можем найти цепочку золотых ячеек игрока-N (где N мало, например 5 или 6), которая имеет наименьшую длину.
Даже на самый простой поиск времени будет достаточно.
- Выберите первое золото в этой цепочке и используйте его поле значения в качестве матрицы стратегии.
Окончательные улучшения
После того, как мы научились «растекаться» по карте, давайте проведем аналогичное «распространение» от каждого монстра в течение нескольких ходов и найдем все клетки, в которых может оказаться монстр, а также количество ходов, в которых он окажется.сделай это.
Это позволит игроку совершенно безопасно пролезть по трубе над головой монстра.
И последний момент – при расчете стратегии и мнимой стоимости золота мы не учитывали положение остальных игроков, просто «стирая» их при анализе карты.
Оказывается, отдельные замороженные идиоты могут блокировать доступ к целым регионам, поэтому был добавлен дополнительный процессор для отслеживания замороженных противников и замены их бетонными блоками при анализе.
Особенности реализации
Поскольку основной алгоритм рекурсивный, необходимо иметь возможность быстро изменять объекты состояния и возвращать их в исходное состояние для дальнейшей модификации.Я использовал Java, язык сбора мусора, и итерация миллионов изменений, связанных с созданием недолговечных объектов, может привести к множественным сборкам мусора за один ход игры, что может оказаться фатальным с точки зрения производительности.
Поэтому вам нужно быть предельно осторожным с используемыми вами структурами данных; Я использовал только массивы и списки.
Ну или используйте проект Валгала на свой страх и риск :)
Исходный код и игровой сервер
Исходный код можно найти здесь на GitHub .Не судите строго, многое делалось на скорую руку.
Игровой сервер проекта наслаждаться предоставит инфраструктуру для запуска ботов и мониторинга игры.
На момент создания текущей версией была версия 1.0.26.
Запустить сервер можно следующей строкой: call mvn -DMAVEN_OPTS=-Xmx1024m -Dmaven.test.skip=true clean jetty:run-war -Dcontext=another-context -Ploderunner
Сам проект чрезвычайно интересен, предоставляя игры на любой вкус.
Заключение
Если ты прочитал все это до конца без предварительной подготовки и все понял, то ты редкий человек.Теги: #игры #Разработка игр #Алгоритмы #искусственный интеллект #java #боты
-
Качества Ит-Директора
19 Dec, 24 -
Беспроводной Привод Mblok На Kickstarter
19 Dec, 24 -
Как Сжать Плоского Кота
19 Dec, 24 -
Цифровые Мероприятия В Москве С 23 По 29 Мая
19 Dec, 24
