Play MasterMind Game

This is a reasonable attempt at playing the game of MasterMind. It tries to make optimal guesses to increase its likelihood of getting a correct answer in as few guesses as possible.

Guess 6 ->1 7 8 5
Green = 0  Yellow = 2
Since lost a Yellow, eliminate 1
Try changing #4 from 5 to 2

Green count is right digit, and right spot.
Yellow count is right digit, but wrong spot.

mm.c - source file

   1: /* Master Mind -- Steve O'Hara -- 1/3/94 */
   2: 
   3: #include <stdio.h>
   4: #include <stdlib.h>
   5: #include <ctype.h>
   6: #include <time.h>
   7: 
   8: 
   9: /* Some tough cases for Seed: 9491 14213 18368 56764 */
  10: 
  11: /* Averaged 11.84 tries across 500 games */
  12: 
  13: 
  14: /********* You can change these *********/
  15: 
  16: #define MAXSLOTS 10
  17: #define MAXNUMBERS 20
  18: 
  19: #define DEBUGSWITCH 0	/* 0 or 1 */
  20: #define PRINTANSWER 0	/* 0 or 1 */
  21: 
  22: 
  23: /********* Do not change these *********/
  24: 
  25: #define YES   1		/* For 'guess' */
  26: #define NO    2
  27: #define MAYBE 3
  28: 
  29: #define ALL   1		/* For re-entry to 'guess' */
  30: #define SOME  2
  31: #define NONE  3
  32: 
  33: #define DEBUG if (DEBUGSWITCH) printf
  34: 
  35: #define KNOW(s,g)									\
  36: 	for (i=0; i<slots; i++) state[i][g-1] = NO;		\
  37: 	for (j=0; j<numbers; j++) state[s][j] = NO;		\
  38: 	state[s][g-1] = YES
  39: 
  40: 
  41: unsigned int Seed;	/* Easier this way */
  42: FILE *out = NULL;
  43: 
  44: 
  45: static int RAND(int a, int b)
  46: {
  47: 	int		r;
  48: 	
  49: 	r = (int) (b * (rand()/(RAND_MAX+1.0))) + a;
  50: 	return r;
  51: } /* End of RAND */
  52: 
  53: 
  54: static int random (int *prev, int nprev, int n)
  55: {
  56: 	int		i;
  57: 	int		num;
  58: 	int		tries;
  59: 	
  60: 	tries = 0;
  61: 	while (tries++ < 5000)
  62: 	{
  63: 		num = RAND (1, n);
  64: 		for (i=0; i<nprev; i++)
  65: 		{
  66: 			if (num == prev[i]) break;	/* Duplicate */
  67: 		}
  68: 		if (i == nprev) return num;		/* Unique */
  69: 	}
  70: 	
  71: 	fprintf (stderr, "\nSeed = %u : Can't find a random number\n", Seed);
  72: 	exit (1);
  73: } /* End of random */
  74: 
  75: 
  76: static void initRand (int quiet)
  77: {
  78: 	char	ans[25];
  79: 
  80: 	if (quiet)
  81: 	{
  82: 		Seed = clock ();
  83: 	}
  84: 	else
  85: 	{
  86: 		printf ("\nEnter seed (return for random) -->");
  87: 		gets (ans);
  88: 		if (ans[0] != '\0')
  89: 		{
  90: 			sscanf (ans, "%u", &Seed);
  91: 		}
  92: 		else
  93: 		{
  94: 			Seed = clock ();
  95: 			printf ("Seed = %u\n", Seed);
  96: 		}
  97: 	}
  98: 	srand (Seed);		/* Initialize random number generator */
  99: } /* End of initRand */
 100: 
 101: 
 102: static void init (int *values, int slots, int numbers)
 103: {
 104: 	int		slot;
 105: 	
 106: 	for (slot=0; slot<slots; slot++)
 107: 	{
 108: 		values[slot] = random (values, slot, numbers);
 109: 	}
 110: 
 111: #if PRINTANSWER
 112: 	printf ("\nAnswer: ");
 113: 	for (slot=0; slot<slots; slot++)
 114: 	{
 115: 		printf (" %d", values[slot]);
 116: 	}
 117: 	printf ("\n");
 118: #endif
 119: } /* End of init */
 120: 
 121: 
 122: static void check (int *values, int *guesses, int slots, int *green, int *yellow)
 123: {
 124: 	int		i;
 125: 	int		slot;
 126: 	
 127: 	*green = 0;
 128: 	*yellow = 0;
 129: 	for (slot=0; slot<slots; slot++)
 130: 	{
 131: 		/* printf ("Guess[%d] = %d  Answer = %d\n", slot+1,
 132: 				guesses[slot], values[slot]); */
 133: 		if (values[slot] == guesses[slot]) *green += 1;
 134: 		else	/* See if right number, wrong place */
 135: 		{
 136: 			for (i=0; i<slots; i++)
 137: 			{
 138: 				/* Already know won't match for i == slot */
 139: 				if (values[i] == guesses[slot]) *yellow += 1;
 140: 			}
 141: 		}
 142: 	}
 143: } /* End of check */
 144: 
 145: 
 146: static int guessed (int number, int *guesses, int slots)
 147: {
 148: 	int		i;
 149: 	
 150: 	for (i=0; i<slots; i++)
 151: 	{
 152: 		if (guesses[i] == number+1) return 1;
 153: 	}
 154: 	return 0;
 155: } /* End of guessed */
 156: 
 157: 
 158: static void guess (int *guesses, int slots, int numbers, int green, int yellow)
 159: {
 160: 	int		deltaGreen;
 161: 	int		i, j;
 162: 	int		number;
 163: 	int		slot;
 164: 	int		tries;
 165: 
 166: 	static int code;
 167: 	static int prevGreen;
 168: 	static int prevGuess;
 169: 	static int prevSlot;
 170: 	static int prevYellow;
 171: 	static int slot1, slot2;
 172: 	static int state[MAXSLOTS][MAXNUMBERS];
 173: 	
 174: 	if (green < 0 || yellow < 0)	/* Very first guess */
 175: 	{
 176: 		for (slot=0; slot<slots; slot++)
 177: 		{
 178: 			guesses[slot] = random (guesses, slot, numbers);
 179: 			for (number=0; number<numbers; number++)
 180: 			{
 181: 				state[slot][number] = MAYBE;
 182: 			}
 183: 		}
 184: 		code = NONE;
 185: 		return;
 186: 	}
 187: 	
 188: 	/* Re-entering after a test? */
 189: 	if (code == SOME)
 190: 	{
 191: 		deltaGreen = green - prevGreen;	/* green changes */
 192: 		
 193: 		if (yellow > prevYellow)		/* Gained 1 yellow */
 194: 		{
 195: 			if (deltaGreen == 0)
 196: 			{
 197: 				printf ("Since gained a Yellow, eliminate %d\n", prevGuess);
 198: 				fprintf (out, "Since gained a Yellow, eliminate %d\n", prevGuess);
 199: 			}
 200: 			for (i=0; i<slots; i++) state[i][prevGuess-1] = NO;
 201: 		}
 202: 		else if (yellow < prevYellow)	/* Lost 1 yellow */
 203: 		{
 204: 			j = guesses[prevSlot];
 205: 			for (i=0; i<slots; i++) state[i][j-1] = NO;
 206: 			if (deltaGreen == 0)
 207: 			{
 208: 				printf ("Since lost a Yellow, eliminate %d\n", j);
 209: 				fprintf (out, "Since lost a Yellow, eliminate %d\n", j);
 210: 				guesses[prevSlot] = prevGuess;
 211: 				yellow = prevYellow;
 212: 			}
 213: 		}
 214: 		if (deltaGreen > 0)				/* Gained 1 green */
 215: 		{
 216: 			printf ("Since gained a Green, know #%d is %d\n",
 217: 						prevSlot+1, guesses[prevSlot]);
 218: 			fprintf (out, "Since gained a Green, know #%d is %d\n",
 219: 						prevSlot+1, guesses[prevSlot]);
 220: 			KNOW (prevSlot, guesses[prevSlot]);
 221: 		}
 222: 		else if (deltaGreen < 0)		/* Lost 1 green */
 223: 		{
 224: 			printf ("Since lost a Green, know #%d is %d\n",
 225: 						prevSlot+1, prevGuess);
 226: 			fprintf (out, "Since lost a Green, know #%d is %d\n",
 227: 						prevSlot+1, prevGuess);
 228: 			KNOW (prevSlot, prevGuess);
 229: 			guesses[prevSlot] = prevGuess;
 230: 			green = prevGreen;
 231: 			yellow = prevYellow;
 232: 		}
 233: 	}
 234: 	else if (code == ALL)
 235: 	{
 236: 		if (green - prevGreen == 2)			/* Gained 2 greens */
 237: 		{
 238: 			printf ("Since gained 2 Greens, know #%d is %d and #%d is %d\n",
 239: 					slot1+1, guesses[slot1],
 240: 					slot2+1, guesses[slot2]);
 241: 			fprintf (out, "Since gained 2 Greens, know #%d is %d and #%d is %d\n",
 242: 					slot1+1, guesses[slot1],
 243: 					slot2+1, guesses[slot2]);
 244: 			KNOW (slot1, guesses[slot1]);
 245: 			KNOW (slot2, guesses[slot2]);
 246: 		}
 247: 		else if (prevGreen - green == 2)	/* Lost 2 greens */
 248: 		{
 249: 			printf ("Since lost 2 Greens, know #%d is %d and #%d is %d\n",
 250: 					slot1+1, guesses[slot2],
 251: 					slot2+1, guesses[slot1]);
 252: 			fprintf (out, "Since lost 2 Greens, know #%d is %d and #%d is %d\n",
 253: 					slot1+1, guesses[slot2],
 254: 					slot2+1, guesses[slot1]);
 255: 			KNOW (slot1, guesses[slot2]);
 256: 			KNOW (slot2, guesses[slot1]);
 257: 			prevGuess = guesses[slot2];
 258: 			guesses[slot2] = guesses[slot1];
 259: 			guesses[slot1] = prevGuess;
 260: 			green = prevGreen;		/* Might not be needed */
 261: 			yellow = prevYellow;
 262: 		}
 263: 	}
 264: 	
 265: 	/* If all previous guesses were wrong, clear 'em and try again */
 266: 	if (green + yellow == 0)
 267: 	{
 268: 		printf ("All numbers guessed are wrong\n");
 269: 		fprintf (out, "All numbers guessed are wrong\n");
 270: 		for (i=0; i<slots; i++)
 271: 		{
 272: 			number = guesses[i]-1;	/* Can't be right anyplace */
 273: 			for (slot=0; slot<slots; slot++)
 274: 			{
 275: 				state[slot][number] = NO;
 276: 			}
 277: 		}
 278: 	}
 279: 	
 280: 	/* All the right numbers, some in the right place */
 281: 	else if (green + yellow == slots)
 282: 	{
 283: 		if (prevGreen + prevYellow < slots)
 284: 		{
 285: 			printf ("All numbers guessed are right, but in wrong order\n");
 286: 			fprintf (out, "All numbers guessed are right, but in wrong order\n");
 287: 		}
 288: 		for (slot=0; slot<slots; slot++)
 289: 		{
 290: 			if (green == 0)
 291: 			{
 292: 				number = guesses[slot]-1;
 293: 				state[slot][number] = NO;	/* Was Yellow */
 294: 			}
 295: 			
 296: 			for (number=0; number<numbers; number++)
 297: 			{
 298: 				if (!guessed (number, guesses, slots))
 299: 				{
 300: 					state[slot][number] = NO;
 301: 				}
 302: 			}
 303: 		}
 304: 		
 305: 		if (green > 0)	/* Only if have something good */
 306: 		{
 307: 			/* Find 2 non-Green columns and swap them */
 308: 			tries = 0;
 309: 			while (tries++ < 5000)
 310: 			{
 311: 				slot1 = RAND (0, slots);
 312: 				slot2 = RAND (0, slots);
 313: 				if (slot1 != slot2 &&
 314: 						state[slot1][guesses[slot2]-1] == MAYBE &&
 315: 						state[slot2][guesses[slot1]-1] == MAYBE)
 316: 				{
 317: 					prevGreen = green;
 318: 					prevYellow = yellow;
 319: 					prevGuess = guesses[slot2];
 320: 					guesses[slot2] = guesses[slot1];
 321: 					guesses[slot1] = prevGuess;
 322: 					code = ALL;
 323: 					printf ("Try swapping #%d with #%d\n",
 324: 								slot1+1, slot2+1);
 325: 					fprintf (out, "Try swapping #%d with #%d\n",
 326: 								slot1+1, slot2+1);
 327: 					DEBUG ("ALL: swap guess[%d] and guess[%d]\n",
 328: 								slot1+1, slot2+1);
 329: 					return;
 330: 				}
 331: 			}
 332: 			fprintf (stderr, "\nSeed = %u : unable to swap\n", Seed);
 333: 			exit (1);
 334: 		}
 335: 	}
 336: 	
 337: 	/* Still trying to find all the right numbers */
 338: 	else
 339: 	{
 340: 		/* Pick a non-Green column and change its value */
 341: 		tries = 0;
 342: 		while (tries++ < 5000)
 343: 		{
 344: 			slot = RAND (0, slots);
 345: 			for (number=0; number<numbers; number++)
 346: 			{
 347: 				if (state[slot][number] == YES) break;
 348: 			}
 349: 			if (number == numbers) break;	/* Not green yet */
 350: 		}
 351: 		if (tries == 5000)
 352: 		{
 353: 			fprintf (stderr, "\nSeed = %u : all correct ?!?!\n", Seed);
 354: 			exit (1);
 355: 		}
 356: 	
 357: 		tries = 0;
 358: 		while (tries++ < 5000)
 359: 		{
 360: 			number = RAND (0, numbers);
 361: 			if (!guessed (number, guesses, slots) &&
 362: 					state[slot][number] != NO)
 363: 			{
 364: 				break;
 365: 			}
 366: 		}
 367: 		if (tries == 5000)
 368: 		{
 369: 			fprintf (stderr, "\nSeed = %u : stuck in a loop\n", Seed);
 370: 			exit (1);
 371: 		}
 372: 	
 373: 		prevGreen = green;
 374: 		prevYellow = yellow;
 375: 		prevSlot = slot;
 376: 		prevGuess = guesses[slot];
 377: 		guesses[slot] = number+1;
 378: 		code = SOME;
 379: 		printf ("Try changing #%d from %d to %d\n",
 380: 					slot+1, prevGuess, number+1);
 381: 		fprintf (out, "Try changing #%d from %d to %d\n",
 382: 					slot+1, prevGuess, number+1);
 383: 		DEBUG ("SOME: guess[%d] from %d to %d\n",
 384: 					slot+1, prevGuess, number+1);
 385: 		return;
 386: 	}
 387: 	prevGreen = green;
 388: 	prevYellow = yellow;
 389: 	
 390: 	/* Find any possible solution */
 391: 	tries = 0;
 392: 	while (tries++ < 5000)
 393: 	{
 394: 		for (slot=0; slot<slots; slot++)
 395: 		{
 396: 			for (i=0; i<100; i++)
 397: 			{
 398: 				j = RAND (0, numbers);
 399: 				if (state[slot][j] == NO || guessed (j, guesses, slot))
 400: 				{
 401: 					continue;
 402: 				}
 403: 				
 404: 				guesses[slot] = j+1;
 405: 				break;		/* Guessed a slot ok */
 406: 			}
 407: 			if (i == 100) break;	/* Failed */
 408: 		}
 409: 		if (slot == slots) break;	/* Done */
 410: 	}
 411: 	if (tries == 5000)
 412: 	{
 413: 		fprintf (stderr, "\nSeed = %u : No possible solution\n", Seed);
 414: 		exit (1);
 415: 	}
 416: 	printf ("Try random new guess\n");
 417: 	fprintf (out, "Try random new guess\n");
 418: 	code = NONE;
 419: } /* End of guess */
 420: 
 421: 
 422: static int play (int human, int quiet, int slots, int numbers)
 423: {
 424: 	char	ans[20];
 425: 	int		green;
 426: 	int		guesses[MAXSLOTS];
 427: 	int		i;
 428: 	int		slot;
 429: 	int		tries;
 430: 	int		values[MAXSLOTS];
 431: 	int		yellow;
 432: 	
 433: 	
 434: 	/* Randomize the numbers */
 435: 	initRand (quiet);
 436: 	init (values, slots, numbers);
 437: 	
 438: 	fprintf (out, "Seed = %u\n", Seed);
 439: 	
 440: 	/* Now guess until they get it right */
 441: 	green = -1;		/* For 'guess' to know this is first time */
 442: 	yellow = -1;
 443: 	tries = 0;
 444: 	while (tries++ < 1000)
 445: 	{
 446: 		if (human)
 447: 		{
 448: 			printf ("\nEnter guess %d ->", tries);
 449: 			for (slot=0; slot<slots; slot++)
 450: 			{
 451: 				scanf ("%d", &guesses[slot]);
 452: 			}
 453: 		}
 454: 		else
 455: 		{
 456: 			guess (guesses, slots, numbers, green, yellow);
 457: 			if (!quiet)
 458: 			{
 459: 				printf ("\nGuess %d ->", tries);
 460: 				fprintf (out, "\nGuess %d ->", tries);
 461: 				for (slot=0; slot<slots; slot++)
 462: 				{
 463: 					printf ("%d ", guesses[slot]);
 464: 					fprintf (out, "%d ", guesses[slot]);
 465: 				}
 466: 				printf ("   (press return or q to quit) ");
 467: 				fprintf (out, "\n");
 468: 				ans[0] = getchar ();
 469: 				if (tolower (ans[0]) == 'q') exit (0);
 470: 			}
 471: 		}
 472: 		
 473: 		/* Make sure guesses are valid */
 474: 		for (slot=0; slot<slots; slot++)
 475: 		{
 476: 			/* printf ("guess[%d] = %d\n", slot+1, guesses[slot]); */
 477: 			if (guesses[slot] < 1 || guesses[slot] > numbers)
 478: 			{
 479: 				printf ("\nInvalid guess for slot #%d (valid 1-%d)\n",
 480: 							slot+1, numbers);
 481: 				break;
 482: 			}
 483: 			for (i=0; i<slot; i++)
 484: 			{
 485: 				if (guesses[i] == guesses[slot])
 486: 				{
 487: 					printf ("\nDuplicate guesses (slots %d and %d) are not allowed\n",
 488: 							i+1, slot+1);
 489: 					break;
 490: 				}
 491: 			}
 492: 			if (i < slot) break;	/* Duplicate */
 493: 		}
 494: 		if (slot < slots) continue;	/* Something went wrong */
 495: 		
 496: 		/* Compute #Greens & #Yellows */
 497: 		check (values, guesses, slots, &green, &yellow);
 498: 		
 499: 		/* If #Green = #slots, done! */
 500: 		if (green == slots)
 501: 		{
 502: 			if (quiet)
 503: 			{
 504: 				printf ("Seed=%5u  Tries=%2d  Answer =", Seed, tries);
 505: 				for (slot=0; slot<slots; slot++)
 506: 				{
 507: 					printf (" %d", values[slot]);
 508: 				}
 509: 				printf ("  (return or q to quit) ");
 510: 				gets (ans);
 511: 				if (tolower (ans[0]) == 'q') exit (0);
 512: 			}
 513: 			else
 514: 			{
 515: 				printf ("\nCongratulations!  Got 'em all!!\n");
 516: 				fprintf (out, "\nCorrect answer!\n");
 517: 			}
 518: 			return (tries);
 519: 		}
 520: 		
 521: 		if (!quiet) 
 522: 		printf ("Green = %d  Yellow = %d\n", green, yellow);
 523: 		fprintf (out, "Green = %d  Yellow = %d\n", green, yellow);
 524: 	}
 525: 	fprintf (stderr, "Seed = %u : too many guesses\n", Seed);
 526: 	exit (1);
 527: } /* End of play */
 528: 
 529: 
 530: int main (int argc, char *argv[])
 531: {
 532: 	char	ans[20];
 533: 	int		games;
 534: 	int		human;
 535: 	int		numbers;
 536: 	int		repeat;
 537: 	int		slots;
 538: 	double	sum;
 539: 	int		tries;
 540: 	
 541: 	if (argc < 3)
 542: 	{
 543: 		slots = 4;
 544: 		numbers = 9;
 545: 	}
 546: 	else
 547: 	{
 548: 		sscanf (argv[1], "%d", &slots);
 549: 		if (slots < 2 || slots > MAXSLOTS)
 550: 		{
 551: 			fprintf (stderr, "\nInvalid #slots %d (valid 2-%d)\n",
 552: 						slots, MAXSLOTS);
 553: 			exit (1);
 554: 		}
 555: 		sscanf (argv[2], "%d", &numbers);
 556: 		if (numbers <= slots || numbers > MAXNUMBERS)
 557: 		{
 558: 			fprintf (stderr, "\nInvalid #numbers %d (valid %d-%d)\n",
 559: 						numbers, slots+1, MAXNUMBERS);
 560: 			exit (1);
 561: 		}
 562: 	}
 563: 	
 564: 	/* Who is playing? */
 565: 	printf ("\nWho is playing (h=human, m=multiple, else computer) ->");
 566: 	gets (ans);
 567: 	if (tolower (ans[0]) == 'h') human = 1; else human = 0;
 568: 	if (tolower (ans[0]) == 'm') repeat = 1; else repeat = 0;
 569: 	
 570: 	out = fopen ("mm.out", "w");
 571: 	if (!out)
 572: 	{
 573: 		fprintf (stderr, "\nUnable to write to mm.out\n");
 574: 		exit (0);
 575: 	}
 576: 	
 577: 	if (!repeat)
 578: 	{
 579: 		play (human, repeat, slots, numbers);
 580: 	}
 581: 	else
 582: 	{
 583: 		printf ("\n");	/* spacer */
 584: 		games = 0;
 585: 		sum = 0;
 586: 		while (1)
 587: 		{
 588: 			tries = play (human, repeat, slots, numbers);
 589: 			games++;
 590: 			sum += tries;
 591: 			printf ("     Avg = %.2lf tries (games=%d)\n", sum/games, games);
 592: 		}
 593: 	}
 594: 	
 595: 	fclose (out);
 596: 	fprintf (stderr, "\nFinished writing to mm.out\n");
 597: 
 598: 	return 0;
 599: } /* End of main */
 600: 

mm.out - Sample output

   1: Seed = 6980
   2: 
   3: Guess 1 ->8 3 4 5 
   4: Green = 0  Yellow = 2
   5: Try changing #2 from 3 to 7
   6: 
   7: Guess 2 ->8 7 4 5 
   8: Green = 0  Yellow = 3
   9: Since gained a Yellow, eliminate 3
  10: Try changing #1 from 8 to 9
  11: 
  12: Guess 3 ->9 7 4 5 
  13: Green = 0  Yellow = 3
  14: Try changing #3 from 4 to 8
  15: 
  16: Guess 4 ->9 7 8 5 
  17: Green = 0  Yellow = 3
  18: Try changing #3 from 8 to 6
  19: 
  20: Guess 5 ->9 7 6 5 
  21: Green = 0  Yellow = 2
  22: Since lost a Yellow, eliminate 6
  23: Try changing #1 from 9 to 1
  24: 
  25: Guess 6 ->1 7 8 5 
  26: Green = 0  Yellow = 2
  27: Since lost a Yellow, eliminate 1
  28: Try changing #4 from 5 to 2
  29: 
  30: Guess 7 ->9 7 8 2 
  31: Green = 0  Yellow = 3
  32: Try changing #3 from 8 to 4
  33: 
  34: Guess 8 ->9 7 4 2 
  35: Green = 0  Yellow = 3
  36: Try changing #3 from 4 to 5
  37: 
  38: Guess 9 ->9 7 5 2 
  39: Green = 0  Yellow = 2
  40: Since lost a Yellow, eliminate 5
  41: Try changing #3 from 4 to 8
  42: 
  43: Guess 10 ->9 7 8 2 
  44: Green = 0  Yellow = 3
  45: Try changing #1 from 9 to 4
  46: 
  47: Guess 11 ->4 7 8 2 
  48: Green = 0  Yellow = 3
  49: Try changing #4 from 2 to 9
  50: 
  51: Guess 12 ->4 7 8 9 
  52: Green = 0  Yellow = 4
  53: Since gained a Yellow, eliminate 2
  54: All numbers guessed are right, but in wrong order
  55: Try random new guess
  56: 
  57: Guess 13 ->8 4 9 7 
  58: Green = 1  Yellow = 3
  59: Try swapping #2 with #3
  60: 
  61: Guess 14 ->8 9 4 7 
  62: Green = 0  Yellow = 4
  63: Try random new guess
  64: 
  65: Guess 15 ->7 8 9 4 
  66: 
  67: Correct answer!
  68: 
Email: steve@oharasteve.com