Solving Mastermind with Go

Designing a webpage and improving performance in Go

I recently discovered the gopherjs package, a source-to-source compiler that converts Go into JavaScript. gopherjs opens another avenue to web development for those of us leery of JavaScript, the lingua franca of the web. Intrigued by the possibility of creating a webpage in a familiar language, I set out to program the board game Mastermind in pure Go. The result is pictured left and is playable online. If a logic puzzle sounds like too much work, just press the “Solve in 5 or less moves” button to let the computer play instead.

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.

Win

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.

I coded Knuth’s algorithm in Go and compiled it, but JavaScript was too slow to find the algorithm’s next move on the fly. My workaround was to precompute the sequence of moves for every solution and store them in a trie. As shown in the picture, the trie gives the algorithm’s next move based on feedback. It has a common root and 6⁴ = 1296 leaves (6 colors and 4 columns). Its max depth is five, verifying Knuth’s claim of solving the game by five moves. The trie is built in Go and compiled into JavaScript, which walks it at the click of the solve button.

Partial trie of codes played by Knuth algorithm

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:

• Concurrency
• 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.

Time taken to build the complete trie of moves made by the Knuth algorithm

Along the way, I found several generally applicable ways to speed up Go1.9 code. As always, your mileage may vary.

• Use constants const rather than variables var. When I changed numColors and numCols from 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 down so 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.

Number of moves needed to win variants of Mastermind with Knuth’s algorithm. * Traditional game.

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.