Jotto: Math
Jan. 31st, 2002 03:48 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
mattlistenerDuring another bout of Jotto insomnia the other night I hit on the math one must use to calculate the best Jotto-word to guess. (I should be able to explain this to mortals -- I was a Philosophy major, not Math or CS.)
For each word that remains in the wordspace, consider the rest of the wordspace. Get the likelihood of each outcome (answers 0, 1, 2, 3, 4, 5) by scoring your current candidate against every other word.
Now, all you want to do is rule out as many other words as possible with your guess. If 1/3 of the remaining words have exactly 3 matches with this word, then a '3' outcome would rule out the other 2/3 of the set. Call 2/3 the value (ie worth) of outcome '3'.
To get the value of a potential guess, get the average value of each of its outcomes. However, you need the *weighted* average, since the outcomes are differently likely. So, multiply each value by its likelihood.
If the outcomes divide 1/6, 4/6, and 1/6 between '3', '4', and '5', the value of the word would be:
1/6 * 5/6 + 4/6 * 2/6 + 1/6 * 5/6 = 18/36 = 1/2
If for another word the outcomes divide evenly between '3', '4', and '5', the value of that word would be:
1/3 * 2/3 + 1/3 * 2/3 + 1/3 * 2/3 = 6/9 = 2/3 == much better!
The bad news: this is what Comp Sci students call an n-squared problem. Here, n is the size of the wordspace, and it's n-squared because each word has to be checked against every other word to calculate its set of possible outcomes. For 1,000 words this will require 1,000,000 calculations. n-squared problems are the worst to write algorithms for, because they exhaust computing resources at much lower n's.
The good news: my desktop unix box at work might be able to gobble this up and still be hungry for breakfast. Stay tuned.
For each word that remains in the wordspace, consider the rest of the wordspace. Get the likelihood of each outcome (answers 0, 1, 2, 3, 4, 5) by scoring your current candidate against every other word.
Now, all you want to do is rule out as many other words as possible with your guess. If 1/3 of the remaining words have exactly 3 matches with this word, then a '3' outcome would rule out the other 2/3 of the set. Call 2/3 the value (ie worth) of outcome '3'.
To get the value of a potential guess, get the average value of each of its outcomes. However, you need the *weighted* average, since the outcomes are differently likely. So, multiply each value by its likelihood.
If the outcomes divide 1/6, 4/6, and 1/6 between '3', '4', and '5', the value of the word would be:
1/6 * 5/6 + 4/6 * 2/6 + 1/6 * 5/6 = 18/36 = 1/2
If for another word the outcomes divide evenly between '3', '4', and '5', the value of that word would be:
1/3 * 2/3 + 1/3 * 2/3 + 1/3 * 2/3 = 6/9 = 2/3 == much better!
The bad news: this is what Comp Sci students call an n-squared problem. Here, n is the size of the wordspace, and it's n-squared because each word has to be checked against every other word to calculate its set of possible outcomes. For 1,000 words this will require 1,000,000 calculations. n-squared problems are the worst to write algorithms for, because they exhaust computing resources at much lower n's.
The good news: my desktop unix box at work might be able to gobble this up and still be hungry for breakfast. Stay tuned.
