Ghost (game)
Ghost is a written or spoken word game in which players take turns adding letters to a growing word fragment, trying not to be the one to complete a valid word. Each fragment must be the beginning of an actual word, and usually some minimum is set on the length of a word that counts, such as three or four letters. The player who completes a word loses the round and earns a "letter" (as in the basketball game horse), with players being eliminated when they have been given all five letters of the word "ghost".
Ghost can be played by two or more players of any age and requires no equipment, although it can be played with pencil and paper instead of being spoken aloud.
Game play
A player is chosen at random to start the game, and begins by naming any letter of the alphabet. Players then take turns to add letters to this fragment, with the aim being to avoid completing an actual word. The player whose turn it is may - instead of adding a letter - challenge the previous player to prove that the current fragment is actually the beginning of a word. If the challenged player can name such a word, the challenger loses the round; otherwise the challenged player loses the round. If a player bluffs, or completes a word without other players noticing, then play continues. When a round ends, play generally passes to the left.
If any score is kept at all, the traditional method uses the letters of the word "Ghost" in the same fashion as the basketball game horse, with each loss giving the player the next letter of the word, and a player being eliminated when they have all five letters.
In some versions of the game, players that obtain all the letters of "ghost" continue to participate by trying to distract other players and turn them into ghosts. If a player does not have all the letters of the word "ghost" and he or she talks to an existing ghost, they immediately become a ghost. This rule serves to accelerate games of Ghost with many players. This is also a rule in the games of Llama and Llano.
Winning strategy
Since the game tree of Ghost can be derived from the list of combinations of letters that are considered to be words, the game (as played by two players) can be easily "solved" to find a winning strategy for one player.
Alan Frank, a member of the National Puzzlers' League,[1] constructed a sample winning strategy in 1987, based on the Official Scrabble Players Dictionary.[2] Randall Munroe posted a sample winning strategy in 2007 on the news page of his webcomic, xkcd. He based his solution on the Ubuntu dictionary.[3]
Variants
Superghost (also known as Lexicant or Llano) is played by choosing either the beginning or end of the growing word fragment and adding a letter there. For example, given the fragment ERA, a player might offer BERA or ERAD. This version was played by James Thurber and his circle of friends.[4]
Superduperghost is played by deciding whether to reverse the letters of the word fragment before adding a letter to the fragment's beginning or end. For example, given the fragment ERA, a player might offer BERA, ERAD, NARE, or AREN. This variant was first broadly adopted at the 1978 World Science Fiction Convention in Phoenix, Arizona (IguanaCon) and is credited to Cary Hammer and Mark Malamud.
Xghost (sometimes also known as Superduperghost or Llama) is played by adding a letter anywhere in the growing word fragment, including between letters. For example, given the fragment ERA, a player might offer BERA, ERAD, EBRA, or ERMA. This version was invented by Daniel Asimov around 1970. Originally and still often known as Superduperghost, it was played by his circle of mathematics grad student friends at U.C. Berkeley.
Spook is played by adding letters to a "pool" in which no fixed order is assumed. In this game, one's objective is to avoid completing a letter pool which can be ordered to form a word. For example, given the pool {A,B,F,L,S,U}, a player would be unwise to add H, which would form the word BASHFUL. However, he or she might add B, and cite the word FLASHBULB if challenged.
These variants usually require much more effort and time to play than the conventional game, and as such are lesser-known and less popular.
Cheddar Gorge is played by adding a word to the end of a growing sentence fragment, and avoiding the completion of a sentence. This variant was popularized on the BBC Radio show I'm Sorry I Haven't a Clue[5]
Computational Complexity
Given a regular expression R, two players take turns playing Ghost with the language generated by R, the problem of determining whether player 1 has a winning strategy is in EXPSPACE, and is PSPACE-hard. [6]
It's proved to be PSPACE-hard by reducing Generalized Geography, a problem known to be PSPACE-hard, to a game of Ghost. Specifically, given a Generalized Geography graph, a nondeterministic finite automaton can be constructed, which gives a regular expression R, such that player 1 has a winning strategy in Ghost with R if and only if they have a winning strategy in the Generalized Geography game.
This proof extends to Superghost, Superduperghost, Xghost, played on regular languages generated by regular expressions. Thus Superghost, Superduperghost, Xghost played on regular languages are all PSPACE-hard and in EXPSPACE. Spook on regular language is PSPACE-hard, but it's unknown if it's in EXPSPACE.
German Ghost
Because in German, words can be formed quite freely by concatenation, thus it's possible to write a regular expression that generates a regular language L, such that every word in L is technically a word (might be nonsensical) in German. For a game of Ghost played on such languages L, call it German Ghost.
It is shown in the paper that playing German Ghost is PSPACE-hard.
See also
References
- ↑ "NPL Directory". The Enigma. National Puzzlers' League.
- ↑ "Ghostbusters", Word Ways, 1987, page 206
- ↑ Randall Munroe (December 31, 2007). "Ghost". xkcd - The blag of the webcomic.
- ↑ James Thurber (29 September 1959). ""Do 'You Want To Make Something Out of it?, Or, If you Put An "O" On "Understo", You'll Ruin My "Thunderstorm"". The New Yorker. Retrieved 2007-07-10.
- ↑ BBC Website for I'm Sorry I Haven't a Clue.
- ↑ Demaine, Erik; Ma, Fermi; Susskind, Matthew; Waingarten, Erik (May 2015). "You Should Be Scared of German Ghost". Journal of Information Processing. 23 (3): 293–298. doi:10.2197/ipsjjip.23.293.