Ghost (game)

Last updated

Ghost (also known as ghosts [1] or endbee [2] ) is a written or spoken word game in which players take turns to extend the letters of a word without completing a valid word.

Contents

Ghost can be played by two or more players and requires no equipment, although it can be played with pencil and paper instead of being spoken aloud.

Rules

Players take turns to call a letter, adding those letters to a shared, growing word fragment. (For example, if the first player calls "T", the second might call "R" to make "TR".)

Each fragment must be the beginning of 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.

If a complete word is formed in this way, the player who called the final letter of it loses the round. (Usually some minimum is set on the length of a word that counts, such as three or four letters.) The losing player 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".

When a round ends, play generally passes to the left.

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, [3] constructed a sample winning strategy in 1987, based on the Official Scrabble Players Dictionary. [4] 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. [5]

Variants

Superghost

Superghost 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. [6]

This is also known as Fore-and-Aft in Hoyle's Rules of Games, Lexicant, or Llano.

Superduperghost

This 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.[ citation needed ]

Xghost

This 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.[ citation needed ]

This variant is also sometimes known as Llama.

Anaghost

This version allows the player to rearrange (anagram) the letters in addition to adding one. For example, given the fragment ERA, a player might offer EART, EBAR, or NREA. [7]

Spook

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, they 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

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 [8]

History

The name "ghost" is shortened from the original name "three thirds of a ghost"; a player, upon losing, became one, two, and finally three "thirds of a ghost", at which point they would float away and be out of the game. [9] [10]

Computational complexity

Given a regular expression R, if 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. [11]

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.

In German

In German, words can be formed quite freely by concatenation. Because of this, one can write a regular expression that generates a regular language L, such that every word in L is technically a word (which might be nonsensical) in German. A game of ghost played on such languages L is called German ghost. This variant was also shown to be PSPACE-hard. [11]

See also

Related Research Articles

<i>Scrabble</i> Board game with words

Scrabble is a word game in which two to four players score points by placing tiles, each bearing a single letter, onto a game board divided into a 15×15 grid of squares. The tiles must form words that, in crossword fashion, read left to right in rows or downward in columns and are included in a standard dictionary or lexicon.

In computer science, string-searching algorithms, sometimes called string-matching algorithms, are an important class of string algorithms that try to find a place where one or several strings are found within a larger string or text.

<span class="mw-page-title-main">Hex (board game)</span> Abstract strategy board game

Hex is a two player abstract strategy board game in which players attempt to connect opposite sides of a rhombus-shaped board made of hexagonal cells. Hex was invented by mathematician and poet Piet Hein in 1942 and later rediscovered and popularized by John Nash.

<span class="mw-page-title-main">PSPACE</span> Set of decision problems

In computational complexity theory, PSPACE is the set of all decision problems that can be solved by a Turing machine using a polynomial amount of space.

In computational complexity theory, a decision problem is PSPACE-complete if it can be solved using an amount of memory that is polynomial in the input length and if every other problem that can be solved in polynomial space can be transformed to it in polynomial time. The problems that are PSPACE-complete can be thought of as the hardest problems in PSPACE, the class of decision problems solvable in polynomial space, because a solution to any one such problem could easily be used to solve any other problem in PSPACE.

In computational complexity theory, the complexity class EXPTIME (sometimes called EXP or DEXPTIME) is the set of all decision problems that are solvable by a deterministic Turing machine in exponential time, i.e., in O(2p(n)) time, where p(n) is a polynomial function of n.

In computational complexity theory, EXPSPACE is the set of all decision problems solvable by a deterministic Turing machine in exponential space, i.e., in space, where is a polynomial function of . Some authors restrict to be a linear function, but most authors instead call the resulting class ESPACE. If we use a nondeterministic machine instead, we get the class NEXPSPACE, which is equal to EXPSPACE by Savitch's theorem.

<span class="mw-page-title-main">Checkers</span> Board game

Checkers, also known as draughts, is a group of strategy board games for two players which involve diagonal moves of uniform game pieces and mandatory captures by jumping over opponent pieces. Checkers is developed from alquerque. The term "checkers" derives from the checkered board which the game is played on, whereas "draughts" derives from the verb "to draw" or "to move".

<span class="mw-page-title-main">Crossword</span> Grid-based word puzzle

A crossword is a word game consisting of a grid of black and white squares, into which solvers enter words or phrases ("entries") crossing each other horizontally ("across") and vertically ("down") according to a set of clues. Each white square is typically filled with one letter, while the black squares are used to separate entries. The first white square in each entry is typically numbered to correspond to its clue.

<span class="mw-page-title-main">Havannah (board game)</span>

Havannah is a two-player abstract strategy board game invented by Christian Freeling. It belongs to the family of games commonly called connection games; its relatives include Hex and TwixT. Havannah has "a sophisticated and varied strategy" and is best played on a base-10 hexagonal board, 10 hex cells to a side.

Combinatorial game theory measures game complexity in several ways:

  1. State-space complexity,
  2. Game tree size,
  3. Decision complexity,
  4. Game-tree complexity,
  5. Computational complexity.
<span class="mw-page-title-main">Generalized game</span> Game generalized so that it can be played on a board or grid of any size

In computational complexity theory, a generalized game is a game or puzzle that has been generalized so that it can be played on a board or grid of any size. For example, generalized chess is the game of chess played on an board, with pieces on each side. Generalized Sudoku includes Sudokus constructed on an grid.

<span class="mw-page-title-main">Super Scrabble</span> Board game based on Scrabble

Super Scrabble is a board game introduced in 2004 and a variant of Scrabble. It is played on a 21×21 grid board instead of Scrabble's usual 15×15, and uses twice as many letter tiles.

In computational complexity theory, generalized geography is a well-known PSPACE-complete problem.

Scrabble variants are games created by changing the normal Scrabble rules or equipment.

Lexicant is a paper and pencil word game for two players. A letter is written on a sheet of paper, and each player takes turns adding a letter either to the beginning or the end of this ever-growing word stem. Any word-stem a player creates must form part of a valid English word, without actually being a word itself. The first player to create a word loses.

Word chain, also known as grab on behind, last and first, alpha and omega, and the name game, is a word game in which players come up with words that begin with the letter or letters that the previous word ended with. A category of words is usually chosen, there is a time limit such as five seconds, and words may not be repeated in the same game. The version of the game in which cities are used is called geography, and a generalized version with place names is called Atlas.

<span class="mw-page-title-main">Go and mathematics</span> Calculations of the game complexity of go

The game of Go is one of the most popular games in the world. As a result of its elegant and simple rules, the game has long been an inspiration for mathematical research. Shen Kuo, an 11th century Chinese scholar, estimated in his Dream Pool Essays that the number of possible board positions is around 10172. In more recent years, research of the game by John H. Conway led to the development of the surreal numbers and contributed to development of combinatorial game theory (with Go Infinitesimals being a specific example of its use in Go).

In computational complexity theory, the language TQBF is a formal language consisting of the true quantified Boolean formulas. A (fully) quantified Boolean formula is a formula in quantified propositional logic where every variable is quantified, using either existential or universal quantifiers, at the beginning of the sentence. Such a formula is equivalent to either true or false. If such a formula evaluates to true, then that formula is in the language TQBF. It is also known as QSAT.

References

  1. ↑ Hoyle's Rules of Games
  2. ↑ "Ghosts word game". Encyclopedia Britannica. Retrieved 14 October 2021.
  3. ↑ "NPL Directory". The Enigma. National Puzzlers' League.
  4. ↑ "Ghostbusters", Word Ways, 1987, page 206
  5. ↑ Randall Munroe (December 31, 2007). "Ghost". xkcd - The blag of the webcomic.
  6. ↑ 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.
  7. ↑ David Parlett, Botticelli and Beyond
  8. ↑ BBC Website for I'm Sorry I Haven't a Clue.
  9. ↑ Try One of My Games, 1970
  10. ↑ Mulvey, Mina (1971). Good Housekeeping Complete Book of Home Entertaining. Good Housekeeping Books.
  11. 1 2 Demaine, Erik D.; Ma, Fermi; Susskind, Matthew; Waingarten, Erik (2015). "You Should Be Scared of German Ghost". Journal of Information Processing. 23 (3): 293–298. doi: 10.2197/ipsjjip.23.293 . ISSN   1882-6652.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.