From: wiener@bnr.ca (Michael Wiener)Newsgroups: sci.math Subject: Re: sci.math FAQ: Master MindDate: 29 Nov 1995 20:44:49 GMT In article , alopez-o@neumann.uwaterloo.ca (Alex Lopez-Ortiz) writes: |> For the game of Master Mind it has been proven that no more than five |> moves are required in the worst case.|> |> One such algorithm was published in the Journal of Recreational |> Mathematics; in '70 or '71 (I think), which always solved the 4 peg |> problem in 5 moves. Knuth later published an algorithm which solves |> the problem in a shorter number of moves - on average - but can take |> six guesses on certain combinations.|> |> In 1994, Kenji Koyama and Tony W. Lai found, by exhaustive search that |> 5625/1296 = 4.340 is the optimal strategy in the expected case. This |> strategy may take six guesses in the worst case. A strategy that uses |> at most five guesses in the worst case is also shown. This strategy |> requires 5626/1296 = 4.341 guesses. I have done a full game-theoretic analysis of the 4-peg, 6-colour version of mastermind. By game theoretic, I mean that the chooser of the code tries to maximize the number of guesses in addition to the guesser trying to minimize the number of guesses. The result (from a program that ran for months) was that the chooser of the code should choose at random from the 1290 codes that do not consist of pegs all the same colour. An optimal strategy for the guesser gives 5600/1290 = 4.341 as the expected number of guesses. I was disappointed to discover that this strategy is the same as the one for the case where the chooser picks any code at random. In this case, the guesser requires, on average, 25/6 = 4.167 guesses to find a code with pegs all the same colour. Thus, the code chooser should avoid codes with all pegs the same colour. Mike Wiener ================================================================================= Anmerkung (siehe "Glück, Logik und Bluff", S. 319): Vor dem Ergebnis von * Wiener 4,341 waren die folgenden Schranken für den Minimax-Wert bekannt: * Flood: <= 4,3674 (aufgrund eines angegebenen Mixes von 4 Suchstrategien) * Koyama/Lai: >= 4,340 (Codierer wählt seinen Code gleichwahrscheinlich)