[HN Gopher] Adversarial Wordle
___________________________________________________________________
Adversarial Wordle
Author : zeebeecee
Score : 109 points
Date : 2022-01-09 12:14 UTC (10 hours ago)
(HTM) web link (qntm.org)
(TXT) w3m dump (qntm.org)
| FabHK wrote:
| 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!
| Karellen wrote:
| Hmmmm....for my first go, I got 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?
| baking wrote:
| I agree. My word was "HIPPY." I don't know how you would
| exploit it though.
| bidirectional wrote:
| 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.
| macintux wrote:
| 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.
| GrantZvolsky wrote:
| 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.
| Scaevolus wrote:
| Mastermind? :-)
| FabHK wrote:
| What makes the strategy a bit different from Mastermind is
| that you have so many more letters than colours.
| jjnoakes wrote:
| 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.
| GrantZvolsky wrote:
| Yes, this is it. I came up with the idea while trying to
| figure out whether any challenge is solvable in four
| guesses.
| ColinWright wrote:
| See also: https://news.ycombinator.com/item?id=29864418
|
| Same idea, different implementation.
| p0cc wrote:
| @zeebeecee In word.js, why do you have a list of
| `impossibleWords`? Many of them are valid English words, like
| FEARS.
| CyberShadow wrote:
| 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.
| rishabhd wrote:
| Loved it. After trying two three times in vain, I landed up at
| words.js and cheated. To each to its own I guess.
| green-eclipse wrote:
| 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 :)
| grouphugs wrote:
| rkudeshi wrote:
| 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."
| fredleblanc wrote:
| 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.
| Julesman wrote:
| Zero CSS?
| Jerrrry wrote:
| He added keyboard support but seemed to have broke
| functionality, even after cache clearing.
| [deleted]
| aqme28 wrote:
| 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)
| LVDOVICVS wrote:
| 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.
| raviparikh wrote:
| I made my own adversarial wordle just now, not realizing this one
| already existed: https://swag.github.io/evil-wordle
| MattRix wrote:
| 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.
| whaatt wrote:
| 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.
| re wrote:
| 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.
| kthejoker2 wrote:
| 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 ...
| NelsonMinar wrote:
| qntm's novel "There Is No Antimemetics Division" is one of the
| best things I read last year. https://qntm.org/scp
| kthejoker2 wrote:
| 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.
| ..
| klodolph wrote:
| 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.
| christiangenco wrote:
| 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
| salomon812 wrote:
| 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.
| chrismorgan wrote:
| 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.
| dmurray wrote:
| 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).
| Sesse__ wrote:
| If you're left with BLACK/FLACK/SLACK, you guess BEEFS, which
| tells you which is the correct one. So two guesses, not
| three.
| zem wrote:
| it would be fun to see if you can pick a word and then force
| that to be the green word by your guesses
| Karellen wrote:
| Adversarial2 Wordle
| jrochkind1 wrote:
| 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...
| ec109685 wrote:
| 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)
| zwegner wrote:
| 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...
| salomon812 wrote:
| 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!
| [deleted]
| Vetch wrote:
| 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)
| m0th87 wrote:
| 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.
| salomon812 wrote:
| 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)
| bmitc wrote:
| 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?
| salomon812 wrote:
| 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.
| jameshart wrote:
| A variation on this path that both uses more familiar words and
| sticks to 'hard mode' rules is
|
| ARISE
|
| MOLDY
|
| COUNT
|
| VOUCH
|
| POUCH
| klodolph wrote:
| Are you using the same dictionary? I used the same technique,
| and got: NARES DOILY TOUCH
|
| And then VOUCH / COUCH / POUCH / GOUCH / MOUCH.
| salomon812 wrote:
| 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.
| [deleted]
| vitus wrote:
| 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
| ["cigar","rebut","sissy","humph","awake","blush","focal","e
| vade",
|
| showing up in the minified js (which are the first 8 words
| in possibleWords in order).
| salomon812 wrote:
| 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.)
| salomon812 wrote:
| 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)
| MereInterest wrote:
| 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-...
| [deleted]
| scubbo wrote:
| 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.
|
| [0] https://blog.scubbo.org/posts/cheating-at-word-games/
| salomon812 wrote:
| 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)
| salomon812 wrote:
| 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)
| CyberShadow wrote:
| 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.
| mayneack wrote:
| This is a 4 step solution:
| https://twitter.com/zwegner/status/1480037275803308034
| indigodaddy wrote:
| So I don't really get this exactly.. I guessed twice and then it
| solves it for me??
| PebblesRox wrote:
| Did you accidentally click "give up" the third time?
| brk wrote:
| It sounds like you hit the "Give Up" button by accident.
| MerelyMortal wrote:
| 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.
___________________________________________________________________
(page generated 2022-01-09 23:01 UTC)