hangman.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# The Hangman Game"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def hangman(secret_word, guesser, max_mistakes=8, verbose=True, **guesser_args):\n",
    "    \"\"\"\n",
    "        This function plays the hangman game with the provided guesser and returns the number of incorrect guesses. \n",
    "        \n",
    "        secret_word: a string of lower-case alphabetic characters, i.e., the answer to the game\n",
    "        guesser: a function which guesses the next character at each stage in the game\n",
    "            The function takes a:\n",
    "                mask: what is known of the word, as a string with _ denoting an unknown character\n",
    "                guessed: the set of characters which already been guessed in the game\n",
    "                guesser_args: additional (optional) keyword arguments, i.e., name=value\n",
    "        max_mistakes: limit on length of game, in terms of number of allowed mistakes\n",
    "        verbose: silent or verbose diagnostic prints\n",
    "        guesser_args: keyword arguments to pass directly to the guesser function\n",
    "    \"\"\"\n",
    "    secret_word = secret_word.lower()\n",
    "    mask = ['_'] * len(secret_word)\n",
    "    guessed = set()\n",
    "    if verbose:\n",
    "        print(\"Starting hangman game. Target is\", ' '.join(mask), 'length', len(secret_word))\n",
    "    \n",
    "    mistakes = 0\n",
    "    while mistakes < max_mistakes:\n",
    "        if verbose:\n",
    "            print(\"You have\", (max_mistakes-mistakes), \"attempts remaining.\")\n",
    "        guess = guesser(mask, guessed, **guesser_args)\n",
    "\n",
    "        if verbose:\n",
    "            print('Guess is', guess)\n",
    "        if guess in guessed:\n",
    "            if verbose:\n",
    "                print('Already guessed this before.')\n",
    "            mistakes += 1\n",
    "        else:\n",
    "            guessed.add(guess)\n",
    "            if guess in secret_word and len(guess) == 1:\n",
    "                for i, c in enumerate(secret_word):\n",
    "                    if c == guess:\n",
    "                        mask[i] = c\n",
    "                if verbose:\n",
    "                    print('Good guess:', ' '.join(mask))\n",
    "            else:\n",
    "                if len(guess) != 1:\n",
    "                    print('Please guess with only 1 character.')\n",
    "                if verbose:\n",
    "                    print('Sorry, try again.')\n",
    "                mistakes += 1\n",
    "                \n",
    "        if '_' not in mask:\n",
    "            if verbose:\n",
    "                print('Congratulations, you won.')\n",
    "            return mistakes\n",
    "        \n",
    "    if verbose:\n",
    "        print('Out of guesses. The word was', secret_word)    \n",
    "    return mistakes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# a function allowing interactive play\n",
    "def human(mask, guessed, **kwargs):\n",
    "    \"\"\"\n",
    "    This is a simple function for manual play.\n",
    "    \"\"\"\n",
    "    print('\\nEnter your guess:')\n",
    "    return input().lower().strip()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "interactive = False  # set True to play the game interactively"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "# play the interactive game\n",
    "if interactive:\n",
    "    hangman('whatever', human, 8, True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Load datasets\n",
    "### Preprocessing NLTK's Brown corpus"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Number of word types in test = 1000\n",
      "Number of word types in train = 39234\n"
     ]
    }
   ],
   "source": [
    "# load and preprocess words for test and train\n",
    "from nltk.corpus import brown\n",
    "import numpy as np\n",
    "import re \n",
    "\n",
    "np.random.seed(1)\n",
    "\n",
    "# training_set stores the rest word types for training\n",
    "training_set = []\n",
    "# test_set stores 1000 word types for testing\n",
    "test_set = []\n",
    " \n",
    "valid_words = []\n",
    "words = [word.lower() for word in brown.words()]   # lowercase the words\n",
    "words = set(words)    # remove duplicates\n",
    " \n",
    "for word in words:\n",
    "    non_alpha = re.sub(\"[a-z]\", \"\", word).strip()  \n",
    "    if len(non_alpha) == 0:         # save if only alphabets exist in the word        \n",
    "        valid_words.append(word)\n",
    "\n",
    "np.random.shuffle(valid_words)        \n",
    "\n",
    "test_set = valid_words[0:1000]\n",
    "training_set = valid_words[1000:]\n",
    "\n",
    "print(\"Number of word types in test =\", len(test_set))\n",
    "print(\"Number of word types in train =\", len(training_set))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "# test block\n",
    "assert(len(training_set) > 35000 and len(training_set) < 45000)\n",
    "assert(len(test_set) == 1000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "# play hangman using random words from test set\n",
    "interactive = True\n",
    "if interactive:\n",
    "    hangman(np.random.choice(test_set), human, 8, True)\n",
    "interactive = False"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Implementation\n",
    "### 1. Random guesser"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "def test_guesser(guesser, test=test_set):\n",
    "    \"\"\"\n",
    "        This function takes a guesser and measures the average number of incorrect guesses made over all the words in the test_set. \n",
    "    \"\"\"\n",
    "    total = 0\n",
    "    for word in test:\n",
    "        total += hangman(word, guesser, 26, False)\n",
    "    return total / float(len(test))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Guessing word = loeser\n",
      "Number of mistakes made by the random guesser = 11\n",
      "\n",
      "Testing the random guesser using every word in test set\n",
      "Average number of incorrect guesses:  16.692\n"
     ]
    }
   ],
   "source": [
    "import string\n",
    "import random\n",
    "\n",
    "alphabets = list(string.ascii_lowercase)\n",
    "\n",
    "def random_guesser(mask, guessed, **kwargs):\n",
    "    valid_alphabets = []\n",
    "    \n",
    "    for alpha in alphabets:\n",
    "        if not (alpha in guessed) and not (alpha in mask):\n",
    "            valid_alphabets.append(alpha)\n",
    "        \n",
    "    next_guess = random.choices(valid_alphabets)[0]\n",
    "\n",
    "    return next_guess\n",
    "\n",
    "random_word = np.random.choice(test_set)\n",
    "print(\"Guessing word =\", random_word)\n",
    "print(\"Number of mistakes made by the random guesser =\", hangman(random_word, random_guesser, 26, False))\n",
    "\n",
    "result = test_guesser(random_guesser)\n",
    "print(\"\\nTesting the random guesser using every word in test set\")\n",
    "print(\"Average number of incorrect guesses: \", result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "# test block\n",
    "assert(result > 10 and result < 20)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2. Unigram guesser"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Testing the unigram guesser using every word in test set\n",
      "Average number of incorrect guesses:  10.385\n"
     ]
    }
   ],
   "source": [
    "from collections import Counter\n",
    "\n",
    "unigram_counts = None\n",
    "\n",
    "unigram_counts = Counter()\n",
    "\n",
    "for training_word in training_set:\n",
    "    for alpha in training_word:\n",
    "        unigram_counts[alpha] += 1\n",
    "\n",
    "def unigram_guesser(mask, guessed, unigram_counts=unigram_counts):\n",
    "    '''\n",
    "    Each position has the same probability to have a specific character, \n",
    "    so the product based on a specific position is not considered. \n",
    "    All probabilities share the same denominator, so frequency is used instead of probability. \n",
    "    These ways can simplify the solution.\n",
    "    '''\n",
    "    freq_dict = {} \n",
    "    \n",
    "    for alpha in alphabets:\n",
    "        if (not alpha in guessed) and (not alpha in mask):\n",
    "            freq_dict[alpha] = unigram_counts[alpha]\n",
    "            \n",
    "    next_guess = max(freq_dict, key=freq_dict.get)\n",
    "    \n",
    "    return next_guess        \n",
    "                        \n",
    "result = test_guesser(unigram_guesser)\n",
    "print(\"Testing the unigram guesser using every word in test set\")\n",
    "print(\"Average number of incorrect guesses: \", result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "# test block\n",
    "assert(result > 5 and result < 15)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3. Unigram guesser by length (conditional unigram)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Testing the length-conditioned unigram guesser using every word in test set\n",
      "Average number of incorrect guesses:  10.352\n"
     ]
    }
   ],
   "source": [
    "from collections import defaultdict\n",
    "\n",
    "unigram_counts_by_length = None\n",
    "\n",
    "unigram_counts_by_length = defaultdict(Counter)\n",
    "\n",
    "for training_word in training_set:\n",
    "    for alpha in alphabets: \n",
    "        length = len(training_word)\n",
    "        count = training_word.count(alpha)\n",
    "        unigram_counts_by_length[length][alpha] += count\n",
    "\n",
    "def unigram_length_guesser(mask, guessed, unigram_counts_by_length=unigram_counts_by_length, unigram_counts=unigram_counts):\n",
    "\n",
    "    prob_dict = {}\n",
    "    length = len(mask)\n",
    "    \n",
    "    for alpha in alphabets:\n",
    "        if (alpha in guessed) or (alpha in mask):\n",
    "            continue\n",
    "        elif not length in unigram_counts_by_length.keys():\n",
    "            prob_dict[alpha] = unigram_counts[alpha]\n",
    "        else:\n",
    "            prob_dict[alpha] = unigram_counts_by_length[length][alpha]\n",
    " \n",
    "    next_guess = max(prob_dict, key=prob_dict.get)\n",
    "    \n",
    "    return next_guess  \n",
    "\n",
    "result = test_guesser(unigram_length_guesser)\n",
    "print(\"Testing the length-conditioned unigram guesser using every word in test set\")\n",
    "print(\"Average number of incorrect guesses: \", result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "# test block\n",
    "assert(result > 5 and result < 15)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4. Bigram guesser"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Testing the bigram guesser using every word in test set\n",
      "Average number of incorrect guesses:  8.729\n"
     ]
    }
   ],
   "source": [
    "bigram_counts = None\n",
    "\n",
    "bigram_counts = defaultdict(Counter)\n",
    "\n",
    "for training_word in training_set:\n",
    "    word = '$' + training_word        # set a starting mark\n",
    "    for i in range(0, len(word)-1):\n",
    "        left_alpha = word[i]\n",
    "        alpha = word[i+1]\n",
    "        bigram_counts[left_alpha][alpha] += 1\n",
    "\n",
    "total_unigram_counts = sum(unigram_counts.values())\n",
    "\n",
    "def bigram_guesser(mask, guessed, bigram_counts=bigram_counts, unigram_counts = unigram_counts): # add extra arguments if needed\n",
    "    prob_dict = defaultdict(lambda : 0)\n",
    "    \n",
    "    for alpha in alphabets:\n",
    "        if (alpha in guessed) or (alpha in mask):\n",
    "            continue\n",
    "        for i in range(0,len(mask)): \n",
    "            if mask[i] != '_':          # continue if the position is guessed already \n",
    "                continue\n",
    "            \n",
    "            left_alpha = '$' if i == 0 else mask[i-1]   \n",
    "                \n",
    "            if left_alpha == '_':       # if no conditional alphabet exists on the left, use unigram counts result\n",
    "                prob_dict[alpha] += unigram_counts[alpha] / total_unigram_counts\n",
    "            else:\n",
    "                if left_alpha in bigram_counts.keys():\n",
    "                    total_bigram_counts = sum(bigram_counts[left_alpha].values())\n",
    "                    prob_dict[alpha] += bigram_counts[left_alpha][alpha] / total_bigram_counts\n",
    "                           \n",
    "    next_guess = max(prob_dict, key=prob_dict.get)\n",
    "    \n",
    "    return next_guess\n",
    "\n",
    "result = test_guesser(bigram_guesser)\n",
    "print(\"Testing the bigram guesser using every word in test set\")\n",
    "print(\"Average number of incorrect guesses: \", result)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5. My guesser"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Testing my amazing AI guesser using every word in test set\n",
      "Average number of incorrect guesses:  7.658\n"
     ]
    }
   ],
   "source": [
    "# initialise dictionaries bidirectional n-gram models\n",
    "bigram_counts_rev = defaultdict(Counter)\n",
    "trigram_counts = defaultdict(lambda: defaultdict(Counter))\n",
    "trigram_counts_rev = defaultdict(lambda: defaultdict(Counter))\n",
    "\n",
    "# set the optimal parameters\n",
    "k = 0.01\n",
    "v = len(alphabets)\n",
    "uni_gamma, bi_gamma, tri_gamma = 0.1, 0.2, 0.7\n",
    "\n",
    "# generate n-gram dictionaries\n",
    "for training_word in training_set:\n",
    "    word = '$' + training_word + '/'\n",
    "    for i in range(1, len(word)-1):\n",
    "        right1_alpha = word[i+1]\n",
    "        alpha = word[i]\n",
    "        bigram_counts_rev[right1_alpha][alpha] += 1\n",
    "        if i >= 2:\n",
    "            left1_alpha = word[i-1]\n",
    "            left2_alpha = word[i-2]\n",
    "            trigram_counts[left2_alpha][left1_alpha][alpha] += 1\n",
    "        if i < (len(word)-2):\n",
    "            right2_alpha = word[i+2]\n",
    "            trigram_counts_rev[right2_alpha][right1_alpha][alpha] += 1\n",
    "\n",
    "# count the vocab sizes\n",
    "bi_v, bi_v_rev, tri_v, tri_v_rev = 0, 0, 0, 0\n",
    "for left1_alpha in bigram_counts.keys():\n",
    "    bi_v += len(bigram_counts[left1_alpha].keys())\n",
    "for right1_alpha in bigram_counts_rev.keys():\n",
    "    bi_v_rev += len(bigram_counts_rev[right1_alpha].keys())\n",
    "for left1_alpha in trigram_counts.keys():\n",
    "    for left2_alpha in trigram_counts[left1_alpha].keys():\n",
    "        tri_v += len(trigram_counts[left2_alpha][left1_alpha].keys())\n",
    "for right1_alpha in trigram_counts_rev.keys():\n",
    "    for right2_alpha in trigram_counts_rev[right1_alpha].keys():\n",
    "        tri_v_rev += len(trigram_counts_rev[right2_alpha][right1_alpha].keys())\n",
    "        \n",
    "def my_amazing_ai_guesser(mask, guessed, unigram_counts = unigram_counts, \\\n",
    "                          bigram_counts=bigram_counts, bigram_counts_rev = bigram_counts_rev, \\\n",
    "                          trigram_counts = trigram_counts, trigram_counts_rev = trigram_counts_rev ): \n",
    "    \n",
    "    prob_dict = defaultdict(lambda:0)\n",
    "    \n",
    "    for alpha in alphabets:\n",
    "        if (alpha in guessed) or (alpha in mask):\n",
    "            prob_dict[alpha] = 0\n",
    "            continue\n",
    "    \n",
    "        for i in range(0,len(mask)): \n",
    "            if mask[i] != '_':\n",
    "                continue   \n",
    "            \n",
    "            prob_dict[alpha] += uni_gamma*((unigram_counts[alpha] +k)/ (total_unigram_counts + k*v))\n",
    "    \n",
    "            left1_alpha = '$' if i == 0 else mask[i-1]\n",
    "            right1_alpha = '/' if i == len(mask)-1 else mask[i+1]\n",
    "            \n",
    "            if left1_alpha != '_': \n",
    "                total_bigram_counts = sum(bigram_counts[left1_alpha].values())\n",
    "                prob_dict[alpha] += bi_gamma*((bigram_counts[left1_alpha][alpha]+ k)/ \\\n",
    "                                              (total_bigram_counts + k*bi_v))\n",
    "            if right1_alpha != '_':\n",
    "                total_bigram_counts_rev = sum(bigram_counts_rev[right1_alpha].values())\n",
    "                prob_dict[alpha] += bi_gamma*((bigram_counts_rev[right1_alpha][alpha] +k)/ \\\n",
    "                                        (total_bigram_counts_rev + k*bi_v_rev))\n",
    "            if i >= 1:\n",
    "                left2_alpha = '$' if i == 1 else mask[i-2]\n",
    "                if not '_' in [left1_alpha, left2_alpha]: \n",
    "                    total_trigram_counts = sum(trigram_counts[left2_alpha][left1_alpha].values())\n",
    "                    prob_dict[alpha] += tri_gamma*((trigram_counts[left2_alpha][left1_alpha][alpha]+ k)/ \\\n",
    "                                            (total_trigram_counts + k*tri_v))\n",
    "            if i <= (len(mask)-2):\n",
    "                right2_alpha = '/' if i == len(mask)-2 else mask[i+2]\n",
    "                if not '_' in [right1_alpha, right2_alpha]: \n",
    "                    total_trigram_counts_rev = sum(trigram_counts_rev[right2_alpha][right1_alpha].values())\n",
    "                    prob_dict[alpha] += tri_gamma*((trigram_counts_rev[right2_alpha][right1_alpha][alpha]+ k)/ \\\n",
    "                                            (total_trigram_counts_rev + k*tri_v_rev))\n",
    "                   \n",
    "    next_guess = max(prob_dict, key=prob_dict.get)\n",
    "    return next_guess\n",
    "\n",
    "result = test_guesser(my_amazing_ai_guesser)\n",
    "print(\"Testing my amazing AI guesser using every word in test set\")\n",
    "print(\"Average number of incorrect guesses: \", result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.7.11"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}