Узнайте, можно ли решить пасьянс алгоритмами, как работают ИИ-солверы и что они говорят о стратегии.
Да — и нет, в зависимости от того, что именно понимается под «решением» и о каком варианте идёт речь. Компьютерные решатели полностью проанализировали все стандартные раздачи FreeCell, выявив восемь заведомо невыигрываемых раскладов и подтвердив, что остальные тысячи раздач можно выиграть. Аналогичным образом были оценены вероятности выигрыша для Клондайка, Spider и Forty Thieves на основе анализа миллионов случайных раздач. В этом смысле пасьянс во многом «решён» алгоритмически — известны преде
Да — и нет, в зависимости от того, что означает "решено" и какая вариация рассматривается. Вычислительные решатели тщательно проанализировали каждую раздачу в стандартном наборе FreeCell, каталогизировав восемь нерешаемых раздач с уверенностью и подтвердив, что остальные 32 000 с лишним раздач все выигрышные. Те же решатели установили минимальные уровни выигрыша, описанные в этом стратегическом кластере: доля раздач Klondike, Spider и Forty Thieves, которые по своей сути решаемы, была оценена с высокой степенью уверенности с помощью автоматического исчерпывающего поиска по миллионам случайно сгенерированных раздач. В этом смысле пасьянс был широко решен алгоритмически — математика того, какие раздачи выигрышные, в значительной степени установлена, и автоматические решатели могут находить последовательности выигрышных ходов для большинства выигрышных раздач, с которыми они сталкиваются.
С другой стороны, пасьянс не был полностью решен алгоритмически, и нерешенные аспекты представляют собой действительно сложные вычислительные задачи. Анализ выигрыша в Klondike не является точным — это остается диапазоном вероятностей (примерно 79–91% выигрышных), а не точной цифрой — потому что неопределенность лицом вниз в Klondike создает проблему скрытой информации, которая делает полное исчерпывающее анализирование вычислительно неосуществимым в больших масштабах. Даже в полностью видимых вариантах, таких как FreeCell, определение того, является ли конкретная позиция выигрышной, является задачей в классе вычислительной сложности PSPACE-полных задач — классе задач, которые, как считается, сложнее, чем NP-полные задачи, и для которых не известно существование алгоритма полиномиального времени. Существование эффективных алгоритмов, которые идеально решают все варианты пасьянса за разумное время, не гарантируется никаким текущим математическим результатом, и несколько вариантов остаются открытыми исследовательскими задачами в области информатики.
Для практического игрока в пасьянс связь между алгоритмами и стратегией пасьянса наиболее полезна в двух направлениях: понимание того, что алгоритмические решатели установили о выигрыше раздач (что напрямую информирует о наших ожиданиях по коэффициентам выигрыша в нашем руководстве по шансам на победу), и понимание того, какие алгоритмические техники соответствуют человеческому стратегическому мышлению — потому что наиболее эффективная человеческая стратегия пасьянса оказывается применением упрощенной версии того же эвристического поиска, который используют автоматические решатели.
С алгоритмической точки зрения, пасьянс — это задача поиска для одного игрока: начиная с начального состояния (перетасованной раздачи), решатель должен найти последовательность законных ходов, которая преобразует начальное состояние в состояние выигрыша (все карты на фундаментах в правильном порядке). Пространство состояний — общее количество различных позиций на доске, через которые может пройти игра — астрономически велико. Одна игра Klondike имеет пространство состояний, оцениваемое в миллиарды и триллионы различных позиций, когда рассматриваются все возможные последовательности ходов от всех возможных начальных раздач. Forty Thieves, с его 80-картной двухколодной таблицей, имеет пропорционально большее пространство состояний, что делает исчерпывающий поиск вычислительно дорогим даже для современного оборудования.
Основные алгоритмические подходы, применяемые к поиску в пасьянсе, это: исчерпывающий поиск в глубину, который систематически исследует все возможные последовательности ходов, пока не будет найден выигрышный путь или не будут подтверждены все пути как проигрышные; эвристический поиск с приоритетом, который приоритизирует ходы на основе оценок качества позиций и сначала исследует многообещающие пути; и моделирование Монте-Карло, которое запускает тысячи случайных игр из текущей позиции и использует долю игр, которые достигают состояния выигрыша, как оценку вероятности выигрыша позиции. Каждый подход имеет разные компромиссы между вычислительной стоимостью и качеством решения, и каждый соответствует разному уровню человеческого стратегического мышления.
Исчерпывающий поиск в глубину: точные ответы, высокая вычислительная стоимость. Поиск в глубину (DFS) исследует каждую возможную последовательность ходов из начальной позиции, возвращаясь назад, когда достигаются тупики, пока не будет подтвержден выигрышный путь или все пути не будут подтверждены как ведущие к проигрышным позициям. Для FreeCell, где полная информация делает пространство состояний полностью перечисляемым, DFS может окончательно определить, является ли данная раздача выигрышной, и найти выигрышную последовательность, если таковая существует. Восемь невыигрышных раздач FreeCell (включая известные раздачи 11,982 и 146,692) были выявлены решателями DFS, которые подтвердили, путем исчерпывающего исследования, что ни одна законная последовательность ходов из этих начальных позиций не приводит к победе. Для Klondike DFS сталкивается с проблемой скрытой информации: закрытые карты могут быть любыми из нескольких возможных карт, и решатель должен либо предполагать конкретные значения скрытых карт (что приводит к выводам, зависящим от этих предположений), либо разветвляться по всем возможным назначениям скрытых карт (что умножает пространство поиска на количество возможных конфигураций скрытых карт, делая полное исчерпывающее исследование непрактичным для больших выборок). Вот почему коэффициент выигрыша Klondike является диапазоном, а не точной цифрой — это результат вероятностного выборочного анализа по многим случайным раздачам, а не полного исчерпывающего анализа всех возможных раздач.
Эвристический поиск с приоритетом: быстрые почти оптимальные решения, отсутствие гарантии полноты. Поиск с приоритетом использует функцию оценки — эвристический балл, который оценивает качество позиции на доске — чтобы определить, какие состояния исследовать в первую очередь. Высококачественная эвристика для пасьянса может оценивать позиции на основе количества карт в основании, количества открытых закрытых карт, количества доступных законных ходов и степени консолидации мастей в последовательностях таблицы. Поиск с приоритетом с хорошей эвристикой находит выигрышные решения значительно быстрее, чем DFS, на выигрышных раздачах, но не может гарантировать, что он нашел оптимальное (самое короткое) решение, и может не найти никакого решения на раздачах, где выигрышный путь требует временного отхода от того, что эвристика считает хорошей позицией. Эвристический подход с приоритетом наиболее прямо аналогичен стратегии человеческого эксперта: оба используют функцию оценки качества позиции (эвристику) для управления выбором ходов, оба сначала исследуют многообещающие пути, и оба могут упустить решения, которые требуют контринтуитивных промежуточных позиций, которые выглядят хуже, прежде чем они станут лучше.
Монте-Карло симуляция: вероятностные оценки, подходящие для скрытой информации. Методы Монте-Карло выполняют большое количество случайных игр из текущей позиции — делая законные ходы случайным образом, пока игра не закончится победой или поражением — и используют пропорцию побед по всем играм как вероятностную оценку выигрышности позиции. Монте-Карло особенно подходит для Klondike и других вариантов со скрытой информацией, потому что он естественно справляется с неопределенностью: каждая игра случайным образом назначает значения скрытых карт, соответствующие текущему известному распределению, исследует случайную последовательность ходов оттуда и вносит свой результат победы/поражения в оценку. Полученная оценка вероятности выигрыша не является точным ответом — это среднее значение выборки с статистической неопределенностью — но она вычислительно осуществима и производит откалиброванные доверительные интервалы, которые улучшаются по мере добавления большего количества игр. Симуляция Монте-Карло является вычислительным аналогом человеческой вероятностной оценки, описанной в нашем руководстве по вероятностной стратегии: оба оценивают выигрышность позиции на основе выборки возможных исходов, а не на основе полного перечисления.
Модель эвристического поиска объясняет, почему работает принудительная последовательность сканирования. Принудительная последовательность сканирования — Фонд? Открыть? Чистая сборка? Пустая колонка? Запас последним — это эвристика, которую может выполнить человек, которая присваивает приоритетные веса типам ходов так же, как алгоритмическая эвристика присваивает приоритетные баллы позициям на доске. Ходы в фонд приоритизируются, потому что они напрямую продвигают условие победы; ходы по открытию приоритизируются, потому что они расширяют пространство состояний будущих выигрышных позиций; розыгрыши из запаса имеют низкий приоритет, потому что они потребляют конечные ресурсы, ценность которых наивысшая, когда таблица полностью оценена. Этот порядок приоритетов не произволен — он близко соответствует порядкам приоритета ходов, которые эмпирически обученные эвристики пасьянса присваивают тем же типам ходов. Принудительная последовательность сканирования является, по сути, ручным приближением к эвристике с приоритетом, которую используют автоматизированные решатели.
Функция отмены позволяет человеку тестировать гипотезы, аналогичные алгоритмическому разветвлению. Автоматизированные решатели исследуют несколько ветвей дерева ходов одновременно, возвращаясь назад от тупиков, чтобы попробовать альтернативные пути. Человеческие игроки не могут исследовать ветви одновременно, но функция отмены в онлайн-пасьянсе предоставляет приближение: игрок может сделать ход, наблюдать его последствия через несколько ходов, и отменить до точки разветвления, чтобы попробовать альтернативу, если первый путь оказывается необещающим. Это спекулятивное разветвление — сделать ход, чтобы протестировать гипотезу о том, что он позволяет, а затем отменить, если гипотеза опровергнута — является эквивалентом шага возврата в DFS, который может выполнить человек. Игроки, которые систематически используют отмену для тестирования гипотез, а не только для исправления ошибок, применяют человеческую версию исчерпывающего поиска, который делает решатели DFS эффективными на сложных позициях.
Идентификация круговой зависимости — это версия обнаружения тупиков, которую может выполнить человек. Когда решатель DFS достигает позиции, из которой нет выигрышного пути, он обнаруживает это, исчерпывая все возможные продолжения и находя, что ни одно не приводит к победе — это вычислительно затратный процесс. Человеческие игроки могут обнаружить подмножество тупиковых позиций гораздо быстрее, идентифицируя круговые зависимости: конфигурации, где карта A не может двигаться, пока карта B не двинется, и карта B не может двигаться, пока карта A не двинется, без внешнего разрешения. Эта проверка круговой зависимости является эвристикой обнаружения тупиков, которую может выполнить человек, которая, когда положительна, предоставляет ту же информацию, что и алгоритмическое обнаружение тупиков, не требуя исчерпывающего поиска. Развитие привычки идентификации круговой зависимости является основным практическим преимуществом понимания того, как работают алгоритмические решатели — это преобразует затратный вычислительный процесс в быструю проверку, которую может выполнить человек, производя то же решение об отказе более эффективно.
Полная информация FreeCell делает его вариантом, где алгоритмическая и человеческая стратегии наиболее близки. В FreeCell, где все карты открыты с первого хода, человеческие игроки могут в принципе вычислить то же полное дерево ходов, которое исследует автоматизированный решатель. Практическая разница заключается в вычислительной мощности: решатель может исследовать миллионы позиций в секунду, в то время как человеческий игрок может оценивать, возможно, от пяти до десяти позиций в минуту. Но структура проблемы — полная информация, детерминированные результаты, полностью перечисляемое пространство состояний — идентична между человеческой и алгоритмической игрой. Вот почему FreeCell является лучшим вариантом для развития глубочайшего стратегического мышления: его полная информационная среда дает человеческим игрокам доступ к полной оценке качества позиции, которую используют эвристические решатели, позволяя условную последовательность ходов и полную оценку ожидаемой ценности, описанную на экспертном уровне в руководстве по вероятностной стратегии. Играя в FreeCell с систематическим тестированием гипотез на основе отмены, человек-игрок приближается к тому, чтобы вручную запустить алгоритмического решателя.
Верить, что существование алгоритмических решателей означает, что каждая раздача решаема. Алгоритмические решатели находят выигрышные пути в выигрышных раздачах — они не создают выигрышные пути там, где их нет. Восемь нерешаемых раздач FreeCell были выявлены алгоритмическими решателями именно потому, что решатели исчерпали все возможные пути и не нашли ни одного, ведущего к победе. В вариантах с более высокими показателями нерешаемости (Сорок воров 40–60%, Пасьянс Паука 4-колоды 45–60%) алгоритмические решатели подтверждают, что большая часть случайных раздач не имеет выигрышного пути, что означает, что ни один алгоритм — каким бы сложным он ни был — не может выиграть эти игры. Существование мощных решателей не изменяет структуру пространства раздач; оно лишь позволяет нам более точно анализировать эту структуру.
Предположение, что выигрышный путь решателя является единственным выигрышным путем. Большинство выигрышных раздач пасьянса имеют несколько выигрышных путей — несколько различных последовательностей ходов, которые все приводят к условию победы. Решатель, который находит один выигрышный путь, не нашел единственный путь; он нашел один путь из потенциально сотен или тысяч. Это важно для человеческой игры, потому что конкретный путь решателя может быть крайне неинтуитивным — требуя хода, который выглядит активно вредным за несколько шагов до того, как его польза станет очевидной — в то время как другие выигрышные пути для той же раздачи более доступны для человеческого распознавания шаблонов. Существование найденного решателем выигрышного пути подтверждает, что раздача решаема; это не обязательно руководство о том, как человеческий игрок должен подходить к той же раздаче наиболее эффективно.
Отношение алгоритмических коэффициентов выигрыша как применимых к случайной игре. Когда решатель определяет, что 35% раздач Klondike Turn 1 решаемы при оптимальной игре, эта цифра предполагает идеальное обращение с информацией, оптимальный выбор ходов на каждом этапе принятия решения и отсутствие человеческих когнитивных ограничений. Случайная человеческая игра достигает 15–25% в Klondike, стратегическая игра достигает 35–45%, но алгоритмический оптимальный потолок примерно 79–91% (потолок решаемости) достижим только решателем с доступом ко всему пространству состояний. Правильная интерпретация данных о коэффициентах выигрыша алгоритма для человеческих игроков не как личного эталона, а как структурной ссылки: она говорит игроку, насколько велика разница между их текущим коэффициентом выигрыша и теоретическим потолком, вызванная математикой раздачи по сравнению с качеством стратегии. Для полного фреймворка по использованию этих структурных данных смотрите наше руководство по качеству раздач.
FreeCell — это оптимальная игра для опыта связи алгоритма и стратегии, потому что ее полная информация делает взаимосвязь между систематическим поиском и правильной игрой непосредственно наблюдаемой. Игрок FreeCell, который методично прослеживает дерево ходов — оценивая все законные ходы, выбирая путь с наивысшим приоритетом, используя отмену для проверки альтернативных ветвей и идентифицируя круговые зависимости, которые подтверждают тупики — выполняет упрощенную версию эвристического поиска с приоритетом, который используют автоматизированные решатели. Пасьянс Паука вводит скрытое измерение информации, которое делает полный алгоритмический анализ неосуществимым и требует вероятностного подхода оценки методов Монте-Карло — переведенного в человеческую игру как оценка ходов с учетом вероятности, описанная в руководстве по вероятностной стратегии. Вместе FreeCell (полная информация, детерминированный, эвристический поиск) и Пасьянс Паука (частичная информация, вероятностный, оценка Монте-Карло) охватывают две основные алгоритмические парадигмы, которые исследует ИИ в пасьянсе, и развитие сильной игры в обоих предоставляет самое глубокое понимание того, как алгоритмическая и человеческая стратегии пасьянса соотносятся.
Алгоритм, который можно выполнить человеком и который наиболее близко приближен к тому, что делают автоматизированные решатели, сочетает три компонента: принудительная последовательность сканирования в качестве эвристики приоритета ходов (Фонд → Открытие → Чистая сборка → Пустая колонка → Запас), основанное на отмене тестирование гипотез в качестве механизма возврата и идентификация круговой зависимости в качестве сокращенного метода обнаружения тупиков. Вместе эти три компонента реализуют упрощенный эвристический поиск с возвратом и частичным обнаружением тупиков — те же три компонента, которые определяют наиболее эффективные автоматизированные решатели, адаптированные к человеческой когнитивной способности. Игрок, который развивает все три компонента как постоянные привычки, выполняет наиболее близкое человеческое приближение к алгоритму, который максимизирует коэффициент выигрыша по всей распределенной раздаче.
FreeCell проще для алгоритмов по тем же причинам, по которым он наиболее удобен для человеческого стратегического анализа: полная информация устраняет проблему скрытой ветвления карт, почти 100% выигрышность означает, что почти все позиции имеют выигрышные пути, и четыре свободные ячейки плюс восемь колонок обеспечивают достаточную гибкость, что путь решения редко требует контринтуитивных регрессивных ходов. Вычислительная сложность решения конкретной позиции FreeCell все еще является PSPACE-полной в худшем случае — это означает, что не гарантируется существование полиномиального алгоритма — но на практике хорошо реализованные эвристические решатели находят выигрышные пути для почти всех раздач FreeCell за миллисекунды. Spider 1-Suit также легко решается благодаря своему ограничению на одну масть. На трудном конце, скрытая информация Klondike делает его более сложным для окончательного решения алгоритмами, чем его очевидная простота предполагает, а большое состояние с двумя колодами в Forty Thieves с ограниченными правилами сборки делает его вычислительно дорогим, даже когда предполагается полная информация.
Приоритетный выбор ходов + проверка альтернатив через отмену + анализ тупиков.
FreeCell.
Теоретически да, практически — нет.