Mark Gritter (markgritter) wrote,
Mark Gritter
markgritter

Solving the "ghost" word game.

Ghost is played as follows: First player names a letter. Each subsequent player adds a letter to the front or back of the word fragment so far. If a player names a word of at least four letters, she loses. If a player is challenged to name a word containing the fragment he produced, and cannot, he loses (otherwise the challenger loses.)

Example play: H -> GH -> GHO -> NGHO -> ONGHO -> challenge -> STRONGHOLD

Who wins with optimal play in two-player Ghost?

I wrote some code to find out. You can see it here: https://gist.github.com/mgritter/60514d8591b62cfc08f8fdf0bf020f11


Ghost with the SOWPODS word list is a first-player win. The winning first moves are to 'U' or 'Y' only.

After U, the winning 3-letter positions are

UAA, AUH, UBC, BUF, GUC, CCU, UDC, DUH, UEE, AEU, BUF, BFU, UGF, GUB, AUH, HUE, UID, IUJ, FUJ, JUB, CUK, CKU, EUL, LUH, UMH, CMU, UNM, NUH, EUO, OUJ, UPD, BPU, UQA, QUH, URJ, RUQ, USJ, SUK, UTV, LTU, CUU, GUV, VUG, WUK, UXG, XUP, AUY, YUA, GUZ, DZU

UW: challenge, no valid extension

(This list could be compacted a little bit, CUU could follow either CU or UU, so CCU is not needed.)

From GUZ, the only legal move is to GUZZ, eventually leading to GUZZLE or GUZZLING. This seems fairly typical; there are very few valid choices further down the tree. The branch with the most choices for the losing player is UID, and here are the winning responses:

UIDA response is UIDAB

UIDD response is UIDDA

UIDE response is LUIDE

UIDG response is UIDGE

UIDI response is UIDID

UIDL response is QUIDL

LUID response is LUIDE

UIDN response is QUIDN

UIDO response is GUIDO

UIDR response is LUIDR

RUID response is RUIDE

UIDS response is RUIDS

TUID response is CTUID

UIDU response is QUIDU

UIDW response is GUIDW

UIDY response is LUIDY

The low average branching factor suggests the strategy could be memorized with a fairly limited word list.
Subscribe

  • Predictions for 2018

    Tintri asked me to put together some technology predictions for 2018. You can access the "on-demand webinar" here:…

  • (no subject)

    Here's the letter I sent my representative about just one part of the R tax plan: Representative Lewis, The recently released tax reform…

  • Selecting Strings in Solidity

    For a personal project implementing procedurally generated content on Ethereum, I would like to find the most efficient way to accomplish the…

  • Post a new comment

    Error

    switch
    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
    Help
  • 2 comments