@bad-indentation

Yet another Rust command-line project! I’ve actually wanted to make a Reversi solver for a while now, and after doing a bit of research into Monte Carlo Tree Searches (MCTS), I think this project will be a valuable learning experience. I was originally going to do Minimax with alpha-beta pruning, which would have been nicely deterministic, but I also foresaw that being a pain. I’ve played around with Minimax for simpler games, and while it’s conceptually straightforward, I felt like taking a break from the headache of pruning and optimizing a full search through an enormous game tree. Furthermore, recursion with mutable parameters is especially brutal with Rust’s borrow checker, and I suppose there isn’t much learning experience to be gained from applying a familiar algorithm to another game. Or, perhaps, I am simply lazy and looking for novelty. At any rate, MCTS is the route we’re going. Besides adding a fancy new algorithm to my toolbelt, my goal for this project is make my Rust code a little more idiomatic and tidy. I’ve lumped all the logic into lib.rs in my previous Rust projects, but now I’ve finally taken two minutes to look up how to properly extract modules into different files. :) I’m also going to define some custom traits and make heavier use of generics; my hope is that my code is modular enough that one could copy the MCTS part of the crate and apply it to a different game without making any modifications. As usual, there isn’t much of an exciting development in this first log. So far I’ve created a BoardPiece enum and a Board struct. Since Board just contains a couple u64s (for bitmasks) and a usize tuple for keeping track of the board’s dimensions, I’ve decided to derive the Copy trait to save myself further borrow checker woe. So far, tests are passing, and I can index the bitmasks just like a normal 2D array using the get_piece method I wrote. Since there isn’t much output to see, I thought I’d show some of the example code in the awesome auto-generated docs Cargo generated for me:

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.

Finished the first iteration of the Rust backend, passed some tests, and linked it to the UI. It definitely works, for the signature GoL patterns (blocks, loaves, gliders, etc.) are emerging, but the system is still quite unable to handle the 1000x1000 grid I had hoped for. The bottleneck may simply be the PyO3 interface, or (very likely) there may be much room for optimization in my Rust code.

Wrote most of the Python frontend using Pygame (graphics are neither my forte nor my passion, and I wanted to focus on the internal logic). Also began working on a Rust struct accessible via PyO3 which encapsulates and mutates the GoL grid. This is really my first go at PyO3 and Maturin (or any cross-language project, for that matter), but it seems Python and Rust have been communicating nicely so far.

Finally published to crates.io.

Serious refactor - DFS + pruning was actually not an efficient solution to the problem; simple character counting using HashMaps much faster.

Finished first iteration of solver; working on optimizations.

Successfully implemented depth-first search to generate all possible anagrams of the scrambled input. Used a pre-computed HashSet of valid prefixes to quickly prune any branches that wouldn’t lead to valid English words.

Implemented CLI interface using Clap. Added –verbose flag for logging and –include-partial for words that do not use all available letters.

Initial optimizations include removing words that could never be made using the available letters- that is, words that are too long or contain invalid letters.

Further optimizations include using concurrency when reading the file and using smart pointers to avoid excessive cloning. Also considering the possibility of iterating over candidate WORDS and determining whether they are a valid solutions instead of using combinatorics.