Re: Challenge: Design A Better Hangman Algorithm

As an aside, or perhaps Part II of the challenge, is to consider what happens when the "opponent" chooses words based on the degree of guessing difficulty (whether it's known that a certain guessing algorithm is employed, or just assuming generic hueristics about guessing).

For instance, when I've played casually with someone the first time, I usually pick "rhythm", since it has no conventional vowels. (This only works once though). After that, I would try a word from a set of words of the same length with many letters/positions in common, but not just a simple substitution. (This is harder as word length goes up.)

Can the algorithm have a special mode to counter biased word choice?

-QM
--
Quantum Mechanics: The dreams stuff is made of

Comment on Re: Challenge: Design A Better Hangman Algorithm

Replies are listed 'Best First'.
Re^2: Challenge: Design A Better Hangman Algorithm by Limbic~Region (Chancellor) on Jul 15, 2009 at 22:28 UTC
QM, For the record, my algorithm(s) wins on the word 'rhythm' but with only 1 wrong guess to spare (6 used and 7 is default). I did indicate that you could pre-process a dictionary to optimize your algorithm. In my case, I know that with my 'simple' solution, I lose on 2254 of the 60K words tested. These 2254 words then become what I believe you are considering biased and are the very ones I am hoping people come up with a solution for. If I use an alternate algorithm against just these words, I can win 787 but still lose 1467. As JavaFan pointed out elsewhere in that thread, for certain words - guessing is all you can do. I have absolutely no problem if you can figure out this word is biased early on and use an alternate algorithm for it. My issue is that the algorithm that works better on these biased words doesn't work great on normal words. In short, the answer is yes if you can figure out how. Cheers - L~R	[reply]
Re^2: Challenge: Design A Better Hangman Algorithm by JavaFan (Canon) on Jul 16, 2009 at 16:46 UTC
I've implemented two algorithms. 1) look which letter(s) appear in the most words which are still possible, pick the one which appears in most words. Break ties randomly. 2) look at all the letters that appear in the words that are still possible, pick one weighted on frequency (so, if there are 15 words left, and 'l' appears in 10, 'm' in 5, than the chance of picking 'l' is twice the chance of picking 'm'). Using this with a dictionary of 355k words, algorithm 1) always find 'rhythm' with no guesses to spare (7 failures). algorithm 2) sometimes fails to find 'rhythm' in 7 failures or less, but the average number of failures is less (6.60). This surprised me.	[reply]