5 ms·

Mastermind Solver

33 points by stefanpie 3y ago

mock-possum 3y ago
That’s fun. A step by step story of implementing the algorithm would be interesting to expand on.
HlessClaudesman 3y ago
I implemented a mastermind solver the old fashioned way ~6 years ago, he started school today.
- marktani 3y ago
  can you prove your solver is complete?
oezi 3y ago
Wait, I thought the original mastermind rules contain position in the white/black pegs.
- kasey_junk 3y ago
  I own variants with white/black, white/red and white/brown (the oldest I have).
rwmj 3y ago
Shout out to another student on my university course. We had to implement this algorithm as a class exercise. Most people "discovered" 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! 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's implementation simply worked out the answer from the date and process PID and knowledge of how the linear congruential generator worked.
- PennRobotics 3y ago
  (from a research paper by F. Dörre and V. Klebanov) The bitcoin theft incident. The presumed genesis of the attack is as follows: Bitcoin operates a public database of all transactions, the block chain. Each transaction is cryptographically signed by its initiator using the ECDSA scheme. Creating ECDSA signatures requires a per-transaction nonce. Partial predictability of nonces allows for one class of attacks, but using the same nonce for two transactions signed by the same key---which is what probably happened---constitutes a catastrophic security failure. Anyone can easily identify this case from the information recorded in the block chain, reconstruct the victim’s private key, and divert their money to a bitcoin address of choice. No intrusion into the victim’s system is necessary. A loss of seed entropy in the PRNG used for generating nonces increases the probability of the breach. This ultimately caused Google to replace the Android PRNG, which was only providing 40% of the requested entropy for this particular use. ----- I also recall someone had discovered an online poker service's shuffle algorithm was something common (maybe Fisher-Yates?) based on java.util.Random with system time as a seed. Once you see your own hand and part of the board, you get a fairly accurate idea of what could be in someone else's hand from the small-ish sample of possible deals around system time.
  - microtonal 3y ago
    Ah, yeah, the online poker example is in Sedgwick and Wayne’s books and/or slides. Found it: https://algs4.cs.princeton.edu/lectures/keynote/21ElementarySorts.pdf https://algs4.cs.princeton.edu/lectures/keynote/21Elementary... Slide 61-62, has some more references.
  - stevekemp 3y ago
    And of course this site was "hacked", via a weak random number source: https://news.ycombinator.com/item?id=639976 https://news.ycombinator.com/item?id=639976
- klyrs 3y ago
  I do hope that student got full credit; that's marvelous.
lgeorget 3y ago
"this game is wordle with colored pegs instead of letters" For some reason, that sentence from a young PhD student made me feel old instantly.
pnut 3y ago
Mssachutues
- onychomys 3y ago
  https://www.biblegateway.com/passage/?search=john+8%3A7&version=KJV https://www.biblegateway.com/passage/?search=john+8%3A7&vers...
danbruc 3y ago
The scoring function is wrong, checking for white is not as simple as calling contains. if guess[i] == secret_code[i]: red += 1 else: if guess[i] in secret_code: white += 1 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.
- svat 3y ago
  Wordle programs often start with a similar bug in their (similar) scoring function. Apart from tracking positions and consuming them as you suggested, there's also another approach to writing the scoring function, suggested by Knuth's notation in the paper mentioned in another comment: from collections import Counter def score_guess(guess, secret_code): red = sum(guess[i] == secret_code[i] for i in range(len(guess))) total = (Counter(guess) & Counter(secret_code)).total() return (red, total - red) assert score_guess('YYYY', 'XXXY') == (1, 0) assert score_guess('YYYX', 'XXXY') == (0, 2) (The `&` on `Counter` computes minimum of the two counts.)
- bnycum 3y ago
  Reminds me of the 3Blue1Brown video about Wordle, and then it's followup video. I guess that's kind of a spoiler, but still worth a watch. https://www.youtube.com/watch?v=v68zYyaEmEA https://www.youtube.com/watch?v=v68zYyaEmEA https://www.youtube.com/watch?v=fRed0Xmc2Wg https://www.youtube.com/watch?v=fRed0Xmc2Wg
svat 3y ago
The Knuth approach said to be implemented in this post is described in: > The computer as Master Mind. Journal of Recreational Mathematics 9 (1976), pp. 1–6. Reprinted with an addendum as Chapter 25 of Selected Papers on Fun and Games. https://www.cs.uni.edu/~wallingf/teaching/cs3530/resources/knuth-mastermind.pdf https://www.cs.uni.edu/~wallingf/teaching/cs3530/resources/k... 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/table), and discusses various later results/ideas. For example, the addendum mentions that while Knuth'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't want to quote at length, but see https://stackoverflow.com/a/54917672 https://stackoverflow.com/a/54917672 and the discussion on the German Wikipedia https://de.wikipedia.org/w/index.php?title=Mastermind_(Spiel)&oldid=231513977#Strategien https://de.wikipedia.org/w/index.php?title=Mastermind_(Spiel.... In this post however, it looks like • the scoring function is wrong, as pointed out in comment here by danbruc, • the code in the post simply guesses at random ("It only randomly selects its next guess from a pool of possible remaining guessing"), while Knuth's approach is of "choosing at every stage a test pattern that minimizes the maximum number of remaining possibilities over all conceivable responses by the codemaker". (In fact if you run the program in the post, it takes 6 guesses to win!)
phwitti 3y ago
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 'fancy' online version: https://www.phwitti.com/projects/mastermind/ https://www.phwitti.com/projects/mastermind/ ). To write a blog post about it is on the todo list ;).
be7a 3y ago
Mastermind intrigued me in the same way as the author some time ago, and I've used it as a standard problem when trying out new computational frameworks/methods ever since. Here is my Rust version with multi-threading, SIMD, WASM running on your device inside a WebApp: https://0xbe7a.github.io/mastermind/ https://0xbe7a.github.io/mastermind/ Repo: https://github.com/0xbe7a/mastermind https://github.com/0xbe7a/mastermind 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.
ludiludi 3y ago
Here's my visual implementation of Knuth's algorithm to solve Mastermind! Click "Solve within 5 moves" https://ludi317.github.io/ https://ludi317.github.io/ Gory details here: https://github.com/ludi317/ludi317.github.io https://github.com/ludi317/ludi317.github.io
pickledcods 3y ago
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. 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/=10);for(;puts((k=r-s)?q=r-5:"?"),k&&k-5;)for (scanf("%d",&k),p=s;p-r;){for(i=j=0;j-16;p[j%4]|=l=!(p[j%4]-q[j/4])?i++,64:0,j|=l/17,j++);for(j=0;j-5;i+=!((*p++&=63)-q[j++])*9);for(;k-i+9&&j--;*--p=*--r);}} You think of a 4 digit number, the code tries to guess it. You give it 2 digit answers for red and white.
segfaltnh 3y ago
Unexpectedly fun to open a HN article and have someone talk about visiting my city (Newburyport) on vacation. Hope they had a great time! I also have a copy of Mastermind that my parents had as kids, it's probably from the 70s? Cool vibes all around, HN. :-)

Mastermind Solver

33 points by stefanpie 3y ago

mock-possum 3y ago

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

HlessClaudesman 3y ago

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

marktani 3y ago
can you prove your solver is complete?

oezi 3y ago

Wait, I thought the original mastermind rules contain position in the white/black pegs.

kasey_junk 3y ago
I own variants with white/black, white/red and white/brown (the oldest I have).

rwmj 3y ago

Shout out to another student on my university course. We had to implement this algorithm as a class exercise. Most people "discovered" 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! 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's implementation simply worked out the answer from the date and process PID and knowledge of how the linear congruential generator worked.

PennRobotics 3y ago
(from a research paper by F. Dörre and V. Klebanov) The bitcoin theft incident. The presumed genesis of the attack is as follows: Bitcoin operates a public database of all transactions, the block chain. Each transaction is cryptographically signed by its initiator using the ECDSA scheme. Creating ECDSA signatures requires a per-transaction nonce. Partial predictability of nonces allows for one class of attacks, but using the same nonce for two transactions signed by the same key---which is what probably happened---constitutes a catastrophic security failure. Anyone can easily identify this case from the information recorded in the block chain, reconstruct the victim’s private key, and divert their money to a bitcoin address of choice. No intrusion into the victim’s system is necessary. A loss of seed entropy in the PRNG used for generating nonces increases the probability of the breach. This ultimately caused Google to replace the Android PRNG, which was only providing 40% of the requested entropy for this particular use. ----- I also recall someone had discovered an online poker service's shuffle algorithm was something common (maybe Fisher-Yates?) based on java.util.Random with system time as a seed. Once you see your own hand and part of the board, you get a fairly accurate idea of what could be in someone else's hand from the small-ish sample of possible deals around system time.
- microtonal 3y ago
  Ah, yeah, the online poker example is in Sedgwick and Wayne’s books and/or slides. Found it: https://algs4.cs.princeton.edu/lectures/keynote/21ElementarySorts.pdf https://algs4.cs.princeton.edu/lectures/keynote/21Elementary... Slide 61-62, has some more references.
- stevekemp 3y ago
  And of course this site was "hacked", via a weak random number source: https://news.ycombinator.com/item?id=639976 https://news.ycombinator.com/item?id=639976
klyrs 3y ago
I do hope that student got full credit; that's marvelous.

lgeorget 3y ago

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

pnut 3y ago

Mssachutues

onychomys 3y ago
https://www.biblegateway.com/passage/?search=john+8%3A7&version=KJV https://www.biblegateway.com/passage/?search=john+8%3A7&vers...

danbruc 3y ago

The scoring function is wrong, checking for white is not as simple as calling contains. if guess[i] == secret_code[i]: red += 1 else: if guess[i] in secret_code: white += 1 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.

svat 3y ago
Wordle programs often start with a similar bug in their (similar) scoring function. Apart from tracking positions and consuming them as you suggested, there's also another approach to writing the scoring function, suggested by Knuth's notation in the paper mentioned in another comment: from collections import Counter def score_guess(guess, secret_code): red = sum(guess[i] == secret_code[i] for i in range(len(guess))) total = (Counter(guess) & Counter(secret_code)).total() return (red, total - red) assert score_guess('YYYY', 'XXXY') == (1, 0) assert score_guess('YYYX', 'XXXY') == (0, 2) (The `&` on `Counter` computes minimum of the two counts.)
bnycum 3y ago
Reminds me of the 3Blue1Brown video about Wordle, and then it's followup video. I guess that's kind of a spoiler, but still worth a watch. https://www.youtube.com/watch?v=v68zYyaEmEA https://www.youtube.com/watch?v=v68zYyaEmEA https://www.youtube.com/watch?v=fRed0Xmc2Wg https://www.youtube.com/watch?v=fRed0Xmc2Wg

svat 3y ago

The Knuth approach said to be implemented in this post is described in: > The computer as Master Mind. Journal of Recreational Mathematics 9 (1976), pp. 1–6. Reprinted with an addendum as Chapter 25 of Selected Papers on Fun and Games. https://www.cs.uni.edu/~wallingf/teaching/cs3530/resources/knuth-mastermind.pdf https://www.cs.uni.edu/~wallingf/teaching/cs3530/resources/k... 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/table), and discusses various later results/ideas. For example, the addendum mentions that while Knuth'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't want to quote at length, but see https://stackoverflow.com/a/54917672 https://stackoverflow.com/a/54917672 and the discussion on the German Wikipedia https://de.wikipedia.org/w/index.php?title=Mastermind_(Spiel)&oldid=231513977#Strategien https://de.wikipedia.org/w/index.php?title=Mastermind_(Spiel.... In this post however, it looks like • the scoring function is wrong, as pointed out in comment here by danbruc, • the code in the post simply guesses at random ("It only randomly selects its next guess from a pool of possible remaining guessing"), while Knuth's approach is of "choosing at every stage a test pattern that minimizes the maximum number of remaining possibilities over all conceivable responses by the codemaker". (In fact if you run the program in the post, it takes 6 guesses to win!)

phwitti 3y ago

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 'fancy' online version: https://www.phwitti.com/projects/mastermind/ https://www.phwitti.com/projects/mastermind/ ). To write a blog post about it is on the todo list ;).

be7a 3y ago

Mastermind intrigued me in the same way as the author some time ago, and I've used it as a standard problem when trying out new computational frameworks/methods ever since. Here is my Rust version with multi-threading, SIMD, WASM running on your device inside a WebApp: https://0xbe7a.github.io/mastermind/ https://0xbe7a.github.io/mastermind/ Repo: https://github.com/0xbe7a/mastermind https://github.com/0xbe7a/mastermind 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.

ludiludi 3y ago

Here's my visual implementation of Knuth's algorithm to solve Mastermind! Click "Solve within 5 moves" https://ludi317.github.io/ https://ludi317.github.io/ Gory details here: https://github.com/ludi317/ludi317.github.io https://github.com/ludi317/ludi317.github.io

pickledcods 3y ago

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. 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/=10);for(;puts((k=r-s)?q=r-5:"?"),k&&k-5;)for (scanf("%d",&k),p=s;p-r;){for(i=j=0;j-16;p[j%4]|=l=!(p[j%4]-q[j/4])?i++,64:0,j|=l/17,j++);for(j=0;j-5;i+=!((*p++&=63)-q[j++])*9);for(;k-i+9&&j--;*--p=*--r);}} You think of a 4 digit number, the code tries to guess it. You give it 2 digit answers for red and white.

segfaltnh 3y ago

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