This 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.
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)
It'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).
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.
"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."
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.
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.
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!
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)
Looking at the similarities, I'm wondering if the adversarial nature will generally lead to higher-than-naively-expected frequencies of:
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?
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)
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.
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.
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.
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).
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: