Рубрика «поиск в ширину»

Пару месяцев назад мне наконец пришлось признать, что я недостаточно умён, чтобы пройти некоторые уровни головоломки Snakebird. Единственным способом вернуть себе часть самоуважения было написание солвера. Так я мог бы притвориться, что создать программу для решения головоломки — это почти то же самое, что и решить её самому. Код получившейся программы на C++ выложен на Github. Основная часть рассматриваемого в статье кода реализована в search.h и compress.h. В этом посте я в основном буду рассказывать об оптимизации поиска в ширину, который бы потребовал 50-100 ГБ памяти, чтобы он уместился в 4 ГБ.

Позже я напишу ещё один пост, в котором будет описана специфика игры. В этом посте вам нужно знать, что мне не удалось найти никаких хороших альтернатив грубому перебору (brute force), потому что ни один из привычных трюков не сработал. В игре множество состояний, потому что есть куча подвижных или толкаемых объектов, при этом важна форма некоторых из них, которая может меняться со временем. Не было никакой пригодной консервативной эвристики для алгоритмов наподобие A*, позволяющих сузить пространство поиска. Граф поиска был ориентированным и заданным неявно, поэтому одновременный поиск в прямом и обратном направлении оказался невозможным. Единственный ход мог изменить состояние множеством несвязанных друг с другом способов, поэтому не могло пригодиться ничего наподобие хеширования Зобриста.

Приблизительные подсчёты показали, что в самой большой головоломке после устранения всех симметричных положений будет порядка 10 миллиардов состояний. Даже после упаковки описания состояний с максимальной плотностью размер состояния составлял 8-10 байт. При 100 ГБ памяти задача оказалась бы тривиальной, но не для моей домашней машины с 16 ГБ памяти. А поскольку Chrome нужно из них 12 ГБ, мой настоящий запас памяти ближе к 4 ГБ. Всё, что будет превышать этот объём, придётся сохранять на диск (старый и ржавый винчестер).
Читать полностью »