home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / sci / math / 16946 < prev    next >
Encoding:
Internet Message Format  |  1992-12-15  |  2.6 KB
  1. Path: sparky!uunet!usc!usc!not-for-mail
  2. From: haddadi@sipi.usc.edu (Navid Haddadi)
  3. Newsgroups: sci.math
  4. Subject: Re: Master Mind:A question.
  5. Date: 15 Dec 1992 04:03:29 -0800
  6. Organization: University of Southern California, Los Angeles, CA
  7. Lines: 42
  8. Sender: haddadi@sipi.usc.edu
  9. Message-ID: <1gkhihINN78k@sipi.usc.edu>
  10. References: <1992Dec5.180849.15981@dartvax.dartmouth.edu> <1992Dec13.221551.12761@scorch.apana.org.au> <gay.724358375@sfu.ca>
  11. NNTP-Posting-Host: sipi.usc.edu
  12. Keywords: Master Mind Game
  13.  
  14. In article <gay.724358375@sfu.ca> gay@selkirk.sfu.ca (Ian D. Gay) writes:
  15. >jimgar@scorch.apana.org.au (Jim Garner) writes:
  16. >
  17. >>evant@coos.dartmouth.edu (Evan E. Thomas) writes:
  18. >
  19. >>|My question regards the game "MasterMind" where 4 pegs are chosen (from an
  20. >>[deletions]
  21. >>|You would be told that 1 color is exactly right and that two others are in
  22. >>|the solution.  You have exactly 10 guesses to find the solution.  Is there
  23. >>|an algorithm that will insure victory?
  24. >
  25. >>There is an optimal strategy that has been published. It is very long
  26. >>and divided into cases, so I wouldn't call it an algorithm. But it
  27. >>certainly can be done in less than 10 guesses every time. All I
  28. >>remember is that your first guess should contain 2 colours only, 2
  29. >>pegs of each.
  30. >
  31. > ...
  32. >that the 5-peg version can usually be solved in 6 guesses; presumably 
  33. >...
  34.  
  35. Say we are dealing with 5 pegs and 10 colors. So that all possible
  36. guesses can be represented by {00000,00001,00002,....} There are
  37. obviously 100,000 possibilities. Say, that we have a way of generating
  38. all the numbers between 00000 and 99999 in a random sequence (for example,
  39. by a shift register). It is not too difficult to search the entire
  40. space. For example, let the first guess be G1. Then let G2 be the
  41. second sample of the entire space of possibilities. Now score G1 w.r.t.
  42. G2 and compare the score to the actual score of G1. If they are not the same
  43. discard G2 and take the next *random* sample. If they are the same then
  44. propose G2 as a solution. If G2 is not the solution, start the process
  45. again with G3. This time both G1 and G2 are scored w.r.t. G3 and the
  46. resulting scores are compared to the acutal scores. We can discard G_N
  47. as soon as a contradictory score is obtained for smallest n<N. In this
  48. way searching the entire space only once, a solution is obtained.
  49. The resulting program is very simple and also very fast. The key is that
  50. the sequence must be generated in a random way. Although, I have not
  51. done the analysis, I doubt that the "optimal" solution is any faster (in terms
  52. of the number of guesses) than this simple method.
  53.  
  54. Navid. 
  55. haddadi@sipi.usc.edu
  56.