19 October 2011

Бот для игры в Sokoban брутфорсом

Game development
Sandbox
Когда я начал играть в BoxWorld (игра типа Sokoban) первые 20-30 уровней было интересно, но дальше сложность и однообразие стали перевешивать и я решил писать бота. Никакого хитрого алгоритма решения придумать не смог, поэтому писал брутфорс. Писал на C#.

В первой версии перебирал движения самого грузчика (робота). Перебирал рекурсивно в глубину, для защиты от зацикливания хранил все пройденные варианты в массиве. Решение он выдавал в виде строки, указывающей в каком порядке нажимать кнопки в игре. Эту последовательность я загружал в программу 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 терабайт.

Тут-то я понял, что «еще подождать и бот переберет все ходы» как на первых уровнях уже не получится. Надо что-то кардинально менять в алгоритме, на каждом ходу проводить более сложный и долгий анализ, но зато отсекать бОльшие поддеревья вариантов. Но как именно это сделать пока не знаю… может Вы сможете мне посоветовать? Использовать какие-то приемы из области графов, муравьиные алгоритмы, нейронные сети?
Tags:botgamebruteforceSokobanBoxWorldбот
Hubs: Game development
+29
6.1k 21
Comments 35
Popular right now
Senior Game Designer (Playable Ads)
from 120,000 ₽AllcorrectRemote job
Full-stack web developer
from 150,000 to 300,000 ₽Rubrain.comRemote job
Hyperscale - Performance Engineer
from 150,000 to 350,000 ₽Rubrain.comRemote job
Business Development Manager
from 60,000 to 270,000 ₽EVEN LabМосква
Top of the last 24 hours