Following up on my previous post about optimal hangman strategy, I’ve run some more experiments, fixed up and tested my script, with some interesting results.
First of all, I tested the script in a game of hangman against every single word in a 70k word dictionary. I played with 10 lives before losing, which is probably on the conservative side, 12 seems like a common figure. The script lost on 469 words, of which 99 were 3 letters long. There were 20 words 7 letters long, all of which ended in ‘ing’. There were no words of 8 letters or longer.
I’ve made a complete list of losing words available, as running the test takes several hours to complete.
In terms of getting around this – unfortunately it is impossible to do better. The only improvement that could be made is randomizing between choices of letter that have equal probability, so that the words that are unreachable cannot be determined. This results in a larger number of words that potentially lose, but a lower probability of losing on those words (and no words will definitely lose).
Obviously you’ll get different output from different dictionaries, larger dictionaries will result in more failures.
These are fairly promising results though, unless you were guessing against an opponent who also had access to optimal-strategy data and knew which words were most likely to be difficult to guess, you’re going to be able to win most of the time with this approach.
Tom:
I suggest, then, that we set up a competition, in the style of rpscontest.com
Competition provides a dictionary and the ruleset (I suggest 9 lives!).
Each player contributes an algorithm that
1. Chooses a list of words for opponent(s) to guess
2. Guesses the words of opponent(s)
| April 3, 2012 @ 3:45 pm
Interesting, although there is basically only one approach towards how to play hangman ‘correctly’. The only differentiator in such a competition would be performance on words which cannot be determined without losing 9 lives. In those cases you wouldn’t be able to do better than random guesses!
| April 3, 2012 @ 4:18 pm
Sure – so there are potentially several levels of strategy
What words should you add to the list that are ‘unguessable’
How can you set up a random (or otherwise) program to best cover the ‘unguessable’ words your opponent might pick.
| April 5, 2012 @ 1:59 am
I’ve updated the script. When there is more than one letter with the same optimal frequency, it now chooses randomly. This partitions the wordlist into those on which the script will always win, and those on which it will not always win. There are no words on which it will always lose.
| April 5, 2012 @ 7:17 pm
* actually http://webdocs.cs.ualberta.ca/~darse/rsbpc.html is the site I meant
| April 3, 2012 @ 3:46 pm
In fact, there’s only one way to play Rock Paper Scissors optimally – deliberately make random plays. If someone is playing with any other known strategy, you can exploit their strategy (and then they can exploit yours).
In practice, the random strategy ends up half way down the results table.
| April 5, 2012 @ 2:01 am