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)