stringtranslate.com

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

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

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

Правила

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

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

Любую ячейку или верхнюю карту любого каскада можно переместить для построения таблицы или переместить в пустую ячейку, пустой каскад или его основу. Полные или частичные таблицы можно перемещать для построения существующих таблиц или перемещать в пустые каскады путем рекурсивного размещения и удаления карт через промежуточные места. Компьютерные реализации часто демонстрируют это движение, но игроки, использующие физические колоды, обычно перемещают таблицу сразу. Максимальное количество карточек в таблице, которые можно переместить в другую таблицу, равно количеству пустых ячеек плюс одна, причем это число удваивается для каждого пустого каскада: , где – количество пустых каскадов, – количество пустых ячеек. [5] Максимальное число, которое можно переместить в пустой каскад, равно . [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 году . монохромный дисплей на системах 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 × 1067 , отдельные сделки. Однако некоторые игры фактически идентичны другим, поскольку масти, присвоенные картам, произвольны или столбцы можно менять местами. С учетом этих факторов получается примерно 1,75 × 1064 различных игры. [2]

Рекомендации

  1. ^ Леонхард, Вуди (2009). Windows 7 «все в одном» для чайников. Джон Уайли и сыновья. п. 293. ИСБН 9780470487631.
  2. ^ abcdefgh Келлер, Майкл (4 августа 2015 г.). «FreeCell — Часто задаваемые вопросы (FAQ)» . Лаборатория пасьянсов . Проверено 7 февраля 2017 г.
  3. ^ Гленн, Джим и Дентон, Кэри. Сокровищница семейных игр (стр. 105). Ридерс Дайджест, 2003 г. ( ISBN 9780762104314 ) 
  4. ^ «PySol - Правила для Freecell» . Документация PySolFC . Проверено 3 февраля 2018 г.
  5. ^ ab "пасьянс - 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...»
  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.

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

Викискладе есть медиафайлы по теме FreeCell .

Смотрите также