Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Mastermind Solver

stefanabikaram.com

Post reply on HN
Print view View original

1–10 of 23 posts

Re: Mastermind Solver

#5

Post by rwmj »

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.

Re: Mastermind Solver

#8

Post by danbruc »

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.

Re: Mastermind Solver

#9

Post by svat »

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/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 and the discussion on the German Wikipedia 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!)

Re: Mastermind Solver

#10

Post by PennRobotics »

rwmj wrote: 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 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.

Post reply on HN