В обычном пасьянсе карты просто тасуют и раздают, поэтому среди раскладов попадаются такие, что не решаются никак (Какой процент раскладов пасьянса выигрывается). В приложении Пасьянс «Клондайк» расклады для «Новой игры» заранее решает компьютер, и используются только те, что удалось решить до конца. Здесь мы просто расскажем, как это устроено.
1. Тасуем и раздаём
Сначала 52 карты хорошо тасуют и раздают так же, как в обычном пасьянсе. Пока это обычный расклад, и неизвестно, решается ли он.
2. Пробуем ходы по очереди
Затем компьютер пытается решить расклад. Это похоже на путь на ощупь по лабиринту.
- Записать все ходы, которые можно сделать в текущей позиции.
- Выбрать один из них, самый перспективный, и сделать его.
- В новой позиции снова повторить пункты 1 и 2.
- Когда ходов не остаётся, вернуться в предыдущую позицию и выбрать другой ход, который ещё не пробовали.
- Когда все 52 карты лежат на базовых стопках, последовательность ходов и есть «решение».
Компьютер решает, зная, какие карты закрыты. Человек играет иначе, но чтобы проверить, что «у расклада есть решение», этого достаточно.
Сначала пробуем перспективные ходы
Порядок, в котором пробуют ходы, строится по тем же соображениям, что и у людей. Например, сначала пробуют ходы, которые открывают закрытую карту, и ходы, которые отправляют на базовые стопки карты с маленькими числами. Так решение чаще находится быстрее. Но отложенные ходы не выбрасывают, при необходимости их тоже пробуют.
Одну позицию не проверяют дважды
Колоду можно проходить много раз, поэтому в одну и ту же позицию можно вернуться не раз. Поэтому приложение запоминает уже проверенные позиции и не идёт дальше, если снова в такую попадает.
3. Задаём пределы
У некоторых раскладов позиций для проверки очень много. Поэтому в приложении для одного расклада заданы пределы: 0,5 секунды, 50 тысяч позиций и 512 ходов.
Результатов три.
| Результат | Использовать? |
|---|---|
| Решение найдено | Да |
| Всё перепробовали, решения нет | Нет |
| Достигнут предел | Нет |
Расклад, где «достигнут предел», может на самом деле решаться, но мы не смогли это проверить, поэтому не используем. Важно различать «не решается» и «не удалось проверить до конца».
Когда на iPhone испытали набор из 100 определённых раскладов, при пределе 0,5 секунды решение нашлось у 41. Если увеличить предел до 2 секунд, получалось те же 41, и число не менялось.
4. Воспроизводим решение с начала и проверяем
Найденное решение ещё раз воспроизводят ход за ходом, начиная с раздачи, и проверяют.
- Все ли 52 карты на месте и нет ли одинаковых карт.
- Можно ли каждый ход сделать по правилам.
- Лежат ли в конце все 52 карты на базовых стопках.
Только то, что прошло все проверки, используют как «расклад, который можно решить». В приложении с самого начала есть 100 таких проверенных раскладов. Новые расклады тоже понемногу создаются и копятся, пока приложение открыто, чтобы не мешать игре. Для этого связь не нужна.
Что гарантируется
Приложение гарантирует, что «из позиции сразу после раздачи решение есть». В зависимости от ходов, выбранных по дороге, можно и зайти в тупик. Тогда можно вернуться кнопкой «Отмена» к развилке или начать заново кнопкой «Заново», и путь к победе всегда найдётся (Что делать, если пасьянс зашёл в тупик).
Решения, которые нашёл компьютер, включают обходные ходы и не самые короткие. О числе ходов в решениях рассказано в статье За сколько ходов можно выиграть.
