A recent question about Programming a Prolog solver for a Master Mind type problem generated a question about a scoring rule ambiguity for Master Mind, which is not solved by the Wikipedia page entry for "Master Mind"
Suppose you have this situation, with letters a stand-in for color:
If you have a code: ABCD
And the guess is: EEAA
... Does the codemaker indicate:
- 0 black pegs and 2 white pegs because there are no entries in the guess with the correct color at the correct place, and the two As are correct guesses but on the wrong place.
- 0 black pegs and 1 white peg because there are no entries in the guess with the correct color at the correct place, and the only one of the A in the guess can be paired with the A in the code.
Case 2 is equivalent to drawing lines between the code pegs and the guess pegs, going for the vertical lines first (pair any pegs with same color at same position) and following up with any remaining diagonal lines (pair any pegs with same color at different positions).
Is (2) the right way of scoring?
Formal
In the paper Mastermind is NP-Complete by Jeff Stuckman and Guo-Qiang Zhang give the following definition of b (the number of black pegs) and w-b (the number of white pegs). To make things short, they go for scoring method (2):
So, to make the labeling clear:
1234 <--- Position indicators
If you have a code: ABCD <--- The array x[i] of code colors, 1 ≤ i ≤ 4
And the guess is: EEAA <--- The array y[i] of guess colors, 1 ≤ i ≤ 4
Evidently in the above b = 0 because there is no i in [1,2,3,4] where x[i] = y[i]
w is a bit trickier, it is a sum over the colors, where j ranges over the colors:
+--j
|
| +--Number of occurrences of color j in array x
| |
| | +--Number of occurrences of color j in array y
| | |
| | | +--Minimum of both values (== number of possible pairings for that color)
| | | |
Color A 1 2 1
Color B 1 0 0
Color C 1 0 0
Color D 1 0 0
Color E 0 2 0
-----
Sum: 1 = w = number of possible pairings in the (code,guess) pair
So, number of black pegs: b = 0 So, number of white pegs: w-b = 1-0 = 1