So I’ve clearly lost my New Year’s Resolution; it’s been 6 weeks since my last post. In that time, I had my last finals of freshman year, moved back home after exactly 9 months of being in LA, went to a wedding, visited grandparents… it was a lot. to get back in rhythm for writing blog posts, I wanted to make a post about how I turned a game about guessing words into a math problem.

My code for this post can be found here: Wordle Analysis

Wordle as a Math Problem

At its core, Wordle can be conceptualized as a problem of information theory and optimal decision-making. The goal is to identify a single secret 5-letter word from a known set of possibilities (ans.txt in the repository) by making a series of guesses. Each guess gets a result (green, yellow, and black colors that say if a letter is in the correct position, in the wrong position, or not in the secret word) that provides information that prunes the set of potential answers. The mathematical objective is to select guesses that maximize the expected information gain, thereby minimizing the average number of turns required to identify the secret word.

Key Parts of the Code

The repository contains several Python scripts that work together to solve Wordle. Here are the key functions:

checkguess(guess: str, answer: str, precomputed_dict=None)

This function simulates the Wordle feedback mechanism. Given a guess and the actual answer, it returns a 5-character string indicating ‘G’ (Green), ‘Y’ (Yellow), or ‘B’ (Black) for each letter’s status. It utilizes a precomputed dictionary for efficiency (and the code for generating the dictionary is included in the repository).

def checkguess(guess: str, answer: str, precomputed_dict=None):
    """
    Retrieves the Wordle result for a guess-answer pair from a precomputed dictionary.

    Args:
        guess: The 5-letter word guessed by the player (e.g., "crane").
        answer: The 5-letter secret word (e.g., "train").
        precomputed_dict: Dictionary containing precomputed guess-answer results.

    Returns:
        A 5-character string ('G', 'Y', 'B') representing the result:
        - 'G' (Green): Letter is correct and in the correct position.
        - 'Y' (Yellow): Letter is correct but in the wrong position.
        - 'B' (Black/Grey): Letter is not in the answer word.

    Raises:
        AssertionError: If precomputed_dict is not provided.
        KeyError: If the guess-answer combination is not in the dictionary.
    """
    assert precomputed_dict is not None, "precomputed_dict must be provided"
    return precomputed_dict[guess][answer]

Because of Github’s size limits, I did not include the dictionary itself because the file is too large (600MB when only [all valid words x all answers] are included, 4GB when all 15000^2 combinations of [all valid words x all valid words] are included).

filterwords(wordlist, guess: str = None, wordleresult: str = None, precomputed_dict=None)

This function is crucial for narrowing down the possible answer words. After a guess is made and its result is known, filterwords takes the current list of possible words and returns a new, reduced list containing only those words that would produce the exact same Wordle result if they were the true answer.

def filterwords(wordlist, guess: str = None, wordleresult: str = None, precomputed_dict=None):
    """
    Filter a list of words based on a guess and its result.

    If a guess and result are provided, return a new list of words that match the given result.
    If the guess and result are not provided, return the original wordlist.

    Args:
        wordlist: The list of words to filter.
        guess: The guess to filter by.
        wordleresult: The result of the guess.
        precomputed_dict: A dictionary of precomputed results.

    Returns:
        A list of words that match the given result, or the original wordlist if no guess and result are provided.
    """
    assert wordlist is not None, "wordlist must be provided"
    if guess and wordleresult:
        outputlist = [word for word in wordlist if checkguess(guess, word, precomputed_dict) == wordleresult.upper()]
        assert len(outputlist) > 0, "No words left after filtering, should be impossible"
        return outputlist
    else:
        return wordlist

onestep(guess: str, wordleresult: str, answordlist=None, precomputed_results=None, secondary_word_list = None)

This is the core logic for determining the next optimal guess in a greedy fashion. Given the current guess and its result, onestep filters the answordlist to get the remaining possible answers. Then, for each potential next guess (from either the answordlist or a secondary_word_list like valid.txt), it calculates what the average size of the filtered word list would be if that guess were made. The function returns the guess that yields the smallest average remaining word list size, representing the most “information-rich” guess.

def onestep(guess: str, wordleresult: str, answordlist=None, precomputed_results=None, secondary_word_list = None):
    """
    Given a guess and the result of that guess, returns the next best guess that will best
    reduce the word list.

    Args:
        guess: The guess that was made.
        wordleresult: The result of the guess ('G', 'Y', 'B').
        answordlist: The list of words that could be the answer.
        precomputed_results: A dictionary of precomputed results.
        secondary_word_list: An optional secondary word list to use in place of answordlist.

    Returns:
        The next best guess, the average length of the possible answer word list if that guess is made,
        and the list of possible answer words after the guess is made.
    """
    assert precomputed_results is not None, "precomputed_results must be provided"
    assert answordlist is not None, "wordlist must be provided"
    possible_answer_words = filterwords(answordlist, guess, wordleresult, precomputed_results)
    if len(possible_answer_words) == 1:
        return possible_answer_words[0], 1.0, possible_answer_words
    possible_results = {}
    min_post_list = float('inf')
    for guessword in (possible_answer_words if not secondary_word_list else secondary_word_list):
        lengths = {}
        for possibleanswer in possible_answer_words:
            result = checkguess(guessword, possibleanswer, precomputed_results)
            if result in lengths:
                lengths[result][0] += 1
            else:
                lengths[result] = [1, filterwords(possible_answer_words, guess = guessword, wordleresult = result, precomputed_dict=precomputed_results)]
        possible_results[guessword] = sum([lengths[key][0] * len(lengths[key][1]) for key in lengths])
        if possible_results[guessword] < min_post_list:
            min_post_list = possible_results[guessword]

    return min(possible_results, key=possible_results.get), min(possible_results.values()), possible_answer_words

Improving the Bot: Looking Ahead (Beyond One Step)

The current bot employs a greedy strategy, meaning it always chooses the guess that provides the most information in the immediate next step (i.e., onestep). While this is often effective, it doesn’t guarantee the absolute minimum number of moves over the entire game. To truly minimize the average number of moves, the bot would need to look further ahead, similar to how advanced chess bots evaluate multiple moves in advance.

This improvement would involve implementing an algorithm akin to a minimax or expectimax search. Instead of just picking the best onestep choice, the bot would:

  1. Simulate Future Moves: For each potential guess, it would simulate all possible Wordle results and the subsequent reduction in the word list.
  2. Recursively Evaluate: For each of these reduced word lists, it would recursively call the decision-making process to find the optimal next guess, and so on, for a predetermined ‘depth’ of moves (e.g., 2, 3, or more steps ahead).
  3. Minimize Expected Value: The bot would then choose the initial guess that leads to the lowest expected number of total turns, considering the probabilities of each possible Wordle result at each stage.

Computational Complexity:

The primary challenge with looking further ahead is the exponential increase in computational complexity. If N is the number of possible guesses and M is the average number of distinct Wordle results for a given guess, then looking k steps ahead could involve approximately $O(N \times M^k)$ evaluations. For Wordle, M can be significant (up to $3^5 = 243$ unique results), making a deep search computationally intensive without heavy optimization or pruning techniques.

Despite the computational cost, a multi-step lookahead approach would theoretically yield a more optimal Wordle solver, as it could anticipate scenarios where an immediate “best” guess leads to a difficult state later in the game. This is a common trade-off in AI for games: a deeper search often leads to better play, but at a higher computational expense.