2
$\begingroup$

In attempting an analysis of worst-case scenarios in MasterMind, I started working towards matching Knuth's analysis, when I realized that there seems to be a contradiction in his stated methods and his results.

Analyzing the starting move 1122, my algorithm comes up with 1134, whereas Knuth's Figure 1 B says that 2344 will be the best move to use next. Both 1134 and 2344 eliminate the same number of possibilities, so why does Knuth choose 2344, against his stated convention of taking "the first ... test pattern in numeric order" that "minimizes the maximum number of remaining possibilities"?

You can check my algorithm's output. The game so far would be:

1122 B
1344 W

And the 44-line output is (changed to match Knuth's base-1 format and sorted for convenience):

3523
3525
3526
3532
3552
3562
3623
3625
3626
3632
3652
3662
4525
4526
4552
4562
4625
4626
4652
4662
5155
5156
5165
5166
5425
5426
5452
5462
5523
5532
5623
5632
6155
6156
6165
6166
6425
6426
6452
6462
6523
6532
6623
6632

If the output isn't missing any logical possibilities, then why does he violate his own convention?

$\endgroup$
1
  • $\begingroup$ I wasn't aware, but that article has since been updated and extended with other algorithms in Knuth's book, Selected Papers on Fun and Games: www-cs-faculty.stanford.edu/~knuth/fg.html Until I get access to the book I'm still unclear about whether the update answers this question, though. $\endgroup$
    – Kev
    Mar 14, 2017 at 17:21

1 Answer 1

Reset to default
2
$\begingroup$

Knuth states that 1344 (not 2344) will be the best move.

I do not have the original article but the reprint in his Selected Papers on Fun & Games. There he states the criterion for his choice:

... choosing at every stage a test pattern that minimizes the maximum number of remaining possibilities, ... If this minimum can be achieved by a "valid" pattern (a pattern that makes "four black hits" possible), a valid one should be used. Subject to this condition, the first such pattern in numeric order was selected.

And 1344 can result in four black hits but 1134 can't as two 1s do not work.

$\endgroup$
4
  • $\begingroup$ I guess that was part of the update, then. (If you see the PDF I linked to, page 4, it says "B = (2344: ...". Good to know it was fixed. I guess I was born too late to get any hexadecimal dollars for this. :) ) $\endgroup$
    – Kev
    Apr 25, 2017 at 15:54
  • 1
    $\begingroup$ That has not changed. You have to look at line F. 1122 gets a B and according to page 2 of the linked PDF you have to continue with $\alpha_{10}$ and this is "256F". $\endgroup$
    – Udo Wermuth
    Apr 25, 2017 at 16:12
  • $\begingroup$ Uhoh, I think I've missed a couple things here, but it's been a few weeks. You're right, he explicitly states that F should be taken in this particular example. (Also, my OP above was wrong saying that my algorithm predicts 1134--the latest had it coming up with 1134 just like Knuth, but thanks for commenting on it.) Anyway, the text you quoted is the same as the original PDF, and with it I see my question still stands. I'll try to update the question for clarity. $\endgroup$
    – Kev
    Apr 26, 2017 at 15:22
  • $\begingroup$ On second thought: I see now that he does seem to follow the pattern as stated--chalk it up to not enough caffeine that day? :) Thanks for drawing my attention back here so I could see it more clearly. $\endgroup$
    – Kev
    Apr 26, 2017 at 15:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .