Solving Wordle in 3.64 guesses on average, 99.4% of the time • Hacker News Board

Re: Solving Wordle in 3.64 guesses on average, 99.4% of the time

#31

Post by hgibbs » Sun, Jan 23, 2022, 9:52 PM UTC

npinsker wrote: post #16

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 r…

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.

Re: Solving Wordle in 3.64 guesses on average, 99.4% of the time

#32

Post by OJFord » Sun, Jan 23, 2022, 9:53 PM UTC

canjobear wrote: post #13

Going for greens is a good heuristic, but the general solution is to seek guesses that shrink the size of the set of compatible words the most. https://langproc.substack.com/p/information-theoretic-analys...

Or, especially in first guess or so, shrink the set of letters used by the remaining compatible words, which is subtly different right?

Re: Solving Wordle in 3.64 guesses on average, 99.4% of the time

#33

Post by thxg » Sun, Jan 23, 2022, 9:53 PM UTC

This [1] solves it in 3.4212 average guesses 100% of the time and claims optimality, which is 99% of the difficulty it seems. For the limited 2671-word set of possible words, I think the question is now settled (for the whole 12k-word set, I don't think anyone tried anything).

It was posted here four days ago [2].

[1] http://sonorouschocolate.com/notes/index.php?title=The_best_...

[2] https://news.ycombinator.com/item?id=30006724

Re: Solving Wordle in 3.64 guesses on average, 99.4% of the time

#34

Post by tomlockwood » Sun, Jan 23, 2022, 9:53 PM UTC

zeroonetwothree wrote: post #18

canjobear wrote: post #13

Going for greens is a good heuristic, but the general solution is to seek guesses that shrink the size of the set of compatible words the most. https://langproc.substack.com/p/information-theoretic-analys...

Using essentially this method I get that the best initial guess is RAISE (there are some others that are very close). It seems the author of this post didn’t use the actual word list from the game so got a different word.

I used the actual wordlist, yoinked out of the javascript with my totally elite dev-tools-in-chrome-hacking!

But yeah, given the frequency of letters, in position, in the target list, the answer is SLATE.

Re: Solving Wordle in 3.64 guesses on average, 99.4% of the time

#35

Post by canjobear » Sun, Jan 23, 2022, 9:54 PM UTC

zeroonetwothree wrote: post #18

canjobear wrote: post #13

Going for greens is a good heuristic, but the general solution is to seek guesses that shrink the size of the set of compatible words the most. https://langproc.substack.com/p/information-theoretic-analys...

Using essentially this method I get that the best initial guess is RAISE (there are some others that are very close). It seems the author of this post didn’t use the actual word list from the game so got a different word.

Yeah when I ran my script using the real wordlist I got RAISE too. (Just updated the article.)

Re: Solving Wordle in 3.64 guesses on average, 99.4% of the time

#36

Post by LeoPanthera » Sun, Jan 23, 2022, 9:56 PM UTC

See also Absurdle, an adversarial Wordle that is designed to be as difficult as possible: https://qntm.org/files/wordle/

I won't spoil how it works, but click the "?" button on the page if you want to know.

Re: Solving Wordle in 3.64 guesses on average, 99.4% of the time

#37

Post by shagie » Sun, Jan 23, 2022, 9:56 PM UTC

matthewfelgate wrote: post #29

Thanks for sharing. I have a feeling that a perfect algorithm should be able to solve all wordles in 4 guesses. (but I might be wrong) The problem with a lot of approaches is they seem to locally optimise for each guess rather than optimise over all the guesses (if that makes sense?) I get the feeling guessing the most frequent letters might not be the best approach, because does it cut down the number of possible wo…

A bit ago on HN there was a link to Evil Wordle - https://swag.github.io/evil-wordle/ ( https://news.ycombinator.com/item?id=29864418 ) and there's another variation of it at https://qntm.org/files/wordle/

On NPR ( https://www.npr.org/2022/01/23/1075168693/youve-heard-of-wor... )

> QNTM: So with Wordle, in theory, you can win in one guess. I've won in two guesses a couple of times. Absurdle - you cannot beat it in less than four guesses. Four is the limit. But generally just good luck - you're going to need it.

The worst case for Wordle and evil world or Absurdle should be the same... its just that evil and absurd are always the worst case.

Re: Solving Wordle in 3.64 guesses on average, 99.4% of the time

#38

Post by vba616 » Sun, Jan 23, 2022, 9:58 PM UTC

>so far what was taking 1GB of RAM in Python is taking, literally 1MB in Rust

Is anybody hiring people to fix situations like this at work? i.e. this script that was written in a hurry needs to be revised to be 10^3 times more efficient, in space or time.

Re: Solving Wordle in 3.64 guesses on average, 99.4% of the time

#39

Post by [deleted] » Sun, Jan 23, 2022, 9:58 PM UTC

npinsker wrote: post #16

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 r…

[deleted]

Re: Solving Wordle in 3.64 guesses on average, 99.4% of the time

#40

Post by npinsker » Sun, Jan 23, 2022, 9:58 PM UTC

canjobear wrote: post #13

Going for greens is a good heuristic, but the general solution is to seek guesses that shrink the size of the set of compatible words the most. https://langproc.substack.com/p/information-theoretic-analys...

> From an information-theoretic perspective, the optimal initial guess is the one which is maximally informative about the target, given the resulting pattern.

This statement (which motivates the rest of the analysis) isn't correct, because it doesn't take into account the highly irregular search space of what you're actually allowed to guess. Sets of possible words can vary a lot in terms of how easily they can be further cut down: for example, if you're on hard mode and your set of possible words is [BILLY, DILLY, FILLY, HILLY, SILLY, WILLY], then you might be in trouble.