Призрак (игра)

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

В «Привидение» могут играть двое или более игроков, и для этого не требуется никакого оборудования, хотя в игру можно играть с помощью карандаша и бумаги, а не проговаривать слова вслух.

Игроки по очереди называют букву, добавляя эти буквы к общему, растущему фрагменту слова. (Например, если первый игрок называет «Т», второй может назвать «Р», чтобы получилось «ТР».)

Каждый фрагмент должен быть началом конкретного слова.

Игрок, чья очередь, может — вместо добавления буквы — бросить вызов предыдущему игроку, чтобы тот доказал, что текущий фрагмент на самом деле является началом слова. Если оспариваемый игрок может назвать такое слово, оспаривающий проигрывает раунд; в противном случае оспариваемый игрок проигрывает раунд. Если игрок блефует или заканчивает слово так, что другие игроки этого не заметили, то игра продолжается.

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

Когда раунд заканчивается, ход обычно переходит к левому ходу.

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

Алан Фрэнк, член Национальной лиги головоломок , ^[3] в 1987 году разработал пример выигрышной стратегии на основе Официального словаря игроков в Скрэббл . ^[4] Рэндалл Манро опубликовал пример выигрышной стратегии в 2007 году на новостной странице своего веб-комикса xkcd . Он основал свое решение на словаре Ubuntu . ^[5]

Superghost играется путем выбора начала или конца фрагмента растущего слова и добавления туда буквы. Например, учитывая фрагмент ERA, игрок может предложить B ERA или ERA D. В эту версию играл Джеймс Тербер и его круг друзей. ^[6]

В Правилах игр Хойла, Lexicant или Llano это также известно как «вперед-назад» .

В эту игру играют, решая, следует ли переставить буквы слова фрагмент перед добавлением буквы в начало или конец фрагмента. Например, если задан фрагмент ERA, игрок может предложить B ERA, ERA D , N ARE или ARE N . Этот вариант был впервые широко принят на Всемирном конвенте научной фантастики 1978 года в Финиксе, штат Аризона (IguanaCon) и приписывается Кэри Хаммеру и Марку Маламуду . ^{[ необходима цитата ]}

Это играется путем добавления буквы в любом месте растущего фрагмента слова, в том числе между буквами. Например, учитывая фрагмент ERA, игрок может предложить B ERA, ERA D , E B RA или ER M A.

Эта версия была изобретена Дэниелом Азимовым примерно в 1970 году. Первоначально и до сих пор часто известная как Superduperghost , в нее играл его круг друзей-математиков-выпускников Калифорнийского университета в Беркли . ^{[ требуется ссылка ]}

Этот вариант иногда также называют ламой.

Эта версия позволяет игроку переставлять ( анаграмма ) буквы в дополнение к добавлению одной. Например, учитывая фрагмент ERA, игрок может предложить EAR T , E B AR или N REA. ^[7]

Spook играется путем добавления букв в «пул», в котором не предполагается фиксированный порядок. В этой игре цель состоит в том, чтобы избежать завершения пула букв, который может быть упорядочен для формирования слова. Например, учитывая пул {A,B,F,L,S,U}, игроку было бы неразумно добавлять H, что образовало бы слово BASHFUL. Однако он может добавить B и сослаться на слово FLASHBULB, если его оспорят.

Эти варианты обычно требуют гораздо больше усилий и времени для игры, чем обычная игра, и поэтому менее известны и популярны.

Cheddar Gorge играется добавлением слова в конец растущего фрагмента предложения и избеганием завершения предложения. Этот вариант был популяризирован в радиошоу BBC I'm Sorry I Haven't a Clue . ^[8]

Название «призрак» является сокращением от оригинального названия «три трети призрака»; игрок, проиграв, становился одной, двумя и, наконец, тремя «третями призрака», после чего он уплывал и выбывал из игры. ^{[9] [10]}

При наличии регулярного выражения R , если два игрока по очереди играют в Ghost с языком, сгенерированным R , проблема определения того, имеет ли игрок 1 выигрышную стратегию, находится в EXPSPACE и является PSPACE-трудной . ^[11]

Доказано, что она является PSPACE-трудной, путем сведения Обобщенной Географии , проблемы, известной как PSPACE-трудная, к игре Призрак. В частности, учитывая граф Обобщенной Географии, можно построить недетерминированный конечный автомат , который дает регулярное выражение R, такое, что у игрока 1 есть выигрышная стратегия в Призраке с R тогда и только тогда, когда у него есть выигрышная стратегия в игре Обобщенная География.

Это доказательство распространяется на Superghost, Superduperghost, Xghost, сыгранные на обычных языках, сгенерированных регулярными выражениями. Таким образом, Superghost, Superduperghost, Xghost, сыгранные на обычных языках, являются PSPACE-трудными и находятся в EXPSPACE. Spook на обычном языке является PSPACE-трудным, но неизвестно, находится ли он в EXPSPACE.

В немецком языке слова могут быть образованы довольно свободно путем конкатенации. Благодаря этому можно написать регулярное выражение, которое генерирует регулярный язык L, такой, что каждое слово в L технически является словом (которое может быть бессмысленным) в немецком языке. Игра в привидение, играемая на таких языках L, называется немецким привидением . Этот вариант также оказался PSPACE-трудным. ^[11]

• Unhalfkiring