Attempting to beat Dr. Chris Plaue PhD's AI for hangman
The methods available in HangmanAI include
- default constructor whose responsibilities are to open up dictionary.data (which must be in the same directory as your hangman program)
- char makeGuess (String, String) where the first parameter is the word with blanks (lower case letters, blanks are -). The second parameter is a string of guessed words.
##Tasks
- Build AI
- Build Testing program
- Build Validation program
- Finish/Enhance AI (priority map for characters)
- Speed up Runtime
- Use JAVA 8's MapReduce .parallelStream().filter(predicate)!
##Validation Procedure
accuracy = number of guesses / number of actual guesses
MINE: 0.7792318457931986
PLAUE: 0.47667409819988715
I have achieved a 30.3% increase in accuracy over Dr. Chris Plaue PhD's Algorithm.
The Dictionary contains 172820 elements.
Also runtime, not theoretical runtime, is a lot lower.
##AI Step by Step Word: interaction
Constructor:
- Load Dictionary into a Map where the key is Integer, and the value is a ArrayList of Strings into dictionaryMap
- The key is the length of the word, and the value is the words which are that length
dictionaryMap:
2=[aa, ab]
3=[aah, aal, aas, aba]
4=[aahs, aals]
5=[aahed, aalii, aargh, abaca]
6=[aahing, aaliis, aarrgh, abacas]
7=[aarrghh]
8=[aardvark, aardwolf, aasvogel]
9=[aardvarks, aasvogels]
10=[aardwolves]
Word: -----------
First run of the method makeGuess(String word, String guessed)
loop will
- deep-copy each word that is 11 characters long int wordList
- count the occurances of each characters in all the words that are 11 characters long into characterMap
wordList: [abandonment, abbreviated, abbreviates, abbreviator, abdications, abdominally, abecedarian, aberrancies, aberrations, abhorrences, abhorrently, ...
characterMap: {f=1866, g=4652, d=5221, e=19341, b=2758, c=7518, a=12541, n=12736, o=11360, l=8730, m=4907, j=178, k=977, h=3846, i=16729, w=867, ...
Word: -----------
Make the dictionaryMap in step 0 eligible for JAVA garbage collection
Word: -----------
Convert characterMap from key->value to value->key into SortedMap frequencyMap
frequencyMap: {178=[j], 275=[q], 464=[x], 801=[z], 867=[w], 977=[k], 1707=[v], 1866=[f], 2644=[y], 2758=[b], 3846=[h], 4652=[g], 4907=[m], 5093=[p], ...
Word: -----------
Grab the last key's value off of frequencyMap [e]
Guess: e
Word: ---e-------
Second run of makeGuess("---e-------", "e")
Convert the ---e-------
into ...e.......
for the Pattern.matches(regex, str)
Run the Pattern matcher over each word in wordList
The regex will only match words which are the same length, and contain all the characters in the same place, and all '.' are ignored, words which don't match are removed.
Also see if the word in wordList contains any of the missed characters, (guessed - active) and remove word.
Convert characterMap into frequencyMap
wordList: [abnegations, abreactions, absenteeism, accelerando, accelerants, accelerated, accelerates, accelerator, accentually, accentuated, accentuates, acceptances, acceptation, acceptingly, ...
characterMap: {f=294, g=508, d=737, b=273, c=756, a=1257, n=1664, o=895, l=978, m=481, j=19, k=122, h=396, i=1794, w=141, v=263, u=540, t=1561, s=1738, ...
frequencyMap: {11=[q], 19=[j], 64=[z], 66=[x], 122=[k], 141=[w], 263=[v], 273=[b], 294=[f], 333=[y], 396=[h], 481=[m], 508=[g], 540=[u], 586=[p], 737=[d], 756=[c], 895=[o], ...
Last key's value off of frequencyMap [r]
If there are two characters with same frequency, it takes the first. (this area can be refined by creating a character priority list and tweaking)
Guess: r
Word: ---er------
Third run of makeGuess("---er------", "er")
wordList: [adverbially, adversarial, adversaries, adversative, adverseness, adversities, advertences, advertently, advertisers, advertising, advertizing, advertorial, ...
characterMap: {f=90, g=141, d=276, b=84, c=215, a=438, n=598, o=288, l=293, m=138, j=3, k=28, h=146, i=669, w=53, v=99, u=272, t=590, s=609, q=1, p=288, z=32, y=120, x=26}
frequencyMap: {1=[q], 3=[j], 26=[x], 28=[k], 32=[z], 53=[w], 84=[b], 90=[f], 99=[v], 120=[y], 138=[m], 141=[g], 146=[h], 215=[c], 272=[u], 276=[d], 288=[o, p], 293=[l], 438=[a], ...
Last key's value off of frequencyMap [i]
Guess: i
Word: i--er---i--
Fourth run of makeGuess("i--er---i--", "eri")
wordList: [imperialism, imperialist, imperilling, inferential, inferiority, infertility, innerspring, innervating, innervation, interacting, interaction, interactive, ...
characterMap: {f=12, g=17, d=3, c=11, a=22, n=73, o=10, l=19, m=7, h=3, v=4, u=2, t=46, s=14, p=8, z=2, y=6, x=1}
frequencyMap: {1=[x], 2=[u, z], 3=[d, h], 4=[v], 6=[y], 7=[m], 8=[p], 10=[o], 11=[c], 12=[f], 14=[s], 17=[g], 19=[l], 22=[a], 46=[t], 73=[n]}
Last key's value off of frequencyMap [n]
Guess: n
Word: in-er---i-n
Fifth run of makeGuess("in-er---i-n", "erin")
wordList: [innervation, interaction, interfusion]
characterMap: {f=1, v=1, u=1, t=4, s=1, c=1, a=2, o=3}
frequencyMap: {1=[f, v, u, s, c], 2=[a], 3=[o], 4=[t]}
Last key's value off of frequencyMap [t]
Guess: t
Word: inter--ti-n
Sixth run of makeGuess("inter--ti-n", "erint")
wordList: [interaction]
characterMap: {c=1, a=1, o=1}
frequencyMap: {1=[c, a, o]}
Last key's value off of frequencyMap [c, a, o]
Guess: c
Word: inter-cti-n
Sixth run of makeGuess("inter-cti-n", "erintc")
wordList: [interaction]
characterMap: {a=1, o=1}
frequencyMap: {1=[a, o]}
Last key's value off of frequencyMap [a, o]
Guess: a
Word: interacti-n
Sixth run of makeGuess("interacti-n", "erintca")
wordList: [interaction]
characterMap: {o=1}
frequencyMap: {1=[o]}
Last key's value off of frequencyMap [o]
Guess: o
Word: interaction
Accuracy: 1.0