HOWTO: Hangman

This program comes written in a number of modules to allow you to simulate playing Hangman between three versions of two opponents, an Executioner and a Player: interactive, simple, and clever.

• Hangman: general functions to facilitate the game, no matter who is playing
• InteractivePlayer: plays by prompting the user to input a guess — an example, you do not need to modify this module
• SimplePlayer: plays by choosing a random letter that has not been guessed previously
• CleverPlayer: plays by choosing the letter that appears in the most possible words
• InteractiveExecutioner: prompts the user to input the secret and does not change it during the game — an example, you do not need to modify this module
• SimpleExecutioner: chooses the secret randomly from the possible words and does not change it during the game
• CleverExecutioner: randomly chooses the secret whose length allows the most words to remain possible and changes the secret after each guess such that it remains consistent with previous guesses and allows the most words to remain possible
• Tools: contains general functions for printing out parts of your data structures for debugging purposes — you do not need to modify this module
  

You can pit any of the Executioners against any of the Players by changing the top two import statements in the Hangman module. For example, as given to start the project, the lines below allow two people to play against each other interactively:

import InteractiveExecutioner as Executioner
import InteractivePlayer as Player

If you changed the lines as follows, you could play a more common version of the game as found on many websites, with a person guessing against the computer that chose a random word:

import SimpleExecutioner as Executioner
import InteractivePlayer as Player

Or you could simply watch two algorithms play against each other without any interaction:

import CleverExecutioner as Executioner
import CleverPlayer as Player

Example runs of all combinations of Executioner and Player are available online and in the snarfable version. In the output files named _debug, we have included printed information that shows how the algorithm is playing the game, either as an Executioner or as a Player. The secret word and the number of possible words that could be the secret word are shown as well as any additional information about the data structures the algorithm is using.

Step 1: Hangman

This module facilitates playing the game:

• sets up the game
• enforces the rules until the game is over
• allows both players to take turns
• displays information about the state of the game

The primary function is playGame, which takes a list of words to use as the shared vocabulary between the two players and an int, the number of missed guesses allowed before the player is hung. The list of words allows you to control the number and type of possible words making it easier to test your program (several example word files are given with the project). The number of misses allows you to make the game easier or harder for the player.

The playGame function mostly just calls other functions, three of which you will need to implement to make the game work. The code for this step is very short, but it requires understanding how all of the given code interacts to ensure that it works properly. You will need to figure out what each function's parameters represent in the game, how they change as the game is played, and how to the results of these functions are used to move the game forward.

Complete the following functions in the Hangman module.

def updateKnowledge (guess, secret, knowledge):
    """
    returns a list of strings representing the current state of the secret,
      guessed letters are filled in, unknown letters are replaced by an '_'      
    """

def isGameWon (knowledge):
    """
    returns a boolean, True is the game is won, False otherwise
      (i.e., no more letters are unknown in the knowledge)
      note, also prints a winning message if it is True
    """

def isGameLost (missesLeft):
    """
    returns a boolean, True is the game is lost, False otherwise
      (i.e., no more misses are allowed)
      note, also prints a losing message if it is True
    """

No other changes should be made to the Hangman module.

Step 2: Simple Opponents

In order for opponents to be substitutable, all Player modules must implement the three functions described below and all Executioner modules must implement the two functions described below. The playGame function calls those functions and if they are not defined and implemented properly, then the game itself will not work.

For Players, following functions must be implemented:

def startStrategy (knowledge, wordList):
    """
    returns nothing
    knowledge, a list of strings, represents the initial state of the secret, 
      all letters are replaced by an '_' to denote they are unknown
    possibleWords, a list of strings, represents the only possible words from
      which the secret will be chosen

    this function is called after the secret is chosen, but before the game starts
      it gives the player a chance to setup any global variables that might be 
      useful to help its strategy in guessing the secret word 
    """

def getGuess (guesses):
    """
    returns a string of a single letter that represents the player's guess
    guesses, a list of strings, represents all previous guesses made by the player
    note, if the player wants to remember this guess, it should be saved as a
      global variable to be used in updateStrategy
    """

def updateStrategy (wasGuessCorrect, knowledge):
    """
    returns nothing
    wasGuessCorrect, a boolean, whether or not the last guess was in the secret 
    knowledge, a list of strings, represents the current state of the secret, 
      guessed letters are filled in, unknown letters are replaced by an '_'      

    this function is called after the guess has been checked against the current 
      secret, but before the next round of the game starts
      it gives the player a chance to update any global variables that might be 
      useful to help its strategy in guessing the secret word
    """

For example, in the module InteractivePlayer, the functions startStrategy and updateStrategy do not do anything algorithmically (since all the strategy for is done by the user entering the guesses), but they still must exist.

For Executioners, following functions must be implemented:

def chooseSecretWord (wordList):
    """
    returns a string, the secret to be guessed from wordList, a list of strings

    this function is called to start the game, giving the executioner a chance 
      to choose the secret to be guessed
    """

def updateSecret (guess):
    """
    returns a string, the secret to be guessed
    guess, a string, is the letter most recently guessed by the player

    this function is called after the guess is made, but before it is checked 
      against the secret, giving the executioner a chance to modify the secret
    """
  

For example, in the module InteractiveExecutioner, the function updateSecret does not do anything algorithmically (since the secret remains the same for the entire game), but the playGame function that calls it assigns the return value to be the current secret, so it must return a reasonable string. Since the secret is not passed in as a parameter, the Executioner itself must store the secret in a variable that it can use later when updateSecret is called. Thus the use of the module variable, _secret, that is assigned when the user is prompted in chooseSecretWord and then recalled as the only line in the function updateSecret. The Python syntax, global _secret, lets each function know that the variable was previously declared within the module, outside of any function.

In this step, your task is to complete an algorithmic Executioner and Player, that can play the game without any interaction from the user. Both opponents algorithms are based on simply choosing their respective values randomly.

Step 3 : Clever Opponents

This step is the meat of the program because this is where you will attempt to make opponents with some "intelligence", i.e., algorithms that are able to play hangman with some skill.

Clever Executioner

In this version of the executioner, which some might say is diabolically clever or some might say it is cheating or evil, the secret is changed with each letter guessed. The evil adjective was applied in a 2011 Nifty Assignment, but a form of the game dubbed cheating is described on this website. For this algorithm you will leverage the power of dictionaries and a greedy algorithm in which the executioner changes its mind, by changing its secret word so that the new secret word is consistent with previous guesses, but harder (perhaps) to guess.

The fundamental goal of this algorithm is to always keep the largest possible number of words that could be the secret. Thus, chooseSecretWord initially chooses the secret based on which word length is most represented in the given list of words (since the only knowledge initially given is how many letters are in the word). Then, each time the user guesses a letter, updateSecret changes the secret so that it represents a pattern that has the most possibilities in the remaining words. The Player is not aware that the Executioner is changing the secret word because each change is consistent with all of the guesses made so far.

For example, given the following list of possible words (the secret is 4 letters long):

[ 'oboe', 'noon', 'odor', 'room', 'solo', 'trio', 'goto', 'oath', 'oxen', 'pick', 'frat', 'hoop' ]

and the player first guesses the letter 'o'. This table shows the patterns made from the possible words and which words fit those patterns:

Pattern	Words Matching Pattern
'_ o o _'	'noon', 'room', 'hoop'
'_ _ _ _'	'pick', 'frat'
'o _ _ _'	'oath', 'oxen'
'o _ o _'	'oboe', 'odor'
' _ o _o'	'solo' 'goto'
'_ _ _ o'	'trio'

The most words correspond to the pattern '_ o o _' so this algorithm would pick a secret word at random from the list of three words: ['noon', 'room', 'hoop']. The player may think she has hit the jackpot with two O's in the word, but there are more words to eliminate than with any other template.

If the player's second guess is an 'h', then this table shows the patterns made from the possible words and which words fit those patterns:

Pattern	Words Matching Pattern
'_ o o _'	'noon', 'room'
'h o o _'	'hoop'

The most words still correspond to the pattern '_ o o _' so this algorithm would pick a secret word at random from the list of three words: ['noon', 'room'] since these are the only remaining words that contain two 'O's in the middle, but do not contain an 'H' (i.e., they are consistent with the player's guessing history). Note, in the case of a tie, choose the pattern that reveals the least information (i.e., includes the fewest instances of the guessed letter, including and especially no instances).

Dictionaries are a natural fit for this algorithm because the pattern can serve as the key and the words matching the pattern can serve as the value.

Some of the example runs include debugging print statements showing the top 5 patterns for each guess made.

Clever Player

There are many strategies for picking which letter to guess but, in this version, you will focus on using another greedy algorithm: one that chooses the letter that includes the most possible words. To achieve this, there are two phases to the algorithm:

1. reducing the total possible words to those that are consistent with the displayed knowledge. In startStrategy, this means retaining only words whose length is the same as the secret and in updateStrategy, this means retaining only words that match the current pattern of the secret.
2. choosing the letter that occurs in most of the remaining words or the first alphabetical letter if there is a tie (although there are more sophisticated ways to break the tie). This choice is made in getGuess and does not affect the words remaining because whether the guess is correct or not is not known until updateStrategy.

For example, given the same list of possible words as above (the secret is 4 letters long):

[ 'oboe', 'noon', 'odor', 'room', 'solo', 'trio', 'goto', 'oath', 'oxen', 'pick', 'frat', 'hoop' ]

This table shows the each letter's coverage of the possible words:

Letter	Words Containing Letter
'o'	'oboe', 'noon', 'odor', 'room', 'solo', 'trio', 'goto', 'oath', 'oxen', 'hoop'
'r'	'odor', 'room', 'trio', 'frat'
't'	'trio', 'goto', 'oath', 'frat'
'a'	'oath', 'frat'
'e'	'oboe', 'oxen'
'i'	'trio', 'pick'
'h'	'oath', 'hoop'
'n'	'noon', 'oxen'
'p'	'pick', 'hoop'
'c'	'pick'
'b'	'oboe'
'd'	'odor'
'g'	'goto'
'f'	'frat'
'k'	'pick'
'm'	'room'
'l'	'solo'
's'	'solo'
'x'	'oxen'

The most words correspond to the letter 'O' so this algorithm would return that letter.

Assuming this algorithm is playing against the CleverExecutioner described previously, updateStrategy would update the list of remaining words to just these three ['noon', 'room', 'hoop']. The player would then construct the following table regarding each letter's coverage of the possible words:

Letter	Words Containing Letter
'h'	'hoop'
'm'	'room'
'n'	'noon'
'p'	'hoop'
'r'	'room'

Since each letter only covers one word, the algorithm has nothing to gain by choosing one letter over another, so it returns the letter 'H'.

Dictionaries are a natural fit for this algorithm because the letter can serve as the key and the words containing that letter can serve as the value.

Some of the example runs include debugging print statements showing the top 5 patterns for each guess made.

It is interesting to note that if a CleverPlayer plays against a CleverExecutioner the result of a game with the same list of possible words will always end in the same result because the executioner will always choose a secret of the same length (yields the most words), which will lead the player to always choose the same letter first (yields the most words), which will lead the executioner to choose the same pattern for its secret (yields the most words), and so on and so on. Without randomness, or some other means of adjusting to the opponent, both of these greedy algorithms will simply play the same game over and over.