Mastermind
Marc Aldebert
I'm pretty sure that someone here will know that!
Let me know (preferably by email) if you know the answer or if you have a program
that plays "perfect" mastermind.
Marc.
dec...@ibm.net
I have a related question. Back during the Rubics' Cube craze I saw a brief
discussion involving an interesting concept: "The Length of Gods Algorithm"
The question is essentially this: What is the greatest number of moves
needed to solve the puzzle [game] when playing the perfect algorithm? For
example, can 4x6 mastermind always be solved in 8 moves, 7 moves?
Vesa Timonen
>I have a related question. Back during the Rubics' Cube craze I saw a brief
>discussion involving an interesting concept: "The Length of Gods Algorithm"
>The question is essentially this: What is the greatest number of moves
>needed to solve the puzzle [game] when playing the perfect algorithm? For
>example, can 4x6 mastermind always be solved in 8 moves, 7 moves?
>
I have made a program which analyses mastermind's moves.
It uses a heuristic method to select best moves and
I think it's quite close to optimal player.
In 4x6, 6 guesses is needed. Average is 4.436.
In 4x8, 7 guesses is needed. Average is 5.21.
In 3x6, 5 guesses is needed. Average is 3.977.
Vesa
Risto Widenius
> I have made a program which analyses mastermind's moves.
> It uses a heuristic method to select best moves and
> I think it's quite close to optimal player.
> In 4x6, 6 guesses is needed. Average is 4.436.
The brute force algorithm by Knuth has an average of 4.478. R.W. Irwing
later reduced the average to 4.369 with a slightly optimized algorithm
which is easy to code in almost any high-level language. Both algorithms
use 5 guesses at most. V. Chvatal has published an elaborated analysis
in Combinatorica 3 (1983) - including the math for the optimal strategy
for M pegs and N colours.
For an heuristic algorithm I think the 4.436 average is tremendous.
--
"Det är på tiden att byta hö i skorna." -- rw
Paul Palmer
In <49hogd$r...@ici-paris.ensta.fr>, alde...@ensta.fr (Marc Aldebert) writes:
>A friend of mine asked me yesterday if the Mastermind game had been solved.
>I'm pretty sure that someone here will know that!
>Let me know (preferably by email) if you know the answer or if you have a program
>that plays "perfect" mastermind.
I have a related question. Back during the Rubics' Cube craze I saw a brief
discussion involving an interesting concept: "The Length of Gods Algorithm"
The question is essentially this: What is the greatest number of moves
needed to solve the puzzle [game] when playing the perfect algorithm? For
example, can 4x6 mastermind always be solved in 8 moves, 7 moves?
Archive-name: sci-math-faq/mastermind
Last-modified: Nov 20, 1995
Version: 7.0
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.
--
Paul Palmer
Department of Mathematics E-mail: pal...@math.orst.edu
Kidder Hall 368
Oregon State University, Corvallis, Oregon 97331-4605