Терпение игра | |
Игра Freecell на KDE | |
Именованные варианты | Игра Бейкера |
---|---|
Семья | Свободная ячейка |
Палуба | Одиночная 52-карта |
См. Также Глоссарий терминов терпения. |
FreeCell - это карточная игра- пасьянс, в которой используется стандартная колода из 52 карт. Он кардинально отличается от большинства пасьянсов тем, что очень мало сделок невозможно решить, и все карты сдаются в открытую с самого начала игры. Хотя программные реализации различаются, большинство версий помечают руки числом (полученным из начального значения, используемого генератором случайных чисел для перетасовки карт).
Microsoft включила компьютерную игру FreeCell в каждый выпуск операционной системы Windows с 1995 года, что значительно повысило популярность игры среди пользователей персональных компьютеров и даже привело к созданию нескольких веб-сайтов, посвященных FreeCell. Microsoft FreeCell настолько важен для многих игроков FreeCell, что многие другие программные реализации стремятся к совместимости с его генератором случайных чисел, чтобы воспроизвести его пронумерованные руки.
Количество карт, которые может переместить игрок, эквивалентно количеству пустых ячеек плюс одна, причем это число удваивается в зависимости от количества пустых каскадов. Математическое уравнение для количества карточек, которые можно переместить, имеет вид (2 M) × (N + 1), где M - количество пустых каскадов, а N - количество пустых ячеек.
По оценкам, 99,999% возможных сделок являются решаемыми. Сделка номер 11982 из версии FreeCell для Windows является примером неразрешимой сделки FreeCell, единственной сделкой среди исходных «Microsoft 32000», которая неразрешима.
Один из старейших предков FreeCell - Eight Off. В июне 1968 года издание Scientific American, Мартин Гарднер описал в своей колонке «Математические игры» игра К.Л. Бейкер, который похож на Солитер, за исключением того, что карты на табло строятся по масти, а не альтернативные цветами. Гарднер писал: «Бейкера этой игре научил его отец, который, в свою очередь, научился ей у англичанина в 1920-е годы». Этот вариант теперь называется «Игра Бейкера». Истоки FreeCell могут восходить еще дальше к 1945 году и к скандинавской игре под названием «Наполеон на острове Святой Елены» (а не в пасьянсе « Наполеон на острове Святой Елены», также известном как «Сорок разбойников»).
Пол Альфилль изменил Baker's Game, построив карты в соответствии с другими цветами, создав таким образом FreeCell. Он реализовал первую компьютеризированную версию, будучи студентом-медиком в Университете Иллинойса, на языке программирования TUTOR для образовательной компьютерной системы PLATO в 1978 году. Альфилль смог отобразить легко узнаваемые графические изображения игральных карт на монохромном дисплее 512 × 512 на экране. системы PLATO.
Эта исходная среда FreeCell позволяла играть в игры с 4–10 столбцами и 1–10 ячейками в дополнение к стандартной игре 8 × 4. Для каждого варианта программа хранила ранжированный список игроков с самыми длинными выигрышными сериями. Также существовала система турниров, которая позволяла людям соревноваться, чтобы выиграть сложные тщательно подобранные сделки. Пол Альфилль более подробно описал эту раннюю среду FreeCell в интервью 2000 года.
В 2012 году исследователи использовали методы эволюционных вычислений для создания выигрышных игроков FreeCell.
Другие пасьянсы, связанные с или вдохновленные Солитер включают Seahaven башни, Пингвин, сталактиты, ForeCell, Антарес (крест с Scorpion ), а также несколько других.
В игре FreeCell количество карточек постоянно. Это означает, что в постоянное время человек или компьютер могут перечислить все возможные ходы из данной начальной конфигурации и обнаружить выигрышный набор ходов или, если игра не может быть решена, его отсутствие. Чтобы провести интересный анализ сложности, необходимо построить обобщенную версию игры FreeCell с картами 4 × n. Эта обобщенная версия игры является NP-полной ; маловероятно, что существует какой-либо алгоритм, более эффективный, чем перебор, который может найти решения для произвольных обобщенных конфигураций FreeCell.
Их 52! (то есть 52 факториала ), или приблизительно 8 × 10 67, различных сделок. Однако некоторые игры фактически идентичны другим, потому что масти, назначенные картам, произвольны или столбцы можно менять местами. С учетом этих факторов получается примерно 1,75 × 10 64 различных игр.