From: wiener@bnr.ca (Michael Wiener) Newsgroups: sci.math Subject: Re: sci.math FAQ: Master Mind Date: 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 ============================================================================== To: Subject: Mathematical analysis of Mastermind and other games Date: Sun, 9 May 1999 00:28:06 +0200 From: Joerg.Bewersdorff@t-online.de (Joerg Bewersdorff) Many thanks for saving the USENET post concerning mastermind from Mike Wiener. It covers a lack of my book "Glueck, Logik ..." (Luck, logic and bluff: mathematics in games - methods, results and limits"). In the chapter dealing with mastermind I only refered the results of optimal strategy in the sense of worst case (Knuth) and average case (Koyama & Lai). Concerning the minimax solution of the variant with 4 piles and 6 colors I only found approximations in the literature. Some details of my book are presented on my homepage (see below). But I'm sorry that most parts are written in German (like the book itself). With best regards Joerg Bewersdorff --------------------------------------------------------------------------- Joerg Bewersdorff Josef-Mehlhaus-Str. 8 D-65549 Limburg Germany FON ++49-(0)6431-8537 FAX ++49-(0)6431-9574-44 Email joerg.bewersdorff@t-online.de WWW http://www.t-online.de/home/joerg.bewersdorff ----------------------------------------------------------------------------