6 ms·

I wrote a solver a few weeks ago that solves easy mode in 3.45 guesses and hard mode in 3.55 guesses. Rather than using heuristics, it explored a large portion

I wrote a solver a few weeks ago that solves easy mode in 3.45 guesses and hard mode in 3.55 guesses. Rather than using heuristics, it explored a large portion of the game tree (with a little pruning) and I'm hopeful that it's optimal. Interestingly, the EV-optimal hard mode strategy takes 3.52 guesses on average, but requires 7 guesses a tiny fraction of the time, so I instead exposed the best strategy that always requires 6 or fewer guesses. If you're interested, you can play with it here: http://www.npinsker.me/puzzles/wordle/ http://www.npinsker.me/puzzles/wordle/ and the source (written in neophyte's Rust) is here: https://gist.github.com/npinsker/a495784b9c6eacfe481d8e38963b335c https://gist.github.com/npinsker/a495784b9c6eacfe481d8e38963... (edit: It's posted elsewhere in the thread, but this is actually not optimal and someone else achieved better results! http://sonorouschocolate.com/notes/index.php?title=The_best_strategies_for_Wordle http://sonorouschocolate.com/notes/index.php?title=The_best_...)

tomlockwood 5y ago
Oh dang! I was guessing that the optimal approach would be under 3.5 for easy mode, but was expecting it to be closer to 3! Amazing work. My next go at the problem is in Rust, which I am a total newcomer to. Thanks for sharing!
hgibbs 5y ago
As a point of curiosity, what do you mean by optimal? To me, I can see at least two (potentially different) cost functions that a Wordle strategy can aim to minimise. Firstly, you can try to minimise the expected number of guesses, and secondly you can try to minimise the expected number of guesses conditional on never losing the game. In principle you could optimise for the first but not the second by allowing a small list of hard words to take > 6 guesses on average. Part of my point is the lack of an absolute definition of optimal: strategies are only optimal up to the specified coat function.
- furyofantares 5y ago
  They specified that in the post, they were able to constrain to a strategy that guarantees 6 or fewer and then optimize for EV to get 3.55, but could get down to 3.52 by allowing some small number of words to take more than 6. I would be interested to know if 6 is the lowest you can constrain it. Can you guarantee a solution in 5, and if so what is the best EV with that constraint?
  - npinsker 5y ago
    Yes, you can -- I believe the EV was around 3.47 for that. The "greedy" strategy (minimizing the worst-case size of the largest set) also ends up using at most 5 words. Perhaps unsurprisingly, you can't guarantee at most 4 words.
    - Sesse__ 5y ago
      You can get EV of 3.46393 with a guaranteed maximum of five tries. (I don't know whether this bound is tight.)
      - pxx 5y ago
        This bound is not tight. http://sonorouschocolate.com/notes/index.php?title=The_best_strategies_for_Wordle http://sonorouschocolate.com/notes/index.php?title=The_best_...
        Sesse__ 5y ago
        Good to know. Another possible question is: What is the best strategy minimizing (at any point) _first_ the maximum number of tries, and second the EV (average number of tries over all possible words)? That's subtly different from either answer.
- hervature 5y ago
  Funnily enough, I think neither of those notions are the correct thing to optimize. For me, you want to minimize the maximum number of guesses. This leads to an equilibrium. Otherwise, your opponent can just abuse your strategy.
  - pxx 5y ago
    Isn't that just #2, but changing the definition of losing to be the least number of rounds where you can always win (which for Wordle is 5)? These small changes to the definition don't seem to change ev (or the code needed to generate it) that much. If you don't care about optimizing the EV at all, the greedy tree already has the property you're interested in.
  - noxvilleza 5y ago
    Adversarial strategies are another type of problem entirely (as in, if you're playing Word Mastermind). Wordle is a 1-player game, so I find hgibbs's comment totally reasonable. I would think that 'optimal' is more accurately his second definition - minimizing avg guesses but always winning (as in, losing is +inf guesses).
  - hgibbs 5y ago
    My point is exactly that though - the choice of cost function is subjective. There is no best cost function, just a mapping from costs functions to optimal strategies.
  - eru 5y ago
    What do you mean by opponent? The entity choosing the word in a game like Wordle or Hang Man is more like the dungeon master in a game of D&D than an opponent in the traditional sense? They are there to help you have fun.
  - hnkain 5y ago
    The (exact) optimal EV-minimizing strategies (assuming each target word is equally likely) always solve in 5 of fewer guesses in normal mode, and always solve in 6 guesses in hard mode. If you wish to guarantee 5 guesses in hard mode, there's a different (optimal) strategy with slightly higher EV. See: http://sonorouschocolate.com/notes/index.php?title=The_best_strategies_for_Wordle http://sonorouschocolate.com/notes/index.php?title=The_best_... I don't think a maximum-number-of-guesses optimizer leads to an equilibrium (if you mean Nash equilibrium), assuming you're playing the game where the score of the game for the setter is the number of guesses. In particular, if the solver's strategy is deterministic, the setter will always pick one of the words that needs 5 guesses. There's no reason to think the nash equilibrium can be easily found.
- svat 5y ago
  IMO, never losing the game is the bare minimum for any reasonable cost function: never take > 6 guesses. Beyond that, you can have different optimization functions based on whether you're trying to minimize the worst-case depth of the decision tree (number of guesses) for each position, or the average depth, or some other reasonable function of the distribution over number of guesses. Although you could have arbitrarily many cost functions, a fairly general class is the following: pick some nonnegative constants (w1, w2, w3, w4, w5, w6, w7), and for a certain strategy, define the cost as: w1*n1 + w2*n2 + w3*n3 + w4*n4 + w5*n5 + w6*n6 + w7*n7 where nk (for 1≤k≤6) is the number of hidden (solution) words for which the strategy takes n guesses, and n7 is the number of words for which the strategy loses the game. Then, • Setting w7 infinite / very high is a way of encoding the condition that you not lose the game. (You can set it finite/small if you don't mind occasionally losing the game for some reason!) • Setting w1 = 1, w2 = 2, …, w6 = 6 will simply minimize the average number of guesses, • Having them grow exponentially, e.g. setting wk = c^(k-1), where c is some constant larger than 12972 (the number of acceptable guess words) will make sure that the minimal-cost strategy first minimizes the maximum number of guesses, then break ties by having the fewest words take that many guesses, and so on.
  - tshaddox 5y ago
    > IMO, never losing the game is the bare minimum for any reasonable cost function: never take > 6 guesses. I wouldn’t think so. If I get 99.9% of rounds correct with 3 guesses (and fail to find a solution to 0.1% of the rounds), and you get 100% of rounds with 6 guesses, I’d say I’ve soundly defeated you 99.9% of the time.
    - svat 5y ago
      Right, that point of view makes sense if you imagine two players separately playing Wordle and comparing their results, and indeed that's what the OP may have been thinking. But as far as I know, Wordle is primarily a game for one player to play against the computer, where eventually getting to the word (or not) is the most prominent outcome (the only notion of "win" or "defeat" in the game itself), and solving it in fewer guesses is just a bonus. But sure, if you don't care about occasionally losing, you can just set an appropriate weight for w7 within the same family of cost functions.
- tshaddox 5y ago
  If two players are competing in a single round of wordle, then surely the player who guesses the correct word in the fewer number of guesses wins, right? Then it seems natural to say that the better of two players is the one with the most wins after playing all possible rounds. The only problem is that I think this definition leads to the possibility of non-transitivity, where A beats B, B beats C, and C beats A.
deleted 5y ago
[deleted]
stavros 5y ago
That looks great! It would be very interesting to see the set of words "left" after a guess, too.
theolivenbaum 5y ago
Nice! I was wondering almost the same thing this morning while my wife was playing Wordle - ended up coding an assistant to help you choose the optimum words. If anyone wants to check it out, I published it here https://curiosity.ai/wordle/ https://curiosity.ai/wordle/ - source code is also available here https://github.com/theolivenbaum/wordle-assist https://github.com/theolivenbaum/wordle-assist.
desbo 5y ago
This is great. But it seems to fail with words containing repeat letters, for example, with my word as BOOKS, not on hard mode: SOARE JUMBY BOOST (at this point, it claimed to have won!)
- pxx 5y ago
  books isn't a valid solution. it's on the guesslist but not the wordlist.
  - mrb 5y ago
    Correct. In fact, thousands of plural words are allowed as guesses, but the solution will never be plural. Source: I grep'd the lists of solutions and authorized guesses.
  - eco 5y ago
    I used the combined solution and valid word list when I was playing around with a program to find good starting words. Feels too much like cheating otherwise.
Humphrey 5y ago
It fails with the word "frogs", as it tells me it is "gross"
- nerdo 5y ago
  Frogs isn't in the wordle list: https://github.com/tomlockwood/wordle-solve/blob/main/lib/words.py https://github.com/tomlockwood/wordle-solve/blob/main/lib/wo...
ycombobreaker 5y ago
I've seen a number of solvers; but my partner has forbidden me from writing one, forcing me to do everything in wetware. 3-4 guesses seems right intuitively. I saw some speculation that the dictionary was well-known, is that true? Seems to me that the problem as-stated allows the guesser to discover a nonword "for free", but otherwise expects the dictionary to be "all five letter words" which is much larger than the real solution space. Though, maybe in practice that doesn't change the solvability by much.
- kevlened 5y ago
  The wordlist is more than well-known, the word for each day is predetermined. The entire game runs in the browser and the selected word is based on the date. Here’s a quick script based on any date you select: https://codepen.io/kevlened/full/NWaOmPw https://codepen.io/kevlened/full/NWaOmPw
- tomlockwood 5y ago
  This program actually inadvertently created a quite philosophical discussion amongst my friends! Some of them contended that writing a program to solve wordle sucked the joy out of the process of solving it, even if I solved the puzzle myself, first.
  - ycombobreaker 5y ago
    Yes it's interesting, precisely because it's intuitively "solvable" by machines. There's joy in solving by hand, and joy in creating a solver, but probably no joy in running your solver every day and sharing with your friends. Because every decision is some maximum-likelihood estimate, there's no tension or drama in the sequence of guesses. In fact, simply the act of creating an infallible solver (100% likelihood of 6 guesses or less) demonstrates the futility of competing with their soft, fleshy skills. I do think any solver that uses the solution-set is "cheating", but I suspect it makes little difference in the total solution (like... 2-3 bits of additional information needed, just a fraction of a round).
    - 5y ago
forrestthewoods 5y ago
Neat! The graph of every possible game for Hard mode should be pretty tractable. Sounds like you wrote almost exactly what I started but have been too lazy to finish. > but requires 7 guesses a tiny fraction of the time, so I instead exposed the best strategy that always requires 6 or fewer guesses. That's awesome. My question is "what is the minimum number of guesses to solve every word while guaranteeing it never loses". For hard mode I'm pretty sure this can be provably brute forced. Easy mode requires enough pruning I'm not sure it can be proved.
bscphil 5y ago
If you just brute force solve with greedy search (always pick the word that results in the highest average reduction in remaining possible words), you get a solution with an average of 3.47. Even only guessing words on the primary word list (which Wordle uses to pick the word of the day) you can get 3.51. That's as far as I've chased the problem. I'm surprised to hear that optimal play only gets you 3.4212 (according to the link you posted).
deleted 5y ago
[deleted]

tomlockwood 5y ago

Oh dang! I was guessing that the optimal approach would be under 3.5 for easy mode, but was expecting it to be closer to 3! Amazing work. My next go at the problem is in Rust, which I am a total newcomer to. Thanks for sharing!

hgibbs 5y ago

As a point of curiosity, what do you mean by optimal? To me, I can see at least two (potentially different) cost functions that a Wordle strategy can aim to minimise. Firstly, you can try to minimise the expected number of guesses, and secondly you can try to minimise the expected number of guesses conditional on never losing the game. In principle you could optimise for the first but not the second by allowing a small list of hard words to take > 6 guesses on average. Part of my point is the lack of an absolute definition of optimal: strategies are only optimal up to the specified coat function.

furyofantares 5y ago
They specified that in the post, they were able to constrain to a strategy that guarantees 6 or fewer and then optimize for EV to get 3.55, but could get down to 3.52 by allowing some small number of words to take more than 6. I would be interested to know if 6 is the lowest you can constrain it. Can you guarantee a solution in 5, and if so what is the best EV with that constraint?
- npinsker 5y ago
  Yes, you can -- I believe the EV was around 3.47 for that. The "greedy" strategy (minimizing the worst-case size of the largest set) also ends up using at most 5 words. Perhaps unsurprisingly, you can't guarantee at most 4 words.
  - Sesse__ 5y ago
    You can get EV of 3.46393 with a guaranteed maximum of five tries. (I don't know whether this bound is tight.)
    - pxx 5y ago
      This bound is not tight. http://sonorouschocolate.com/notes/index.php?title=The_best_strategies_for_Wordle http://sonorouschocolate.com/notes/index.php?title=The_best_...
      - Sesse__ 5y ago
        Good to know. Another possible question is: What is the best strategy minimizing (at any point) _first_ the maximum number of tries, and second the EV (average number of tries over all possible words)? That's subtly different from either answer.
hervature 5y ago
Funnily enough, I think neither of those notions are the correct thing to optimize. For me, you want to minimize the maximum number of guesses. This leads to an equilibrium. Otherwise, your opponent can just abuse your strategy.
- pxx 5y ago
  Isn't that just #2, but changing the definition of losing to be the least number of rounds where you can always win (which for Wordle is 5)? These small changes to the definition don't seem to change ev (or the code needed to generate it) that much. If you don't care about optimizing the EV at all, the greedy tree already has the property you're interested in.
- noxvilleza 5y ago
  Adversarial strategies are another type of problem entirely (as in, if you're playing Word Mastermind). Wordle is a 1-player game, so I find hgibbs's comment totally reasonable. I would think that 'optimal' is more accurately his second definition - minimizing avg guesses but always winning (as in, losing is +inf guesses).
- hgibbs 5y ago
  My point is exactly that though - the choice of cost function is subjective. There is no best cost function, just a mapping from costs functions to optimal strategies.
- eru 5y ago
  What do you mean by opponent? The entity choosing the word in a game like Wordle or Hang Man is more like the dungeon master in a game of D&D than an opponent in the traditional sense? They are there to help you have fun.
- hnkain 5y ago
  The (exact) optimal EV-minimizing strategies (assuming each target word is equally likely) always solve in 5 of fewer guesses in normal mode, and always solve in 6 guesses in hard mode. If you wish to guarantee 5 guesses in hard mode, there's a different (optimal) strategy with slightly higher EV. See: http://sonorouschocolate.com/notes/index.php?title=The_best_strategies_for_Wordle http://sonorouschocolate.com/notes/index.php?title=The_best_... I don't think a maximum-number-of-guesses optimizer leads to an equilibrium (if you mean Nash equilibrium), assuming you're playing the game where the score of the game for the setter is the number of guesses. In particular, if the solver's strategy is deterministic, the setter will always pick one of the words that needs 5 guesses. There's no reason to think the nash equilibrium can be easily found.
svat 5y ago
IMO, never losing the game is the bare minimum for any reasonable cost function: never take > 6 guesses. Beyond that, you can have different optimization functions based on whether you're trying to minimize the worst-case depth of the decision tree (number of guesses) for each position, or the average depth, or some other reasonable function of the distribution over number of guesses. Although you could have arbitrarily many cost functions, a fairly general class is the following: pick some nonnegative constants (w1, w2, w3, w4, w5, w6, w7), and for a certain strategy, define the cost as: w1*n1 + w2*n2 + w3*n3 + w4*n4 + w5*n5 + w6*n6 + w7*n7 where nk (for 1≤k≤6) is the number of hidden (solution) words for which the strategy takes n guesses, and n7 is the number of words for which the strategy loses the game. Then, • Setting w7 infinite / very high is a way of encoding the condition that you not lose the game. (You can set it finite/small if you don't mind occasionally losing the game for some reason!) • Setting w1 = 1, w2 = 2, …, w6 = 6 will simply minimize the average number of guesses, • Having them grow exponentially, e.g. setting wk = c^(k-1), where c is some constant larger than 12972 (the number of acceptable guess words) will make sure that the minimal-cost strategy first minimizes the maximum number of guesses, then break ties by having the fewest words take that many guesses, and so on.
- tshaddox 5y ago
  > IMO, never losing the game is the bare minimum for any reasonable cost function: never take > 6 guesses. I wouldn’t think so. If I get 99.9% of rounds correct with 3 guesses (and fail to find a solution to 0.1% of the rounds), and you get 100% of rounds with 6 guesses, I’d say I’ve soundly defeated you 99.9% of the time.
  - svat 5y ago
    Right, that point of view makes sense if you imagine two players separately playing Wordle and comparing their results, and indeed that's what the OP may have been thinking. But as far as I know, Wordle is primarily a game for one player to play against the computer, where eventually getting to the word (or not) is the most prominent outcome (the only notion of "win" or "defeat" in the game itself), and solving it in fewer guesses is just a bonus. But sure, if you don't care about occasionally losing, you can just set an appropriate weight for w7 within the same family of cost functions.
tshaddox 5y ago
If two players are competing in a single round of wordle, then surely the player who guesses the correct word in the fewer number of guesses wins, right? Then it seems natural to say that the better of two players is the one with the most wins after playing all possible rounds. The only problem is that I think this definition leads to the possibility of non-transitivity, where A beats B, B beats C, and C beats A.

deleted 5y ago

[deleted]

stavros 5y ago

That looks great! It would be very interesting to see the set of words "left" after a guess, too.

theolivenbaum 5y ago

Nice! I was wondering almost the same thing this morning while my wife was playing Wordle - ended up coding an assistant to help you choose the optimum words. If anyone wants to check it out, I published it here https://curiosity.ai/wordle/ https://curiosity.ai/wordle/ - source code is also available here https://github.com/theolivenbaum/wordle-assist https://github.com/theolivenbaum/wordle-assist.

desbo 5y ago

This is great. But it seems to fail with words containing repeat letters, for example, with my word as BOOKS, not on hard mode: SOARE JUMBY BOOST (at this point, it claimed to have won!)

pxx 5y ago
books isn't a valid solution. it's on the guesslist but not the wordlist.
- mrb 5y ago
  Correct. In fact, thousands of plural words are allowed as guesses, but the solution will never be plural. Source: I grep'd the lists of solutions and authorized guesses.
- eco 5y ago
  I used the combined solution and valid word list when I was playing around with a program to find good starting words. Feels too much like cheating otherwise.

Humphrey 5y ago

It fails with the word "frogs", as it tells me it is "gross"

nerdo 5y ago
Frogs isn't in the wordle list: https://github.com/tomlockwood/wordle-solve/blob/main/lib/words.py https://github.com/tomlockwood/wordle-solve/blob/main/lib/wo...

ycombobreaker 5y ago

I've seen a number of solvers; but my partner has forbidden me from writing one, forcing me to do everything in wetware. 3-4 guesses seems right intuitively. I saw some speculation that the dictionary was well-known, is that true? Seems to me that the problem as-stated allows the guesser to discover a nonword "for free", but otherwise expects the dictionary to be "all five letter words" which is much larger than the real solution space. Though, maybe in practice that doesn't change the solvability by much.

kevlened 5y ago
The wordlist is more than well-known, the word for each day is predetermined. The entire game runs in the browser and the selected word is based on the date. Here’s a quick script based on any date you select: https://codepen.io/kevlened/full/NWaOmPw https://codepen.io/kevlened/full/NWaOmPw
tomlockwood 5y ago
This program actually inadvertently created a quite philosophical discussion amongst my friends! Some of them contended that writing a program to solve wordle sucked the joy out of the process of solving it, even if I solved the puzzle myself, first.
- ycombobreaker 5y ago
  Yes it's interesting, precisely because it's intuitively "solvable" by machines. There's joy in solving by hand, and joy in creating a solver, but probably no joy in running your solver every day and sharing with your friends. Because every decision is some maximum-likelihood estimate, there's no tension or drama in the sequence of guesses. In fact, simply the act of creating an infallible solver (100% likelihood of 6 guesses or less) demonstrates the futility of competing with their soft, fleshy skills. I do think any solver that uses the solution-set is "cheating", but I suspect it makes little difference in the total solution (like... 2-3 bits of additional information needed, just a fraction of a round).
  - 5y ago

forrestthewoods 5y ago

Neat! The graph of every possible game for Hard mode should be pretty tractable. Sounds like you wrote almost exactly what I started but have been too lazy to finish. > but requires 7 guesses a tiny fraction of the time, so I instead exposed the best strategy that always requires 6 or fewer guesses. That's awesome. My question is "what is the minimum number of guesses to solve every word while guaranteeing it never loses". For hard mode I'm pretty sure this can be provably brute forced. Easy mode requires enough pruning I'm not sure it can be proved.

bscphil 5y ago

If you just brute force solve with greedy search (always pick the word that results in the highest average reduction in remaining possible words), you get a solution with an average of 3.47. Even only guessing words on the primary word list (which Wordle uses to pick the word of the day) you can get 3.51. That's as far as I've chased the problem. I'm surprised to hear that optimal play only gets you 3.4212 (according to the link you posted).

deleted 5y ago

[deleted]