Conference rusure::math

Don't everyone jump at this problem at once!  Gosh folks, it's
been around since last October, and no one's taken even a nibble.

Anyway, I've written a program for evaluating Mastermind guess sets.
You run it like this:

$ mcr me:mset 1123 2345 6262 5514

Eval = 500/1296

What that answer means is that if you represent the six possible colors
in Mastermind as 1,2,3,4,5 and 6, and you make the four guesses
1123, 2345, 6262, 5514, then depending on what the secret combination
is, you'll get one of 500 different sets of responses, out of the
possible 1296 possible secret combinations (6*6*6*6).

If we can find a set of guesses that evaluates to 1296/1296, then
such a set of guesses in Mastermind would allow the secret combination
to be known precisely no matter what it was !

How close to such a perfect guess set can we come, in the fewest number
of guesses?

My experience from playing Mastermind is that if I get scores to
my guesses as I go along, I can usually get the answer in 5 or 6 guesses
tops.  So I'm wondering if 6 cleverly chosen guesses can uniquely
determine the secret colors no matter what they are.

Here are some more examples:

$ mcr me:mset 1123 2345 6262 5514 4413

Eval = 875/1296


$ mcr me:mset 1123 2345 6262 5514 4413 4421

Eval = 981/1296


$ mcr me:mset 1123 2345 6262 5514 4414 4421

Eval = 1018/1296


$ mcr me:mset 1123 2345 6262 5515 4414 4421

Eval = 1024/1296


$ mcr me:mset 1123 2341 6262 5515 4414 4421

Eval = 975/1296


How close can you get to 1296/1296 ????


If you want to try the program, I've posted it at the end of this message.
The above examples show how to run it once you've compiled it.  I use logical
name "me:", but of course you can choose something different.

Compile the program with

	$ cc mset
	$ link mset,sys$input/option
	sys$share:vaxcrtl.exe/share

Program follows.  Enjoy!  /Eric

#define max_color 6

char score (c1, c2, test)
{
char p1[4] = {c1/1000, (c1/100) % 10, (c1%100)/10, c1%10};
char p2[4] = {c2/1000, (c2/100) % 10, (c2%100)/10, c2%10};

char e[4] = {p1[0]==p2[0],p1[1]==p2[1],p1[2]==p2[2],p1[3]==p2[3]};

int imp = 1 + max_color;

int i, j;

int a = 0;

int ez = 0;

for (i=0; i<=3; i++) if (e[i]) p1[i]=imp++, p2[i]=imp++, ez++;

for (i=0; i<=3; i++) for (j=0; j<=3; j++)
    if (i!=j) if (p1[i]==p2[j]) a++, p1[i]=imp++, p2[j]=imp++;

if (test) printf ("c1 = %d, c2 = %d, e = %d, a = %d\n", c1, c2, ez, a);

return ez*2 + a;
}

response (answer, n_guesses, guesses) int guesses[];
{

	int result = 0;

	int i;

	for (i=0; i<n_guesses; i++)
	{
	result <<= 4;
	result += score (answer, guesses[i], 0);
	}

	return result;
}

#define max_answers max_color*max_color*max_color*max_color
eval (n_guesses, guesses) int guesses[];
{

	int answers[max_answers];

	int i,j;

	int n_responses=0, next_response, responses[max_answers];

	char unique_flag;

	for (i=0; i<max_answers; i++)
	{
	int digits[4] = {i};

	for (j=0; j<=3; j++)
	    j <=3 ? (digits[j+1] = digits[j]/max_color):0,
	    digits[j] = digits[j]%max_color + 1;

	answers[i] = ((digits[0]*10 + digits[1])*10 + digits[2])*10 + digits[3];
	}

	for (i=0; i<max_answers; i++)
	{
	next_response = response (answers[i], n_guesses, guesses);

	unique_flag = 1;

	for (j=0; j<n_responses; j++)
	if (unique_flag = (next_response != responses[j])) continue;
	else break;

	if (unique_flag) responses[n_responses++] = next_response;
	}

	printf ("Eval = %d/%d\n", n_responses, max_answers);
}

main(argc, argv) int argv[];

{

#define max_guesses 20
#define max_chars 500

char i_buf[max_chars];

int guesses[max_guesses];

int i;

int n_guesses;

i = 0;

n_guesses = argc-1 <= max_guesses? argc-1 : max_guesses;

if (n_guesses > 8)

	{

	printf ("Sorry, only 8 guesses allowed, I'll use first 8.\n");
	n_guesses = 8;

	}

for (i=0; i<n_guesses; i++)

	{

	if (sscanf (argv[i+1], "%d", &guesses[i]) != 1)
	printf ("Didn't understand \"%s\", try again.\n", argv[i+1]), exit(0);


	}

	eval (n_guesses, guesses);

}

    I have used a program similar to .-1 to prove that there
    exists a set of six guesses you can make in the game of
    Mastermind, so that NO MATTER what the secret colors are,
    once you've been given the responses to the special set
    of six guesses, you'll be able to deduce EXACTLY what
    the secret colors are.
    
    If we assume the six colors are labeled 1,2,3,4,5 and 6, here
    are the strategic six guesses:
    
    	3211 3542 2665 4623 5356 4443
    
    What this means is, with the above six guesses, every possible
    secret combination will cause a DIFFERENT set of responses.
    For example, if the secret combination is 1234, the responses
    will be:
    
    	xx
    	oo   ooo  o    ooo  o    oo
    
    where x means exact, and o means almost.  For NO other secret
    possibility other than 1234 will the responses be exactly like
    this.
    
    If we speak a rationale for this set of six guesses, it
    might sound like this.  First, guess two colors the same, and
    the other two unique:
    
       	3211
    
    Now keep one of the unique ones the same for some control,
    move the other unique one to a different position, and introduce
    two new colors:
    
    	3542
    
    Now throw away one of the original uniques, move the other unique
    to yet another column, and introduce the remaining color.
    
    	etc.
    
    Any more interest yet ?  I think it's fascinating.
            
    /Eric

     Is there a better way to use the six answers than to
     look up the answer in a table?  Do you think a person
     could learn to solve it in this way?
     
     Dan

I don't play mastermind and I'm not a maths purist, but would't the 
following be just as efficient?

1234
2345
3456
4561
5612
6123

I would think that results from this would be easier to see. I expect that 
I could deduce the actual series here.

If any row has four x's we have our answer.

If there are no rows with more than one x and o then the intersection of the 
four rows with one x or o is the single number that is repeated four times.

If there is a row with no x's or o's then the two numbers not in that row 
are the numbers in the series. One will be repeated twice or they both will 
repeat once. 

OR 

If there are no rows with a total of three x's or o's then there are only 
two numbers in the series. These will be the intersection of the three 
guesses with a total of two x's and o's.

If there are only two rows with a total of three x's and o's then the 
intersection of these two will tell us three of our numbers. it will also 
tell us that one of these numbers repeats.

If there are four rows with a total of three x's and o's then the numbers 
that appear three times in these four gueses are the numbers.

I think that should always give us the numbers. The positioning would then 
be simple.

I am working on a simple Pascal program to do this, and will post it if I'm 
not beatn to it.

Cheers,

Mark.

I don't know why Mark's guesses (in .4) don't work, but Eric's program (in .1)
gives it an 'efficiency' of 862/1296 -- short of the 1296/1296 that's wanted.

		3153		6426
    
1234		o o		 o o
2345		 o o		o o
3456		x x		 x x
4561		 o o		o o
5612		o o		 o o
6123		 x x		x x

>  If there are no rows with a total of three x's or o's then there are only 
>  two numbers in the series. These will be the intersection of the three 
>  guesses with a total of two x's and o's.

    ???
    
    John

Reply .4 does *not* give an answer.  That answer has at least
one set of responses for which at least FOUR different secret
combinations is possible.

The answer we seek is one for which each possible set of responses
has only ONE possible secret combination.

At the end of this reply I've posted the latest version of my program.
To try Bradley's wrong answer, you'd store the program somewhere, such
as in logical directory ME:MSET.EXE, and say to dcl:

	$ mcr me:mset 1234 2345 3456 4561 5612 6123

The program reveals

	eval = 1083/1296, big partition = 4, guesses = 1234 2345 3456...

This means that depending on the secret combination, Bradley's guesses
would produce only 1083 different responses, meaning that there are
213 different possible secret combinations that share a set of
responses with at least one other combination, in which case you would
NOT know what the secret combination is.

Furthermore, there's at least one response set you could get for
which there are at least FOUR different secret combinations and you
still wouldn't know which of those four is the one.

Does this make sense?

/Eric

Here's the latest version of the program.  You can say

	$ mcr me:mset 0

if you want it to search for the best combo, printing out better
and better answers as it goes (takes about an hour to run, or two, or three,
depending on your vax)

#define max_color 6

#define max_answers max_color*max_color*max_color*max_color

#define max_guesses 20

#define max_chars 500

int answers[max_answers];

int c_to_dec[max_answers*1000+max_answers*100+max_answers*10+max_answers];

char scores[max_answers][max_answers];

char slow_score (c1, c2)
{
char p1[4] = {c1/1000, (c1/100) % 10, (c1%100)/10, c1%10};
char p2[4] = {c2/1000, (c2/100) % 10, (c2%100)/10, c2%10};

char e[4] = {p1[0]==p2[0],p1[1]==p2[1],p1[2]==p2[2],p1[3]==p2[3]};

int imp = 1 + max_color;

int i, j;

int a = 0;

int ez = 0;

for (i=0; i<=3; i++) if (e[i]) p1[i]=imp++, p2[i]=imp++, ez++;

for (i=0; i<=3; i++) for (j=0; j<=3; j++)
    if (i!=j) if (p1[i]==p2[j]) a++, p1[i]=imp++, p2[j]=imp++;

if (ez==4 && a==0) ez=3, a=1;
else if (ez==0 && a==4) ez=3, a=2;

return (ez<<2) + a;
}

#define fast_score(c1, c2)(						\
	scores[c_to_dec[c1]][c_to_dec[c2]] == -1 ?			\
	(scores[c_to_dec[c1]][c_to_dec[c2]] = slow_score (c1,c2)):0,	\
	scores[c_to_dec[c1]][c_to_dec[c2]])

response (answer, n_guesses, guesses) int guesses[];
{

	int result = 0;

	int i;

	for (i=0; i<n_guesses; i++)
	{
	result <<= 4;
	result += fast_score (answer, guesses[i]);
	}

	return result;
}

int eval (n_guesses, guesses, largest_part_size) int guesses[],
	    *largest_part_size;
{

	int i,j;

	int n_responses, responses[max_answers], popularity[max_answers];

	n_responses = 0;

	for (i=0; i<max_answers; i++)
	{
	responses[n_responses] = response (answers[i], n_guesses, guesses);
	popularity[n_responses] = 0;

	for (j=0; j<=n_responses; j++)
	if (responses[j]==responses[n_responses])
	    {
	    popularity[j]++;
	    break;
	    }
	if (j==n_responses) n_responses++;
	}

	*largest_part_size=0;
	for (i=0; i<n_responses; i++)
	    if (popularity[i] > *largest_part_size) *largest_part_size =
		popularity[i];

	return n_responses;
}

print_result (eval, n_guesses, guesses, part_size) int guesses[max_guesses];

{
	int i;

	printf ("\nEval = %d/%d, big partition = %d, ", eval, max_answers,
	    part_size);
	printf ("guesses (%d) = ", n_guesses);

	for (i=0; i<n_guesses; i++) printf ("%d ", guesses[i]);

	printf ("\n\n");
}

compute_best ()

{

	int i;

	int n_guesses;

	int guesses[max_guesses], best_guesses[max_guesses];

	int best_eval=0, new_eval;

	for (n_guesses=1; n_guesses<=max_guesses; n_guesses++)
	{
	int small_part_size = max_answers, part_size;

	for (i=0; i<max_answers; i++)
	{
	guesses[n_guesses-1] = answers[i];

	new_eval = eval (n_guesses, guesses, &part_size);

	if (new_eval > best_eval ||
	    new_eval==best_eval && part_size<small_part_size)

	{
	best_eval = new_eval;
	small_part_size = part_size;
	best_guesses[n_guesses-1] = answers[i];
	print_result (best_eval, n_guesses, best_guesses, part_size);
	}
	}
	guesses[n_guesses-1] = best_guesses[n_guesses-1];
	printf (".\n");

	if (small_part_size==1) exit(1);
	}
}

main(argc, argv) int argv[];

{

char i_buf[max_chars];

int guesses[max_guesses];

int i, j;

int n_guesses;

	for (i=0; i<max_answers; i++)
	{
	int digits[4] = {i};

	for (j=0; j<=3; j++)
	    j <=3 ? (digits[j+1] = digits[j]/max_color):0,
	    digits[j] = digits[j]%max_color + 1;

	answers[i] = ((digits[0]*10 + digits[1])*10 + digits[2])*10 + digits[3];
	c_to_dec[answers[i]] = i;
	}

	for (i=0; i<max_answers; i++)
	for (j=0; j<max_answers; j++) scores[i][j] = -1;

i = 0;

n_guesses = argc-1 <= max_guesses? argc-1 : max_guesses;

if (n_guesses > 8)

	{
	printf ("Sorry, only 8 guesses allowed, I'll use first 8.\n");
	n_guesses = 8;
	}

for (i=0; i<n_guesses; i++)

	{
	if (sscanf (argv[i+1], "%d", &guesses[i]) != 1)
	printf ("Didn't understand \"%s\", try again.\n", argv[i+1]), exit(0);

	if (i!=0 || guesses[i]!=0)
	if (
	    guesses[i]%10 < 1 || guesses[i]%10 > 6 ||
	    guesses[i]/10%10 < 1 || guesses[i]/10%10 > 6 ||
	    guesses[i]/100%10 < 1 || guesses[i]/100%10 > 6 ||
	    guesses[i]/1000 < 1 || guesses[i]/1000 > 6)
	printf("Guess \"%s\" must be 4 digits, each 1 through 6.\n", argv[i+1]),
	    exit(0);
	}

	if (n_guesses==1 && guesses[0]==0) compute_best ();
	else
	    {
	    int part_size;
	    int eval_num = eval (n_guesses, guesses, &part_size);
	    print_result (eval_num, n_guesses, guesses, part_size);
	    }
}

I think that my set of guesses will only work if there are no repeating 
numbers. I'll think about this.

I am beginning to think that six guesses may not be enough to know exactly 
when numbers may be repeated.

Intersesting problem eh?

Cheers,

Mark.

     re .8
     
>>   I am beginning to think that six guesses may not be enough to know exactly
>>   when numbers may be repeated.
     
     Eric already gave a solution with six guesses in an earlier
     reply.
     
     Dan

    Here's even more embarrassment regarding the guess set
    
    	1234 2345 3456 4561 5612 6123
    

    
    
    The 6123 adds absolutely no information !  You're just as well
    off without it.
    
    
    Instead of 6123, the best thing to replace it with is 5321.
    However, even that doesn't uniquely identify the secret combination.
    In other words
    
    	1234 2345 3456 4561 5612 5321
    
    does not isolate the answer.
    
    /Eric

    I suspect that a 5-element guess set will suffice!!!  I base this
    suspicion on the following guess set, which very nearly suffices:

	1123 2445 3652 4535 3264

    It identifies all but 58 of 1296 combinations, and the largest partition
    has only 2 elements.  It can be made complete with the sixth guess: 6251.

    Even better:

	1123 1244 2535 2646 5336  (note all the 'doubles')
    or
	1123 1442 2533 5456 5662
    or
	1123 1242 4551 6343 6456
    or
	1123 1256 2636 3545 4452

    These identify all but 28 of 1296 combinations, and the largest partition
    has only 2 elements.

    I think it's worth mounting an exhaustive search for a perfect 5-set.

If a 5-guess set is available, it strikes me that one of the 6 numbers 
should be available only by inference, while the rest should be available 
even in the worst of conditions (two 'o' replies on each guess). So I
suggest
	1123 3242 5334 4451 2515
which is rich in doubles and has a check for each digit in each position
(6 by negative inference). Someone want to evaluate this for me?

Lynn Yarbrough 

The 5-guess set from 775.13 partitions the 1296 combinations into 1018
parts, 790 of which contain 1 member (yea!), 184 of which contain 2
members, 39 of which contain 3 members, 4 with 4, and one set contains
5 members.

The 'rating' scheme I've been using would give this the evaluation:

	     2        2       2      2      2
	790*1  + 184*2  + 39*3  + 4*4  + 1*5  - 1296 = 670 

    I've included the latest version of my program.  It has a new feature.
    You can ask it to evaluate the best set, given a starting point.
    you do this by including a "0" at the end of the list.
    
    For example, to evaluate someone's suggested numbers (edp?) a few
    replies back, here's a sample of the beginning of the run:
    
$ MCR ME:MSET 1123 2445 3652 0

Eval = 641/1296, big partition = 9, guesses (4) = 1123 2445 3652 1111 


Eval = 811/1296, big partition = 7, guesses (4) = 1123 2445 3652 1112 


Eval = 856/1296, big partition = 6, guesses (4) = 1123 2445 3652 1114 


Eval = 887/1296, big partition = 6, guesses (4) = 1123 2445 3652 1116 


Eval = 928/1296, big partition = 6, guesses (4) = 1123 2445 3652 1134 


Eval = 936/1296, big partition = 6, guesses (4) = 1123 2445 3652 1146 


Eval = 959/1296, big partition = 6, guesses (4) = 1123 2445 3652 1164 


Eval = 984/1296, big partition = 5, guesses (4) = 1123 2445 3652 1215 

%JBC-F-JOBABORT, job aborted during execution
    

    
    
    Here's a listing of the MSET program that lets you do the evaluations:
    
/*
 * Program to compute how good a Mastermind guess is, or to find best
 * set of Mastermind guesses from a partial guess list.
 *
 * Author:  Eric Osman, Digital, 6/1/88
 *
 * Examples of usage:
 *
 *	$ cc mset
 *	$ link mset, sys$input/opt
 *	sys$library:vaxcrtl/share
 *
 *	$ mcr me:mset 0		! computes best guess set
 *
 *	$ mcr me:mset 1123 1234 2345	! computes how good this set is
 *
 *	$ mcr me:mset 1111 0	! computes best set including 1111
 */

#define max_color 6

#define max_answers max_color*max_color*max_color*max_color

#define max_guesses 8 /* limited by byte-stuffing in eval routine */

#define max_chars 500

int answers[max_answers];

int c_to_dec[max_answers*1000+max_answers*100+max_answers*10+max_answers];

char scores[max_answers][max_answers];

char slow_score (c1, c2)
{
char p1[4] = {c1/1000, (c1/100) % 10, (c1%100)/10, c1%10};
char p2[4] = {c2/1000, (c2/100) % 10, (c2%100)/10, c2%10};

char e[4] = {p1[0]==p2[0],p1[1]==p2[1],p1[2]==p2[2],p1[3]==p2[3]};

int imp = 1 + max_color;

int i, j;

int a = 0;

int ez = 0;

for (i=0; i<=3; i++) if (e[i]) p1[i]=imp++, p2[i]=imp++, ez++;

for (i=0; i<=3; i++) for (j=0; j<=3; j++)
    if (i!=j) if (p1[i]==p2[j]) a++, p1[i]=imp++, p2[j]=imp++;

if (ez==4 && a==0) ez=3, a=1;
else if (ez==0 && a==4) ez=3, a=2;
else if (ez==0 && a==0) ez=3, a=3;

return (ez<<2) + a;
}

#define fast_score(c1, c2) ((*(s0= &scores[c_to_dec[c1]][c_to_dec[c2]]) \
  == 0) ? (*s0 = slow_score (c1,c2)):*s0)

response (answer, n_guesses, guesses) int guesses[];
{

	int result = 0;

	int i; char *s0;

	for (i=0; i<n_guesses; i++)
	{
	result <<= 4;
	result += fast_score (answer, guesses[i]);
	}

	return result;
}

int eval (n_guesses, guesses, largest_part_size) int guesses[],
	    *largest_part_size;
{

	int i,j;

	int n_responses, responses[max_answers], popularity[max_answers];

	n_responses = 0;

	for (i=0; i<max_answers; i++)
	{
	responses[n_responses] = response (answers[i], n_guesses, guesses);
	popularity[n_responses] = 0;

	for (j=0; j<=n_responses; j++)
	if (responses[j]==responses[n_responses])
	    {
	    popularity[j]++;
	    break;
	    }
	if (j==n_responses) n_responses++;
	}

	*largest_part_size=0;
	for (i=0; i<n_responses; i++)
	    if (popularity[i] > *largest_part_size) *largest_part_size =
		popularity[i];

	return n_responses;
}

print_result (eval, n_guesses, guesses, part_size) int guesses[max_guesses];

{
	int i;

	printf ("\nEval = %d/%d, big partition = %d, ", eval, max_answers,
	    part_size);
	printf ("guesses (%d) = ", n_guesses);

	for (i=0; i<n_guesses; i++) printf ("%d ", guesses[i]);

	printf ("\n\n");
}

compute_best (partial_n_guesses, best_guesses) int best_guesses[max_guesses];

{

	int i;

	int n_guesses;

	int guesses[max_guesses];

	int best_eval, new_eval;

	int small_part_size;

	for (i=0; i<partial_n_guesses; i++)
	    guesses[i] = best_guesses[i];

	best_eval = eval (partial_n_guesses, guesses, &small_part_size);

	for (n_guesses=partial_n_guesses+1; n_guesses<=max_guesses; n_guesses++)
	{
	int part_size;

	for (i=0; i<max_answers; i++)
	{
	guesses[n_guesses-1] = answers[i];

	new_eval = eval (n_guesses, guesses, &part_size);

	if (new_eval > best_eval ||
	    new_eval==best_eval && part_size<small_part_size)

	{
	best_eval = new_eval;
	small_part_size = part_size;
	best_guesses[n_guesses-1] = answers[i];
	print_result (best_eval, n_guesses, best_guesses, part_size);
	}
	}
	guesses[n_guesses-1] = best_guesses[n_guesses-1];
	printf (".\n");

	if (small_part_size==1) exit(1);
	}
}

main(argc, argv) int argv[];

{

char i_buf[max_chars];

int guesses[max_guesses];

int i, j, k, l;

int n_guesses;

int index = 0;

	for (i=1; i<=6; i++)
	for (j=1; j<=6; j++)
	for (k=1; k<=6; k++)
	for (l=1; l<=6; l++)
	{
	int code = ((i*10 + j)*10 + k)*10 + l;
	answers[index] = code;
	c_to_dec[code] = index++;
	}

i = 0;

n_guesses = argc-1 <= max_guesses? argc-1 : max_guesses;

if (n_guesses > max_guesses)

	{
	printf ("Sorry, only %d guesses allowed, I'll use first %d.\n",
	    max_guesses, max_guesses);
	n_guesses = max_guesses;
	}

for (i=0; i<n_guesses; i++)

	{
	if (sscanf (argv[i+1], "%d", &guesses[i]) != 1)
	printf ("Didn't understand \"%s\", try again.\n", argv[i+1]), exit(0);

	if (i!=n_guesses-1 || guesses[i]!=0)
	if (
	    guesses[i]%10 < 1 || guesses[i]%10 > 6 ||
	    guesses[i]/10%10 < 1 || guesses[i]/10%10 > 6 ||
	    guesses[i]/100%10 < 1 || guesses[i]/100%10 > 6 ||
	    guesses[i]/1000 < 1 || guesses[i]/1000 > 6)
	printf("Guess \"%s\" must be 4 digits, each 1 through 6.\n", argv[i+1]),
	    exit(0);
	}

	if (guesses[n_guesses-1]==0) compute_best (n_guesses-1, guesses);
	else
	    {
	    int part_size;
	    int eval_num = eval (n_guesses, guesses, &part_size);
	    print_result (eval_num, n_guesses, guesses, part_size);
	    }
}
    

    Edp asked about possible solutions that leave out a color, and infer
    it instead.
    
    I wrote a program to investigate that.  It did not find a solution
    in less than 7 guesses.  The program is set up to find the best
    solutions that DON'T contain the digit "6".
    
    Here's the best 6-guess solution it came up with:
    
Eval = 1273/1296, big partition = 2, guesses (6) = 1123 2453 3515 4134 4322 5541

    Here's the smallest complete solution it found:

Eval = 1296/1296, big partition = 1, guesses (7) =
    1123 2453 3515 4134 4322 5541 4235
    
    
    /Eric

Eric,

How come the first two versions of your program give different answers to 
the same series?

**************************************************************************
$ mcr usersc_5:[bradley.work]mset.exe 1123 3242 5334 4451 2551
Eval = 1069/1296, big partition = 4, guesses (5) = 1123 3242 5334 4451 2551
**************************************************************************
$ mcr usersc_5:[bradley.work]mset.exe;-1 1123 3242 5334 4451 2551
Eval = 932/1296
**************************************************************************

By the way, your first program said that your winning six fails. :-)
Did yor program come up with these Guesses?

re: .13 Lynn,

Your guesses will fail for 1666 and 6166, or 6266 and 6662 etc.

Cheers,

Mark.

    Re .16:
    
    That wasn't me; it was Lynn in .13.  I'm thinking about the search
    program Gilbert suggested -- how do we restrict the search?  Also, what
    is the optimal strategy for _The Price is Right_ variation -- you have
    a fixed amount of time to make as many guesses as you wish, but making
    a guess requires an amount of time proportional to the distance from
    the origin of the right-most change from the previous guess plus an
    amount of time proportional to the number of changes from the previous
    guess. 
    
    
    				-- edp

    I apologize for previous versions of my program that contained bugs.
    
    Please only use the most recent version I posted for MSET.
    
    Thanks.
    
    /Eric

>                                        I'm thinking about the search
>   program Gilbert suggested -- how do we restrict the search?

    Certainly we can't try all 6^20 possible 5-guess sets!

    Suppose a 5-guess universal guess-set exists.  The following
    transformations produce another one:

	'Rename' or permute the 6 colors
	Reorder the 5 individual guesses
	Rearrange the 4 'columns'

    Let's define an ordering amoung guess-sets.  We'll use the obvious
    one -- write out the guess set (as we've been doing), and compare
    the strings.  We normalize a guess-set by transforming it onto the
    minimal one.  For example, every guess-set can be transformed into
    one (the inimal one) that starts with one of the guesses:

	1111
	1112
	1122
	1123
	1234

    The second guess is at the second level of the search tree.  These
    are also limited:  (read on, there's more text at the end).

	1111 1111
	     1112
	     1122
	     1123
	     1234
	     2222
	     2223
	     2233
	     2234
	     2345
	1112 1112
	     1113
	     1121
	     1122
	     1123
	     1131
	     1132
	     1133
	     1134
	     1211
	     1212
	     1213
	     1221
	     1222
	     1223
	     1231
	     1232
	     1233
	     1234
	     2112	(but not 2111)
	     2113
	     ...
	     2345
	1122 1122
	     ...
	1123 1123
	     1124
	     1131
	     1132	(but not 1133)
	     1133
	...

    And so on.  Note that if the first guess is 1234, then none of the
    following guesses may have duplicate colors (since that could then
    be transformed into a 'smaller' guess-set, hence, it's not normalized).

    Also, determining whether a guess-set is normalized is not as expensive
    as it may seem.  Hint: you'd start by determining the numbers of
    duplicate colors in each guess. 

    I'd suggest that this approach proceed through the first three levels;
    the first three guesses.  Then assess the situation.

    The guesses partition the 6^4 possible secret combinations into
    equivalence classes. It may be that one of those classes contains so
    many combinations that it's impossible for two more guesses to
    completely distinguish them (i.e., if there are than 14^2 combinations,
    two more guesses can't possibly distinguish amoung them all -- the
    actual value is smaller than 14^2).  This helps prune the search
    tree (BTW, this pruning could be done before the third level as well).

    Of course, you could be more clever and examine the distribution amoung
    the partitions to determine whether the number of remaining guesses may
    suffice to completely distingush them.  (How do you measure the
    information content available from a guess?  Or the information needed
    to distinguish amoung the elements in each of the partitions?)

    Anyway, I'd estimate the whole search can be done in a couple MIP-days.

   That question of normalizing guesses is an interesting and subtle
    one.
    
    Consider these two examples:
    
    	3211 3542 2664
    
    		This divides space state into 491 parts, with largest
    		partition having 15 elements.
    
    	3211 3542 2665
    
    		This divides space state inrto 496 parts, with largest
    		partition having 14 elements.
    
    To the casual observer, these two guess sets look the same.  The
    digits 4 and 5 are mentioned in the second guess.  In the third
    guess, we put one of those two digits in the last column.  Why
    should it matter which we choose ?
    
    /Eric

     Re .21         3211 3542 2664
                vs  3211 3542 2665
     
     I would guess that the 5 and the 4 do not occur
     "symmetrically" in the second guess.
     
     The five was used in the second position, in which the
     other guesses had a lone two and a doubled six.  The
                         ^^^^
     four was in the third position, in which the other guesses
     had a doubled one and a doubled six.
           ^^^^^^^
     
     Change the first guess from 3211 to 3213.  Are they the
     same now? ... [pause as I run your program] ... uh, er,
     um, ...
     
          3213 3542 2664:  486/1296, big partition = 12
          3213 3542 2665:  487/1296, big partition = 15
     
     Never mind.  :-)
     
     On the other hand, there is
     
          3213 3452 2664:  487/1296, big partition = 15
          3213 3542 2665:  487/1296, big partition = 15
     
     in which the four and five are just swapped, and these
     are indeed the same, as they should be.
     
     Dan

I have written a pascal program to show why a particular guess set fails.

For example, the last set of 5 guesses given by .12 clt::gilbert show 14 
patterns that generate a combination the same as another preceding pattern.

(N.B. the pears of numbers indicate the number correct, and the number 
correct but in the wrong position for each guess. ie X's,O's)

$ run tmp
Enter the number of guesses.
5
Enter numbers for guess 1.
1 1 2 3
Enter numbers for guess 2.
1 2 5 6
Enter numbers for guess 3.
2 6 3 6
Enter numbers for guess 4.
3 5 4 5
Enter numbers for guess 5.
4 4 5 2
1123 1256 2636 3545 4452 
2225 failed with 1644 0,2 1,0 1,0 1,1 1,0 .
2321 failed with 2313 0,1 0,1 1,1 0,2 1,2 .
3221 failed with 3213 0,1 1,0 0,2 1,1 1,2 .
4341 failed with 3414 1,1 1,1 0,1 0,1 0,2 .
5142 failed with 4521 1,2 1,1 0,1 0,3 1,1 .
5222 failed with 1464 1,1 0,1 0,1 1,1 1,0 .
5441 failed with 4514 1,2 1,1 0,0 0,2 0,1 .
5642 failed with 2465 1,2 1,1 1,1 0,3 0,1 .
6116 failed with 1661 0,0 0,0 1,1 1,1 1,1 .
6233 failed with 2263 0,1 0,1 1,2 1,1 1,1 .
6332 failed with 2362 1,0 0,1 1,2 0,2 0,2 .
6345 failed with 3564 0,2 2,1 0,2 0,2 0,1 .
6415 failed with 4561 1,1 1,1 0,1 0,3 0,1 .
6654 failed with 5466 1,1 0,2 1,1 1,1 0,0 .
There were 14 failures in this series.

Does this help?

Cheers,

Mark.

************* Program Follows ***************************

program tmp(input,output);
const
    col = 6;
var
    filter : array [1..6,1..4] of integer;
    i,j,k,l,m,n : integer;
    res : array [1..1296] of integer;
    fails : integer;
    top : integer;
value
    top := 6;
    filter := ((3,2,1,1),(3,5,4,2),(2,6,6,5),(4,6,2,3),(5,3,5,6),(4,4,4,3));
{    filter := ((1,2,3,4),(2,3,4,5),(3,4,5,6),(4,5,6,1),(5,6,1,2),(6,1,2,3));}

procedure enter_series;
var
    i : integer;
begin
    writeln(output,'Enter the number of guesses.');
    readln(input,top);
    for i := 1 to top do
    begin
        writeln(output,'Enter numbers for guess ',i:1,'.');
        readln(input,filter[i,1],filter[i,2],filter[i,3],filter[i,4]);
    end;
end;

function calc_filter : integer;
var
    tmp,right,wrong,total,sub1,sub2 : integer;
    used,fused : array [1..4] of boolean;
    g : array [1..4] of integer;
begin
    g[1] := i;
    g[2] := j;
    g[3] := k;
    g[4] := l;

    total := 0;
    for sub1 := 1 to top do
    begin
        right := 0;
        wrong := 0;
        total := total * 15;
        for tmp := 1 to 4 do
        begin
            used[tmp] := g[tmp] = filter[sub1,tmp];
            fused[tmp] := used[tmp];
            if used[tmp] then right := right + 1;
        end;
        for tmp := 1 to 4 do { check wrongs }
        begin
            if not used[tmp] then
            begin
                sub2 := 0;
                repeat
                    sub2 := sub2 + 1;
                    if not fused[sub2] then
                    begin
                        if g[tmp] = filter[sub1,sub2] then
                        begin
                            used[tmp] := true;
                            fused[sub2] := true;
                            wrong := wrong + 1;
                        end;
                    end;
                until (sub2 = 4) or used[tmp];
            end;
        end;
{
writeln(output,i:1,j:1,k:1,l:1,' ',filter[sub1,1]:1,filter[sub1,2]:1,
        filter[sub1,3]:1,filter[sub1,4]:1,' right - ',
        right:1,' wrong - ',wrong:1);
}
        case right of
            0 : total := total + wrong;
            1 : total := total + 5 + wrong;
            2 : total := total + 9 + wrong;
            3 : total := total + 12 + wrong;
            4 : total := total + 14;
        end;
    end;
    calc_filter := total;
end;

procedure dump_pattern(k : integer);
var
i : integer;
n : array [1..6] of integer;
begin
    i := k;
    n[1] := i rem 15;
    i := i div 15;
    n[2] := i rem 15;
    i := i div 15;
    n[3] := i rem 15;
    i := i div 15;
    n[4] := i rem 15;
    i := i div 15;
    n[5] := i rem 15;
    i := i div 15;
    n[6] := i rem 15;
{
writeln(output,n[1]:1,' ',n[2]:1,' ',n[3]:1,' ',n[4]:1,' ',n[5]:1,' ',n[6]:1);
}
    for i := 1 to top do
    begin
        case n[i] of
            0 : write(output,'0,0 ');
            1 : write(output,'0,1 ');
            2 : write(output,'0,2 ');
            3 : write(output,'0,3 ');
            4 : write(output,'0,4 ');
            5 : write(output,'1,0 ');
            6 : write(output,'1,1 ');
            7 : write(output,'1,2 ');
            8 : write(output,'1,3 ');
            9 : write(output,'2,0 ');
            10 : write(output,'2,1 ');
            11 : write(output,'2,2 ');
            12 : write(output,'3,0 ');
            13 : write(output,'3,1 ');
            14 : write(output,'4,0 ');
        end;
    end;
end;

procedure dump_guess(n : integer);
var
    i,a,b,c,d : integer;
begin
    i := n - 1;
    d := i rem col + 1;
    i := i div col;
    c := i rem col + 1;
    i := i div col;
    b := i rem col + 1;
    i := i div col;
    a := i rem col + 1;
    write(output,a:1,b:1,c:1,d:1);
end;

function check_filter : boolean;
var
    n : integer;
begin
    if m < 2 then check_filter := true
    else begin
        n := 0;
        repeat
            n := n + 1;
        until (n = (m - 1)) or (res[m] = res[n]);
        if res[m] = res[n] then
        begin
            check_filter := false;
            write(output,i:1,j:1,k:1,l:1,' failed with ');
            dump_guess(n);
            write(output,' ');
            dump_pattern(res[n]);
            writeln(output,'.');
         end else check_filter := true;
     end;
end;

begin
    enter_series;
    for i := 1 to top do
    begin
        for j := 1 to 4 do write(output,filter[i,j]:1);
        write(output,' ');
    end;
    writeln(output);
    fails := 0;
    for i := 1 to 1296 do res[i] := 0;
    for i := 1 to col do
    for j := 1 to col do
    for k := 1 to col do
    for l := 1 to col do
    begin
        m := ((i-1)*col*col*col) + ((j-1)*col*col) + ((k-1)*col) + l;
        res[m] := calc_filter;
        if not check_filter then fails := fails + 1;
    end;
    writeln(output,'There were ',fails:1,' failures in this series.');
end.

re .23:
	Yes, it does help.  It took me a while to understand the output,
	though -- part of it seems backwards.  In dump_pattern, I think you
	want to change:

		for i := 1 to top do	-to-	for i := top downto 1 do

	Thanks.  That there are so many permutations suggests that it
	may be possible to prune a guess-set by (quickly) finding a failure
	(or multiple failures).

Article: 23113
From: rwi@dcs.glasgow.ac.uk (Dr Rob Irving)
Newsgroups: sci.math
Subject: Re: Mastermind
Message-ID: <1991Dec9.090852.23426@dcs.glasgow.ac.uk>
Date: 9 Dec 91 09:08:52 GMT
Organization: Glasgow University Computing Science Dept.
 
 
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.
 
*******************************************************************************
e-mail: rwi@dcs.glasgow.ac.uk@nsfnet-relay.ac.uk
 
Mail: Rob Irving,
      Computing Science Dept.,
      University of Glasgow,
      Glasgow G12 8QQ,
      SCOTLAND  
 
Phone: (0)41-339-8855 x 4478;    Home (0)389-841-638
       (suppress leading 0 from overseas)
*******************************************************************************