What is the maths behind solving wordle game assuming I have a dictionary and a games…
- User
What is the maths behind solving wordle game assuming I have a dictionary and a games list, optimize for lowest average score
- Assistant
Below is an explanation of one mathematically rigorous approach to “solving” Wordle optimally (with the objective of minimizing the average number of guesses). The idea is to model the game as a decision process and then choose guesses that, on average, reduce the uncertainty about the answer as much as possible. In short, we are building an optimal decision tree.
Below are the steps and the mathematics behind it:
1. Problem Setup
- Dictionary (D): A large list of all possible words you can guess.
- Game List (T): A (usually smaller) list of words that could be the hidden answer.
At any stage of the game, you have a subset ( T \subseteq \text{(Game List)} ) that contains all words still consistent with previous guesses and their feedback.
2. Feedback and Partitioning
In Wordle, when you make a guess ( g ) and the hidden word is ( w ), the game returns feedback in the form of color patterns (green, yellow, gray). More mathematically, there is a function: [ f(g, w) = \text{feedback pattern} ] For a fixed guess ( g ) and the current candidate set ( T ), this feedback will partition ( T ) into groups: [ T_p = {w \in T ; |; f(g, w) = p } ] for each possible pattern ( p ).
3. Expected Information Gain / Entropy
A common and powerful criterion is to choose the guess that maximizes your expected information gain. This is often measured via entropy. Recall that if your candidate set is ( T ), then before guessing you have an “uncertainty” of ( \log(|T|) ) (using the logarithm base 2 if you wish, though any base is fine).
Given a guess ( g ), you will receive a feedback pattern ( p ) with probability: [ P(p) = \frac{|T_p|}{|T|}. ] After feedback ( p ), the number of possibilities reduces to ( |T_p| ). Therefore, the remaining uncertainty is proportional to ( \log(|T_p|) ).
The expected remaining uncertainty after guess ( g ) is: [ E_{\text{rem}}(g) = \sum_{p} \frac{|T_p|}{|T|} \log(|T_p|). ] The information gain from guess ( g ) is roughly: [ \text{IG}(g) = \log(|T|) - E_{\text{rem}}(g). ] Thus, one strategy is to choose the ( g ) that maximizes ( \text{IG}(g) ), or equivalently, minimizes: [ \sum_{p} \frac{|T_p|}{|T|} \log(|T_p|). ]
4. Recursion and Expected Number of Moves
Another formulation is to recursively define the cost (or expected number of moves) needed to solve the puzzle: [ C(T) = \begin{cases} 0,& \text{if } |T| = 1 \ 1 + \min_{g \in D} \sum_{p} \frac{|T_p|}{|T|} , C(T_p),& \text{otherwise.} \end{cases} ] Here, ( C(T) ) is the expected number of additional guesses (not counting the current guess) needed when your candidate set is ( T ). For each guess ( g ) that you could make, and for each pattern ( p ) that ( g ) might yield, ( C(T_p) ) is the cost from that branch. One then picks the guess ( g ) that minimizes this expected cost. (Note that one must add 1 for the current guess.)
This style of recurrence is very similar in spirit to the formulation in optimal binary—or in this case, multi-way—decision tree design.
5. Minimax vs. Average-Case Optimization
- Minimax approach: You might instead wish to minimize the maximum number of moves in the worst-case scenario. This would choose the guess ( g ) that minimizes: [ \max_{p} ; C(T_p). ]
- Average-case approach: As shown above, when optimizing for lowest average score, you use the expected cost: [ 1+\min_{g \in D} \sum_{p} \frac{|T_p|}{|T|} , C(T_p). ]
Since the question asks for the “lowest average score,” we use the expected cost formulation.
6. Computational Considerations
In theory, one could compute ( C(T) ) by recursion (or dynamic programming) over all subsets ( T ) to find the optimal first guess and subsequent moves. In practice, this is computationally very intensive because the number of possible candidate sets and guess scenarios is enormous. Therefore, much of the literature on optimal Wordle solvers resorts to:
- Heuristics: For example, choosing a guess that maximizes the entropy, as outlined above.
- Approximate search methods: Such as Monte Carlo tree search, greedy algorithms, or other machine learning techniques.
- Pre-computation: For known dictionaries (like the Wordle game list), the optimal decision tree can be computed offline and stored.
7. Summary of the Maths
To summarize, the mathematics behind solving Wordle optimally (for a low average score) include:
- Partitioning the candidate set: Use the feedback function ( f(g, w) ) to divide the candidate set into groups.
- Probability weighting: Each group has probability ( |T_p|/|T| ) assuming uniform distribution.
- Entropy/information theory: Compute the expected information gain from a guess.
- Recursive optimization: Define a recurrence for the expected number of moves: [ C(T) = \begin{cases} 0, & \text{if } |T| = 1 \ 1 + \min_{g \in D} \sum_{p} \frac{|T_p|}{|T|} , C(T_p), & \text{otherwise.} \end{cases} ]
- Decision tree formulation: Ultimately, the solution to Wordle is captured by an optimal decision tree where each node is a guess and branches correspond to the different feedback patterns.
This framework is at the heart of the “math behind solving Wordle” when you try to minimize the average number of guesses.
I hope this explanation provides you with a clear understanding of the mathematical foundations used to optimize a Wordle solver!
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.