Солитер (карточная игра) | это... Что такое Солитер (карточная игра)? (original) (raw)
Солитер для [1], или «Свободная ячейка»[2] (англ. FreeCell) — карточный пасьянс. Поскольку пасьянс относительно новый и известен исключительно по компьютерным реализациям, устоявшегося русского названия нет.
Пасьянс удачно сочетает высокую сложность (намного сложнее «Косынки»), полную информацию и мизерный процент комбинаций, которые невозможно сложить.
Содержание
Правила
- Используется стандартная колода карт (52 карты).
- Раскладывается вся колода в 8 колонок, лицом вверх. Таким образом, будет четыре колонки по 7 карт и ещё четыре — по 6.
- Также есть 4 ячейки, именуемых «домом», и 4 «свободных» ячейки. На момент начала игры все они пусты.
- Разрешено перекладывать одну карту из колонки или свободной ячейки:
- в любую другую колонку — на следующую по старшинству карту другого цвета (например, чёрного валета — только на красную даму).
- либо на свободную ячейку, если она пуста (таким образом, каждая из свободных ячеек может хранить только одну карту);
- либо в пустую колонку;
- либо в «дом» — карты одной масти, начиная с туза и заканчивая королём.
- Пасьянс сходится, если удаётся переместить всю колоду в «дом».
Если нужно перенести стопку карт, это можно сделать только по одной, используя пустые колонки и свободные ячейки. Имея n свободных ячеек и 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·1064 разных раскладов. В 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] Поскольку шансы на плохой расклад и без этого крайне малы, такое упрощение считается сомнительным.
Примечания
- ↑ Название в Windows XP
- ↑ Название в Windows 95
- ↑ 1 2 3 4 5 FreeCell FAQ(англ.)
- ↑ Interview with Paul Alfille(англ.)
- ↑ Microsoft FreeCell, «О программе»
- ↑ Джим Хорн. Алгоритм перетасовки карт Microsoft(англ.)
- ↑ Malte Helmert, Complexity results for standard benchmark domains in planning, Artificial Intelligence Journal 143(2):219-262, 2003; в файле с. 44—49(англ.)
- ↑ FreeCell Solver
- ↑ FreeCell Pro Evaluation Edition
Компоненты Microsoft Windows | ||
---|---|---|
Основные | Aero • Desktop Window Manager • Проводник (Explorer) • Панель задач • Меню "Пуск" • Shell (namespace • Special Folders • File associations) • Search (Saved search • iFilters) • Graphics Device Interface • WIM • Next Generation TCP/IP stack () • .NET Framework • Audio • Printing (XML Paper Specification) • Active Scripting (WSH • VBScript • COM (OLE • OLE Automation • DCOM • ActiveX • ActiveX Document • Structured storage • Transaction Server) • Previous Versions • WDDM • UAA • Win32 console | |
Службыуправления | Backup and Restore Center • Панель управления (Applets) • Диспетчер устройств • Очистка диска • Дефрагментация диска • Event Viewer • Management Console • Problem Reports and Solutions • Sysprep • • Диспетчер задач • System File Checker • Восстановление системы • Windows Installer • Windows PowerShell • Windows Update • WinSAT • Windows Easy Transfer | |
Приложения | Калькулятор • Calendar • Таблица символов • Contacts • DVD Maker • Fax and Scan • Internet Explorer • Journal • Outlook Express • Почта Windows • Magnifier • Media Center • Meeting Space • Mobile Device Center • Mobility Center • Movie Maker • Narrator • Notepad • Paint • Фотоальбом • Private Character Editor • Remote Assistance • Sidebar • Snipping Tool • Звукозапись • Windows Media Player • Windows Speech Recognition • Игры | Chess Titans • Hold 'Em • InkBall • Mahjong Titans • Purble Place • Пасьянс «Косынка» • Пасьянс «Паук» • Сапёр • Пасьянс «Свободная ячейка» • Пинбол • Червы |
Ядро ОС | hal.dll • System Idle Process • Registry (реестр) • Windows service • Service Control Manager • EXE • Boot Manager • Recovery Console • I/O • WinRE • WinPE • Kernel Patch Protection | |
Службы | Autorun • BITS • Task Scheduler • Wireless Zero Configuration • Shadow Copy • Windows Error Reporting • Multimedia Class Scheduler • CLFS | |
Файловые системы | Hard link • Junction point • Mount Point • Reparse point • Symbolic link • TxF • FAT • CDFS • UDF • DFS • IFS | |
Сервер | Domains • Active Directory • DNS • Групповая политика • Roaming user profiles • Folder redirection • Координатор распределённых транзакций • MSMQ • Windows SharePoint Services • Windows Media Services • Rights Management Services • IIS • Terminal Services • WSUS • Network Access Protection • DFS Replication • Remote Differential Compression • Print Services for UNIX • Remote Installation Services • Windows Deployment Services • Windows System Resource Manager • Hyper-V | |
Архитектура | NT series architecture • Object Manager • Startup process (Vista) • I/O request packets • Kernel Transaction Manager • Logical Disk Manager • Security Accounts Manager • Windows Resource Protection • LSASS • CSRSS • SMSS | |
Безопасность | UAC • BitLocker • Defender • DEP • Protected Media Path • Mandatory Integrity Control • UIPI • Windows Firewall • Security Center | |
Совместимость | Unix subsystem (Interix) • Virtual DOS Machine • Windows on Windows • WOW64 |