ipynb/Ghost.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Ghost\n",
    "\n",
    "According to [Wikipedia](https://en.wikipedia.org/wiki/Ghost_(game&#41;):\n",
    "\n",
    ">  **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.*\n",
    "\n",
    "I'd like to create a program to allow any two players (human or computer) to play the game, and I'd like to figure out who wins if both players play optimally. The concepts I will need to define, and my implementation choices, are as follows:\n",
    "\n",
    "- **Words**: I will read a standard online word list, `enable1`, and make a set of all the words of sufficient length.\n",
    "- **Fragment**: a fragment is a `str` of letters, such as `'gho'`.\n",
    "- **Beginning**: each word has a set of valid beginnings: for `ghost` it is `{'', g, gh, gho, ghos, ghost}`.  \"Prefix\" is a synonym of \"beginning\".\n",
    "- **Vocabulary**: A `Vocabulary` object holds a set of all the `words` in a dictionary, as well as all the valid `fragments` (beginnings) of the words.\n",
    "- **Player**: The first player will be called player `0`; the second player `1`. \n",
    "- **Play**: A play is a new fragment formed by adding one letter to the end of the existing fragment.\n",
    "- **Legal Play**: A play that is a valid prefix of some word. `enable1.legal_plays('gho') = {'ghos, 'ghou'}`.\n",
    "- **Strategy**: A strategy is a function with signature `strategy(vocab, fragment) -> play`.\n",
    "- **Game**: `play_game(vocab, *strategies)` plays a game between two (or more) player strategies.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Vocabulary: Words, Fragments, Legal Plays, and `enable1`\n",
    "\n",
    "`Vocabulary(words)` takes a collection of words as input, stores the words as a set, and also stores all the legal fragments of those words. `legal_plays(fragments)` gives a set of all plays that can be formed by adding a letter to create a legal word fragment. I also define the function `words` to split any string into component words."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Vocabulary:\n",
    "    \"Holds a set of legal words and a set of legal prefix fragments of those words.\"\n",
    "    def __init__(self, words, minlength=3):\n",
    "        self.words = {word for word in words if len(word) >= minlength}\n",
    "        self.fragments = {word[:i] for word in self.words for i in range(len(word) + 1)}\n",
    "        \n",
    "    def legal_plays(self, fragment): \n",
    "        return {fragment + L for L in alphabet} & self.fragments     \n",
    "    \n",
    "alphabet = 'abcdefghijklmnopqrstuvwxyz'\n",
    "    \n",
    "words = str.split # Function to split a str into words"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here is a small example with a vocabulary of just three words:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'game', 'ghost', 'ghoul'}"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "v = Vocabulary(words('game ghost ghoul'))\n",
    "\n",
    "v.words"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'', 'g', 'ga', 'gam', 'game', 'gh', 'gho', 'ghos', 'ghost', 'ghou', 'ghoul'}"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "v.fragments"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And here is a large vocabulary, from a standard online Scrabble™ word list known as `enable1`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "! [ -e enable1.txt ] || curl -O http://norvig.com/ngrams/enable1.txt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "enable1 = Vocabulary(words(open('enable1.txt').read()))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's explore `enable1`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(172724, 387878, 'ethylenediaminetetraacetates')"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(enable1.words), len(enable1.fragments), max(enable1.words, key=len)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'ghos', 'ghou'}"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "enable1.legal_plays('gho')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'ewe'}"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "enable1.legal_plays('ew')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'tha', 'the', 'thi', 'tho', 'thr', 'thu', 'thw', 'thy'}"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "enable1.legal_plays('th')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Players and Winners\n",
    "\n",
    "The first player is `0` and the second player is `1`. These names are convenient because:\n",
    "- During the course of the game, the player whose turn it is to play next is always the length of the current fragment mod 2.\n",
    "- When the game ends, the winning player is the length of the current fragment mod 2.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "to_play = winner = lambda fragment: len(fragment) % 2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Who Wins?\n",
    "\n",
    "Who wins a game if both players play rationally?  To answer that, consider the general situation at some point\n",
    "during the game where\n",
    "a player is presented with a fragment. That player can win if either:\n",
    "- The fragment is a complete word (meaning the other player just formed the word, and thereby lost).\n",
    "- The fragment is not a legal fragment (meaning the other player made a mistake, and thereby lost).\n",
    "- At least one of the legal plays  in this position puts the opponent in a position from which they *cannot* win.\n",
    "\n",
    "The function `win(vocab, fragment)` implements this. It returns a winning fragment if there is one, otherwise `False`. In particular, it returns `fragment` if the current player has already won (because `fragment` is\n",
    "a word or illegal fragment), and it returns one of the legal plays if that play leads to a position from\n",
    "which the opponent *cannot* `win`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "def win(vocab, fragment=''):\n",
    "    \"\"\"Does the current player have a forced win? \n",
    "    If so, return a play (or the current fragment) that leads to a win.\"\"\"\n",
    "    if fragment in vocab.words or fragment not in vocab.fragments:\n",
    "        return fragment\n",
    "    for play in vocab.legal_plays(fragment):\n",
    "        if not win(vocab, play):\n",
    "            return play \n",
    "    return False"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's test `win` to gain some confidence that we got it right:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# No winning play because all words have odd number of letters.\n",
    "win(Vocabulary(words('cat camel gecko'))) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'g'"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 'g' is a winning play (but 'c' would be a loser)\n",
    "win(Vocabulary(words('cat camel goat gerbil'))) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# No winning play; doomed to 'camel' or 'gar'\n",
    "win(Vocabulary(words('cat camel goat gecko gerbil gar'))) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'g'"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 'g' wins because 'ga' can be answered with 'gan' and 'ge' with 'ge'\n",
    "win(Vocabulary(words('cat camel goat gecko gerbil gar gannet'))) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# TL;DR: The Answer\n",
    "\n",
    "Can the first player win with the `enable1` vocabulary?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "win(enable1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**No.** The game is a win for the second player, not the first.\n",
    "This agrees with [xkcd](https://xkcd.com/)'s Randall Munroe, who [says](https://blog.xkcd.com/2007/12/31/ghost/) *\"I hear if you use the Scrabble wordlist, it’s always a win for the second player.\"*\n",
    "\n",
    "But ... Wikipedia says that the minimum word length can be \"three or four letters.\" In `enable1` the limit was three; let's try again with a limit of four:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'n'"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "enable1_4 = Vocabulary(enable1.words, 4)\n",
    "\n",
    "win(enable1_4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Yes.** The first player can win with this vocabulary, by playing `'n'` first (and there might be other first plays that also force a win). It makes sense that it is easier for the first player to win, because we've eliminated a bunch of three-letter words from the vocabulary, all of which are losers for the first player. So here's a good meta-strategy: Say \"*Hey, let's play a game of Ghost. We can use the `enable1` word list. Would you like the limit to be 3 or 4 letters?*\" Then if your opponent says three (or four) you can say \"*OK, since you decided that, I'll decide to go second (or first).*\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Playing the Game: Strategies\n",
    "\n",
    "We define a *strategy* as a function that is given a vocabulary and a fragment as arguments, and returns a legal play. Below we define `rational`, a strategy that wins whenever it is possible to do so and plays randomly otherwise,  and `ask` (a strategy factory that returns a strategy that, when called, will ask the named person to input a fragment)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "\n",
    "def rational(vocab, fragment): \n",
    "    \"Select a play that makes opponent not win (if possible), otherwise a random play.\"\n",
    "    return win(vocab, fragment) or random.choice(list(vocab.legal_plays(fragment)))\n",
    "\n",
    "def ask(name):\n",
    "    \"Return a strategy that asks for the next letter.\"\n",
    "    return lambda _, fragment: input('Player ' + name + ' given \"' + fragment + '\" plays? ')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here is a function to play a game. You give it a vocabulary, two (or possibly more) strategies, and optionally a `verbose` keyword to say if you want a line printed for each play or not."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "from itertools import cycle\n",
    "\n",
    "def play(vocab, *strategies, verbose=False):\n",
    "    \"Return (winner, final_fragment) for a game of Ghost between these strategies.\"\n",
    "    fragment = ''\n",
    "    for (p, strategy) in cycle(enumerate(strategies)): # p is the player number\n",
    "        play = strategy(vocab, fragment)\n",
    "        if verbose:\n",
    "            print('Player {}, given \"{}\", plays \"{}\".'.format(p, fragment, play))\n",
    "        if play not in vocab.legal_plays(fragment):\n",
    "            return (winner(fragment + '?'), play) # Player loses for making an illegal play\n",
    "        elif play in vocab.words:\n",
    "            return (winner(play), play)           # Player loses for making a word\n",
    "        else:\n",
    "            fragment = play                       # Keep playing"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1, 'odyssey')"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "play(enable1, rational, rational) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(1, 'truancies'),\n",
       " (1, 'xebec'),\n",
       " (1, 'ods'),\n",
       " (1, 'vying'),\n",
       " (1, 'ewe'),\n",
       " (1, 'bwana'),\n",
       " (1, 'vying'),\n",
       " (1, 'knell'),\n",
       " (1, 'zloty'),\n",
       " (1, 'flirt'),\n",
       " (1, 'zlote'),\n",
       " (1, 'bwana'),\n",
       " (1, 'gjetost'),\n",
       " (1, 'pliancies'),\n",
       " (1, 'flounce'),\n",
       " (1, 'ufologist'),\n",
       " (1, 'flour'),\n",
       " (1, 'dweeb'),\n",
       " (1, 'flirt'),\n",
       " (1, 'ignatia')]"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Does player 1 win every time?\n",
    "\n",
    "[play(enable1, rational, rational, verbose=False) for _ in range(20)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(0, 'nyctalopia')"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "play(enable1_4, rational, rational)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Player P given \"\" plays? d\n",
      "Player P given \"dw\" plays? dwa\n",
      "Player P given \"dwar\" plays? dwarv\n",
      "Player P given \"dwarve\" plays? dwarves\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "(1, 'dwarves')"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "play(enable1, ask('P'), rational)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Minimizing Possible Outcomes\n",
    "\n",
    "Now we know how to play perfectly, if we have a computer handy to execute the strategy.\n",
    "But can we summarize the strategy into a form that is small enough that a human can memorize it? I will define the function `outcomes(vocab, fragment, player)` to return a set of all the words that are possible outcomes of a game, where the opponent can use any strategy whatsoever, but `player` uses a strategy that is:\n",
    "\n",
    "- *Rational*: plays towards a forced win whenever there is one.\n",
    "- *Exploitive*: otherwise tries to give the opponent an opportunity to  make a mistake that can be exploited.\n",
    "- *Minimizing*: within the above constraints, returns the smallest possible set of words."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [],
   "source": [
    "import textwrap \n",
    "\n",
    "def outcomes(vocab, fragment, player):\n",
    "    \"The smallest set of outcome words, if player tries to win, and make the set small.\"\n",
    "    if fragment in vocab.words:\n",
    "        return {fragment}\n",
    "    else:\n",
    "        cases = [outcomes(vocab, play, player) for play in vocab.legal_plays(fragment)]\n",
    "        if to_play(fragment) == player: # Player picks the top priority case\n",
    "            return min(cases, key=lambda words: priority(words, player))\n",
    "        else:                           # Oher player could pick anything\n",
    "            return set.union(*cases)\n",
    "                       \n",
    "def priority(words, player):\n",
    "    \"\"\"Return (lossiness, number_of_words, total_number_of_letters),\n",
    "    where lossiness is 0 if no losses, 1 if mixed losses/wins, 2 if all losses.\n",
    "    The idea is to find the list of outcome words that minimizes this triple.\"\"\"\n",
    "    lossiness = (0 if all(winner(word) == player for word in words) else\n",
    "                 1 if any(winner(word) == player for word in words) else\n",
    "                 2)    \n",
    "    return (lossiness, len(words), sum(map(len, words)))\n",
    "\n",
    "def report_outcomes(vocab, player):\n",
    "    \"Find minimal outcomes for player; print info.\"\n",
    "    oc = outcomes(vocab, '', player)\n",
    "    winners = {w for w in oc if winner(w) == player}\n",
    "    def fill(label, words): \n",
    "        if words:\n",
    "            text = '{} ({}): {}'.format(label, len(words), ' '.join(sorted(words)))\n",
    "            print(textwrap.fill(text))\n",
    "    print('Outcomes ({}) for player {}:'.format(len(oc), player))\n",
    "    fill('Losers', oc - winners)\n",
    "    fill('Winners', winners)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Minimizing Outcomes for Player 0\n",
    "\n",
    "Let's see what minimal set of words player 0 can force the game into (with both vocabularies):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Outcomes (6) for player 0:\n",
      "Losers (1): qursh\n",
      "Winners (5): qaid qiviut qoph qurush qwerty\n"
     ]
    }
   ],
   "source": [
    "report_outcomes(enable1, 0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Interesting!** There are only 6 words; it wouldn't be hard for a human to memorize these. Then, when you are playing as player 0, pick `'q'` first, and then try to steer the game to one of the 5 words with an even number of letters. Unfortunately, one word, `'qursh'` (a monetary unit of Saudi Arabia), has an odd number of letters, which means that if the opponent replies to `'q'` with `'qu'` and to `'qur'` with `'qurs'`, then player 0 will lose. But if the opponent makes any other responses, player 0 will win."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Outcomes (7) for player 0:\n",
      "Winners (7): naan nene ngultrum nirvanic nolo null nyctalopia\n"
     ]
    }
   ],
   "source": [
    "report_outcomes(enable1_4, 0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Neat!** Only 7 words, and the first player can always win by forcing the opponent to one of these words.\n",
    "\n",
    "## Minimizing Outcomes for Player 1\n",
    "\n",
    "Since player 0 can pick any letter, the minimal `outcomes` set for player 1 must be at least 26 words. Let's see how much bigger it turns out to be. \n",
    "\n",
    "With `enable1` we already know that player 1 can force a win, so all the words in the `outcomes` set will have odd length:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Outcomes (55) for player 1:\n",
      "Winners (55): aah aal aargh aas bwana cwm drave dreck drink droit\n",
      "druid dry ewe fjeld fjord gjetost hmm ihram jnana kwashiorkor llano\n",
      "mho nth oquassa prawn prequel prill pro prurigo pry qua quell quiff\n",
      "quomodo qursh rhamnus rheum rhizoid rho rhumb rhyolitic squoosh\n",
      "tchotchke uhlan vying wrath wrest wrist wrong wrung wry xanthic\n",
      "xanthin yttrium zucchetto\n"
     ]
    }
   ],
   "source": [
    "report_outcomes(enable1, 1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Memorize this list and you will never lose as player 1.\n",
    "\n",
    "How about with the other vocabulary?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Outcomes (85) for player 1:\n",
      "Losers (4): hybris hyphen hyte ngultrum\n",
      "Winners (81): aquiculture aquifer aquilegia aquiver bwana cnidarian\n",
      "drave dreck drink droit druid dryness eschatologies eschatology\n",
      "escheat eserine esker esophagus esplanade esquire esquiring essay\n",
      "estuarine estuary esurience fjeld fjord gjetost hyaenic hydatid hyena\n",
      "hyenine hyenoid hygeist hying hylozoism hylozoist hymen hyoid hypha\n",
      "hyraces hyrax hyson ihram jnana kwashiorkor llano mbira ngwee oquassa\n",
      "plaza plethoric plica plonk pluck plyer quaff quell quiff quomodo\n",
      "qursh rhamnus rheum rhizoid rhomb rhumb rhyolitic squoosh tchotchke\n",
      "uhlan vying wrath wrest wrist wrong wrung wryly xanthic xanthin\n",
      "yttrium zucchetto\n"
     ]
    }
   ],
   "source": [
    "report_outcomes(enable1_4, 1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this case there are 85 words, four of which are losses for player 1. But the other 81 words are wins, so with this strategy you'd have a good chance against an imperfect opponent."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# SuperGhost\n",
    "\n",
    "In the variant *SuperGhost*, players can add a letter to either the beginning or the end of a fragment, as long as this forms a fragment that is part of some word. As Wikipedia says, given the fragment `era`, a player might play `bera` or `erad`. I was thinking of SuperGhost when I made the design decision to encapsulate `legal_plays` as a method of `Vocabulary`, rather than as a separate function. Because I did that, I should be able to use all the existing code if I just make a new class, `SuperVocabulary`, that finds *all* fragments (i.e. infixes) rather than just the beginning fragments (i.e. prefixes), and if I change `legal_plays` to add letters to both ends."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [],
   "source": [
    "class SuperVocabulary(Vocabulary):\n",
    "    \"Holds a set of legal words and a set of legal infix fragments of those words.\"\n",
    "    def __init__(self, words, minlength=3):\n",
    "        self.words = {word for word in words if len(word) >= minlength}\n",
    "        self.fragments = {word[i:j] for word in self.words \n",
    "                                    for i in range(len(word)) \n",
    "                                    for j in range(i, len(word) + 1)}\n",
    "        \n",
    "    def legal_plays(self, fragment):\n",
    "        \"All plays (adding a letter to fragment) that form a valid infix.\"\n",
    "        return {p for L in alphabet for p in (fragment + L, L + fragment)} & self.fragments"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now I will create `SuperVocabulary` objects for 3- and 4-letter versions of `enable1`, and check out how many fragments there are in each variant:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [],
   "source": [
    "enable1_3super = SuperVocabulary(enable1.words, 3)\n",
    "enable1_4super = SuperVocabulary(enable1.words, 4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'acrop',\n",
       " 'cropa',\n",
       " 'crope',\n",
       " 'croph',\n",
       " 'cropi',\n",
       " 'cropl',\n",
       " 'cropo',\n",
       " 'cropp',\n",
       " 'cropr',\n",
       " 'crops',\n",
       " 'cropt',\n",
       " 'cropu',\n",
       " 'cropy',\n",
       " 'ecrop',\n",
       " 'icrop',\n",
       " 'ncrop',\n",
       " 'rcrop',\n",
       " 'tcrop'}"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Example legal plays\n",
    "enable1_3super.legal_plays('crop')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'u'"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Can the first player win in SuperGhost with 3-letter words?\n",
    "\n",
    "win(enable1_3super)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'u'"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# How about with a 4-letter limit?\n",
    "\n",
    "win(enable1_4super)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The first player can win with or without three-letter words. And unless the first player is perfect, the rational strategy can do pretty well as seond player as well. Here is a sample game:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Player P given \"\" plays? q\n",
      "Player P given \"cq\" plays? cqu\n",
      "Player P given \"cque\" plays? acque\n",
      "Player P given \"acques\" plays? acquest\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "(1, 'acquest')"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "play(enable1_3super, ask('P'), rational)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I would like to give a concise summary of the strategy for SuperGhost, but my existing `outcomes` function won't do it. That's because it is not enough to know that a particular word results in a win; we have to know in what order the letters of the word are added. I'll leave it as an exercise to find a good way to summarize SuperGhost strategies.\n",
    "\n",
    "# SuperDuperGhost\n",
    "\n",
    "In the variant *SuperDuperGhost*, players have an option to reverse the fragment before adding a letter to the beginning or end. As Wikipedia says,  given the fragment `era`, a player might play `bera, erad, nare,` or `aren`.\n",
    "Wikipedia is not clear, but I interpret this as meaning that the fragment played must still be a fragment of a word (not a reversed fragment of a word). Again, all we need is a new subclass:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class SuperDuperVocabulary(SuperVocabulary):\n",
    "    \"Holds a set of legal words and a set of legal infix fragments of those words.\"\n",
    "        \n",
    "    def legal_plays(self, fragment):\n",
    "        \"All plays that form a valid infix; optionally reverse fragment first.\"\n",
    "        def all4(f, L): return (f + L, f[::-1] + L, L + f, L + f[::-1])\n",
    "        return {p for L in alphabet for p in all4(fragment, L)} & self.fragments"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "enable1_3duper = SuperDuperVocabulary(enable1.words)\n",
    "enable1_4duper = SuperDuperVocabulary(enable1.words, 4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'acrop',\n",
       " 'cropa',\n",
       " 'crope',\n",
       " 'croph',\n",
       " 'cropi',\n",
       " 'cropl',\n",
       " 'cropo',\n",
       " 'cropp',\n",
       " 'cropr',\n",
       " 'crops',\n",
       " 'cropt',\n",
       " 'cropu',\n",
       " 'cropy',\n",
       " 'ecrop',\n",
       " 'icrop',\n",
       " 'iporc',\n",
       " 'ncrop',\n",
       " 'nporc',\n",
       " 'porce',\n",
       " 'porch',\n",
       " 'porci',\n",
       " 'porcu',\n",
       " 'rcrop',\n",
       " 'tcrop'}"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Example legal plays\n",
    "enable1_3duper.legal_plays('crop')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we should check who wins. But I'm impateint: I tried `win(enable1_3duper)`, waited a minute, and it still hadn't returned, so I interrupted that computation and threw in a `lru_cache` decorator; which stops `win` from wasting time repeating the same computation over and over. This brings the time down to about 2 seconds."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [],
   "source": [
    "from functools import lru_cache\n",
    "\n",
    "@lru_cache(None)\n",
    "def win(vocab, fragment=''):\n",
    "    \"\"\"Does the current player have a forced win? \n",
    "    Return fragment if the player has already won, or return a play that forces a win.\"\"\"\n",
    "    if fragment in vocab.words or fragment not in vocab.fragments:\n",
    "        return fragment\n",
    "    for play in vocab.legal_plays(fragment):\n",
    "        if not win(vocab, play):\n",
    "            return play \n",
    "    return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'p'"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "win(enable1_3duper)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'p'"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "win(enable1_4duper)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The first player can win with either vocabulary. Here's a sample game."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Player 0, given \"\", plays \"p\".\n",
      "Player 1, given \"p\", plays \"pr\".\n",
      "Player 0, given \"pr\", plays \"lpr\".\n",
      "Player 1, given \"lpr\", plays \"rple\".\n",
      "Player 0, given \"rple\", plays \"rplex\".\n",
      "Player 1, given \"rplex\", plays \"rplexe\".\n",
      "Player 0, given \"rplexe\", plays \"urplexe\".\n",
      "Player 1, given \"urplexe\", plays \"urplexes\".\n",
      "Player 0, given \"urplexes\", plays \"ourplexes\".\n",
      "Player 1, given \"ourplexes\", plays \"fourplexes\".\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "(0, 'fourplexes')"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "play(enable1_3duper, rational, rational, verbose=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's see how many fragments each vocabulary takes:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[387878, 387844, 1076434, 1076431, 1076434, 1076431]"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[len(v.fragments) \n",
    " for v in [enable1, enable1_4, enable1_3super, enable1_4super, enable1_3duper, enable1_4duper]]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Summary\n",
    "\n",
    "Here's a summary of what we have learned. (*Note:* the bold **qursh**  means it is a losing word):\n",
    "\n",
    "| Variant \t| Shortest \t| Winner \t| First Player Forced Outcomes | 2nd  Outcomes | Fragments\n",
    "|:----:\t|:---:\t    |:---:\t    |:---:                    |:---: |---:\n",
    "| Ghost | 3 \t    | Second \t| qaid qiviut qoph **qursh** qurush qwerty  | 55 words | 387,878\n",
    "| Ghost | 4 \t    | First \t| naan nene ngultrum nirvanic nolo null nyctalopia | 85 words | 387,844\n",
    "| Super | 3\t| First \t| ? | ? | 1,076,434\n",
    "| Super | 4 \t| First \t| ? | ? | 1,076,431\n",
    "| SuperDuper | 3 | First| ? | ? | 1,076,434\n",
    "| SuperDuper | 4 | First| ? | ? | 1,076,431\n",
    "\n",
    "# Further Work\n",
    "\n",
    "Here are some additional ideas to play with:\n",
    "\n",
    "- **Exploitation:** What are some good strategies when you are not guaranteed to win, to exploit an imperfect human opponent? Can you steer the game so that you win if the opponent is unfamiliar with some obscure word(s)? You might need a file of [word frequencies](http://norvig.com/ngrams/count_1w.txt).\n",
    "- **Security:** A strategy function could *cheat*, and modify  `vocab.words`, inserting or deleting some crucial words to ensure victory. Can you harden `play` (and/or change `Vocabulary`) to protect against that?\n",
    "- **Pruning:** Currently `Vocabulary` saves words and fragments that could never be reached in a game. For example, because `'the'` is a word that ends the game, we could never reach `'them'` or `'theme'` or `'thermoluminescences'`. Can you prune away these redundant words/fragments?\n",
    "- **Multi-player:** `play(enable1, ask('A'), ask('B'), ask('C'))` will play a three-player game. But `rational` (along with `win` and `winner`) would no longer work, since they assume there are exactly two players. Can you alter them to allow *n* players?\n",
    "- **SuperGhost Summary:** Can you summarize a SuperGhost or SuperDuperGhost strategy in a way that a human can memorize?\n",
    "- **Xghost:** In *Xghost*, a letter can be added anywhere, so from the fragment `'era'` you could play `'erba'`.\n",
    "- **Spook:** In *Spook*, letters can be rearranged before adding one, so from the fragment `'era'` you could play `'bear'`."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}