Designing a webpage and improving performance in Go
The goal in Mastermind is to crack a hidden code, which is a sequence of colors. The player fills a row with her guess of the code and receives feedback in the form of black and white “pegs” to the right of the row. A black peg means right color, right position for a column in the guess, and a white peg means right color, wrong position. No peg is given for a wrong color. Using the feedback from all her previous moves, the player tries to deduce the solution. She either wins and receives four black pegs by arriving at the solution, or loses by running out of rows on the board.
Writing the frontend in Go required rendering nested
*html.Node structs rather than explicitly spelling out tags in HTML. Arranging the elements just so and setting the finicky style attributes was cumbersome, but it became less painful with practice. Because the game was displayed in the browser, I could easily check if the program was working by checking colors and counts.
In 1976, computer scientist Donald Knuth published a paper with an algorithm that finds the solution in five or less moves. The algorithm works by playing the code that gives the most information, where information is defined as how much the solution space shrinks.
At each turn, it sweeps through every feedback it could receive for every code it could play, and counts the number of possible solutions remaining if that feedback were given for that code. The code that minimizes the maximum number of remaining possibilities over all feedback is the one played. Ties are broken by preferring codes that are themselves possible solutions, then by numerical order.
It’s interesting to note that the algorithm’s primary concern is to trim the set of codes that are possible solutions. That the code it plays could be the solution is a secondary concern, and it even plays codes not in the solution space in order to gain more information. This is a different strategy from what I and probably many others use, which is to limit guesses to the solution space.
Creating the trie was computationally intensive and CPU-bound. By my calculation, the time complexity is O(c⁶r^(3c+1)) where c is number of columns, and r is number of colors. My initial implementation on my 4-core MacBook Pro took 45 mins, so I applied the following optimizations:
- Memoization. I memoized the trie generator function by reading from the trie as it was being built, effectively using it as a cache.
- Tracking codes that were invalid solutions
- Shuffling the order in which trie branches were built to increase “cache” hits from the memoization step
- Rearranging for loops to more efficiently count possible solutions
The cumulative effect of these optimizations generated the trie in two seconds for a 1350x performance boost over the initial implementation. It was gratifying to see the program’s output blitz across the screen in a blur of green text, Matrix-style.
Along the way, I found several generally applicable ways to speed up Go1.9 code. As always, your mileage may vary.
- Use constants
constrather than variables
var. When I changed
numColsfrom constants to variables, compute time doubled. I quickly switched them back.
- Let the default/zero-value of objects be valid initial values. Rather than setting a boolean, like
up, to true before use, change it to
downso that its value, false, is already correct without being set.
- A good heuristic when spinning off goroutines that are CPU-bound is to limit them in number to the number of logical CPUs available.
Granted, all of these optimizations were overkill for the traditional version of Mastermind, which has four columns and six colors. However, they were essential for generating tries for variants of the game with more colors and columns. The heatmap below shows how many moves it takes to solve such variants. As complexity grew, I turned to 48- and 64-CPU machines, but even after pulling out the big guns, computation above certain numbers of colors and columns was just not feasible.
It’s surprising that the number of moves is not monotonic with the number of colors. For example, at five columns, the game with three colors can be solved in fewer moves than the game with two colors. It turns out Knuth’s algorithm is suboptimal, as it is a greedy algorithm that looks only one step ahead to reduce the solution space. Researchers have since come up with algorithms that find the solution in fewer moves on average.
Thanks to Mario Latendresse for discussion on the algorithm and web-games for color gifs.