Adversarial Wordle
qntm.orgThis is great! A few days ago, I wrote a Wordle solver in C. It selects a word to minimize the number of words assuming the worst-case green/yellow.
So, it sounds like these two are in direct conflict. My solver is deterministic, and it looks like the adversarial is too, so they always play the same game:
S E R A I (0 green, 0 yellow, 429 words remain)
M O L D Y (1 green, 0 yellow, 35 words remain)
C E N T U (0 greem, 2 yellow, 2 words remain)
V O U C H (4 green, 0 yellow, 1 word remains)
P O U C H (5 green, 0 yellow, 0 words remain)I've written a Wordle solver in F#. It's interesting because your first word contains the five most probable letters. My solver starts off by selecting, at random, one of the possible words that have these five letters.
Could you say more how you've determined your solver to be deterministic in 6 steps?
Also, I'm not sure I understand what this means:
> It selects a word to minimize the number of words assuming the worst-case green/yellow.
Particularly the part "assuming the worst-case green/yellow". Do you mind elaborating?
So, my algorithm is deterministic because there isn't any random element in it. And then it appears the adversarial doesn't either because the game plays out the same way every time.
So, to generate a single guess, the algorithm will basically try every single word in the dictionary against every possible remaining word. For any given guess, it tracks the count of various possible scorings. The scorings are the positions of greens, and yellows for a total of 243 possible scorings. After looping through all possible remaining words, it finds the max occurrence count within the scoring array. That maximum count becomes that guess's overall utility. It then finds the overall guess that minimizes that utility. (See: https://en.wikipedia.org/wiki/Minimax) After typing this all out, I feel like I didn't do a great job explaining, so let me know what you think.
Thanks for the elaboration. I see what you mean by deterministic now. Is it also deterministic in the sense of always getting an answer within 6 guesses (maybe convergent is a better word)? (Maybe it's not possible to guarantee this. That's something I've been wondering.)
My solver is a naive one at the moment, where I've only done a little analysis to get a good starting word. From there, my solver just tracks the results from each guess and randomly selects a word that meets the constraints for the next guess. That actually works surprisingly well, and it hasn't failed Wordle yet.
I've been meaning to go back and do a more thorough analysis and create a more targeted strategy.
I'd love to see your code! My strategy[0] (not-yet-automated) doesn't aim to minimize in the worst case, but rather to minimize the expected size of the set of possible words.
Have you done any thinking about hard mode? Getting trapped in a 'deep' pattern (?ight: e, f, l, m, n, r, s, t, w) too soon seems like a problem. But this is way outside my bailiwick.
Wow! I really like your analysis!
Yeah, I was trying to determine the utility function that would determine how to select words, but I'm more of a gut-feel, intuitive sort of person. I also tried a squared term like yours, but for some reason, it didn't feel right when I tested it. That version decided the best initial word was `LARES`. I have a sneaky suspicion that we need to account for how common a word was. I think my solver was getting to hung up worrying about BRAXY and CRURA, and giving them similar weight to a word like TRACK.
However, it was very hard to debug because a slightly buggy version was still decent at playing the game! In fact, I'm fairly certain I still have some bugs. I need to comment my code and get it up on Github. It's also super brute force O(n^2)
Okay, I ran it again with the squared term in the utility function. Here's what it did:
L A R E S (0 green, 0 yellow, 576 words remain) T O N I C (1 green, 0 yellow, 50 words remain) B O O D Y (4 green, 0 yellow, 5 words remain) D E G U M (0 green, 2 yellow, 1 word remains) G O O D Y (5 green, 0 yellow, 0 words remain)
Are you using the same dictionary? I used the same technique, and got:
And then VOUCH / COUCH / POUCH / GOUCH / MOUCH.NARES DOILY TOUCHIt's very possible we don't have the same dictionary! I have 8938 words. I confirmed that NARES, DOILY, and TOUCH are in my dictionary. My analysis shows that SERAI's worst-case is 461 words and NARES would have 578.
I found my code a bit difficult to debug at the end because it's still halfway decent at playing wordle. So, I fully admit I might not be doing it right!
But one thing I also did was allow it to pick a word it knew wasn't possible but could eliminate a lot of possibilities quickly.
It's worth noting that there are two dictionaries used in this implementation: "possibleWords" (from which the solution can be drawn) and "impossibleWords" (other words that are valid guesses).
https://qntm.org/files/wordle/words.js
These are most likely the same words in the implementation at https://www.powerlanguage.co.uk/wordle/ based on
showing up in the minified js (which are the first 8 words in possibleWords in order).["cigar","rebut","sissy","humph","awake","blush","focal","evade",Good point! And it's clear to me that this isn't the dictionary I was using. I grabbed a random Scrabble dictionary online and filtered for length of five. I'll rework my code to take all this into account and we'll see what happens (it probably will happen later today.)
Okay! It's been reworked with all of this new information, so it knows what words are possible. And I also had it output what it would consider to be the worst-case scoring and it matches the adversarial's scoring! Here's what I get now:
R A I S E (0 green, 0 yellow, 168 words remain) B L U D Y (1 green, 0 yellow, 13 words remain) C O U N T (2 green, 1 yellow, 2 words remain) V O U C H (4 green, 0 yellow, 1 word remains) P O U C H (5 green, 0 yellow, 0 words remain)I'm guessing that we're both working from the 2019 Collins Scrabble Word list[0], since that's the list of words I used, my implementation also tries to minimize the maximum number of resulting possibilities, and also have SERAI as the first guess every time.
[0] https://boardgames.stackexchange.com/questions/38366/latest-...
A variation on this path that both uses more familiar words and sticks to 'hard mode' rules is
ARISE
MOLDY
COUNT
VOUCH
POUCH
For anyone else wondering what makes this adversarial, here's a tweet explanation from the author: https://twitter.com/qntm/status/1479989124908007426
"Full writeup coming another time but mainly it doesn't pick any single word, it maintains a list of possibilities and reduces the list as little as possible with each guess."
The first time I got to 4 green letters, iOS Safari crashed on me. Wasn’t sure if that was the adversarial part, but laughed hoping it was.
I made my own adversarial wordle just now, not realizing this one already existed: https://swag.github.io/evil-wordle
they are both cool but right now they both have the problem that they don’t recreate the wordle keyboard, which is a big part of what makes the game enjoyable to play.
Self-promoting my own take on this idea (https://skalon.com/2022/01/08), which basically implements it within the familiar Wordle interface.
Was quite surprised to see two other takes on this idea when I was getting ready to post this! IIRC there are a few different undergrad CS programs that have you implement something like this for hangman.
Looks like qntm just updated the UI to include a Wordle-style keyboard (and also renamed it from "Adversarial Wordle" to "Absurdle") in the last few minutes.
I posted this on Twitter last night, but here's my (purported) proof that 4 guesses is optimal: https://gist.github.com/zwegner/508cc183ab94dd27686a40384783...
...and a bit more explanation in the Twitter thread: https://mobile.twitter.com/zwegner/status/148011092775217561...
Ah, apologizes, I missed your post. This analysis is awesome! I did a single look ahead, so it falls into the -OUCH zone and I have to burn some guesses. Doing the full search across all guesses is key. Well done!
We used to play a 2-player version of wordle as kids decades ago, on paper. You could do it yourself with plain paper, but it was also sold as a game with pre-printed paper and other supplies.
https://en.wikipedia.org/wiki/Jotto
Apparently it was invented in 1955.
If wonder if anyone still has any kind of patent or other IP that would be relevant...
This one is even closer given it has the concept of right letter, wrong place: https://en.m.wikipedia.org/wiki/Lingo_(American_game_show)
Somehow, I always get a large tropical seabird...
S T E R N (0 green, 0 yellow)
P L A I D (0 green, 0 yellow)
M U C K Y (1 green, 0 yellow)
G O R G E (1 green, 0 yellow)
W O O F Y (3 green, 0 yellow)
B O O Z Y (4 green, 0 yellow)
B O O B Y (5 green, 0 yellow)
You guessed successfully in 7 guesses!
S T E R N (0 green, 0 yellow)
P L A I D (0 green, 0 yellow)
B O U G H (2 green, 0 yellow)
W O O Z Y (3 green, 0 yellow)
B O O K Y (4 green, 0 yellow)
B O O B Y (5 green, 0 yellow)
You guessed successfully in 6 guesses!Hmmmm....for my first go, I got
Looking at the similarities, I'm wondering if the adversarial nature will generally lead to higher-than-naively-expected frequencies of:T R I A D (0 green, 0 yellow) H O N E S (0 green, 0 yellow) C L U M P (0 green, 2 yellow) B U L K Y (3 green, 0 yellow) F U L L Y (4 green, 0 yellow) G U L L Y (5 green, 0 yellow)Words with 'y', as people will tend to 'eliminate' the common vowels early, leaving 'y' as a 'substitute vowel' to fill in.
Words with repeated and doubled letters, as a round progresses and the pool ov available letters shrinks.
I wonder what other patterns might emerge from the ruleset?
I agree. My word was "HIPPY." I don't know how you would exploit it though.
After 14 failed quesses and only two letters revealed, I read your comment and guessed BOOBY, which left only one letter missing -- the correct answer was BOOZY.
Had you tried BOOZY, then BOOBY would have been the correct answer. It's dynamically filtering the list of available words and trying to prolong the game as long as legally possible.
My simple 12 line solver maintains a list of rejected letters, letters that must be contained and constraints on form (where letter must be and where letters cannot be). There was an additional step where words are weighted by spelling distance before sampling but this usually results in minute and more often no adjustments. This was meant for regular worldle. Works in 5 - 8 (often 6) guesses for adversarial wordle. Example runs:
F I L L S (0 green, 0 yellow)
W H E R E (0 green, 0 yellow)
D O U B T (0 green, 0 yellow)
M A N N A (3 green, 0 yellow)
C A N N Y (4 green, 0 yellow)
N A N N Y (5 green, 0 yellow)
A L L O Y (0 green, 0 yellow)
F E T C H (0 green, 1 yellow)
I N D E X (0 green, 2 yellow)
P R I Z E (3 green, 0 yellow)
B R I B E (3 green, 0 yellow)
G R I M E (5 green, 0 yellow)My solver at wordlesolver.com plays the same 5-move game each time: ARISE, BLUDY, COMET, CHUNK, CHUCK.
It looks like optimal play is 4 moves: https://twitter.com/zwegner/status/1480037275803308034
Your solver is awesome!
I'm really curious what the algorithm is find the 4 move play. Mine only optimizes for a single look-ahead.
With a greedy solver (minimize word pool for the next step), I got ARISE (168) -> BLUDY (13) -> COMET (2) -> NAVAL (1) -> CHUNK.
I think five steps is as good as it gets, as 5*5 is about the size of the alphabet.
Edit: I stand corrected. YEARN (216) -> FLOUT (12) -> CHAMP (1) -> HUMPH.
This is a 4 step solution: https://twitter.com/zwegner/status/1480037275803308034
Just whipped up a (naive) solve in rust: https://gist.github.com/ysimonson/01a1dee41b1b5990c30568fd25...
It usually solves this in under 6 guesses. The guessing could be improved; at the moment it's random, but it could select for words with non-repeating letters to narrow down the search space faster.
Still love seeing Sam's stuff show up in my world! (Check iut Hatetris for another variant of the theme)
An excellent chance to use my Wordle solver based on optimizing information gain (ie guessing to minimize the number of words remaining in a worst case scenario)
Since this is essentially Wordle golf, my score was 5.
RAVED SPLIT BUNCO BOOBY BOOZY
His dictionary is missing some of the SGB wordlist ...
I scraped qntm's wordlist and fed it to my tool, I think it does the same thing as yours (minimize the worst case after a guess... the simple greedy algorithm).
The simple greedy algorithm choses NARES first, then DOILY, then TOUCH.
And then it is left with VOUCH, COUCH, POUCH, GOUCH, MOUCH. This solver algorithm is far from optimal. It is like a 1-ply chess solver.
qntm's novel "There Is No Antimemetics Division" is one of the best things I read last year. https://qntm.org/scp
Allow me to recommend all his writings on Everything2 which is where we first met nearly 20 years ago
https://everything2.com/node/superdoc/Everything+User+Search...
I was literally playing with the idea of 'Adversarial Worlde', as I also called it, yesterday! Except it was multiplayer with one player being randomly assigned either the role of the guesser or the role of the defender.
Then I learnt that the inventor of Wordle is named Josh Wardle, which could be a portmanteau of war and wordle.
Mastermind? :-)
I think similar to wordle, but the defender can change the word being guessed at will as long as they don't invalidate any previous response.
Yes, this is it. I came up with the idea while trying to figure out whether any challenge is solvable in four guesses.
What makes the strategy a bit different from Mastermind is that you have so many more letters than colours.
I struggled with this to start, because if you begin with words that have vowels AEIOU then the real word will have only Y's in it. Like SHYLY, which I just got. So start off with a word with a Y and you'll avoid that fate :)
I’ve taken six guesses four times and eight twice. It’s so very tempting to solve it, finding the quickest path, or at least a local maximum if brute-forcing the entire thing turns out to be too computationally prohibitive.
it would be fun to see if you can pick a word and then force that to be the green word by your guesses
Adversarial² Wordle
I would bet that it has already been soft-solved by kthejoker2 upthread who got it in 5 guesses. I can't conceive of 3 wrong words being enough to narrow it down to a single possibility.
Soft-solved in that he doesn't necessarily have a proof this is the optimal solution, nor an enumeration of all optimal solutions, nor the optimal play from any game state - so there's still plenty to be explored here
I wonder if the author can improve the adversarial methodology to prevent a solution in 5. Eg, being left with BLACK/FLACK/SLACK as options is worse than having TRACE/BRACE/TRACK/CRACK, because the former requires 3 guesses to solve and the latter can be done in two. (Maybe this example is impossible because of TRACT, but I'm certain this effect exists).
If you're left with BLACK/FLACK/SLACK, you guess BEEFS, which tells you which is the correct one. So two guesses, not three.
So I don’t really get this exactly.. I guessed twice and then it solves it for me??
It sounds like you hit the "Give Up" button by accident.
I accidently tapped the "Give Up" button, and it says I guessed correctly. Unless the correct move is not to play, there seems to be a bug.
Did you accidentally click "give up" the third time?
See also: https://news.ycombinator.com/item?id=29864418
Same idea, different implementation.
There's now a keyboard as in wordle, and a writeup by the author:
I tried zero guesses but entered “EEEEE”, hit “Give up” and it told me I got it right in one try and the word was “DECAL”!
Winner, winner, chicken dinner.
@zeebeecee In word.js, why do you have a list of `impossibleWords`? Many of them are valid English words, like FEARS.
Less common words which the adversary will never choose, but will accept from you. Also, the author is https://news.ycombinator.com/user?id=qntm.
I'm not the author, see their writeup here: https://qntm.org/wordle
I like it. My suboptimal play:
C R A N K (0 green, 0 yellow)
M Y T H S (0 green, 0 yellow)
P L U M B (0 green, 1 yellow)
L Y R E S (0 green, 2 yellow)
O I L E D (2 green, 2 yellow)
F I E L D (4 green, 0 yellow)
W I E L D (5 green, 0 yellow)
Loved it. After trying two three times in vain, I landed up at words.js and cheated. To each to its own I guess.
AROSE MINTY GUILD CLICK FLICK
No automation (apart from the first two words that I use in real Wordle)
Zero CSS?
He added keyboard support but seemed to have broke functionality, even after cache clearing.