Mastermind Solver

Shout out to another student on my university course. We had to implement this algorithm as a class exercise. Most people &quot;discovered&quot; the same kind of algorithm which solves it in 3-4 steps. However this other student came up with an implementation which seemed almost supernatural: It would get the right answer in a single step!<p>The random number generator on the old Sparcstations we were using used the time_t and PID as a seed, and the exercise test harness used a random number straight from rand(3) to generate the secret. The student&#x27;s implementation simply worked out the answer from the date and process PID and knowledge of how the linear congruential generator worked.

The Knuth approach said to be implemented in this post is described in:<p>&gt; The computer as Master Mind. <i>Journal of Recreational Mathematics</i> 9 (1976), pp. 1–6. Reprinted with an addendum as Chapter 25 of <i>Selected Papers on Fun and Games.</i><p><a href="https:&#x2F;&#x2F;www.cs.uni.edu&#x2F;~wallingf&#x2F;teaching&#x2F;cs3530&#x2F;resources&#x2F;knuth-mastermind.pdf" rel="nofollow noreferrer">https:&#x2F;&#x2F;www.cs.uni.edu&#x2F;~wallingf&#x2F;teaching&#x2F;cs3530&#x2F;resources&#x2F;k...</a> is the original paper, but the addendum in the 2011 book is 5 pages long, longer than the original article itself (not counting its figure&#x2F;table), and discusses various later results&#x2F;ideas. For example, the addendum mentions that while Knuth&#x27;s approach only minimizes the worst-case number of guesses (5, with 4.4753 on average), we can try to also minimize the expected number of guesses: I don&#x27;t want to quote at length, but see <a href="https:&#x2F;&#x2F;stackoverflow.com&#x2F;a&#x2F;54917672" rel="nofollow noreferrer">https:&#x2F;&#x2F;stackoverflow.com&#x2F;a&#x2F;54917672</a> and the discussion on the German Wikipedia <a href="https:&#x2F;&#x2F;de.wikipedia.org&#x2F;w&#x2F;index.php?title=Mastermind_(Spiel)&amp;oldid=231513977#Strategien" rel="nofollow noreferrer">https:&#x2F;&#x2F;de.wikipedia.org&#x2F;w&#x2F;index.php?title=Mastermind_(Spiel...</a>.<p>In this post however, it looks like<p>• the scoring function is wrong, as pointed out in comment here by danbruc,<p>• the code in the post simply guesses at random (&quot;It only randomly selects its next guess from a pool of possible remaining guessing&quot;), while Knuth&#x27;s approach is of &quot;choosing at every stage a test pattern that <i>minimizes the maximum number of remaining possibilities</i> over all conceivable responses by the codemaker&quot;. (In fact if you run the program in the post, it takes 6 guesses to win!)

The scoring function is wrong, checking for white is not as simple as calling contains.<p><pre><code> if guess[i] == secret_code[i]: red += 1 else: if guess[i] in secret_code: white += 1 </code></pre> With the secret XXXY a guess of YYYY will be scored as one red and three white but it should be just one red. You have to keep track of which positions in the secret have already been consumed, in this case the Y in the secret gets consumed by the Y in the same position in the guess yielding the one red, for the guess YYYX the Y in the secret will be consumed by the first Y in the guess yielding only one white instead of three. Plus of course a second white for the X. When implementing this, one has to be careful that a white does not consume a later red if one wants to do it in a single loop, i.e. it is not good enough to look for any unconsumed match, it must be unconsumed and also not yield a red.

&quot;this game is wordle with colored pegs instead of letters&quot; For some reason, that sentence from a young PhD student made me feel old instantly.

I implemented a mastermind solver the old fashioned way ~6 years ago, he started school today.

Neat. In college we created a version for smart-tv that contained a challenge mode where a certain game would have to be finished in a single turn. Therefore we calculated all possible games where the player always chooses an option that still makes sense until only one move was sensible and would still win the game (we then took only the ones with three of four moves i think and scraped the last move). Sadly I somehow lost the source for the generation, but it took quite a while to calculate -- only the database with the result is left... (the challenge mode can still be played in our super &#x27;fancy&#x27; online version: <a href="https:&#x2F;&#x2F;www.phwitti.com&#x2F;projects&#x2F;mastermind&#x2F;" rel="nofollow noreferrer">https:&#x2F;&#x2F;www.phwitti.com&#x2F;projects&#x2F;mastermind&#x2F;</a> ). To write a blog post about it is on the todo list ;).

Mastermind intrigued me in the same way as the author some time ago, and I&#x27;ve used it as a standard problem when trying out new computational frameworks&#x2F;methods ever since.<p>Here is my Rust version with multi-threading, SIMD, WASM running on your device inside a WebApp: <a href="https:&#x2F;&#x2F;0xbe7a.github.io&#x2F;mastermind&#x2F;" rel="nofollow noreferrer">https:&#x2F;&#x2F;0xbe7a.github.io&#x2F;mastermind&#x2F;</a><p>Repo: <a href="https:&#x2F;&#x2F;github.com&#x2F;0xbe7a&#x2F;mastermind">https:&#x2F;&#x2F;github.com&#x2F;0xbe7a&#x2F;mastermind</a><p>It is quite fast (1.8 Billion position pairs evaluated in 1652ms on my device) and can also exploit some symmetries inside the solution space.

This was my 1996 IOCCC entry, a mastermind solver. Key features are that it is a one-liner (no macros) and everything is coded using for-loops.<p><pre><code> char*p,*q,*r,s[50000];int i,j,k,l;main(){for(r=s,i=10000;i--;r++)for(j=i+3211,k=4;k--;*r++=48+j%10,j&#x2F;=10);for(;puts((k=r-s)?q=r-5:&quot;?&quot;),k&amp;&amp;k-5;)for (scanf(&quot;%d&quot;,&amp;k),p=s;p-r;){for(i=j=0;j-16;p[j%4]|=l=!(p[j%4]-q[j&#x2F;4])?i++,64:0,j|=l&#x2F;17,j++);for(j=0;j-5;i+=!((*p++&amp;=63)-q[j++])*9);for(;k-i+9&amp;&amp;j--;*--p=*--r);}} </code></pre> You think of a 4 digit number, the code tries to guess it. You give it 2 digit answers for red and white.

Here&#x27;s my visual implementation of Knuth&#x27;s algorithm to solve Mastermind!<p>Click &quot;Solve within 5 moves&quot;<p><a href="https:&#x2F;&#x2F;ludi317.github.io&#x2F;" rel="nofollow noreferrer">https:&#x2F;&#x2F;ludi317.github.io&#x2F;</a><p>Gory details here: <a href="https:&#x2F;&#x2F;github.com&#x2F;ludi317&#x2F;ludi317.github.io">https:&#x2F;&#x2F;github.com&#x2F;ludi317&#x2F;ludi317.github.io</a>

Unexpectedly fun to open a HN article and have someone talk about visiting my city (Newburyport) on vacation. Hope they had a great time!<p>I also have a copy of Mastermind that my parents had as kids, it&#x27;s probably from the 70s? Cool vibes all around, HN. :-)

That’s fun. A step by step story of implementing the algorithm would be interesting to expand on.

Wait, I thought the original mastermind rules contain position in the white&#x2F;black pegs.

Mssachutues