What algorithms solve MasterMind, and how many guesses do they need?
competition/games/mastermind New
New entry, edited from material collected for the archive and not yet in a released version.
Problem
What algorithms solve MasterMind, and how many guesses do they need? I've read somewhere that there are a couple of papers describing algorithms to solve Mastermind. Does anyone know if these papers are available on line somewhere? -- Antoun Kanawati <tonyk@cybercom.net> [ Editor: the first line is the editor's. ]
Show solution
Forwarded to me by someone else: I found the following on the Web: "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." -- Jeff Kenton <jkenton@world.std.com>