Comments 35
UFO landed and left these words here
у меня с первого раза получилось 1107. я примерно представляю как уменьшить процентов на 20, но сотни точно не хватит.
>Далеко не факт, что 100 ходов хватит (у вас написано, что рекорд = 444).
Срываю покровы — на каком-то сайте находил таблицу всех уровней с указанием самого короткого решения. И почти все уровни уложились в 100 ходов, исключений было 2 или 3, и данный уровень один из этих исключений. Можно конечно эту границу поднимать, но проблема в том, что даже при 100 ходах оценка вариантов уже получается недостижимой.

>Какие эвристики у вас уже реализованы?
Добавил в статью «Дополнение об эвристиках».
Самое простое улучшение ставить ящики сначала ближе к стене, то есть те конечные точки которые ближе к стене. Сложность упадет на пару порядков.
Небольшое замечание сканировать надо от углов карты по спирали.
Есть предположение составить с начало карту последовательности вставки ящиков на позиции, то есть какую позицию занять первую, вторую и т.д. Предыдущий комментарий частично решает эту проблему. Сложность упадет практически полностью.
Дело в том, что сейчас бот работает в терминах «сдвинуть 1й ящик влево». Как от этого алгоритма перейти к терминам «передвинуть 1й ящик в правый нижний угол карты за 20 движений» мне пока непонятно… тем более что возможно придется передвинуть ящик с конечной позиции дальше в противоположном направлении от стены чтобы освободить место для маневра.
Народ вообще его решает перебором с оценочной функцией. Т. е. на каждом ходу варианты обрабатывает специальная функа, которая пытается «угадать» наилучший. От качества оценочной функции зависит количество ошибок, и, как следствие, скорость работы.
Скорее просчитывается на N (10-20) шагов в глубь, и выбирается наилучший ход, и так на каждом шагу.
Особо заковыристые увы так не решаться уровни.
Могли бы вы дать пример такой функции?
Не могу придумать ничего кроме суммы расстояний от ящиков до ближайших мест назначения.
Предлагаю для начала попытаться упростить задачу. Например очевидно, что в начале надо сдвинуть один из 12 ящиков, при этом 2 из них сдвинуть нельзя (в углах). Дальше необходимо прописать алгоритм заполнения нужных мест. Например я бы сдвинул по 2 ящика сверху и снизу в нижние полости. А потом уже пробовать перебор.
Перебор тут не пойдет, нужно смотреть в сторону Machine Learning. Пока ничего подсказать не смогу, сам начал только тему изучать, но задача интересная, возьму на вооружение.
Решил немного погуглить на дошел до этой страницы:

sokobano.de/wiki/index.php?title=Solver_Statistics

Там перечислены программы для решения различных клонов Sokoban :). Для BoxWorld лишь одна программа смогла решить 98 из 100 уровней, остальные — сильно меньше :). Я думаю, это должно дать вам некоторую пищу для размышлений :)
Ну, что самым продуктивным, по всей видимости, было бы поговорить с разработчиками этих программ и вникнуть в их алгоритмы перед тем, как пытаться решить эту задачу самостоятельно. И что хабр, при всём моём уважении к нему, не является самым лучшим местом для поиска помощников в решении сложных математических задач :)
Интересно, а как и кто составляет начальную позицию?
Какая позиция для фиксированного размера поля приведет к максимальному минимально возможному числу ходов в решении?
Кстати да, всегда интересовал вопрос, как придумываются комбинации в головоломках.
Два ящика рядом у стены не сдвигаемы.

У стены ящик можно сдвинуть только если есть поворот стены внешним углом (ниша в стене) и ниша длиннее одной клетки

квадрат 3*3 с дыркой в центре приводит к прямоугольнику 2*3. Не сдвигаем.

Похоже не только квадрат, но и прямоугольник 3*N, но на доказательство пока нет времени, если есть необходимость могу подоказывать.
Любой прямоугольник 2*2 и более не сдвигаемый.
Добавил в статью «Дополнение об эвристиках».
рамка 3*3 не сдвигаема, 4*4 вполне. Я имел ввиду не монолитный прямоугольник, а с выпавшим центром.
Тогда даже не рамка а «недо-рамка» — минимальным шаблоном будет рамка без 2х ящиков:

И ее можно увеличивать по длине, т.е. недо-рамки 3*N будут не сдвигаемы.

>рамка 3*3 не сдвигаема, 4*4 вполне
Я также не нашел способа раздвинуть рамку 4*4, можете показать решение?
Вы правы, я ошибся (Ночью спать нужно, а не хабрачить). 4*4 тоже не двигается.
Кмк, можно попробовать реализовать A*-поиск на графе состояний поля. Состояние поля — расположение ящиков на уровне. Ребра графа — возможные передвижения ящиков. Метрика для А* — ну например сумма максимальных расстояний между каждым ящиком и 'конечными' ячейками.
Очень интересная мысль.
Но графы это далекая от меня область, что посоветуете почитать по реализации этого алгоритма?
Ну начать можно с википедии, алгоритм сам по себе не очень сложный. Еще о нем говорили в идущем сейчас курсе дистанционного обучения от Стенфорда Ai-class. Юнит 2, видео 23, но лучше весь юнит с начала посмотреть.

Вопрос в том, влезет ли реализация в память. Тут ответить трудно. Но, думается, если оптимизировать хорошо, то должна влезть. Например запретив делать тупиковые ходы, как вы уже сделали.

На счет метрики я ошибся, должна быть сумма минимальных расстояний. Можно составить карту метрики, то есть определить для каждой пустой клетки поля минимальное количество ходов, за которое из нее можно довести ящик до какой-либо конечной клетки при отсутствии других ящиков. Тут можно будет задать клеткам около стены, к которой ящики нельзя подводить, бесконечные значения метрики — тогда A* будет избегать таких состояний поля. Если составить карту, тогда значение метрики для определенного состояния будет вычисляться просто как сумма значений карты метрики для ячеек, в которых располагаются ящики.
Да, это вы хорошо придумали с количеством ходов до места. Я сначала хотел брать просто расстояние по прямой без учета стен… хотя конкретно для этого уровня эти числа будут примерно равны, но для других могут значительно отличаться.

>Вопрос в том, влезет ли реализация в память.
А разве это так критично? Виртуальной-то памяти много, пусть свопается если не влазит.
Или даже лучше перенести списки вариантов из массива памяти в nosql key-value хранилище типа Redis'а, которое также добавит персистентность между запусками бота. А то сейчас при каждом запуске перебор начинается заново.

Прочитал википедию, но с первого раза не все понял, буду перечитывать. Там метрику определяют как f(x) = g(x) + h(x). Правильно я понимаю что вы предлагаете сделать g(x)=0, а h(x)=сумма_минимальных_расстояний(х)?

И почему-то в википедии на 2й анимации точки открываются по всему фронту а не только ближайшие к цели.
Не, g(x) — количество ходов от начального состояния до состояния x.

Про вторую анимацию больше написано на английской вики, у них там похоже функция стоимости хитро выбрана. Хотя действительно, что то странное творится.
А что насчет памяти?
Может сразу есть смысл делать не А* а какой-то более экономичный алгоритм типа IDA*, MA*, SMA*, RBFS?
Какой из эвристических алгоритмов поиска самый лучший?
Тут, к сожалению, ничем не могу сходу помочь — опыта не очень много. Глянуль мельком — все модификации A* не сильно отличаются от него, так что можно реализовать для начала A*, а если он в память не влезет, то привести к одной из модификаций. Про RBFS не нашел инфы.
Когда желтый ящик передвигают на место назначения он становится красным.
нет, я имел ввиду другое — можно ли забить задачу на этапы?

например сперва решить задачу с перетаскиванием какой-то группы ящиков (например только тех ящиков, кторые сейчас красные).

поэтапный брутфорс должен быть эффективнее. Ведь очевидно, что если мы растащили N ящиков и при этом не создали помех для растаскивания остальных M, то 90% задачи уже решено.

Тут, правда. нужна эвристика на эпик фейлы в «landing zone»…
Only those users with full accounts are able to leave comments. Log in, please.