HangStop

After fiddling around with various parameters in the entropy function and benchmarking the results, I decided that any benefits I might find were too small to warrant very much of my time looking for them. Besides, many of them produced negative values for the entropy, which, as I have previously alluded, is acceptable for a heuristic function, but not for the entropy calculation my program promises. I was more open to this discrepancy before, but the improvements I was seeing (if they actually were improvements) were not worth the change. Thus, I decided to write up a README, publish to crates.io, and call it a day. I may come back with more tweaks in the future, but for now, I think the performance is acceptable. (Nevertheless, you can find the data from all of my benchmarking trials in the repository.)

I removed the regular expressions from the Rust program, and it did seem to speed things up a little bit, but the unoptimized builds still took a few seconds to run. I couldn’t really think of any other optimizations that weren’t either a pain to implement or unlikely to work, so I ultimately decided just to run my script with the release build and wait. Thankfully, I seriously overestimated how long the benchmarking would take; it got through 1900-odd Hangman games in under 10 minutes. I wrote up a second quick script (not included in the repository) to test my old Hangman solver, but as this was in Python, calling code I wrote months ago, with only half-hearted attempts at optimization, that bit of benchmarking took hours to run. It really shouldn’t have, but at the time I decided I’d rather simply be patient than to actually figure out what was wrong. I had the results the next morning, so I put everything into some CSV files, whipped up a quick bit of Matplotlib code, and looked at how my new Rust program compared with my old Python program. To my satisfaction, the Rust program generally used less guesses overall than the Python program did. However, the programs were rather similar in the number of incorrect guesses they made, with the Python version beating the Rust one by a slim margin. This, arguably, is the more important metric for Hangman; there isn’t really a limit on how many guesses you make in Hangman, only how many wrong guesses you make. The results were nevertheless unsurprising. My Rust program, after all, attempts to optimize the information gained. The Python program attempts to play safely, though often at the cost of using more guesses overall. The Rust program is a little more willing to guess a rarer letter because it knows that absence of that letter still gives you information. This may be something we want to discourage. My plan is to open up a new branch in my repository and see if I can tweak the entropy calculations to make the algorithm a little more wary of incorrect guesses. I suppose that this would make the “entropy” more of a custom heuristic than true Shannon entropy, which reduces the program’s transparency, but I think the potential strategic gains are worth the tradeoff.

As I was working on my benchmarking script, I found that the program is currently much too slow to play up to 2000 full games of Hangman in a reasonable amount of time, even when compiled with full optimizations. Perhaps compiling regex with the regex crate can get expensive, or perhaps there is some suboptimal use of memory within my code I overlooked. The word list is just under 200,000 words long, and while processing that much data doesn’t take all that long, minor inefficiencies are probably magnified a good bit. I may try swapping out the regular expressions for a custom, domain-specific pattern matching algorithm; however, the performance I’ve observed does seem to depend heavily on the calculations that occur after pruning. The program, after all, does get faster when the state is more restrictive. hangstop "?????????" takes about 3.5 seconds with the unoptimized build, since there are tens of thousands of nine-letter words in the dictionary; hangstop "???ee????" -i "nl" takes less than half the time (albeit still far more time than I would prefer). One particular challenge that comes with optimization is the fact that there is little benefit to precomputing anything. The program, as I have said in previous devlogs, is stateless, and it only makes one guess at a time, so it doesn’t spend any more time using data that it does generating it. Besides ditching regex, I may also experiment with lazy evaluation, or find something else to micro-optimize. :)

Put the finishing touches on the CLI and fixed some little bugs. To the best of my knowledge, I have correctly implemented a search for the letter with the highest entropy given a certain game state. Whether this method is effective is quite another matter. It does seem to be performing decently well for many words - it got “crustacean” after guessing e, s, r, and a. (The program will output the solution immediately as soon as it has eliminated all other candidate words.) “Rusty,” meanwhile, took 13 guesses, 11 of which were wrong. This was no better than my original, naïve program. In some cases - though perhaps they are unlucky cases - the old Python program did significantly better. HangStop took 7 guesses (4 of which were wrong) to uncover “punctuation,” while the Python program only used 4, 1 of which was wrong. This problem deserves a bit of automated testing to ensure I am not subconsciously cherry-picking examples. :) My next step is going to be to write a script to hammer both the Rust CLI tool and the Python backend of my old project with thousands of words and determine whether “count the letters” is really beating the fancy information theory I championed. (As exemplified by the egregious use of DFS in my previous Rust project, one may easily see that I have a bit of a tendency to over-engineer things.)

Wrote the bulk of the information-theory-heavy code. I started by writing a function that takes a letter and a potential solution and returns a bitmask representing which spaces would be uncovered. For instance, get_bitmask('a', "banana") would give you 010101, since there are As at the 1st, 3rd, and 5th indices. Then I wrote a second function which, given a letter and a word list, returns the Shannon entropy, or the expected bits of information, of that letter. This involves counting the occurrences of every bitmask in the word list and taking a weighted sum of the number of bits gained. For instance, if my letter was e and my word list was [hello, lends, flees, stick], the bits of information you could expect to obtain from guessing e is p(01000) * log2(1 / p(01000)) + p(00110) * log2(1 / p(00110)) + p(00000) * log2( 1 / p(00000)), which equals 1.5. Obtaining the bitmask for a given letter and a given word of length l is O(l). Thus, calculating the entropy of a given letter for a certain word list of length n is O(n * l). Calculating the entropy for every one of r remaining letters is O(n * l * r). Since no English words are longer than a few dozen letters and there cannot be more than 26 remaining letters, determining the best letter to guess should be roughly linear with respect to the number of possible words. A few hundred thousand words through a linear-time algorithm should be nothing for Rust, but we will see whether my dubious asymptotic notation skills are supported by the final result. :) Unfortunately, there is not much to see in the screenshots I’ve been attaching; I use test-driven development and make sure my logic is reasonably sound before I even touch the UI, thus the rather boring images of passed unit tests.

Began a new little side project. About a year ago, I wrote a Python app to suggest Hangman guesses. It was simple but surprisingly effective, especially for medium-to-long words. Its obvious weakness was shorter words, especially those under six letters long. I am going to attempt to improve the algorithm using some information theory and Rust magic. I also decided to make this a command line tool, as opposed to the original GUI, since Hangman works elegantly when thought of as a stateless game. Right now, I just wrote up some boilerplate code and passed all the tests.