FreeCell

FreeCell
Игра терпение на
	Игра Freecell на KDE
Именованный вариант	Игра Бейкера
Семья	Свободная ячейка
Палуба	Одиночная 52-карточная
	См. также Глоссарий терминов терпения.

FreeCell — пасьянс карточный , в котором используется стандартная колода из 52 карт . Он фундаментально отличается от большинства пасьянсов тем, что очень немногие расклады являются неразрешимыми. ^{[ 1 ]} и все карты сдаются лицом вверх с самого начала игры. ^{[ 2 ]} Хотя реализации программного обеспечения различаются, большинство версий помечают руки номером (полученным на основе начального значения, используемого генератором случайных чисел для перетасовки карт). ^{[ 2 ]}

Microsoft включала компьютерную игру FreeCell в каждый выпуск операционной системы Windows с 1995 года, что в значительной степени способствовало популярности игры среди пользователей персональных компьютеров и даже привело к созданию нескольких веб-сайтов, посвященных FreeCell. ^{[ 3 ]} Microsoft FreeCell настолько идеальна для многих игроков FreeCell, что многие другие реализации программного обеспечения реализуют совместимость с ее генератором случайных чисел , чтобы воспроизвести ее пронумерованные руки. ^{[ 2 ]}^{[ 4 ]}

Правила

Используется одна стандартная колода из 52 карт. Есть четыре открытые ячейки и четыре открытых фонда . В некоторых альтернативных правилах используется от одной до десяти ячеек. Карты раздаются лицевой стороной вверх в восемь каскадов , четыре из которых состоят из семи карт каждый, а четыре из которых состоят из шести карт. В некоторых альтернативных правилах используется от четырех до десяти каскадов.

Верхняя карта каждого каскада начинает последовательность . Таблицы должны быть построены путем чередования цветов. Фундаменты закладываются по костюму. Основы обычно начинаются с туза и дорастают до короля.

Любую ячейку или верхнюю карту любого каскада можно переместить для построения таблицы или переместить в пустую ячейку, пустой каскад или его основу. Полные или частичные таблицы можно перемещать для построения существующих таблиц или перемещать в пустые каскады путем рекурсивного размещения и удаления карт через промежуточные места. Компьютерные реализации часто демонстрируют это движение, но игроки, использующие физические колоды, обычно перемещают таблицу сразу. Максимальное количество $Max$ Количество карточек в таблице, которые можно переместить в другую таблицу, равно количеству пустых ячеек плюс одна, причем это число удваивается для каждого пустого каскада: $Max=2^{M}\times (N+1)$ , где $M$ – количество пустых каскадов и $N$ это количество пустых ячеек. ^{[ 5 ]} Максимальное число, которое можно переместить в пустой каскад, равно $Max/2$ . ^{[ 5 ]}

Игра выиграна после того, как все карты передвинуты в свои стопки. Подсчитано, что 99,999% возможных сделок решаемы. ^{[ 2 ]} Сделка номер 11982 из версии FreeCell для Windows является примером неразрешимой сделки FreeCell, единственной сделки среди исходных «Microsoft 32 000», которая неразрешима. ^{[ 2 ]}

История и варианты

Одним из старейших предков FreeCell является Eight Off . В июньском выпуске журнала Scientific American за 1968 год Мартин Гарднер описал в своей колонке «Математические игры» игру К. Л. Бейкера, которая похожа на FreeCell, за исключением того, что карты на таблице построены по мастям, а не по альтернативным цветам. Гарднер писал: «Бейкера научил этой игре его отец, который, в свою очередь, научился ей у англичанина в 1920-х годах». ^{[ 6 ]} Этот вариант теперь называется « Игра Бейкера» . Истоки FreeCell могут восходить еще к 1945 году и к скандинавской игре под названием «Наполеон на острове Святой Елены» (а не к пасьянсу « Наполеон на острове Святой Елены» , также известному как «Сорок разбойников»). ^{[ 2 ]}

Пол Альфилль изменил игру Бейкера, создав карты разных цветов, создав таким образом FreeCell. Будучи студентом-медиком в Университете Иллинойса, он реализовал первую компьютеризированную версию языка программирования TUTOR для образовательной компьютерной системы PLATO в 1978 году. ^{[ 7 ]} Альфилле смог отображать легко узнаваемые графические изображения игральных карт на монохромном дисплее 512×512 систем PLATO. ^{[ 8 ]}

Эта оригинальная среда FreeCell допускала игры с 4–10 столбцами и 1–10 ячейками в дополнение к стандартной игре 8 × 4 . Для каждого варианта программа сохраняла ранжированный список игроков с самыми длинными победными сериями. Существовала также система турниров, которая позволяла людям соревноваться за выигрыш тщательно подобранных сделок. Пол Альфилль более подробно описал эту раннюю среду FreeCell в интервью 2000 года. ^{[ 9 ]}

В 2012 году исследователи использовали методы эволюционных вычислений для создания успешных игроков FreeCell. ^{[ 10 ]}

Вариант, в котором движение последовательности карт не ограничено доступными ячейками, известен как Relaxed FreeCell. ^{[ 2 ]}

Другие пасьянсы, связанные с FreeCell или вдохновленные ею, включают Seahaven Towers , Penguin , Stalactites , ForeCell, Antares (крест со Скорпионом ).

Сложность решателя

В игре FreeCell постоянное количество карт. Это означает, что за постоянное время человек или компьютер может составить список всех возможных ходов из заданной начальной конфигурации и обнаружить выигрышный набор ходов или, если предположить, что игра неразрешима, его отсутствие. Чтобы провести интересный анализ сложности, необходимо построить обобщенную версию игры FreeCell с картами 4 × n . Эта обобщенная версия игры является NP-полной ; ^{[ 11 ]} маловероятно, что существует какой-либо алгоритм, более эффективный, чем поиск методом грубой силы, который может найти решения для произвольных обобщенных конфигураций FreeCell.

Их 52! (т. е. 52 факториала ), или примерно 8 × 10 ⁶⁷, отдельные сделки. Однако некоторые игры фактически идентичны другим, поскольку масти, присвоенные картам, произвольны или столбцы можно менять местами. С учетом этих факторов получается примерно 1,75 × 10 ⁶⁴ отдельные игры. ^{[ 2 ]}

Ссылки

^ Леонхард, Вуди (2009). Windows 7 «все в одном» для чайников . Джон Уайли и сыновья. п. 293. ИСБН 9780470487631 .
^ Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час Келлер, Майкл (4 августа 2015 г.). «FreeCell — Часто задаваемые вопросы (FAQ)» . Лаборатория пасьянсов . Проверено 7 февраля 2017 г.
^ Гленн, Джим и Дентон, Кэри. Сокровищница семейных игр (стр. 105). Ридерс Дайджест, 2003 ( ISBN 9780762104314 )
^ «PySol — Правила для Freecell» . Документация PySolFC . Проверено 3 февраля 2018 г.
^ Перейти обратно: ^а ^б "пасьянс - FreeCell: сколько карт можно переместить одновременно?" . Обмен стеками настольных и карточных игр .
^ Гарднер, Мартин (июнь 1968 г.). «Математические игры». Научный американец . 218 (6): 114. Бибкод : 1968SciAm.218f.112G . doi : 10.1038/scientificamerican0668-112 .
^ Марк Дж. П. Вольф Перед катастрофой: Ранняя история видеоигр, 2012, стр. 212 «После Spacewar! В системе PLATO появилось еще несколько игр, в том числе DECWAR (1974, по мотивам «Звездного пути»), Empire (1974), Dungeons & Dragons. – вдохновленная игрой под названием «dnd», выпущенной в 1979 году, Moria (1975), оригинальной Freecell (1978) и симулятором полета Airfight...»
^ Кэй, Эллен (17 октября 2002 г.). «Один даун, осталось 31 999: отдавшись одинокой одержимости» . Нью-Йорк Таймс .
^ Кронин, Деннис (4 мая 2000 г.). «Интервью с Полем Альфилем» . Freecell.net . Проверено 4 марта 2011 г.
^ Эльясаф, Ачия; Гауптман, Ами; Сиппер, Моше (декабрь 2012 г.). «Эволюционный дизайн решателей FreeCell» (PDF) . Транзакции IEEE по вычислительному интеллекту и искусственному интеллекту в играх . 4 (4): 270–281. дои : 10.1109/TCIAIG.2012.2210423 . S2CID 801608 . Архивировано (PDF) из оригинала 20 октября 2015 г.
^ Хельмерт, Мальте (март 2003 г.). «Результаты сложности стандартных контрольных областей при планировании». Искусственный интеллект . 143 (2): 219–262. дои : 10.1016/S0004-3702(02)00364-8 .

Дополнительные источники

«Ученые OHSU утверждают, что FreeCell можно адаптировать для выявления ранних признаков деменции» . Орегонский университет здоровья и науки . Проверено 1 июня 2017 г.
О'Хейл, Марти М. (14 августа 2007 г.). «Четыре достоинства FreeCell» . Журнал «Эскапист». Архивировано из оригинала 8 августа 2011 года . Проверено 9 июня 2012 г.

См. также

[Leonhard2009-1] Леонхард, Вуди (2009). Windows 7 «все в одном» для чайников . Джон Уайли и сыновья. п. 293. ИСБН 9780470487631 .

[FCFAQ-2] Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час Келлер, Майкл (4 августа 2015 г.). «FreeCell — Часто задаваемые вопросы (FAQ)» . Лаборатория пасьянсов . Проверено 7 февраля 2017 г.

[3] Гленн, Джим и Дентон, Кэри. Сокровищница семейных игр (стр. 105). Ридерс Дайджест, 2003 ( ISBN 9780762104314 )

[4] «PySol — Правила для Freecell» . Документация PySolFC . Проверено 3 февраля 2018 г.

[stackex-5] Перейти обратно: ^а ^б "пасьянс - FreeCell: сколько карт можно переместить одновременно?" . Обмен стеками настольных и карточных игр .

[6] Гарднер, Мартин (июнь 1968 г.). «Математические игры». Научный американец . 218 (6): 114. Бибкод : 1968SciAm.218f.112G . doi : 10.1038/scientificamerican0668-112 .

[7] Марк Дж. П. Вольф Перед катастрофой: Ранняя история видеоигр, 2012, стр. 212 «После Spacewar! В системе PLATO появилось еще несколько игр, в том числе DECWAR (1974, по мотивам «Звездного пути»), Empire (1974), Dungeons & Dragons. – вдохновленная игрой под названием «dnd», выпущенной в 1979 году, Moria (1975), оригинальной Freecell (1978) и симулятором полета Airfight...»

[nyt-8] Кэй, Эллен (17 октября 2002 г.). «Один даун, осталось 31 999: отдавшись одинокой одержимости» . Нью-Йорк Таймс .

[9] Кронин, Деннис (4 мая 2000 г.). «Интервью с Полем Альфилем» . Freecell.net . Проверено 4 марта 2011 г.

[10] Эльясаф, Ачия; Гауптман, Ами; Сиппер, Моше (декабрь 2012 г.). «Эволюционный дизайн решателей FreeCell» (PDF) . Транзакции IEEE по вычислительному интеллекту и искусственному интеллекту в играх . 4 (4): 270–281. дои : 10.1109/TCIAIG.2012.2210423 . S2CID 801608 . Архивировано (PDF) из оригинала 20 октября 2015 г.

[11] Хельмерт, Мальте (март 2003 г.). «Результаты сложности стандартных контрольных областей при планировании». Искусственный интеллект . 143 (2): 219–262. дои : 10.1016/S0004-3702(02)00364-8 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]