Eldrow

Eldrow is a variation of the viral word game Wordle where the human and computer roles are reversed. In Wordle, the computer has a secret word that you are trying to guess. In Eldrow, the computer tries to guess the secret word that you have in mind. In today’s post, I wanted to explain my thought process behind Eldrow as well as how it works on a technical level.

The Solver

Strategy

At the heart of Eldrow is the Wordle solver program. Eldrow is greedy: it will try to eliminate as many words as quickly as possible. I’m using the Wordle dictionary and not differentiating between solution words and guessable words, so there are a total of 12,972 words that could be the solution.

To illustrate this strategy, let’s walk through an example game where the word is ABOUT – the most common English word in Wordle’s dictionary.

The first guess, SERAI, is guaranteed to narrow down the solution space to at most 697 words. That means even if we didn’t get any letters, or if we only got one or two letters present but not correct, there can only be at most 697 remaining words that we will need to choose between. This is the best possible performance on the first guess.

The next four best words for the first guess are:

  • reais: 769
  • soare: 769
  • paseo: 776
  • aeros: 801
S (not present), E (not present), R (not present), A (present), I (not present)

In this example game, the A in the fourth position gets a “present” hint, and this narrows down our search space to 697 words. Next, we guess NYALA, which guarantees us a solution space of 74 or less.

First guess: S (not present), E (not present), R (not present), A (present), I (not present). Second guess: N (not present), Y (not present), A (present), L (not present), A (not present).

Our guess didn’t give us any new present or correct letters, but we still ended up ruling out almost 90% of the words it could’ve been!

Unlike the first guess, for which SERAI is always optimal, the best second guess varies wildly with the score of the first guess.

The best guess at this step is BHOOT, which gives us another 10x improvement by guaranteeing that we will have at most 6 words to choose from.

First guess: S (not present), E (not present), R (not present), A (present), I (not present). Second guess: N (not present), Y (not present), A (present), L (not present), A (not present). Third guess: B (present), H (not present), O (correct), O (not present), T (correct).

This time we get lucky, and our hint from BHOOT rules out every single word except for one: ABOUT.

First guess: S (not present), E (not present), R (not present), A (present), I (not present). Second guess: N (not present), Y (not present), A (present), L (not present), A (not present). Third guess: B (present), H (not present), O (correct), O (not present), T (correct). Fourth guess: ABOUT, all correct.

And that’s how the game is played!

Speed

Making the solver fast enough for a game was a major hurdle. I originally wrote the solver in three hours using JavaScript, since that’s the programming language I’m most comfortable in and familiar with, but it soon became clear that I needed to compile to native machine code if I wanted to use it to play Wordle. I used Rust before to write the keyboard layout optimizer that produced RSTHD, and given its speed and expressiveness, it was a natural tool to reach for. Then, once I got the idea to turn the solver into an online game, I compiled the Rust solver to WASM so I could use it with React. Fortunately, existing tools made this extremely easy, despite me not having any successful previous experiences configuring Webpack, Babel, etc.

Compiling to machine code and leveraging SSE and AVX features ended up making a massive difference in performance:

VersionTime to find best first guess
JavaScript57.0 minutes
Rust, compiled to WASM14.7 seconds (230x improvement)
Rust, native & fully optimized (-C target-cpu=native)4.94 seconds (3x improvement)

I was originally planning on adding threads to parallelize the search for the best guess, but after seeing the speed of the solver after porting to Rust, I deemed further optimization unnecessary. The speed of guesses increases exponentially with each guess, so I only had to hard-code lookup tables for the first two guesses to basically guarantee the player will never wait more than 2 or 3 seconds for the next guess.

Another big performance optimization, which I made early on in both the JavaScript and Rust solvers, was also critical in making the solver run fast enough to play against: bitfields and lookup tables.

To find the optimal guess in a given situation, the solver must do two things:

  1. Calculate which words could possibly be the solution based on previous guesses
  2. Calculate which next guess would eliminate the most words from the list of possible solutions in the worst case

A natural solution would be to store candidate words as strings in a hash map and use string operations to filter down the list of candidates when evaluating both previous guesses and potential next guesses. However, this requires a large amount of memory allocations and iterating over strings. Since the list of candidate words is static, we can precompute some useful lookup tables that will speed up runtime performance significantly at the cost of extra code size. I chose to build lookup tables for the following:

  • Lists of words that have a given letter (A–Z) in a given position (1–5)
  • Lists of words that have at least N (1–5) instances of a given letter (A–Z)

Instead of storing the words themselves or hashes of them in the lookup tables, I assigned each word a numeric index based on how common it is (if two words are equally good guesses, the solver will guess the more common word) and stored each list as a bitfield with the bit at each word’s index representing whether or not that word satisfies the given condition. For example, here’s the beginning of the lookup table for “words that have at least one E”:

Byte #0123
Bits10011010110011101011100100111101
Matches
(Bit #)
other (#1)
their (#3)
there (#4)
these (#7)
price (#9)
state (#10)
email (#11)
after (#14)
video (#15)
where (#16)
years (#19)
order (#20)
items (#21)
under (#23)
games (#24)
great (#26)
hotel (#27)
store (#28)
terms (#29)

I use the same bitfield data structure to store the list of current candidate solutions, though in the case of the candidate solutions, enabled bits represent words that are eliminated. (This is just an implementation quirk, and I could’ve just as easily written it the other way around.) With this lookup table, when we encounter a guess with a yellow E, we can apply the information from the guess by bitwise-or’ing the complement of the lookup table into our candidate solution list. This is extremely fast compared to looking for the letter E in each candidate word due to the fact that we can process 64 candidate words per CPU instruction (assuming we’re running a 64-bit machine), and with modern x86 CPUs, SSE and AVX will get that to 256 or even 512 words at a time.

Counting the number of candidate solutions, which we do a lot to rank the suitability of possible guesses, is extremely fast in native code because we can use the popcnt instruction, which is available in both x86 and WASM. In contrast, I had to resort to slower methods for the same functionality in JavaScript.

Results

As Jonathan Olson notes, the greedy strategy in Eldrow is not actually the best strategy if your goal is to minimize the average or maximum number of guesses over all possible words. However, it has the advantage that the optimal solution for this heuristic does not require exhaustively searching the game’s decision tree. Although there isn’t a lot of information about other solvers that can solve for the entire guessable word list (most people only target the solution words), it seems that Eldrow does fairly well:

GuessesWords that take that many guesses to get
11
266
31716
46414
54086
6645
740
84

99.7% of words can be guessed in six tries or less, and the median number of guesses per word is four. Given that there’s only a handful of words that require 7 or 8 guesses, it may be possible to fine tune the decision tree to be able to guess everything in 6 guesses or less. However, the existence of the 7s and 8s is a big part of what makes Eldrow fun – if you want to know what they are, you’ll have to play Eldrow to find them!

The Game

Once I had the solver, the first thing I did was (obviously) see if it would help me beat Wordle. As this got boring, the idea slowly dawned on me that I could make the solver into its own game. I was aware of Absurdle, an adversarial variant in which the computer will try to divulge as little information as possible with each guess, so it only made sense to me that it should have an equal and opposite adversary that tries to gain as much information as possible with each guess.

By the way, since Absurdle and Eldrow are both deterministic, if you pit them against each other you’ll always end up with the word BOBBY in 5 guesses:

⬜⬜⬜⬜⬜
⬜⬜🟨⬜🟩
⬜⬜⬜⬜⬜
⬜🟩⬜⬜🟩
🟩🟩🟩🟩🟩

I wanted the UI to be as simple and intuitive as the original Wordle, so I ended up with a system where tapping a letter toggles through the possible hint types (black, yellow, green; not present, present, correct). I also wanted to ensure that it was accessible to as many people as possible, so I included not only the color blind mode from the original Wordle but also a high contrast mode and support for screen readers. (If you rely on a screen reader, I would love to hear feedback about how well I did because I don’t use a screen reader outside of accessibility testing.)

In terms of tech, it’s nothing too special. I started with some starter code for Rust + WASM and bumbled my way through configuring Webpack and Babel to let me write React in JSX.

Anyway, that’s everything remotely interesting I have to say about Eldrow. If you’re looking for other riffs on the Wordle concept, check out Wordles of the World, which is as far as I know the most comprehensive list of Wordle spinoffs.

Advertisement

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s