Thanks Steve! [ Ссылка ]

Play online: [ Ссылка ]
Thanks Eoin.
Word Mastermind: [ Ссылка ]
Thanks Alex.

I recommend these apps for Android:
Mastermind (but called Bulls and Cows) [ Ссылка ]
Bulls and Cows [ Ссылка ]

----------------

Let's go through some Mastermind algorithms. Here are two human methods:

Randomly Consistent: Picking any remaining valid combination at random. (Swaszek 1999).
FIRST GUESS = ANY, MAX = 10, AVG = 4.638.
Here is an example of 10 consistent guesses: [ Ссылка ]
Randomly Consistent can be improved with FIRST GUESS = 1123, then MAX = 9 and AVG = 4.58.

Simple: This algorithm just goes through the combinations in numerical order from 1111 to 6666, and picking the next consistent combination. (Shapiro 1983).
FIRST GUESS: 1111, MAX = 9, AVG = 5.765
This method can be improved with a FIRST GUESS = 5466, then MAX = 7, AVG = 4.646.

----------------

Here is the Least Worst Case Scenario method:

Least Worst Case Scenario (simple): Consider the table of responses at each step, and choose a combination (from the remaining combinations) with the least worse case scenario. (Norvig 1984).
FIRST GUESS = 1122, MAX = 6, AVG = 4.478

Least Worst Case Scenario (full): Consider the table of responses at each step, and choose the combination (from all combinations) with the least worse case scenario. (Donald Knuth 1977).
FIRST GUESS = 1122, MAX = 5, AVG = 4.476.

***CORRECTION: I said 4.478 not 4.476 in the video. I mixed up the two Worst Case Scenario methods***

In Knuth's paper, he gives an example of a game that needs an inconsistent move to guarantee a solve in 5 steps.
[ Ссылка ]

Using Least Worst Algorithm the most difficult codes are 1221, 2354, 3311, 4524, 5656, 6643.

----------------

Here are some other methods:

Expected Case: Consider the table of responses, and choose the combination with the smallest average scenario. (Irving 1979).
FIRST GUESS 1123, MAX = 6, AVG = 4.395.

Entropy: Using the table of responses, maximise entropy. (Neuwirth, 1982).
FIRST GUESS 1234, MAX = 6, AVG = 4.415.
Entropy is an idea from Information Theory and is quite technical. 3b1b goes into it in detail in his wordle video here: [ Ссылка ]

Most Parts: Using the table of responses, pick the choice with the most non-zero parts. (Kooi 2005).
FIRST GUESS = 1123, MAX = 6, AVG = 4.374.
The idea here is to divide the remaining possibilities into as many buckets as possible. This increases the probability of a lucky guess.
Interestingly, this method performs well in the 4-digit, 6 colour mastermind, but not as well with other numbers of digits and colours.

----------------

And here is the Optimal method:

Optimal: Deep search to create a look-up table that gives the lowest average. (Koyoma and Lai 1993).
FIRST GUESS = 1123, MAX = 6, AVG = 4.340.
Interesting fact, there is only one combination that takes 6 steps, (namely 4421).

Adjusted Optimal: Deep search to find the lowest average, with a max of 5. (Koyoma and Lai 1993).
FIRST GUESS = 1123, MAX = 5, AVG = 4.341.
This is something that got edited out of the video for time. With a few adjustments, the optimal max is reduced to 5, with a tiny increase to the average.

----------------

Here is another humanly possible method, which I think is fun, but is very different:

Static Mastermind: A set of 6 fixed combinations, that can completely determine any secret combination on the seventh step.
GUESSES = 1212, 2263, 3344, 4554, 5316, 6156.
Here is the article: [ Ссылка ]
(My list is different to the article, because I tried to make it more memorable).

----------------

Bulls and Cows: The original game. Using pen and paper, a 4-digit number is chosen without repeats.

Random: FIRST GUESS = ANY, MAX = 8, AVG = 5.445
Least Worst Case: FIRST GUESS = 1234, MAX = 7, AVG = 5.380
Optimal: FIRST GUESS = 1234, MAX = 7, AVG = 5.213

----------------

Generalisations: What about mastermind using n positions, and k colours?

We have partial information about maximums and averages. There is a good summary here [ Ссылка ]

----------------

Further information:

I found good information and references here: [ Ссылка ]
And here: [ Ссылка ]
And wikipedia, obviously: [ Ссылка ]
[ Ссылка ]

I then got the book by Serkan Gur and I thought it was excellent: [ Ссылка ]
Serkan kindly helped me out with some of the details. Thank you Serkan.

свернуть