Mastermind counting algorithm in C

Question

I am working on a game on a client server / server in C and I am still done. My programs work, and it solves the secret of an average of 6-7 guesses. Then I browsed the internet and found Donald Knuth's approach:

• Create a set S of remaining features (there are currently 1296). The first assumption is abab.
• Remove all possibilities from S that would not give the same score of color and white pins if they were the answer.
• For each possible guess (not necessarily in S), calculate how many possibilities from S will be eliminated for each possible color / white. The best indicator is values. Play the guess with the highest score (minimax).
• Go back to step 2 until you get it right.

What I have to say here is that I use 5 positions and 8 colors.

As I try to optimize my program, it’s hard for me to understand what Step 3 would look like, in particular, calculating which guess would eliminate most of the possibilities.

I know that I have to look at each element and compare it with everyone, but I'm not sure how to compare it, since I have no white / black values. And I'm wondering how I can determine which record that meets certain conditions will exclude the maximum possibilities.

Answer 1

I discuss the algorithm and give an implementation (in Scheme, not C) in my blog . The hard part is the predicate in the minimax function:

(or (< size min-size) (and (= size min-size) (member (car ps) pool) (not (member min-probe pool)))) 

You will need to read the entire blog entry to find out the details, but it basically fulfills Knut’s requirement: “if the probe is a new minimum or if it is equal to the current minimum, a pool member and the current minimum is not a pool member, keep it as a new minimum otherwise cycle to the next probe.