AI на минималках: пишем свой Сокобан и учим компьютер его решать

[mattheus]

Спасибо за статью, самому в юности нравилась задача написания солвера для Сокобана. Подскажите, приходилось ли решать обратную задачу: построение уровней для игры, с неким критерием оптимальности, например:

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

Понятно, что критерии слабо формализованы, но суть их сводится к генерации «интересных и разнообразных» уровней. Есть ли общепринятые подходы к задачам генерации уровней для подобных головоломок?

[DaneSoul]

Нельзя ли пойти от обратного: нагенерировать уйму случайных уровней с нужным размером поля и числом ящиков и пройдя по ним солвером считать количество ходов для каждого, отсеивая уровни не удовлетворяющие запросу или не решаемые?

[neurocore]

Наверное можно алгоритмом коллапса волновой функции строить «приемлемые» позиции, которые в дальнейшем проверять солвером. Ну это так, с целью отбросить на раннем этапе заведомо непроходимые карты. На маленьких размерностях хватит наверное обычного рандома.

[egryaznov]

Задача интересная, можно попробовать нагенерировать случайно много уровней, затем генетическими алгоритмами отобрать нужные, и т.д. в цикле. Через n поколений получим самые подходящие уровни.

[ARad]

Решётка # это стена, через неё нельзя пройти и продвинуть ящик.
Буква O это ящик.
Буква X это метка, куда нужно переместить ящик.
Собака @ означает игрока.
Точка. означает пустое место.
Буква G это ящик на метке.

Какая буква обозначает игрока на месте куда надо переместить ящик (X и @ для одной и той же клетки)?

[jaiprakash]

@. Это видно на анимации.

[andy_p]

1. Не нашёл решения 11-го уровня в конце статьи.
2. Хотелось бы иметь оценки скорости работы и объёма памяти для более сложных уровней.
3. Не вникал глубоко в код, поэтому вопрос — вершины в графе порождаются каждый раз динамически из родительской и сохраняются? Если сохраняются, то есть ли проверка, были ли мы в данной конфигурации? Сколько вершин в графе получается, когда решение найдено?
4. Что понимается под AI в данном алгоритме? Поиск пути A*?
5. «граф инцидентных клеток» — это какой-то неправильный термин. Лучше говорить о компонентах связности графа.

[egryaznov]

1. Добавил решение в спойлере.
2. Если брать BFS, то он будет за полиномиальное время со степенью, равной количеству меток. Поэтому чем больше меток, тем дольше выполнение.
3. Не совсем понял о чём вы. Да, проверка есть, мы храним множество посещённых вершин.
4. Под «AI» понимается BFS и A*, назвал статью «AI на минималках», т.к. это известные, чисто детерминированные алгоритмы без машинного обучения и прочих приблуд.

[egryaznov]

Количество меток конечно сильно ухудшает время работы, каждая метка это +1 к степени в асимптотике. Спасти может только А* с отрезанием заранее тупиковых ветвей.

[egryaznov]

На английкой вики в статье про сокобан пишут что апгрейд алгоритма A* до IDA* очень помогает: en.wikipedia.org/wiki/Sokoban#cite_note-9