В FreeCell видны все карты, поэтому игра хорошо подходит для того, чтобы компьютер искал решение. Здесь мы просто расскажем, как компьютер решает FreeCell. Для этой страницы мы написали программу, работающую по тем же правилам, что и приложение «Свободная ячейка», и испытали её.
Перебор: делаем ход и смотрим вперёд
Компьютер, как и человек, проверяет, что будет, если сделать «этот» ход. Разница в числе проверок.
- Выписать все ходы, возможные в текущей позиции (в свободную ячейку, на карту в столбце, на базовую ячейку и так далее).
- Сделать один из ходов и получить новую позицию.
- В этой позиции снова выписать все возможные ходы.
- Если найдена позиция, где на базовые ячейки выложено 52 карты, последовательность ходов до неё и есть ответ.
Такое движение «от позиции к позиции, с ветвлением» называется перебором.
Приём 1: не проверять одну позицию дважды
В FreeCell часто бывает, что разный порядок ходов приводит к одной и той же позиции. Если переложить карту вправо, а потом влево, получится прежняя позиция. Если запоминать проверенные позиции и не проверять повторно ту же самую, лишней работы становится гораздо меньше.
Кроме того, решение одинаково и у позиций, различающихся только порядком столбцов, и у позиций, различающихся только порядком карт в свободных ячейках. Если считать их одной позицией, проверок станет ещё меньше.
Приём 2: сначала проверять перспективные позиции
Если проверять все позиции подряд, уйдёт слишком много времени. Поэтому позициям ставят оценки: «много карт выложено на базовые ячейки», «мало карт лежит поверх карты, которую нужно выложить следующей», «свободные ячейки пусты», и сначала проверяют самые перспективные.
Когда в нашей программе решали расклад № 1 из FreeCell в Windows, решение в 110 ходов нашлось после проверки 843 позиций. Человеку это трудно, а компьютеру — мгновение. Найденная последовательность не обязательно самая короткая (ходы и число ходов до победы).
Как доказать, что решения нет
Если решение найдено, расклад решается. А как доказать, что решения нет?
Ответ: проверить все позиции, до которых можно добраться. Если какой бы ход ни сделали, новых позиций уже не появляется, а позиции с 52 выложенными картами среди них нет, значит, расклад не решается.
Расклад № 11982 из FreeCell в Windows известен как нерешаемый. Наша программа тоже проверила все достижимые позиции (около 95 тысяч), включая ходы возврата с базовых ячеек, и решения не нашла (почти любой расклад FreeCell решается).
Правило переноса нескольких карт не влияет на решаемость
В приложении «Свободная ячейка» за раз переносят не больше «числа пустых свободных ячеек плюс один» карт, и пустой столбец это число не увеличивает (сколько карт можно переносить сразу). Но перенос нескольких карт можно разбить на ходы по одной карте через свободные ячейки и пустые столбцы. Достижимые позиции те же самые, поэтому решаются те же расклады. Меняется только подсчёт числа ходов.
Проверка раскладов в приложении «Свободная ячейка»
В приложении «Свободная ячейка» расклады каждый раз тасуются случайно. Автор решил на компьютере 100 000 случайных раскладов, а найденные решения прошёл до конца на тех же механизмах игры, что и в приложении. У всех 100 000 раскладов нашлось решение.
Но это не доказательство того, что «решается любой расклад». Среди непроверенных раскладов могут изредка оказаться нерешаемые.
Способ рассуждения, которым ищет решение компьютер, пригодится и человеку. Загляните и в статью Стратегия и секреты победы в FreeCell.
