Unraveling the Mechanics of Wordle: A Comprehensive Analysis of Greedy Search Algorithms
Brain teaser games have always captivated the minds of players, and Wordle is no exception. Developed by Josh Wardle and Palak Shah, Wordle quickly gained popularity due to its simplicity, community-driven nature, and addictive gameplay. In this blog post, we explore the rise of Wordle, its gameplay mechanics, and how we employed artificial intelligence agents and algorithms to beat Wordle.
The Rise of Wordle
Wordle, the beloved online word game sensation, traces its origins to the classic pen-and-paper game known as Jotto. In Jotto, players engage in a battle of wits, with one player tasked with concealing a secret word while the other attempts to decipher it. Similar to Wordle's dynamic, each incorrect guess in Jotto prompts the word's keeper to mark a large sheet with red, while every correct guess earns a green mark. This playful exchange of guesses and deductions has captivated players for generations, laying the groundwork for the digital phenomenon that Wordle has become today.
Another inspiration for the game is the television show, Lingo, which started in 1987. On the show, two teams of two individuals each went head to head to fill an entire sheet with five letter words using partial clues and letters. Similar to Wordle, if the team failed to guess the word in 5 tries, they lost.
Understanding Wordle
Players aim to guess a five-letter word in six tries or fewer. Each guess provides feedback in the form of color-coded categories: gray letters (not present in the final word), yellow letters (present but in different positions), and green letters (correctly positioned).
Wordle for AI
In Wordle, each five-letter word represents a potential state, and the goal for an artificial intelligence agent is to find the hidden state, which is the target word. While humans can choose their starting word, the agent is provided with a specified starting word. Although there are 12,966 possible states, only 2,315 are allowed to be goal states, known as the answer list. While restricting the agent to only visit goal states simplifies the task, exploring non-goal states can provide valuable information about letter positions. This setup allows for the problem to be solved using a local search algorithm, even when the goal state is unknown.
Understanding Heuristic Functions
When humans play Wordle, they use the feedback from previous guesses—green for correct letters in the right position, yellow for correct letters in the wrong position, and gray for incorrect letters—to narrow down the potential words. Similarly, AI agents employ heuristic functions, assigning weights to potential guesses based on prior information. These functions guide the AI in selecting the most promising words, aiming to minimize the number of guesses required to uncover the hidden word.
The General Algorithm
Try Wordle Solver yourself on Github: https://github.com/HenryLamBlog/Wordle-Solver
The AI solver operates with a clear objective: given a starting word and a specified heuristic, find the sequence of guesses leading to the hidden word. The algorithm maintains three key lists:
- Green: Records correct letters in the correct positions.
- Yellow: Tracks correct letters in incorrect positions.
- Gray: Marks incorrect letters.
Additionally, a list stores each guessed word to track the progress towards the solution.
The Solving Process
Initialization: The solver starts with the seed word and updates the lists accordingly for the first hidden word.
Guess Selection: The AI generates a list of potential guess words ordered by their heuristic value.
Guess Evaluation:
- Words containing letters from the gray list are skipped.
- Words conflicting with the yellow list are skipped.
- Words lacking green letters in specified positions are skipped.
- The word with the highest heuristic value meeting criteria is chosen.
Update Lists: Upon selecting a guess, the lists are updated, and the process repeats until the hidden word is found.
Achieving Success
After each guess, the program checks if the hidden word is among the guesses. If found, the program prints the sequence of guesses leading to the solution. The process continues for all hidden words, providing a comprehensive solution list.
Experimental Setup
- Solver Development: Adapted from a base program by GitHub user aAa1928, our Greedy Best-First Search solver employs a heuristic-based approach, only expanding nodes with green and yellow letters.
- Comparison Bots: We compare our Greedy Best-First Search solver against Doddle, Jon Paris’s Wordle bot, and The New York Times's Wordle bot, each using different algorithms.
- Human Comparison: Leveraging data from six million Wordle games and analysis on start word trends, we compare the Greedy Best-First Search solver’s performance against human players.
- State Space Reduction: We examine the impact of searching all allowed words versus only answer words on the Greedy Best-First Search solver's efficiency.
Experiment Design
- Solver Comparison: Each solver is provided the same answer list and allowed to guess from all valid words. Tests include using optimal start words "SALET," "RAISE," "CLOUT," and "NYMPH."
- Comparison Against Human Players: The Greedy Best-First Search solver's performance is compared to human success rates and trends in start word choices.
- State Space Reduction Analysis: We evaluate the solver's performance when limited to answer words versus all allowed words.
Results
Average Number of Guesses
| Solver | Average Guesses | % Correct |
|---|---|---|
| Doddle Entropy | 3.430 | 100 |
| Doddle Minimax | 3.481 | 100 |
| Jon Paris, Easy | 3.426 | 100 |
| Jon Paris, Hard | 3.506 | 99.91 |
| Greedy, answers | 3.747 | 98.92 |
| Greedy, all words | 4.518 | 93.05 |
| Greedy, answers 3 seed words | 4.251 | 99.56 |
| Greedy, all words 3 seed words | 4.583 | 97.41 |
The comparison of average guesses among different Wordle solvers sheds light on the efficacy of various strategies and algorithms in tackling the game's challenges. Doddle's algorithms and Jon Paris's easy mode solver demonstrate exceptional performance, consistently solving Wordles in five guesses or fewer. Conversely, the greedy best-first search algorithm, particularly when considering all allowed words as potential states, displays inferior performance, often requiring four or more guesses on average. Interestingly, employing three seed words instead of one, such as "RAISE," "CLOUT," and "NYMPH," introduces a slight impact on performance, with a marginally higher average number of guesses but potentially better success rates within six guesses. This variation underscores the importance of strategy selection and algorithmic approach in optimizing Wordle-solving techniques.
| Guess | Greedy, all | Greedy, answers | NYTimes Bot |
|---|---|---|---|
| 1 | SALET | SALET | CRANE |
| 2 | REALO | LEARN | PETAL |
| 3 | ALINE | IDEAL | BLEAK |
| 4 | ULEMA | GLEAM | GLEAM |
| 5 | GLEAM |
Comparing the greedy algorithm to The New York Times's Wordle bot reveals comparable performance, with both typically solving Wordles in about four guesses. This parity suggests the effectiveness of the greedy approach employed by both solvers in efficiently navigating the Wordle space. Additionally, the comparison highlights the strategic choices made by human players, such as starting with words like "ADIEU" or "SALET," and their impact on solving efficiency. While the common strategy among human players and solvers is to minimize the number of guesses until a solution is reached, the analysis suggests that certain starting words may lead to suboptimal outcomes. Overall, these findings provide valuable insights into the dynamics of Wordle-solving strategies and the interplay between algorithmic efficiency and human intuition in tackling the game's challenges.
Computation Speed
The computation speed was not initially considered a metric for comparing Wordle agents but was added since most solvers had this functionality built-in. Doddle's minimax algorithm was the fastest, taking 19 seconds, likely due to its decision tree-based approach. Doddle's entropy algorithm took 44 seconds, using Shannon entropy to make branches. Jon Paris's easy solver took three minutes and six seconds, while the hard mode solver took six minutes and fourteen seconds, using the A* algorithm on a graph with edges based on entropy.
In contrast, the greedy function developed here performed relatively poorly. When restricted to goal states, it took over three minutes for "SALET" and "RAISE," "CLOUT," and "NYMPH." Running on all allowed words increased the time to over an hour. This inefficiency stemmed from generating a new search list for each of the 2,315 words. Optimizing the greedy function by structuring it like Doddle and Jon Paris's solvers, with decision trees for each option, could dramatically reduce runtime.
Comparison against a Human Player
Percent Success Rates of a Human Player Compared to a Greedy Solver using "ADIEU", "SALET", or "RAISE", "CLOUT" and "NYMPH" as seed word(s). 'X' represents failure.
Comparing the greedy algorithm's performance in Wordle to human players reveals insights into strategy effectiveness and player behavior. While human players often choose suboptimal starting words like "ADIEU," the algorithm demonstrates adaptability to such choices, albeit with slightly reduced efficiency. This highlights players' tendencies towards casual play and suboptimal choices. However, prioritizing optimal starting words significantly improves success rates, solving nearly eighty percent of Wordles by the fourth guess with minimal failure.
Analysis
The analysis of the experiment results reveals several key findings regarding the performance of the greedy best-first search algorithm compared to other Wordle solvers and human players. Firstly, in terms of average number of guesses, the greedy best-first solver performed relatively poorly compared to other algorithms, especially when using all allowed words as the problem states. This suggests that limiting the problem states to just the goal states can prevent the algorithm from getting trapped into taking suboptimal next states.
Computation speed was another important factor, with Doddle's algorithms being the fastest due to their efficient approach of generating the entire game tree. The greedy best-first search algorithm, on the other hand, had longer computation times, especially when using all allowed words as problem states.
Comparing the algorithm's performance against human players revealed that while it performed better than some common human strategies like starting with "ADIEU," it still fell short of optimal performance. However, the algorithm's ability to consistently find solutions within a relatively low number of guesses suggests its potential for aiding human players in solving Wordle puzzles.
Overall, while the greedy best-first search algorithm shows promise as a Wordle solver, there are areas for improvement, such as optimizing computation speed and refining the heuristic function used to select next states. Additionally, exploring alternative approaches, such as using decision trees or entropy-based heuristics, could further enhance the algorithm's performance.
Conclusion:
The findings suggest that the optimized Wordle bots investigated outperform general human performance, as they are less prone to missteps and have access to more comprehensive information about the state space. While it's possible that there are individuals capable of achieving better results than any of the bots analyzed here, the aggregate data indicates that, on average, these bots excel at solving Wordle compared to humans.
Moving forward, there are several directions for future research. Experimenting with different algorithms, particularly ones that allow for playing in easy mode and are not restricted on guesses, could be fruitful. An entropy-based approach, similar to what is commonly used in other Wordle bots, could be explored further. Additionally, investigating Wordle agents for non-five letter words, such as four-letter or six-letter words, could provide interesting insights. Extending the algorithm developed here to handle these variations would likely be straightforward, with the main requirement being generating appropriate guess lists and answer lists.
Overall, as algorithms continue to improve beyond the capabilities of human thinking, it will be intriguing to see what further optimizations and advancements are made in the realm of Wordle bots.
You can read our written report here.
