|
|
|
|
|
|
by Syzygies
1611 days ago
|
|
|
5.291 soare
5.294 roate
5.299 raise
5.311 raile
5.311 reast
5.321 slate
5.342 crate
5.342 salet
5.345 irate
5.346 trace
5.356 arise
5.360 orate
5.370 stare
5.382 carte
5.390 raine
5.400 caret
5.402 ariel
5.406 taler
5.406 carle
5.407 slane
Shown are the twenty best initial guesses using Claude Shannon's definition of information entropy. Each number is the expected number of yes/no questions needed to resolve the remaining uncertainty. Shannon is the "father of information theory", and this is the right measure.One might recognize SOARE as identified elsewhere by a different measure. I am relieved that I give up very little by moving down to the first word I recognize on this list. This takes about 20 minutes to code in Ruby, and four minutes to run. There's no point to using a more efficient language, or wasting part of an hour as I did searching for a clever way to score guess words. In the 1960's my dad used entropy to program Jotto on Kodak's computers. It wasn't feasible then to evaluate every possible clue word, but he determined that one did well enough with a random subset. |
|
|
I have a counter example for a simplified version the game with the following rule changes:
1. The player is only told which letters in the guess are correct (i.e. they are not told about letters that are present but in a different location).
2. If the player knows there is only one possible solution, the player wins immediately (without having to explicitly guess that word).
3. The set of words that the player is allowed to guess may be disjoint from the set of possible solutions.
Here is the list of possible solutions:
(There are 8 words. The 2nd, 3rd and 4th letters are the binary patterns of length 3, and the 1st letter is a carefully chosen "red herring".)Here is the dictionary of words the player is allowed go guess:
(Each guess effectively lets the player query a single letter of the solution.)The information gain for each possible initial guess is identical (all guesses result in a 4-4 split), so a strategy based on information gain would have to make an arbitrary choice.
If the initial guess is axxx (the "red herring"), the expected number of guesses is 3.25.
But a better strategy is to guess xaxx (then guess xxax and xxxa). The expected number of guesses is then 3.
(In this example information gain was tied, but I have a larger example where the information gain for the "red herring" is greater than the information gain for the optimal first guess.)