Когда я начал играть в BoxWorld (игра типа Sokoban) первые 20-30 уровней было интересно, но дальше сложность и однообразие стали перевешивать и я решил писать бота. Никакого хитрого алгоритма решения придумать не смог, поэтому писал брутфорс. Писал на C#.
В первой версии перебирал движения самого грузчика (робота). Перебирал рекурсивно в глубину, для защиты от зацикливания хранил все пройденные варианты в массиве. Решение он выдавал в виде строки, указывающей в каком порядке нажимать кнопки в игре. Эту последовательность я загружал в программу MacroExpress, а она уже посылала нажатия окну игры. Регулируя паузы между отправкой нажатий можно было смотреть прохождение уровней на удобной скорости.
Бот решил несколько первых уровней и на очередном застрял на пару суток. Этот уровень был раза в 2 больше предыдущего, но время поиска решений росло экспоненциально. Так и не дождавшись ответа, я стал писать вторую версию. Движения робота заменил на движения ящиков, т.о. уже не надо хранить ходы пути робота от одного ящика к другому. На каждом ходу я определял до каких ящиков может сейчас добраться робот и в какую сторону толкнуть.
Тогда бот решил несколько следующих уровней и опять застрял. Потом было еще несколько версий:
— добавил ограничение глубины рекурсии, полагая, что большинство уровней можно решить менее чем за 100 движений ящиков;
— пометил на карте статичные тупиковые места, например угол или первый ряд вдоль ровной стены, т.к. потом будет невозможно вытащить оттуда ящик;
— добавил простейший анализ хода и отбрасывание очевидных динамических тупиков типа сдвигание квадрата из 4 ящиков;
— хранение координат всех предыдущих ходов заменил на хранение их хэшей, чтоб больше влазило в память и было быстрее искать;
Все это позволило продвинуться еще на несколько уровней, но стало понятно, что сложность решений сильно увеличивается с каждым уровнем. Тогда я выбрал самый крупный уровень — 86. Уж если бот решит его, то с остальными справится легко.
Итак, уровень 86.
![](https://habrastorage.org/r/w780q1/getpro/habr/post_images/d11/c4e/597/d11c4e5973aaa56ce71542e75a222ca5.jpg)
Он содержит 46 ящиков и 156 клеток поля. При этом 40 клеток это статичные тупиковые места, итого 116 клеток на которые можно двигать ящик. Значит, число разных вариантов не будет превышать 116^46 = 92271483792519010208299118408158326223759549834325815837590809967385695915673894137078445244416. Да, это число из 95 цифр. Оно ~= 9,2e+94. Максимальное число ходов в этом случае нет смысла учитывать т.к. такая оценка оказалась еще больше: допустим максимум ходов = 100, и в среднем на каждом ходу можно толкать каждый ящик хотя бы в одном направлении из четырех, тогда количество вариантов не будет превышать (46*1)^100 ~= 1,9e+166.
Дополнение об эвристиках:
— статичные тупики
![](https://habrastorage.org/r/w1560/getpro/habr/post_images/179/9f3/07c/1799f307c534c9c0825c8ad77e6276d8.png)
Понятно, что если задвинуть ящик на любое место помеченное красным маркером, то потом уже будет невозможно оторвать его от стены чтобы толкать к месту назначения. Такие места я заранее маркирую на карте и бот не делает такие ходы в процессе перебора.
— динамические тупики
![](https://habrastorage.org/r/w1560/getpro/habr/post_images/d98/42a/f95/d9842af95d0a0ab1ac242849788c14eb.png)
Понятно, что если сдвинуть 4 ящика квадратом (в различных сочетаниях с ящиками и стенами), то потом уже будет невозможно оторвать их друг от друга. Бот анализирует каждый ход и не делает ходы, приводящие к такому квадрату.
Более сложных пока не придумал.
Конечно, реальных вариантов будет гораздо меньше первой оценки из-за отсечения динамических тупиков, наверное, на несколько порядков. Но даже если взять половину порядков этого числа (92271483792519010208299118408158326223759549834) и хранить состояние каждого хода всего в одном байте, то потребуется 83920425634022658603 терабайт.
Тут-то я понял, что «еще подождать и бот переберет все ходы» как на первых уровнях уже не получится. Надо что-то кардинально менять в алгоритме, на каждом ходу проводить более сложный и долгий анализ, но зато отсекать бОльшие поддеревья вариантов. Но как именно это сделать пока не знаю… может Вы сможете мне посоветовать? Использовать какие-то приемы из области графов, муравьиные алгоритмы, нейронные сети?
В первой версии перебирал движения самого грузчика (робота). Перебирал рекурсивно в глубину, для защиты от зацикливания хранил все пройденные варианты в массиве. Решение он выдавал в виде строки, указывающей в каком порядке нажимать кнопки в игре. Эту последовательность я загружал в программу MacroExpress, а она уже посылала нажатия окну игры. Регулируя паузы между отправкой нажатий можно было смотреть прохождение уровней на удобной скорости.
Бот решил несколько первых уровней и на очередном застрял на пару суток. Этот уровень был раза в 2 больше предыдущего, но время поиска решений росло экспоненциально. Так и не дождавшись ответа, я стал писать вторую версию. Движения робота заменил на движения ящиков, т.о. уже не надо хранить ходы пути робота от одного ящика к другому. На каждом ходу я определял до каких ящиков может сейчас добраться робот и в какую сторону толкнуть.
Тогда бот решил несколько следующих уровней и опять застрял. Потом было еще несколько версий:
— добавил ограничение глубины рекурсии, полагая, что большинство уровней можно решить менее чем за 100 движений ящиков;
— пометил на карте статичные тупиковые места, например угол или первый ряд вдоль ровной стены, т.к. потом будет невозможно вытащить оттуда ящик;
— добавил простейший анализ хода и отбрасывание очевидных динамических тупиков типа сдвигание квадрата из 4 ящиков;
— хранение координат всех предыдущих ходов заменил на хранение их хэшей, чтоб больше влазило в память и было быстрее искать;
Все это позволило продвинуться еще на несколько уровней, но стало понятно, что сложность решений сильно увеличивается с каждым уровнем. Тогда я выбрал самый крупный уровень — 86. Уж если бот решит его, то с остальными справится легко.
Итак, уровень 86.
![](https://habrastorage.org/getpro/habr/post_images/d11/c4e/597/d11c4e5973aaa56ce71542e75a222ca5.jpg)
Он содержит 46 ящиков и 156 клеток поля. При этом 40 клеток это статичные тупиковые места, итого 116 клеток на которые можно двигать ящик. Значит, число разных вариантов не будет превышать 116^46 = 92271483792519010208299118408158326223759549834325815837590809967385695915673894137078445244416. Да, это число из 95 цифр. Оно ~= 9,2e+94. Максимальное число ходов в этом случае нет смысла учитывать т.к. такая оценка оказалась еще больше: допустим максимум ходов = 100, и в среднем на каждом ходу можно толкать каждый ящик хотя бы в одном направлении из четырех, тогда количество вариантов не будет превышать (46*1)^100 ~= 1,9e+166.
Дополнение об эвристиках:
— статичные тупики
![](https://habrastorage.org/getpro/habr/post_images/179/9f3/07c/1799f307c534c9c0825c8ad77e6276d8.png)
Понятно, что если задвинуть ящик на любое место помеченное красным маркером, то потом уже будет невозможно оторвать его от стены чтобы толкать к месту назначения. Такие места я заранее маркирую на карте и бот не делает такие ходы в процессе перебора.
— динамические тупики
![](https://habrastorage.org/getpro/habr/post_images/d98/42a/f95/d9842af95d0a0ab1ac242849788c14eb.png)
Понятно, что если сдвинуть 4 ящика квадратом (в различных сочетаниях с ящиками и стенами), то потом уже будет невозможно оторвать их друг от друга. Бот анализирует каждый ход и не делает ходы, приводящие к такому квадрату.
Более сложных пока не придумал.
Конечно, реальных вариантов будет гораздо меньше первой оценки из-за отсечения динамических тупиков, наверное, на несколько порядков. Но даже если взять половину порядков этого числа (92271483792519010208299118408158326223759549834) и хранить состояние каждого хода всего в одном байте, то потребуется 83920425634022658603 терабайт.
Тут-то я понял, что «еще подождать и бот переберет все ходы» как на первых уровнях уже не получится. Надо что-то кардинально менять в алгоритме, на каждом ходу проводить более сложный и долгий анализ, но зато отсекать бОльшие поддеревья вариантов. Но как именно это сделать пока не знаю… может Вы сможете мне посоветовать? Использовать какие-то приемы из области графов, муравьиные алгоритмы, нейронные сети?