[Comp.Sci.Dept, Utrecht] Note from archiver<at>cs.uu.nl: This page is part of a big collection of Usenet postings, archived here for your convenience. For matters concerning the content of this page, please contact its author(s); use the source, if all else fails. For matters concerning the archive as a whole, please refer to the archive description or contact the archiver.

Subject: sci.math FAQ: Master Mind

This article was archived around: 17 Feb 2000 22:55:52 GMT

All FAQs in Directory: sci-math-faq
All FAQs posted in: sci.math
Source: Usenet 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