Mastering Mastermind

Intro

Blah blah

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.

An Example

Given our dictionary is cat, can, and car, and the code word is cat. A logical first guess may be t, which the opponent would respond with --t. 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:

[
    {'guess': 't', 'response': '--t'},
    {'guess': 'n', 'response': '!'},
    {'guess': 'c', 'response': 'c-t'},
    {'guess': 'cat', 'response': 'cat'},
]

Game implementation

In python, we can define a function play_game that accepts our four parts defined above.

def play_game(code_word, dictionary, get_next_guess, get_response):
    """
    Arguments:
    code_word      -- The opponent's chosen code word.
    dictionary     -- The set of all possible code words the opponent could've chosen.
    get_next_guess -- A function that will be invoked to return the next guess.
    get_response   -- A function that will be invoked to return the opponent's response to the guess.
    
    Returns:
    game_log -- A list of game turns containing each turn's guess and response.
    """
    game_log = GameLog()
    possible_code_words = list(dictionary)
    while True:
        next_guess, code_words_by_response = get_next_guess(
            possible_code_words,
            get_response,
            game_log)
        response = get_response(
            code_word,
            next_guess,
            game_log)
        game_log.log(next_guess, response)
        if next_guess == code_word:
            return game_log
        possible_code_words = code_words_by_response.get(response)

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.

next_guess, code_words_by_response = get_next_guess(
    possible_code_words, # ['bat', 'cat', 'can', 'car']
    get_response,        # <function get_response>
    game_log             # []
)
assert next_guess == 't'
assert code_words_by_response == {
    'b--;': ['bat'],
    'c--;': ['cat', 'can', 'car'],
    '-a-;': ['bat', 'cat', 'can', 'car'],
    '--t;': ['bat', 'cat'],
    '--n;': ['can'],
    '--r;': ['car'],
    '---;s': ['bat', 'cat', 'can', 'car'],
}

Since the next guess is t, the response is --t. The player now knows that t was a correct guess AND what position the t is in the code word.

response = get_response(
    code_word,  # 'cat'
    next_guess, # 't'
    game_log    # []
)
assert response == '--t;'

Simple line to capture the turn in the game log.

game_log.log(next_guess, response)
assert game_log == [{'guess': 't', 'response': '--t'}]

Since the next guess (t) is not the code word, we move on.

if next_guess == code_word: # False
    return game_log

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 the 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.

possible_code_words = code_words_by_response.get(response)
assert possible_code_words == ['bat', 'cat']

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.

next_guess, code_words_by_response = get_next_guess(
    possible_code_words, # ['bat', 'cat']
    get_response,        # <function get_response>
    game_log             # [{'guess': 't', 'response': '--t'}]
)
assert next_guess == 'c'
assert code_words_by_response == {
    'b-t;': ['bat'],
    'c-t;': ['cat'],
    '-at;': ['bat', 'cat'],
    '---;s': ['cat'],
}

And so on…

Implementing a basic strategy in `get_next_guess`

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.

def get_next_guess(remaining_words, get_response, game_log)
    # If we've whittled down to return one remaining word,
    # return that word as our next guess to finish the game.
    if len(remaining_words) == 1:
        return remaining_words[0]

    next_guess = None
    potential_guesses = 'esiarntolcdupmghbyfvkwzxqj'
    for guess in potential_guesses:
        if guess in game_log.previous_guesses:
            continue
        if guess in remaining_words:
            next_guess = guess
    return next_guess, _get_remaining_code_words_by_response()

Implementing the opponent’s `get_response`

def get_response(code_word, next_guess, game_log)
    """
    Example:
    Returns `ba-a-a` where the code word is `banana` and guesses include `b` and `a`
    """
    all_guesses = game_log.previous_guesses + next_guess

    result = []
    for symbol in code_word:
        if symbol in all_guesses or code_word in guesses:
            result.append(symbol)
        else:
            result.append('-')
        return ''.join(symbol)

Exploring optimal strategies

Naive, success, info gain (maybe others in mastermind paper?)

Exploring optimal strategies in Mastermind

TODO

Exploring optimal strategies in Battleship