sci.math FAQ: Master Mind

From: alopez-o@neumann.uwaterloo.ca (Alex Lopez-Ortiz)
Newsgroups: sci.math
Subject: sci.math FAQ: Master Mind
Date: 17 Feb 2000 22:55:52 GMT
Message-ID: <88hu9o$r5s$1@watserv3.uwaterloo.ca>
Reply-To: alopez-o@neumann.uwaterloo.ca
Summary: Part 22 of 31, New version

Archive-name: sci-math-faq/mastermind
Last-modified: February 20, 1998
Version: 7.5

 
   
                                 Master Mind


                                       
   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.
   
      References
      
   Donald E. Knuth. The Computer as Master Mind. J. Recreational
   Mathematics, 9 (1976-77), 1-6.
   
   Kenji Koyama, Tony W. Lai. An optimal Mastermind Strategy. J.
   Recreational Mathematics, 1994.
-- 
Alex Lopez-Ortiz                                         alopez-o@unb.ca
http://www.cs.unb.ca/~alopez-o                       Assistant Professor	
Faculty of Computer Science                  University of New Brunswick