Channel: singingbanana

Category: Education

Tags: wordlegamejames grimeproblemmastermindmathematicsmathsbulls and cowspuzzlemathsteve mouldmaster mind

Description: Thanks Steve! youtube.com/c/SteveMould Play online: codebreaker.eoin.co Thanks Eoin. Word Mastermind: 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: 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. 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: 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: 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 people.cs.clemson.edu/~goddard/papers/mastermindRevisited.pdf ---------------- Further information: I found good information and references here: mathworld.wolfram.com/Mastermind.html And here: serkangur.freeservers.com And wikipedia, obviously: en.wikipedia.org/wiki/Bulls_and_Cows en.wikipedia.org/wiki/Mastermind_(board_game) I then got the book by Serkan Gur and I thought it was excellent: amazon.com/dp/B01M17PMIQ Serkan kindly helped me out with some of the details. Thank you Serkan.