home *** CD-ROM | disk | FTP | other *** search
/ ftp.pasteur.org/FAQ/ / ftp-pasteur-org-FAQ.zip / FAQ / sci-math-faq / mastermind < prev    next >
Encoding:
Internet Message Format  |  2000-02-18  |  2.2 KB
  1. 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
  2. From: alopez-o@neumann.uwaterloo.ca (Alex Lopez-Ortiz)
  3. Newsgroups: sci.math,news.answers,sci.answers
  4. Subject: sci.math FAQ: Master Mind
  5. Followup-To: sci.math
  6. Date: 17 Feb 2000 22:55:52 GMT
  7. Organization: University of Waterloo
  8. Lines: 37
  9. Approved: news-answers-request@MIT.Edu
  10. Expires: Sun, 1 Mar 1998 09:55:55
  11. Message-ID: <88hu9o$r5s$1@watserv3.uwaterloo.ca>
  12. Reply-To: alopez-o@neumann.uwaterloo.ca
  13. NNTP-Posting-Host: daisy.uwaterloo.ca
  14. Summary: Part 22 of 31, New version
  15. Originator: alopez-o@neumann.uwaterloo.ca
  16. Originator: alopez-o@daisy.uwaterloo.ca
  17. Xref: senator-bedfellow.mit.edu sci.math:347387 news.answers:177507 sci.answers:11215
  18.  
  19. Archive-name: sci-math-faq/mastermind
  20. Last-modified: February 20, 1998
  21. Version: 7.5
  22.  
  23.  
  24.    
  25.                                  Master Mind
  26.  
  27.  
  28.                                        
  29.    For the game of Master Mind it has been proven that no more than five
  30.    moves are required in the worst case.
  31.    
  32.    One such algorithm was published in the Journal of Recreational
  33.    Mathematics; in '70 or '71 (I think), which always solved the 4 peg
  34.    problem in 5 moves. Knuth later published an algorithm which solves
  35.    the problem in a shorter number of moves - on average - but can take
  36.    six guesses on certain combinations.
  37.    
  38.    In 1994, Kenji Koyama and Tony W. Lai found, by exhaustive search that
  39.    5625/1296 = 4.340 is the optimal strategy in the expected case. This
  40.    strategy may take six guesses in the worst case. A strategy that uses
  41.    at most five guesses in the worst case is also shown. This strategy
  42.    requires 5626/1296 = 4.341 guesses.
  43.    
  44.       References
  45.       
  46.    Donald E. Knuth. The Computer as Master Mind. J. Recreational
  47.    Mathematics, 9 (1976-77), 1-6.
  48.    
  49.    Kenji Koyama, Tony W. Lai. An optimal Mastermind Strategy. J.
  50.    Recreational Mathematics, 1994.
  51. -- 
  52. Alex Lopez-Ortiz                                         alopez-o@unb.ca
  53. http://www.cs.unb.ca/~alopez-o                       Assistant Professor    
  54. Faculty of Computer Science                  University of New Brunswick
  55.