Ghost (spel)
Ghost (även känt som spöken eller endbee ) är ett skrivna eller talade ordspel där spelare turas om att lägga till bokstäver till ett växande ordfragment, och försöker att inte vara den som fyller i ett giltigt ord. Varje fragment måste vara början på ett verkligt ord, och vanligtvis ställs ett minimum på längden på ett ord som räknas, till exempel tre eller fyra bokstäver. Spelaren som slutför ett ord förlorar omgången och får en "bokstav" (som i basketspelet häst ), med spelare som elimineras när de har fått alla fem bokstäverna i ordet "spöke".
Ghost kan spelas av två eller flera spelare och kräver ingen utrustning, även om det kan spelas med penna och papper istället för att talas högt.
Spelaren vars tur det är får – istället för att lägga till en bokstav – utmana den föregående spelaren att bevisa att det aktuella fragmentet faktiskt är början på ett ord. Om den utmanade spelaren kan namnge ett sådant ord, förlorar utmanaren omgången; annars förlorar den utmanade spelaren omgången. Om en spelare bluffar, eller slutför ett ord utan att andra spelare märker det, fortsätter spelet. När en omgång slutar går spelet vanligtvis till vänster.
Vinnande strategi
Eftersom spelträdet för Ghost kan härledas från listan över kombinationer av bokstäver som anses vara ord, kan spelet (som spelat av två spelare) enkelt "lösas" för att hitta en vinnande strategi för en spelare.
Alan Frank, en medlem av National Puzzlers' League , konstruerade ett exempel på en vinnande strategi 1987, baserad på Official Scrabble Players Dictionary . Randall Munroe publicerade ett exempel på en vinnande strategi 2007 på nyhetssidan för sin webbserie, xkcd . Han baserade sin lösning på Ubuntu- ordboken.
Varianter
Superghost (även känt som Fore-and-Aft i Hoyle's Rules of Games, Lexicant eller Llano), spelas genom att välja antingen början eller slutet av det växande ordfragmentet och lägga till en bokstav där. Till exempel, givet fragmentet ERA, kan en spelare erbjuda B ERA eller ERA D . Denna version spelades av James Thurber och hans vänkrets.
Superduperghost spelas genom att bestämma om bokstäverna i ordfragmentet ska vändas innan du lägger till en bokstav i fragmentets början eller slutet. Till exempel, givet fragmentet ERA, kan en spelare erbjuda B ERA, ERA D , N ARE eller ARE N . Denna variant antogs först allmänt vid 1978 års World Science Fiction Convention i Phoenix, Arizona (IguanaCon) och krediteras till Cary Hammer och Mark Malamud . [ citat behövs ]
Xghost (ibland även känd som Superduperghost eller Llama) spelas genom att lägga till en bokstav var som helst i det växande ordfragmentet, inklusive mellan bokstäver. Till exempel, givet fragmentet ERA, kan en spelare erbjuda B ERA, ERA D , E B RA eller ER M A. Denna version uppfanns av Daniel Asimov omkring 1970. Ursprungligen och fortfarande ofta känd som Superduperghost , spelades den av hans cirkel av matematikstudentvänner vid UC Berkeley . [ citat behövs ]
Anaghost låter spelaren ordna om ( ana gram) bokstäverna förutom att lägga till en. Till exempel, givet fragmentet ERA, kan en spelare erbjuda EAR T , E B AR eller N REA.
Spook spelas genom att lägga till bokstäver i en "pool" där ingen fast ordning antas. I det här spelet är målet att undvika att slutföra en bokstavspool som kan beställas för att bilda ett ord. Till exempel, med tanke på poolen {A,B,F,L,S,U}, skulle en spelare vara oklokt att lägga till H, vilket skulle bilda ordet BASHFUL. Däremot kan de lägga till B och citera ordet FLASHBULB om de utmanas.
Dessa varianter kräver vanligtvis mycket mer ansträngning och tid att spela än det konventionella spelet, och är som sådana mindre kända och mindre populära.
Cheddar Gorge spelas genom att lägga till ett ord i slutet av ett växande meningsfragment och undvika att fullborda en mening. Den här varianten blev populär i BBC Radio show I'm Sorry I Haven't a Clue
Historia
Namnet "spöke" är förkortat från det ursprungliga namnet "tre tredjedelar av ett spöke"; en spelare, efter att ha förlorat, blev en, två och slutligen tre "tredjedelar av ett spöke", vid vilken tidpunkt de skulle flyta iväg och vara ute ur spelet.
Beräkningskomplexitet
Givet ett reguljärt uttryck R , om två spelare turas om att spela Ghost med språket som genereras av R , är problemet med att avgöra om spelare 1 har en vinnande strategi i EXPSPACE och är PSPACE-svårt .
Det har visat sig vara PSPACE-svårt genom att reducera Generalized Geography , ett problem som är känt för att vara PSPACE-svårt, till ett spel Ghost. Specifikt, givet en generaliserad geografigraf, kan en icke-deterministisk finit automat konstrueras, som ger ett reguljärt uttryck R, så att spelare 1 har en vinnande strategi i Ghost med R om och bara om de har en vinnande strategi i spelet Generalized Geography.
Detta bevis sträcker sig till Superghost, Superduperghost, Xghost, som spelas på vanliga språk som genereras av reguljära uttryck. Så Superghost, Superduperghost, Xghost som spelas på vanliga språk är alla PSPACE-hårda och i EXPSPACE. Spook på vanligt språk är PSPACE-svårt, men det är okänt om det finns i EXPSPACE.
På tyska
På tyska kan ord bildas ganska fritt genom sammanlänkning. På grund av detta kan man skriva ett reguljärt uttryck som genererar ett reguljärt språk L, så att varje ord i L tekniskt sett är ett ord (vilket kan vara meningslöst) på tyska. Ett spökespel som spelas på sådana språk L kallas tyskt spöke . Denna variant visade sig också vara PSPACE-hård.