optimal Mastermind
Don Woods
Mastermind (also known by older pre-commercial names such as "cows and
bulls") is the game where one person picks a sequence (of colors or digits
or whatever) of a fixed length, and the other person then tries to guess
it by guessing sequences. The guesser is told how many of the elements
in his guess are correct (match the corresponding elements in the target
sequence) and how many are in the target sequence but are not in the right
positions. The level of difficulty can be varied by varying the number of
different values that being chosen among for each position (e.g., 6 colors
or 7), the length of the sequence (usually 4), and whether duplicates are
allowed within the target sequence.
Anyway, I've occasionally pondered how one would play this against an
"adversary", in the game theoretic sense. The adversarial chooser doesn't
need to have a particular target sequence in mind. In response to each
guess, he gets to give any answer he wants as long as at least one target
sequence matches that and all previous answers. The game ends when the
adversary is forced to respond: "all correct and in the right positions".
The score is the number of guesses used; the adversary wants to maximise
this score, while the guesser wants to minimise it.
A sample game, using sequences of 4 choices, with duplicates permitted,
from a set of 7 colors (using ROYGBIV as the colors):
ROYG? 0 & 2 (i.e., 2 correct, none if the correct positions)
-> 582 of the original 2401 possible sequences still remain
YGBI? 0 & 2 -> 124 remain
VVRY? 0 & 1 -> 28 remain
GIOR? 1 & 1 (1 correct in right position, 1 other in wrong position)
-> 5 remain
BRGR?
The adversary can now answer any of 0 & 0, 3 & 0, 0 & 2, or 2 & 1, but in
each case the guesser can now deduce the single remaining eligible pattern.
So, as I say, are there any results known on this game? E.g., one obvious
strategy for the adversary is to pick the response that leaves as many
potential sequences as he can. The guesser might then try guesses such
that the remaining search space is reduced as much as possible. But it
might turn out that the guesser can do better by making a guess that allows
the adversary to leave the search space larger this turn, because it leads
to a better partition on the next guess.
Another question I'm curious about is whether the guesser's optimal strategy
always involves guessing a pattern that matches all the answers so far, or
whether it sometimes pays to guess something that can't itself be completely
correct. There's no obvious reason why such guesses should be bad, but
neither is it obvious that they help.
-- Don.
Dennis Breuker
Hi!
Long, long time ago I read something about this on this newsgroup
(I think). I saved some of it. Here it is. Enjoy!
Dennis.
_______________________________________________________________________________
From: marz...@owlnet.rice.edu (Steven Joseph Marzuola)
At least eight people responded to my query about Mastermind. By
request, here is a summary of what I found out.
Yes, Knuth has a paper on it, as does somebody else, apparently in the
mid 1970's. Two different "optimal" strategies are known: It's
possible to always guess in at most 5 guesses, using one strategy.
Another "optimal" strategy may take up to (rarely) six guesses, but
has a lower average number of guesses, (near 4.5) unless the Hider is
cheating.
I was given references to: Math Reviews, the Journal of Recreational
Mathematics, and to Scientific American, in the columns, "Mathematical
Gamer" and Dewdney's "Computer Recreations".
Also, I've been told that 1 black and 1 white peg indeed allows for
the greatest number of possible valid combinations.
My computer implementation was written for an AI class, and wasn't
intended as an exhaustive study of the game. It used an alpha-beta
pruning algorithm with ply-limited minimax search. It works, but I
have almost never tested it using 6 positions and 4 colors (too slow,
given the language (Scheme) and, probably, some gross inefficiencies
in my code. Mostly I have worked with 4 positions and 3 colors.) I'm
also not satisfied with my heuristic, which is supposed to give a
value of how "good" the board is for the Guesser at any point.
Thanks to all who responded.
Steve
_______________________________________________________________________________
Subject: Re: Mastermind
For the version of Mastermind with 4 pegs and 6 colours, Don Knuth [1]
published a strategy that would require at most 5 guesses, and 4.478 guesses
on average (over all possible codes). In [2] this latter figure was reduced to
4.369. Further analysis appears in [3], and [4] contains a more abstract and
general discussion.
1. D.E.Knuth, The Computer as Mastermind, J. Recreational Math. 9 (1976-77),
1-6.
2. R.W.Irving, Towards an optimum Mastermind strategy, J. Recreational Math.
11 (1978-79), 81-87.
3. E.Newirth, Some strategies for Mastermind, Zeitschrift fur Operations
Research 26 (1982), 257-278.
4. V. Chvatal, Mastermind, Combinatorica 3 (1983), 325-329.
Rob Irving.
_______________________________________________________________________________
From: wide...@klaava.Helsinki.FI (Risto Widenius)
[I am crossposting to comp.algorithms, which doesn't exist. I hope this
can be counted as a vote supporting c.a.]
More than a month has passed since I asked for the reference 'Etudes for
Programmers', C Wetherell (1978) -I can't even get my previous article
from the spool- nevertheless I'm summarizing.
Master-Mind is a guessing game played between two players. Each player
in turn makes up a combination of pegs of different colours, and the
other player tries to find out this combination concluding from the
answers to the probes he proposes. In the classical game, which was
popular in the mid-seventies, there are six colours, codes' length is
fixed to four, same colours may be repeated and probes are answered with
black and white pegs indicating the number of correctly placed and
correctly coloured pegs respectively.
Inventing an optimal strategy to break Master-Mind (and corresponding
games') codes has predictably challenged many mathematicians and CS:s.
These are some interesting references:
Chvatal V : Mastermind
Combinatorica, 3 (1983), 325-329
Irwing R.W : Towards an optimum Mastermind strategy
Journal of Recreational Mathematics, 11 (1978), 81-87
Knuth D.E : The Computer as Mastermind
Journal of recreational mathematics, 9 (1976), 1-6
Newirth E : Some strategies for Mastermind
Zeitschrift fur Operations Research, 26 (1982), 257-278
Null A : Computer Recreations
Software - Practice and Experience, 1 (1971), 201-204
Tanenbaum A.S : Computer Recreations: A Heuristic for Playing Jotto
Software - Practice and Experience, 3 (1973), 397-399
The Univ. of Helsinki (my location), for some braindead reason, does not
subscribe to the J. of Recr. Math., and I only know Knuth's strategy by
some references. It seems to me that his strategy is already covered by
Aleph Null some five years earlier, even though he discards the
algorithm as `far too expensive on computation' (he is programming
something called `PDP-8', do I need a smiley here).
Algorithm [brief; find more in the references] :
Start with a set of all permutations (e.g. 4-permutations of 1..6), call
this set P0. Each response Ri consequent to guess Gi eliminates some
number of permutations leaving Pi.
The idea is to choose Gi from P0 so that whatever the answer Ri
will be, Gi will eliminate from Pi-1 _at least_ more members than other
possible G:s would at their worst. This is further optimized by choosing
Gi from Pi-1 if possible. This strategy manages to analyze the game in
advance, and the optimal openings are easily found (AABB, ABAB and ABBA in
the classical version).
Before the compulsory pseudocode I would like to thank Paul Palmer, Gary
Cote and Stig Hemmer for their responses.
Pseudo(C)code :
function answer
{
[returns the amount of black and white pegs]
}
function findG
{
min=sizeof(P0)
for(i loops through P0){
format(array A[nr of poss. answers] with 0:s)
max=0
for(j loops through Pi){
R=answer(i,j)
A[R]++
if(A[R]>max) max=A[r]
}
if(max<=min && (i in Pi) || max<min){
min=max
G=i
}
}
return G
}
John Tromp
>Mastermind (also known by older pre-commercial names such as "cows and
>bulls") is the game where one person picks a sequence (of colors or digits
>or whatever) of a fixed length, and the other person then tries to guess
>it by guessing sequences. The guesser is told how many of the elements
>in his guess are correct (match the corresponding elements in the target
>sequence) and how many are in the target sequence but are not in the right
>positions. The level of difficulty can be varied by varying the number of
>different values that being chosen among for each position (e.g., 6 colors
>or 7), the length of the sequence (usually 4), and whether duplicates are
>allowed within the target sequence.
>Anyway, I've occasionally pondered how one would play this against an
>"adversary", in the game theoretic sense. The adversarial chooser doesn't
Considering an adversary is the same as considering the worst case
for any guessing method.
>So, as I say, are there any results known on this game? E.g., one obvious
>strategy for the adversary is to pick the response that leaves as many
>potential sequences as he can. The guesser might then try guesses such
>that the remaining search space is reduced as much as possible. But it
>might turn out that the guesser can do better by making a guess that allows
>the adversary to leave the search space larger this turn, because it leads
>to a better partition on the next guess.
The most recent article I have on the subject is
"Mastermind Strategy" by Merril M. Flood from the University of
California in San Diego, published in the Journal of Recreational
Mathematics, Vol. 18(3), 1985-86.
It contains several other references, notably one by Knuth, that
appeared in the same journal in 1976-77, and in which he demonstrates
a strategy requiring 5 guesses at the most.
regards,
%!PS % -John Tromp (http://www.cwi.nl/~tromp/)
42 42 scale 7 9 translate .07 setlinewidth .5 setgray/c{arc clip fill
setgray}def 1 0 0 42 1 0 c 0 1 1{0 3 3 90 270 arc 0 0 6 0 -3 3 90 270
arcn 270 90 c -2 2 4{-6 moveto 0 12 rlineto}for -5 2 5{-3 exch moveto
9 0 rlineto}for stroke 0 0 3 1 1 0 c 180 rotate initclip}for showpage
James Layland
Don Woods <d...@zen.genmagic.com> wrote:
>Does anyone know of any results on "optimal" or "adversarial" Mastermind?
From the sci.math FAQ:
Archive-Name: sci-math-faq/mastermind
Last-modified: December 8, 1994
Version: 6.2
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.
--------------------
I remember reading about Knuth's strategy in Scientific American,
in either Dewdney's or Martin Gardner's column, but I can't find
the citation.
--
James Layland
jlay...@grissom.jpl.nasa.gov
Bill Taylor
|> Another question I'm curious about is whether the guesser's optimal strategy
|> always involves guessing a pattern that matches all the answers so far, or
|> whether it sometimes pays to guess something that can't itself be completely
|> correct. There's no obvious reason why such guesses should be bad, but
|> neither is it obvious that they help.
Well making an "impossible guess" can certainly help reduce the average
number of guesses remaining. However, the only example I could construct
in a hurry, was where there had been sub-optimal guessing *before* the
situation arose. Presumably that's OK?
Anyway, here it is: Playing with a line of 4 digits, we have the
information down to (in order)...
N789 , where N is one of 1,2,3 or 4.
If one now makes a "possible" guess, say 1789, one gets it in 1,2,3,or 4
extra guesses, (or perhaps 1,3,3,or 3 if one allows a subsequent impossible).
Either way, that's 2.5 on average.
But if one makes the impossible guess of 1289, then one gets it in
2,2,2,or 3 more guiesses, which is an average of only 2.25 more guesses.
But there's still the open problem:- can this type of situation arise
as part of an optimal guessing strategy? My wild uninformed guess is NO.
-------------------------------------------------------------------------------
Bill Taylor w...@math.canterbury.ac.nz
-------------------------------------------------------------------------------
The squeaky wheel gets replaced.
-------------------------------------------------------------------------------
Marcus Moore
|>
|> Well making an "impossible guess" can certainly help reduce the average
|> number of guesses remaining. However, the only example I could construct
|> in a hurry, was where there had been sub-optimal guessing *before* the
|> situation arose. Presumably that's OK?
|>
|> Anyway, here it is: Playing with a line of 4 digits, we have the
|> information down to (in order)...
|> N789 , where N is one of 1,2,3 or 4.
|>
|> If one now makes a "possible" guess, say 1789, one gets it in 1,2,3,or 4
|> extra guesses, (or perhaps 1,3,3,or 3 if one allows a subsequent impossible).
|> Either way, that's 2.5 on average.
|>
|> But if one makes the impossible guess of 1289, then one gets it in
|> 2,2,2,or 3 more guiesses, which is an average of only 2.25 more guesses.
|>
|>
|> But there's still the open problem:- can this type of situation arise
|> as part of an optimal guessing strategy? My wild uninformed guess is NO.
|>
on your second guess, and score 3 blacks no whites again eg
6789 XXX X=black=right digit in right position
5789 XXX O=white=right dight in wrong position
????
The possible solutions are N789 where N=1,2,3,4,7,8 or 9. The situation is
a severe version of what you described above.
No possible is good on the second guess- you have at best a 4/36 chance of
getting a response other than 2 blacks or 3 blacks. An impossible such
as 9123 or 8192 must be better.
Another small example :
1234 XXOO
The possibles are 1243,1324,1432,2134,3214,4231. If you play a possible, you will
get the solution in on average 2.5 goes, as you are likely to score XOOO each
time. The impossible 4232 gives 2.33 goes.