Mastermind Scoring Algorithm in C

Question

I am working on a client/server mastermind game in C and I have finished so far. My programs are working and it solves the secret in average 6-7 guesses. Then I was looking over the internet and found Donals Knuths approach: - Create a set S of remaining possibilities (at this point there are 1296). The first guess is aabb. - Remove all possibilities from S that would not give the same score of colored and white pegs if they were the answer. - For each possible guess (not necessarily in S) calculate how many possibilities from S would be eliminated for each possible colored/white score. The score of the guess is the least of such values. Play the guess with the highest score (minimax). - Go back to step 2 until you have got it right. What I have to say here is that I use 5 positions and 8 colors. As I am trying to optimize my program I have a hard time understanding how step 3, in particular the calculation of what guess would eliminate the most possibilities, would look like. What I…

Accepted Answer

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

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

You'll have to read the entire blog post to figure out the details, but basically this implements Knuth's "subject to" requirement: if the probe is a new minimum, or if it is equal to the current minimum, is a member of the pool, and the current minimum is not a member of the pool, keep it as the new minimum, otherwise loop to the next probe.

Mastermind Scoring Algorithm in C

Solution

Problem