Live data from Hacker News

Mastermind Solver

stefanabikaram.com

11–20 of 23 posts

Re: Mastermind Solver

#11
post #8

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…

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.)

Re: Mastermind Solver

#15
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/ ). To write a blog post about it is on the todo list ;).

Re: Mastermind Solver

#16
post #8

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…

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=fRed0Xmc2Wg

Re: Mastermind Solver

#17
post #5

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 P…

(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 u…

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/21Elementary...

Slide 61-62, has some more references.

Re: Mastermind Solver

#18
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/

Repo: 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.

Re: Mastermind Solver

#19
post #5

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 P…

I do hope that student got full credit; that's marvelous.

Re: Mastermind Solver

#20
post #5

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 P…

(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 u…

And of course this site was "hacked", via a weak random number source:

https://news.ycombinator.com/item?id=639976

Post reply on HN