Солитер (карточная игра)

Солитер для [1], или «Свободная ячейка»^[2] (англ. FreeCell) — карточный пасьянс. Поскольку пасьянс относительно новый и известен исключительно по компьютерным реализациям, устоявшегося русского названия нет.

Пасьянс удачно сочетает высокую сложность (намного сложнее «Косынки»), полную информацию и мизерный процент комбинаций, которые невозможно сложить.

Правила

• Используется стандартная колода карт (52 карты).
• Раскладывается вся колода в 8 колонок, лицом вверх. Таким образом, будет четыре колонки по 7 карт и ещё четыре — по 6.
• Также есть 4 ячейки, именуемых «домом», и 4 «свободных» ячейки. На момент начала игры все они пусты.
• Разрешено перекладывать одну карту из колонки или свободной ячейки:
  • в любую другую колонку — на следующую по старшинству карту другого цвета (например, чёрного валета — только на красную даму).
  • либо на свободную ячейку, если она пуста (таким образом, каждая из свободных ячеек может хранить только одну карту);
  • либо в пустую колонку;
  • либо в «дом» — карты одной масти, начиная с туза и заканчивая королём.
• Пасьянс сходится, если удаётся переместить всю колоду в «дом».

Если нужно перенести стопку карт, это можно сделать только по одной, используя пустые колонки и свободные ячейки. Имея n свободных ячеек и m пустых колонок, можно перенести в другое место $(n+1) \cdot 2^m$ сложенных по порядку карт, такие комбинации называются «суперходы» (англ. supermoves). Компьютерные версии обычно показывают суперход во всех деталях; играющие с настоящей колодой просто переносят стопку, убедившись, что карты действительно сложены по порядку, а пустых ячеек достаточно.

История

«Свободная ячейка» на PLATO

Предтечами «Свободной ячейки» можно считать пасьянсы «Восьмёрка» и «Сорок разбойников» (он же «Наполеон на острове святой Елены»).^[3] Изобретатель «Свободной ячейки» Пол Олфилл (Paul Alfille), будучи ещё ребёнком, жаловался на то, что большинство пасьянсов оставляли колоду отсортированной по масти; чтобы начать новую игру, требовалось долгая и тщательная перетасовка. Установив правило «чёрный-красный», Олфилл улучшил состояние колоды (даже если пасьянс решён, позиция становится очевидной задолго до того, как будут сложены все карты, и часть колоды складывается по масти, а часть — поочерёдно).^[4] Игра оказалась довольно сложной, но неразрешимые комбинации практически не выпадали.

Впоследствии, в 1978 году, Олфилл реализовал свою игру в рамках системы программированного обучения PLATO на языке программирования TUTOR. Благодаря высокому (по тем временам) разрешению PLATO — 512×512 — удалось нарисовать разборчивые изображения мастей, несмотря на монохромный монитор.

В дальнейшем Джим Хорн (Jim Horne) реализовал «Свободную ячейку» для 1992 — для Windows.^[3][5] Неизвестно, где Хорн узнал о «Свободной ячейке» — вероятно, будучи студентом, имел дело с PLATO. Компания Win32s. Впрочем, «Свободная ячейка» оставалась малоизвестной, пока не оказалась в стандартной поставке Windows 95. В дальнейшем игру включали во все версии Windows вплоть до Seven.

Только после появления Microsoft FreeCell изобретение Олфилла стали включать в книги о карточных играх.^[3]

Реализация Microsoft

Реализация Джима Хорна, опубликованная под именем Microsoft FreeCell, считается классической. Сторонние разработчики обычно делают в своих программах генератор раскладов, совместимый с нумерацией Microsoft.^[6]

Если расклады с переставленными колонками и переименованными мастями считать одинаковыми, в пасьянсе существует 1,75·10⁶⁴ разных раскладов. В MS FreeCell представлено 32000 раскладов, генерирующихся 15-битным датчиком псевдослучайных чисел; встроенная справка заявляла:

Считается (хотя и не доказано), что данный пасьянс сходится при любом раскладе.

В общем случае это неверно: в качестве «пасхального яйца», в игре можно задать явно неразрешимые расклады −1 и −2. Чтобы проверить 32000 раскладов Microsoft, в интернете появился краудсорсинг-проект, проверяющий, действительно ли все расклады разрешимы. В проекте были задействованы более чем 100 заядлых картёжников; к 1995 году только расклад 11982 не поддался ни одному участнику. И по сей день компьютеры неспособны найти решение этого расклада; впрочем, его неразрешимость так и не доказана — для этого нужно математическое доказательство или решение методом перебора. Задача NP-полна по количеству карт^[7] — поэтому ни один из компьютерных «решателей»^[8][9] не делает исчерпывающего перебора.

В Windows XP количество раскладов увеличено до 1 миллиона, первые 32000 раскладов были теми же. Помимо расклада 11982, решение не найдено для раскладов 146692, 186216, 455889, 495505, 512118, 517776 и 781948.

В версии Microsoft суперходы реализованы, но не полностью: с пустыми колонками программа работает как со свободными ячейками. Другими словами, имея три пустых колонки, даже без свободных ячеек можно перенести 8 карт; MS FreeCell перенесёт только четыре.

Вероятность победы

По современным данным, вероятность выпадения разрешимой комбинации оценивается более чем в 99,99 % — одна неразрешимая комбинация на 78 000 разрешимых. Без свободных ячеек сходится всего 0,2 % раскладов. Чтобы любой расклад гарантированно сошёлся, нужно не менее семи свободных ячеек.^[3]

Если упростить правила и разрешить перемещать упорядоченную стопку целиком, не используя свободных ячеек, разрешимы все 1 млн раскладов Microsoft — но потенциально неразрешимые также остались.^[3] Поскольку шансы на плохой расклад и без этого крайне малы, такое упрощение считается сомнительным.

Примечания

1. ↑ Название в Windows XP
2. ↑ Название в Windows 95
3. ↑ ^{1 2 3 4 5} FreeCell FAQ(англ.)
4. ↑ Interview with Paul Alfille(англ.)
5. ↑ Microsoft FreeCell, «О программе»
6. ↑ Джим Хорн. Алгоритм перетасовки карт Microsoft(англ.)
7. ↑ Malte Helmert, Complexity results for standard benchmark domains in planning, Artificial Intelligence Journal 143(2):219-262, 2003; в файле с. 44—49(англ.)
8. ↑ FreeCell Solver
9. ↑ FreeCell Pro Evaluation Edition