Когда я начал играть в BoxWorld (игра типа Сокобана), первые 20-30 уровней были интересны, но потом сложность и однообразие начали перевешивать и я решил написать бота.
Я не смог придумать ни одного хитрого алгоритма решения, поэтому написал перебор.
Написал на С#.
В первом варианте я проделывал движения самого погрузчика (робота).
Я выполнил глубокую рекурсивную итерацию и, чтобы защититься от циклического повторения, сохранил все переданные параметры в массиве.
Решение он дал в виде строки, указывающей в каком порядке нажимать кнопки в игре.
Я загрузил эту последовательность в программу MacroExpress, и она уже отправляла клики в окно игры.
Регулируя паузы между отправкой кликов, можно было наблюдать за прохождением уровней на удобной скорости.
Бот прошел первые несколько уровней и застрял на следующем на пару дней.
Этот уровень был в 2 раза выше предыдущего, но время поиска решения росло в геометрической прогрессии.
Не дожидаясь ответа, я начал писать вторую версию.
Движения робота были заменены перемещениями ящиков, т.е.
больше нет необходимости хранить путь робота от одного ящика к другому.
На каждом повороте я определял, до каких ящиков теперь может дотянуться робот и в каком направлении толкать.
Затем бот прошел следующие несколько уровней и снова застрял.
Потом было еще несколько версий: - добавлен предел глубины рекурсии, полагая, что большинство уровней можно решить менее чем за 100 ходов по ящику; — отмечены на карте статические тупиковые места, например, угол или первый ряд вдоль ровной стены, потому что тогда вынуть ящик оттуда будет невозможно; — добавлен простой анализ хода и отбрасывание очевидных динамических тупиков типа перемещения квадрата из 4 ящиков; — Я заменил хранение координат всех предыдущих ходов на хранение их хешей, чтобы больше помещалось в память и было быстрее искать; Все это позволило нам продвинуться еще на несколько уровней, но стало понятно, что сложность решений сильно возрастает с каждым уровнем.
Тогда я выбрал самый большой уровень — 86. Если бот его решит, то с остальным он справится легко.
Итак, 86 уровень.
Он содержит 46 блоков и 156 ячеек полей.
При этом 40 ячеек — это статические тупиковые места, всего 116 ячеек, по которым можно перемещать ящик.
Это означает, что количество различных вариантов не превысит 116^46 = 92271483792519010208299118408158326223759549834325815837590809967385695915673894137078445244416. Да, это число.
из 95 чисел Это ~= 9.2e+94. В данном случае нет смысла учитывать максимальное количество ходов, потому что эта оценка оказалась еще больше: допустим максимальное количество ходов = 100, и в среднем на каждом ходу можно задвинуть каждый ящик минимум одно направление из четырех, то количество вариантов не превысит (46*1)^100 ~= 1.9e+166 .
Дополнение по поводу эвристики:
- статические тупики 
Понятно, что если вы толкнете ящик в любое место, отмеченное красным маркером, то потом его невозможно будет оторвать от стены, чтобы подтолкнуть к месту назначения.
Я заранее отмечаю такие места на карте и бот в процессе поиска таких ходов не делает.
- динамические тупики 
Понятно, что если переместить 4 ящика в квадрате (в различных комбинациях с ящиками и стенами), то оторвать их друг от друга будет невозможно.
Бот анализирует каждый ход и не делает ходов, приводящих к такому квадрату.
Ничего более сложного я пока не придумал.
Конечно, реальные варианты будут намного меньше первой оценки за счет отсечения динамических тупиков, вероятно, на несколько порядков.
Но даже если мы возьмем половину порядков этого числа (92271483792519010208299118408158326223759549834) и будем хранить состояние каждого хода всего в одном байте, нам понадобится 83920425634022658603 терабайта.
Именно тогда я понял, что «просто подожди еще немного и бот пройдет все ходы» как на первых уровнях уже не получится.
Необходимо что-то радикально изменить в алгоритме, проводить более сложный и длительный анализ каждого хода, но при этом отсекать более крупные поддеревья вариантов.
Но я пока точно не знаю, как это сделать.
может быть вы мне подскажете? Используете какие-нибудь приемы из области графов, муравьиных алгоритмов, нейронных сетей? Теги: #бот #игра #грубая сила #сокобан #BoxWorld #бот #Разработка игр
-
Один Алгоритм Комбинаторной Генерации
19 Oct, 24
