Ghost (game)

Last updated

Ghost (also known as ghosts [1] or pig [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.

<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.

<span class="mw-page-title-main">Shiritori</span> Japanese word game

Shiritori is a Japanese word game in which the players are required to say a word which begins with the final kana of the previous word. No distinction is made between hiragana, katakana, and kanji. "Shiritori" literally means "taking the end" or "taking the rear".

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> Strategy board game

Checkers, also known as draughts, is a group of strategy board games for two players which involve forward movements 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".

A solved game is a game whose outcome can be correctly predicted from any position, assuming that both players play perfectly. This concept is usually applied to abstract strategy games, and especially to games with full information and no element of chance; solving such a game may use combinatorial game theory and/or computer assistance.

<span class="mw-page-title-main">Anagrams (game)</span> Tile-based word game

Anagrams is a tile-based word game that involves rearranging letter tiles to form words.

<span class="mw-page-title-main">TwixT</span> Connection board game in the 3M bookshelf game series

TwixT is a two-player strategy board game, an early entrant in the 1960s 3M bookshelf game series. It became one of the most popular and enduring games in the series. It is a connection game where players alternate turns placing pegs and links on a pegboard in an attempt to link their opposite sides. While TwixT itself is simple, the game also requires strategy, so young children can play it, but it also appeals to adults. The game has been discontinued except in Germany and Japan.

In combinatorial game theory, the strategy-stealing argument is a general argument that shows, for many two-player games, that the second player cannot have a guaranteed winning strategy. The strategy-stealing argument applies to any symmetric game in which an extra move can never be a disadvantage. A key property of a strategy-stealing argument is that it proves that the first player can win the game without actually constructing such a strategy. So, although it might prove the existence of a winning strategy, the proof gives no information about what that strategy is.

<i>Chain Reaction</i> (game show) American television game show

Chain Reaction is an American television game show created by Bob Stewart, in which players compete to form chains composed of two-word phrases.

<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).

<span class="mw-page-title-main">The Game (mind game)</span> Mental thought-suppression game

The Game is a mind game in which the objective is to avoid thinking about The Game itself. Thinking about The Game constitutes a loss, which must be announced each time it occurs. It is impossible to win most versions of The Game. Depending on the variation, it is held that the whole world, or all those who are aware of the game, are playing it at all times. Tactics have been developed to increase the number of people who are aware of The Game, and thereby increase the number of losses.

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.