Path: senator-bedfellow.mit.edu!bloom-beacon.mit.edu!newsswitch.lcs.mit.edu!netnews.com!europa.netcrusader.net!204.71.34.3!newsfeed.cwix.com!torn!watserv3.uwaterloo.ca!alopez-o
From:
[email protected] (Alex Lopez-Ortiz)
Newsgroups: sci.math,news.answers,sci.answers
Subject: sci.math FAQ: Master Mind
Followup-To: sci.math
Date: 17 Feb 2000 22:55:52 GMT
Organization: University of Waterloo
Lines: 37
Approved:
[email protected]
Expires: Sun, 1 Mar 1998 09:55:55
Message-ID: <
[email protected]>
Reply-To:
[email protected]
NNTP-Posting-Host: daisy.uwaterloo.ca
Summary: Part 22 of 31, New version
Originator:
[email protected]
Originator:
[email protected]
Xref: senator-bedfellow.mit.edu sci.math:347387 news.answers:177507 sci.answers:11215
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
[email protected]
http://www.cs.unb.ca/~alopez-o Assistant Professor
Faculty of Computer Science University of New Brunswick
