Comments 35
UFO just landed and posted this here
у меня с первого раза получилось 1107. я примерно представляю как уменьшить процентов на 20, но сотни точно не хватит.
>Далеко не факт, что 100 ходов хватит (у вас написано, что рекорд = 444).
Срываю покровы — на каком-то сайте находил таблицу всех уровней с указанием самого короткого решения. И почти все уровни уложились в 100 ходов, исключений было 2 или 3, и данный уровень один из этих исключений. Можно конечно эту границу поднимать, но проблема в том, что даже при 100 ходах оценка вариантов уже получается недостижимой.
>Какие эвристики у вас уже реализованы?
Добавил в статью «Дополнение об эвристиках».
Срываю покровы — на каком-то сайте находил таблицу всех уровней с указанием самого короткого решения. И почти все уровни уложились в 100 ходов, исключений было 2 или 3, и данный уровень один из этих исключений. Можно конечно эту границу поднимать, но проблема в том, что даже при 100 ходах оценка вариантов уже получается недостижимой.
>Какие эвристики у вас уже реализованы?
Добавил в статью «Дополнение об эвристиках».
Самое простое улучшение ставить ящики сначала ближе к стене, то есть те конечные точки которые ближе к стене. Сложность упадет на пару порядков.
Небольшое замечание сканировать надо от углов карты по спирали.
Дело в том, что сейчас бот работает в терминах «сдвинуть 1й ящик влево». Как от этого алгоритма перейти к терминам «передвинуть 1й ящик в правый нижний угол карты за 20 движений» мне пока непонятно… тем более что возможно придется передвинуть ящик с конечной позиции дальше в противоположном направлении от стены чтобы освободить место для маневра.
Народ вообще его решает перебором с оценочной функцией. Т. е. на каждом ходу варианты обрабатывает специальная функа, которая пытается «угадать» наилучший. От качества оценочной функции зависит количество ошибок, и, как следствие, скорость работы.
UFO just landed and posted this here
Перебор тут не пойдет, нужно смотреть в сторону Machine Learning. Пока ничего подсказать не смогу, сам начал только тему изучать, но задача интересная, возьму на вооружение.
Решил немного погуглить на дошел до этой страницы:
sokobano.de/wiki/index.php?title=Solver_Statistics
Там перечислены программы для решения различных клонов Sokoban :). Для BoxWorld лишь одна программа смогла решить 98 из 100 уровней, остальные — сильно меньше :). Я думаю, это должно дать вам некоторую пищу для размышлений :)
sokobano.de/wiki/index.php?title=Solver_Statistics
Там перечислены программы для решения различных клонов Sokoban :). Для BoxWorld лишь одна программа смогла решить 98 из 100 уровней, остальные — сильно меньше :). Я думаю, это должно дать вам некоторую пищу для размышлений :)
Какую именно пищу? Что не стоит даже начинать? :)
Ну, что самым продуктивным, по всей видимости, было бы поговорить с разработчиками этих программ и вникнуть в их алгоритмы перед тем, как пытаться решить эту задачу самостоятельно. И что хабр, при всём моём уважении к нему, не является самым лучшим местом для поиска помощников в решении сложных математических задач :)
Интересно, а как и кто составляет начальную позицию?
Какая позиция для фиксированного размера поля приведет к максимальному минимально возможному числу ходов в решении?
Какая позиция для фиксированного размера поля приведет к максимальному минимально возможному числу ходов в решении?
Два ящика рядом у стены не сдвигаемы.
У стены ящик можно сдвинуть только если есть поворот стены внешним углом (ниша в стене) и ниша длиннее одной клетки
квадрат 3*3 с дыркой в центре приводит к прямоугольнику 2*3. Не сдвигаем.
Похоже не только квадрат, но и прямоугольник 3*N, но на доказательство пока нет времени, если есть необходимость могу подоказывать.
У стены ящик можно сдвинуть только если есть поворот стены внешним углом (ниша в стене) и ниша длиннее одной клетки
квадрат 3*3 с дыркой в центре приводит к прямоугольнику 2*3. Не сдвигаем.
Похоже не только квадрат, но и прямоугольник 3*N, но на доказательство пока нет времени, если есть необходимость могу подоказывать.
рамка 3*3 не сдвигаема, 4*4 вполне. Я имел ввиду не монолитный прямоугольник, а с выпавшим центром.
Упс, промазал. Сори. Отвечал md55 на вот это
Тогда даже не рамка а «недо-рамка» — минимальным шаблоном будет рамка без 2х ящиков:
И ее можно увеличивать по длине, т.е. недо-рамки 3*N будут не сдвигаемы.
>рамка 3*3 не сдвигаема, 4*4 вполне
Я также не нашел способа раздвинуть рамку 4*4, можете показать решение?
И ее можно увеличивать по длине, т.е. недо-рамки 3*N будут не сдвигаемы.
>рамка 3*3 не сдвигаема, 4*4 вполне
Я также не нашел способа раздвинуть рамку 4*4, можете показать решение?
Кмк, можно попробовать реализовать A*-поиск на графе состояний поля. Состояние поля — расположение ящиков на уровне. Ребра графа — возможные передвижения ящиков. Метрика для А* — ну например сумма максимальных расстояний между каждым ящиком и 'конечными' ячейками.
Очевидная мысль, врядли еще никто не пробовал.
Очень интересная мысль.
Но графы это далекая от меня область, что посоветуете почитать по реализации этого алгоритма?
Но графы это далекая от меня область, что посоветуете почитать по реализации этого алгоритма?
Ну начать можно с википедии, алгоритм сам по себе не очень сложный. Еще о нем говорили в идущем сейчас курсе дистанционного обучения от Стенфорда Ai-class. Юнит 2, видео 23, но лучше весь юнит с начала посмотреть.
Вопрос в том, влезет ли реализация в память. Тут ответить трудно. Но, думается, если оптимизировать хорошо, то должна влезть. Например запретив делать тупиковые ходы, как вы уже сделали.
На счет метрики я ошибся, должна быть сумма минимальных расстояний. Можно составить карту метрики, то есть определить для каждой пустой клетки поля минимальное количество ходов, за которое из нее можно довести ящик до какой-либо конечной клетки при отсутствии других ящиков. Тут можно будет задать клеткам около стены, к которой ящики нельзя подводить, бесконечные значения метрики — тогда A* будет избегать таких состояний поля. Если составить карту, тогда значение метрики для определенного состояния будет вычисляться просто как сумма значений карты метрики для ячеек, в которых располагаются ящики.
Вопрос в том, влезет ли реализация в память. Тут ответить трудно. Но, думается, если оптимизировать хорошо, то должна влезть. Например запретив делать тупиковые ходы, как вы уже сделали.
На счет метрики я ошибся, должна быть сумма минимальных расстояний. Можно составить карту метрики, то есть определить для каждой пустой клетки поля минимальное количество ходов, за которое из нее можно довести ящик до какой-либо конечной клетки при отсутствии других ящиков. Тут можно будет задать клеткам около стены, к которой ящики нельзя подводить, бесконечные значения метрики — тогда A* будет избегать таких состояний поля. Если составить карту, тогда значение метрики для определенного состояния будет вычисляться просто как сумма значений карты метрики для ячеек, в которых располагаются ящики.
Да, это вы хорошо придумали с количеством ходов до места. Я сначала хотел брать просто расстояние по прямой без учета стен… хотя конкретно для этого уровня эти числа будут примерно равны, но для других могут значительно отличаться.
>Вопрос в том, влезет ли реализация в память.
А разве это так критично? Виртуальной-то памяти много, пусть свопается если не влазит.
Или даже лучше перенести списки вариантов из массива памяти в nosql key-value хранилище типа Redis'а, которое также добавит персистентность между запусками бота. А то сейчас при каждом запуске перебор начинается заново.
Прочитал википедию, но с первого раза не все понял, буду перечитывать. Там метрику определяют как f(x) = g(x) + h(x). Правильно я понимаю что вы предлагаете сделать g(x)=0, а h(x)=сумма_минимальных_расстояний(х)?
И почему-то в википедии на 2й анимации точки открываются по всему фронту а не только ближайшие к цели.
>Вопрос в том, влезет ли реализация в память.
А разве это так критично? Виртуальной-то памяти много, пусть свопается если не влазит.
Или даже лучше перенести списки вариантов из массива памяти в nosql key-value хранилище типа Redis'а, которое также добавит персистентность между запусками бота. А то сейчас при каждом запуске перебор начинается заново.
Прочитал википедию, но с первого раза не все понял, буду перечитывать. Там метрику определяют как f(x) = g(x) + h(x). Правильно я понимаю что вы предлагаете сделать g(x)=0, а h(x)=сумма_минимальных_расстояний(х)?
И почему-то в википедии на 2й анимации точки открываются по всему фронту а не только ближайшие к цели.
Не, g(x) — количество ходов от начального состояния до состояния x.
Про вторую анимацию больше написано на английской вики, у них там похоже функция стоимости хитро выбрана. Хотя действительно, что то странное творится.
Про вторую анимацию больше написано на английской вики, у них там похоже функция стоимости хитро выбрана. Хотя действительно, что то странное творится.
А конструкция только из красных ящиков решается? ;)
Когда желтый ящик передвигают на место назначения он становится красным.
нет, я имел ввиду другое — можно ли забить задачу на этапы?
например сперва решить задачу с перетаскиванием какой-то группы ящиков (например только тех ящиков, кторые сейчас красные).
поэтапный брутфорс должен быть эффективнее. Ведь очевидно, что если мы растащили N ящиков и при этом не создали помех для растаскивания остальных M, то 90% задачи уже решено.
Тут, правда. нужна эвристика на эпик фейлы в «landing zone»…
например сперва решить задачу с перетаскиванием какой-то группы ящиков (например только тех ящиков, кторые сейчас красные).
поэтапный брутфорс должен быть эффективнее. Ведь очевидно, что если мы растащили N ящиков и при этом не создали помех для растаскивания остальных M, то 90% задачи уже решено.
Тут, правда. нужна эвристика на эпик фейлы в «landing zone»…
Sign up to leave a comment.
Бот для игры в Sokoban брутфорсом