coeve@ark.UUCP (Dirk van Coeverden) (02/21/85)
Expires:
References:
Sender:
Reply-To: coeve@ark.UUCP (Mike Jonkmans)
Followup-To:
Distribution:
Organization: VU Informatica, Amsterdam
Keywords:
[Not as easy at it looks like!]
I will describe the game of master mind to you first :
There are four places in which six possible colors can be
placed these are not known to you (same colors are not allowed
for simplicity's sake).
You can guess a possible solution by naming four colors.
After you have guessed you get the following information :
A black point for each right color at the right place,
a white point for each right color but at a wrong place,
a zero for every other color.
This will continue until you have guessed all four colors at the
right place.
As the solution can't have two the same colors it is possible
for you to guess for example four red (but you will be
sure then not to have found the right solution).
My question to you all is who knows the best strategy and
in how many turns can you find the solution by using
this strategy (So I am asking for the minimum number
of turns in which you always get the right answer).
Mike Jonkmans
{seismo|decvax|philabs}!mcvax!vu44!ark!coeve
or
coeve@ark.UUCP
P.S. I ask you this question, because I can't solve it
myself (and so the whole faculty of physics)
and because sombody somewhat rudely
stated that it always can be done within five
turns which I believe but it is only empirical.davis@hplabs.UUCP (Jim Davis) (03/05/85)
While back in college I did a class project in an AI class
on MasterMind. I thought you might like to hear a few of my
conclusions. I handled the true game, i.e. the same color
is allowed to be multiply present in both the solution and in
any guess. I used three heuristics in determining the next
move that should be used in breaking the puzzle:
1) The very first move is made by guessing a random permutation
of <1><1><2><3>, for randomly chosen colors <1>, <2>, and <3>.
2) At any point the next move should always be a possible solution.
3) The next move should be chosen so as to minimize the size
of the largest set of posibilities remaining after the reply
to that move.
I would like to emphasize that the above are heuristics.
I can conceive of the posibility that the optimal move at
some point might violate any of these criteria. In my paper
I have a large discussion on these criteria, why they are
useful, and why they are not all powerful.
Here are some statistics on the game that one derives
from these heuristics. If we assume (not a good assumption)
that the code was chosen randomly from the 1296 possibilities
then we get the following distribution of events.
Number of moves to solve pattern: 1 2 3 4 5 6 >=7
Number of patterns solved: 1 13 102 482 615 83 0
Percentage of patterns solved: .1 1.0 7.9 37.2 47.5 6.4 0
(Due to round off, figures do not add to 100%)
Average number of moves to solve randomly chosen pattern: 4.501
The program that I produced played as well as any human
that I found to challenge it. Notice that since human players
do not necessarily choose their patterns at random, I have
ignored a major source of possible play improvement.
Thus I can guarentee to solve the (unrestricted) puzzle
in six moves. Since only 6.4% of the possibilities require
all 6 moves I can well imagine that an optimal solution (1)
to the restricted (2) puzzle should be easily solvable in
5 moves. I hope this helps you out.
Jim Davis
> I will describe the game of master mind to you first :
> There are four places in which six possible colors can be
> placed these are not known to you (same colors are not allowed
> for simplicity's sake).
> You can guess a possible solution by naming four colors.
> After you have guessed you get the following information :
> A black point for each right color at the right place,
> a white point for each right color but at a wrong place,
> a zero for every other color.
> This will continue until you have guessed all four colors at the ght place.
> As the solution can't have two the same colors it is possible
> for you to guess for example four red (but you will be
> sure then not to have found the right solution).
>
> My question to you all is who knows the best strategy and
> in how many turns can you find the solution by using
> this strategy (So I am asking for the minimum number
> of turns in which you always get the right answer).
>
> Mike Jonkmans
> {seismo|decvax|philabs}!mcvax!vu44!ark!coeve
> or
> coeve@ark.UUCP
> P.S. I ask you this question, because I can't solve it myself (and so
> the whole faculty of physics) and because sombody somewhat rudely
> stated that it always can be done within five turns which I believe
> but it is only empirical.
--
----------------------------------
Jim Davis (James W Davis)
Email: {any_of_the_biggies} !hplabs!davis
Arpa: davis%hp-labs@csnet-relay
----------------------------------