Узнайте, как ИИ-солверы оценивают ходы, предсказывают исход и улучшают выигрышные стратегии в пасьянсе.
ИИ-решатель для пасьянса — это вычислительная программа, которая принимает конкретный расклад пасьянса на вход и пытается найти выигрышную последовательность ходов — либо, если такой последовательности не существует, подтвердить, что данный расклад intrinsically невыигрышен. Термин «ИИ» здесь используется в широком смысле: на практике самые эффективные решатели пасьянса — это не нейросети и не современные системы машинного обучения, а скорее классические поисковые алгоритмы, усиленные предметно-
ИИ-решатель для пасьянса — это вычислительная программа, которая принимает конкретный расклад пасьянса на вход и пытается найти выигрышную последовательность ходов — либо, если такой последовательности не существует, подтвердить, что данный расклад intrinsically невыигрышен. Термин «ИИ» здесь используется в широком смысле: на практике самые эффективные решатели пасьянса — это не нейросети и не современные системы машинного обучения, а скорее классические поисковые алгоритмы, усиленные предметно-специфическими эвристиками и стратегиями отсечения, которые рано удаляют неперспективные цепочки ходов. Это различие важно, потому что слово «ИИ» подразумевает обучение на опыте, в то время как классические поисковые решатели работают на явных правилах, — но в сообществе любителей пасьянса оба типа всё равно называют ИИ-решателями, и оба дают стратегические инсайты, которые переносятся на человеческую игру.
Базовая операция любого решателя пасьянса одинакова: он представляет доску как состояние, то есть текущее расположение всех карт; генерирует все легальные ходы из этого состояния, то есть состояния-потомки; оценивает, какие из потомков наиболее перспективны, используя эвристическую функцию или полное переборное перечисление; и исследует потомков в порядке приоритета до тех пор, пока либо не будет достигнуто выигрышное состояние, где все карты лежат в основаниях, либо пока все состояния не будут подтверждены как проигрышные, то есть не окажутся тупиками без легальных ходов. Различия между архитектурами решателей заключаются в том, как именно они расставляют приоритеты между потомками, как находят и отсекают тупиковые ветви и как обрабатывают скрытую информацию в вариантах вроде Klondike, где закрытые карты создают проблему неполной информации, которую невозможно полностью разрешить чистым исчерпывающим перебором.
С точки зрения ИИ-решателя пасьянс — это задача поиска по ориентированному графу. Каждый узел графа — это отдельная позиция доски, то есть конкретное расположение всех карт по таблице, запасу, сбросу, основаниям и свободным ячейкам, если вариант их использует. Каждое ориентированное ребро из узла A в узел B представляет легальный ход, который превращает позицию A в позицию B. Задача решателя — найти путь в этом графе от начального узла, соответствующего стартовому перемешанному раскладу, к любому выигрышному узлу, то есть позиции, в которой все карты правильно разложены по основаниям, либо подтвердить, что такого пути не существует.
Компонент 1: представление состояния. Каждый решатель должен определить компактное и однозначное представление каждой позиции доски, которое захватывает всю информацию, важную для генерации будущих ходов. Типичное представление состояния FreeCell кодирует карту в каждой из восьми колонок, в каждой из четырёх свободных ячеек и вершины четырёх оснований — это примерно 60 значений, полностью задающих позицию. Представление состояния Klondike также должно кодировать порядок карт в запасе и сбросе, а также расположение закрытых карт, что добавляет информацию, которая может быть известна не полностью в зависимости от того, сколько закрытых карт уже было раскрыто. Представление состояния определяет, насколько эффективно решатель может хранить уже посещённые позиции, чтобы не исследовать их повторно, и насколько быстро он может генерировать состояния-потомки из любой данной позиции.
Компонент 2: генерация ходов. Из любого состояния решатель генерирует все легальные состояния-потомки — все позиции, достижимые из текущей позиции ровно одним легальным ходом. Качество генерации ходов напрямую влияет на эффективность решателя: решатель, который генерирует все легальные ходы, включая те, что доказуемо субоптимальны, например перенос карты в свободную ячейку с немедленным возвратом обратно, тратит время на исследование доминируемых ветвей. Высококачественные решатели реализуют правила отсечения уже на этапе генерации ходов, отбрасывая доминируемые ходы ещё до исследования — например, никогда не перемещать карту из свободной ячейки в колонку, если ту же карту можно было бы сразу положить туда без участия свободной ячейки, или никогда не класть карту в основание, если это помешает более низкой карте того же цвета позже оказаться в основании. Эти правила отсечения — это ровно те стратегические принципы, которые применяют сильные человеческие игроки; просто решатель реализует их как ограничения генерации ходов, а не как явный выбор стратегии.
Компонент 3: эвристическая оценка. Эвристическая функция решателя присваивает каждому сгенерированному состоянию-потомку приоритетный балл, определяя, какие состояния будут исследоваться первыми. Хорошая эвристика для пасьянса даёт высокие оценки позициям с большим числом карт в основаниях, меньшим числом закрытых карт в таблице, большим количеством пустых колонок или свободных ячеек и более высокой степенью мастевой консолидации в последовательностях таблицы. Эвристика — это приближение качества позиции, и она напрямую аналогична оценке позиции человеческим игроком. Конкретные признаки, которым качественные пасьянсные эвристики придают наибольший вес, — продвижение оснований, уменьшение числа закрытых карт, сохранение пустых колонок, — это ровно те признаки, которые человеческим игрокам приказывают приоритизировать стратегические рамки из кластера стратегии, такие как принудительная последовательность обзора, дисциплина пустых колонок и баланс оснований. Эвристика не произвольна: её калибруют эмпирически, прогоняя решатель по миллионам раскладов и измеряя, какие веса признаков приводят к наибольшей доле найденных выигрышных путей в рамках заданного вычислительного бюджета.
Правила отсечения при генерации ходов и есть стратегические принципы. Каждое правило отсечения, которое качественный решатель применяет на этапе генерации ходов, соответствует стратегическому принципу, который сильный человек применяет при выборе хода. Правило «никогда не переносить карту в свободную ячейку, если её можно сразу положить в колонку» соответствует принципу экономии свободных ячеек. Правило «никогда не класть карту в основание, если это создаёт разрыв базы построения, блокирующий более низкую карту того же цвета» соответствует принципу баланса оснований. Правило «всегда предпочитать раскрытие закрытой карты построению последовательности с той же немедленной ценностью» соответствует принципу раскрытия прежде всего. Понимание того, что эти принципы являются именно правилами отсечения решателя, то есть правилами, удаляющими доминируемые последовательности ходов из пространства поиска, объясняет, почему они работают: это не произвольные соглашения, а математически оправданное исключение типов ходов, имеющих более низкую ожидаемую ценность, чем их альтернативы, по всему распределению раскладов.
Эвристическая функция объясняет, что именно нужно максимизировать. Эвристическая функция решателя пасьянса — это линейная комбинация характеристик доски, взвешенных по их эмпирическому вкладу в вероятность победы: продвижение оснований имеет наивысший вес, уменьшение числа закрытых карт — высокий вес, число пустых колонок — средне-высокий, а занятость свободных ячеек — средне-негативный. Такая структура весов и есть целевая функция, которую максимизирует правильная стратегия в пасьянсе, и она напрямую объясняет, почему порядок приоритетов в принудительной последовательности обзора является правильным. Ходы в основания получают максимальный балл у эвристики, потому что напрямую и необратимо продвигают условие победы. Ходы на раскрытие получают второй по величине балл, потому что уменьшают число закрытых карт, второй по важности признак. Чистые табличные построения получают третий приоритет, потому что улучшают организацию последовательностей, не продвигая напрямую два сильнейших признака эвристики. Доборы из запаса стоят последними, потому что расходуют конечный ресурс запаса, не продвигая напрямую ни один из ключевых признаков эвристики; они необходимы, но в большинстве состояний, где доступны ходы по таблице, их эвристическая цена превышает выгоду.
Механизм возврата назад объясняет правильное использование undo. Решатель использует backtracking, чтобы исследовать альтернативные пути, когда кажущийся перспективным путь приходит в тупик: он возвращается к последней точке ветвления и пробует следующего потомка с наивысшим эвристическим баллом вместо той ветви, которая провалилась. Люди, использующие функцию undo в онлайн-пасьянсе, делают то же самое: когда последовательность ходов приводит к очевидному тупику, откат к последней meaningful точке ветвления и попытка альтернативного пути — это и есть тот же шаг возврата назад. Ключевое различие состоит в том, что решатели откатываются систематически: они помнят все неисследованные ветви в каждой точке ветвления и исследуют их по порядку приоритета, тогда как люди откатываются выборочно, используя распознавание паттернов, чтобы решить, какие ветви вообще стоит тестировать, а не перебирая всё исчерпывающе. Развитие лучшего распознавания того, какие альтернативные ветви стоит пробовать после тупика, — это главный способ, с помощью которого человеческая игра с undo приближается к уровню решателя.
Убеждение, что выигрышный путь решателя — это оптимальная человеческая стратегия. ИИ-решатель находит один выигрышный путь — обычно путь, который его эвристическая функция оценивает как наиболее перспективный из начальной позиции. Этот путь ведёт к победе, но это не обязательно самый эффективный путь, не обязательно самый понятный путь для человека и не обязательно путь, который лучше всего развивает стратегические привычки, переносимые в будущие игры. Пути решателя часто включают ходы, которые за несколько шагов до проявления пользы выглядят почти контрпродуктивными: они временно увеличивают занятость свободных ячеек, временно уменьшают число карт в основаниях или временно разрушают полезные последовательности, — потому что решатель видит достаточно далеко вперёд, чтобы оценить такие регрессивные ходы по их конечному улучшению позиции. Люди, пытающиеся просто повторять путь решателя, не понимая, почему делается каждый ход, часто находят эти линии непостижимыми и начинают меньше доверять собственному суждению, когда их интуиция расходится с ходом решателя. Правильное использование анализа решателя — не следовать конкретному пути, а понять, на какие структурные особенности позиции направлен ход решателя, и развивать те навыки оценки позиции, которые позволяют распознавать эти цели в игре реального времени.
Предположение, что решатель, не нашедший решение, тем самым подтвердил невыигрышность расклада. Не все решатели пасьянса являются полными. Некоторые используют ограничения по времени или по числу узлов, которые останавливают поиск раньше, чем будут исчерпаны все возможные пути. Решатель, завершивший работу без найденного решения, мог бы найти выигрышный путь, если бы получил больше вычислительного времени; он не подтвердил, что выигрышного пути не существует, если только не исследовал все пути исчерпывающе и не нашёл ни одного. Только решатель с гарантией полноты — тот, который исследует все достижимые состояния и возвращает либо выигрышный путь, либо подтверждённое исчерпание всех путей, — может definitively подтвердить невыигрышность. Для практических целей невыигрышные расклады FreeCell и показатели невыигрышности других вариантов в статистическом кластере были установлены именно полными решателями с гарантией исчерпания. Доступные игрокам онлайн-решатели часто такой гарантии не имеют, и их отрицательные результаты следует понимать как «в пределах бюджета поиска путь не найден», а не как «пути не существует».
Пасьянс Скорпион иллюстрирует проблему скрытой информации, которая делает анализ решателей для игр семейства Клондайк дорогим: три закрытые колонки в начале, в сочетании с требованиями к построению одной масти, похожими на Spider, создают пространство поиска, где решатель должен разветвляться по возможным назначениям скрытых карт, одновременно управляя требованиями к консолидации мастей. Игрок в Скорпион, который развивает привычку мысленно перечислять возможные скрытые комбинации карт перед каждым открывающим ходом, является...
Какова лучшая человеческая стратегия, основанная на том, как работают AI-решатели? Четыре привычки, выведенные из работы решателей, обеспечивают наибольшее улучшение коэффициента выигрыша. Принудительная последовательность сканирования (Фонд → Открыть → Чистое построение → Пустая колонка → Запас) реализует эвристический приоритетный порядок решателя. Тестирование гипотез на основе отмены реализует механизм обратного отслеживания решателя. Проверка круговой зависимости реализует обрезку обнаружения тупиков решателя. И принятие контринтуитивных путей — готовность сделать...
Четыре человеческие привычки, выведенные из архитектуры решателей, дают наибольший прирост винрейта. Принудительная последовательность обзора — Foundation → Uncover → Pure build → Empty column → Stock — реализует порядок приоритетов эвристики решателя. Проверка гипотез через undo реализует механизм возврата назад. Проверка циклических зависимостей реализует отсечение тупиков. И принятие контринтуитивных путей — готовность делать ходы, которые в краткосрочной перспективе выглядят хуже, — реализует готовность решателя исследовать ходы с низкой немедленной эвристической ценностью, если они ведут к высокой ценности терминальной позиции. Вместе эти четыре привычки захватывают сущностную архитектуру качественного решателя пасьянса в форме, исполнимой человеком в реальном времени, без миллионов узлов в секунду, которые отличают решатель от человека.
FreeCell стабильно остаётся самой лёгкой для анализа во всех архитектурах решателей, потому что полная информация, почти стопроцентная выигрышность и достаточные промежуточные ресурсы в сочетании создают поисковую задачу, где состояние полностью специфицировано в каждом узле, почти все расклады имеют несколько выигрышных путей, что снижает шанс исчерпания поиска без нахождения одного из них, а правила отсечения ходов работают особенно эффективно, поскольку ограничения вращения свободных ячеек быстро исключают большие фрагменты графа ходов. Решатели обычно находят решения FreeCell за миллисекунды или секунды. На трудном конце спектра Forty Thieves сложнее всего именно для подтверждения невыигрышных раскладов: его большое пространство состояний и ограничительные правила построения делают исчерпывающий перебор путей, необходимый для подтверждения невыигрышности, вычислительно дорогим. Скрытая информация Klondike делает его самым трудным для точного анализа выигрышности, даже если попытки решения отдельных раскладов обычно быстрее, чем полное исчерпание путей в Forty Thieves.
Для вариантов с полной информацией — FreeCell, Yukon, Scorpion после раскрытия всех закрытых карт — достаточная вычислительная мощность позволяет решить любой конкретный расклад через исчерпывающий поиск, потому что граф поиска конечен и полностью перечислим. Для вариантов со скрытой информацией — Klondike, Spider до тех пор, пока не разыграны все раздачи — граф поиска экспоненциально больше из-за ветвления по скрытым картам, и понятие «достаточной вычислительной мощности» становится труднее определить: при бесконечной мощности все случаи решаемы, но практический порог для полного анализа всех возможных раскладов Klondike далеко выходит за пределы современного железа и остаётся открытой проблемой как в теоретической информатике, так и в инженерии практических решателей. Правильное понимание состоит в том, что возможности ИИ-решателей образуют спектр — от почти мгновенных решений лёгких раскладов FreeCell до вычислительно неразрешимых задач полного анализа Klondike, — а человеческое стратегическое развитие стремится сокращать разрыв между человеком и решателем на tractable конце этого спектра.