search

alex1770 / wordle

Finding optimal play in the game of wordle
MIT License
54 stars 16 forks source link

Appears to not produce optimal worst case output in all cases #10

Open JustAnotherArchivist opened 1 month ago

JustAnotherArchivist commented 1 month ago

I was playing with a different word list today and discovered that this does not always find the optimal solution. Using the word lists guesslist.txt and hiddenlist.txt, in the chain tares.BBBBB.colin.BBBBB.pygmy.YBBYG, there are three remaining options: bumpy, dumpy, or jumpy. This is the decision tree produced by wordle -a guesslist -h hiddenlist -w tares.BBBBB.colin.BBBBB.pygmy.YBBYG -p tree:

jumpy BGGGG4 bumpy BGGGG5 dumpy GGGGG6
                   GGGGG5
      GGGGG4

So the program claims that the optimal solution takes 2 more guesses on average and 3 more in the worst case. However, this is not correct. The guess list includes jibed. While this cannot be the solution itself, it guarantees a solution in the next guess, i.e. the worst case is only 2 more guesses. Indeed, providing this guess with -w tares.BBBBB.colin.BBBBB.pygmy.YBBYG.jibed produces the correct decision tree:

jibed BBBBY4 dumpy GGGGG5
      BBYBB4 bumpy GGGGG5
      GBBBB4 jumpy GGGGG5

While you could argue that both trees are equally good due to the same number of average guesses (which I wouldn't agree with), this also causes the program to claim that it is impossible to solve the game in five guesses (-g5), which is obviously incorrect.

alex1770 commented 1 month ago

The definition of optimal it uses is that it minimises the average number of guesses required, assuming the hidden word is chosen randomly from the hidden list. Alternatively/equivalently, it adds up the number of guesses required for each of the possible hidden words, and finds the strategy that minimises that.

So in your example, by design it regards a guess of jumpy (possible remaining number of guesses 1+2+3) the same as jibed (2+2+2).

If you use -g5 then it will force it to use <=5 guesses if that is possible and that is the behaviour I find. I couldn't reproduce your "impossible" answer. Are you sure there is no mistype?

wordle -a guesslist -h hiddenlist -w tares.BBBBB.colin.BBBBB.pygmy.YBBYG -p tree -g5

abide BBBBB4 jumpy GGGGG5
      BBBYB4 dumpy GGGGG5
      BYBBB4 bumpy GGGGG5