Modeling The Game of Hangman
We’re going to model a game such as Hangman in python with four parts:
code_word: This is the code word we’re trying to break. Aka, the word that the opponent has chosen, and the player must determine.
dictionary: The entire set of code words that the opponent can choose from.
get_next_guess: The player’s strategy given the current state of the game.
get_response: The response that the opponent will given the player’s next guess.
Given our dictionary is
car, and the code word is
A logical first guess may be
t, which the opponent would respond with
After some time, the player will determine the code word and may use
cat as their next guess.
An example game log may look like the following:
In python, we can define a function
play_game that accepts our four parts defined above.
Line by line game walkthrough
On the first loop, we are starting with the full dictionary. The responsibility of
get_next_guess is twofold: Return the next guess and return possible sets
of remaining words indexed by the opponent’s response. This index will be
used on the last line of the loop to whittle down the set of remaining words
that still match the current state of the game.
Since the next guess is
t, the response is
--t. The player now knows
t was a correct guess AND what position the
t is in the code word.
Simple line to capture the turn in the game log.
Since the next guess (
t) is not the code word, we move on.
After the turn is complete, we whittle down the set of possible words based
on the response (
--t) we received back from
get_response. Looking at
code_words_by_response assertion above, we see that we now only have
two remaining words that could match the current state of the game. We’re now
ready to start the second loop.
The second loop is exactly the same except we have a shorter list of possible code words and an entry in the game log. We’ll only show the first step in the loop, since the rest should be self explanatory.
And so on…
Implementing a basic strategy in
An example of a naive solution
get_next_guess that we most often used as kids is shown below.
It knows the order of the most commonly occurring letters in the english dictionary
and tries them one by one. We will ignore the
_get_remaining_code_words_by_response() implementation for now to keep things simple.
Don’t worry, we’ll revisit it when we start building more complex strategies.
Implementing the opponent’s
Exploring optimal strategies
Naive, success, info gain (maybe others in mastermind paper?)
Exploring optimal strategies in Mastermind
Exploring optimal strategies in Battleship
2D optimization problem, what if we wanted to add a third? In next post, we’ll add time as a third dimension.