Introduction
Wordle, a popular word-guessing game, serves as an excellent benchmark for sequential decision-making under uncertainty. In each game, a player attempts to identify a hidden five-letter "mystery word" within six tries. After each guess, the game provides feedback: green for correct letters in the correct position, yellow for correct letters in the wrong position, and gray for letters not present in the word. Mathematically, this is a sequential search problem where the objective is to minimize the expected number of guesses. This paper frames Wordle as a Partially Observable Markov Decision Process (POMDP) and applies "rollout" algorithms—a reinforcement learning technique—to achieve near-optimal performance with significantly lower computational overhead than traditional dynamic programming.
Problem Formulation: Wordle as a POMDP
The challenge of Wordle lies in its partial observability; the player knows the dictionary of possible words but does not know which specific word is the target. The "state" of the game is the subset of the dictionary that remains consistent with all previous feedback. The player's "belief" is a probability distribution over this subset.
Existing approaches generally fall into two categories:
- Heuristics: Fast strategies like "Maximum Information Gain" (MIG) select words that, on average, reduce the size of the remaining word list the most. While computationally efficient, these greedy approaches are often sub-optimal because they do not account for the long-term consequences of a guess.
- Exact Dynamic Programming (DP): These methods calculate the optimal move for every possible game state by exhaustively searching the game tree. While they yield perfect play, the computational cost is immense; solving Wordle optimally has been reported to take days on high-performance multi-core systems.
Methodology: The Rollout Algorithm
The authors propose a "middle way" using the Rollout Algorithm, an online reinforcement learning method rooted in the concept of Approximation in Value Space. This approach improves a base policy (heuristic) by looking ahead and simulating future outcomes.
The Rollout Step
The algorithm operates by performing a one-step look-ahead. For a given state, it identifies a set of candidate guesses. For each candidate, it simulates the entire remainder of the game using a base heuristic (e.g., MIG) for all subsequent moves. By calculating the "average Q-factor"—the expected total number of guesses required if a specific word is chosen now and the heuristic is followed later—the algorithm can identify the move that minimizes the total expected cost.
This mechanism is mathematically analogous to a single iteration of Policy Iteration or a single step of Newton’s method for solving the Bellman equation. If the base heuristic is reasonably effective, the rollout improvement often lands remarkably close to the global optimum.
Key Insights and Results
A critical simplification in the authors' model is the assumption of a uniform distribution over the mystery word list. This ensures that the belief state remains uniform over the remaining valid words, eliminating the need for complex recursive estimators like Kalman filters.
The Rollout+MIG strategy was evaluated against theoretical optimal scores in both "Easy Mode" (any valid word can be guessed) and "Hard Mode" (subsequent guesses must adhere to all revealed clues).
| Mode | Heuristic (MIG) | Rollout (MIG) | Optimal Score |
|---|---|---|---|
| Easy Mode | 3.6108 | 3.4345 | 3.4212 |
| Hard Mode | 3.6078 | 3.5231 | 3.5084 |
The results show that the rollout approach comes within 0.4% of the optimal score, providing a 5% improvement over the standard MIG heuristic in Easy mode. Furthermore, the method scales efficiently; it successfully solved 6-letter Wordle variants in seconds, a task where exact DP would face exponential complexity.
Conclusion and Future Work
The application of rollout algorithms to Wordle demonstrates that near-optimal control can be achieved in complex search spaces without exhaustive computation. By leveraging the power of look-ahead simulation, the rollout method bridges the gap between simple heuristics and computationally expensive exact solutions. Future research could incorporate non-uniform word frequencies and explore more volatile, stochastic environments where feedback might be noisy, further extending the utility of this adaptive control framework.
Summary updated