Mastermind with Steve Mould

Thanks Steve! https://www.youtube.com/c/SteveMould

Play online: https://codebreaker.eoin.co/
Thanks Eoin.
Word Mastermind: https://stressfle.nikolaus.uk/
Thanks Alex.

I recommend these apps for Android:
Mastermind (but called Bulls and Cows) shorturl.at/uvxNU
Bulls and Cows shorturl.at/ekF12

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

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: https://www.cut-the-knot.org/ctk/Rafler.shtml
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.
https://www.cs.uni.edu/~wallingf/teaching/cs3530/resources/knuth-mastermind.pdf

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: https://youtu.be/v68zYyaEmEA

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: https://www.cut-the-knot.org/ctk/Mastermind.shtml
(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 https://people.cs.clemson.edu/~goddard/papers/mastermindRevisited.pdf

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

Further information:

I found good information and references here: https://mathworld.wolfram.com/Mastermind.html
And here: http://www.serkangur.freeservers.com/
And wikipedia, obviously: https://en.wikipedia.org/wiki/Bulls_and_Cows
https://en.wikipedia.org/wiki/Mastermind_(board_game)

I then got the book by Serkan Gur and I thought it was excellent: https://www.amazon.com/dp/B01M17PMIQ
Serkan kindly helped me out with some of the details. Thank you Serkan.

Видео Mastermind with Steve Mould канала singingbanana