[Search for users] [Overall Top Noters] [List of all Conferences] [Download this site]

Conference rusure::math

Title:	Mathematics at DEC

Moderator:	RUSURE::EDP

Created:	Mon Feb 03 1986
Last Modified:	Fri Jun 06 1997
Last Successful Update:	Fri Jun 06 1997
Number of topics:	2083
Total number of notes:	14613

497.0. "Mastermind" by GALLO::JMUNZER () Mon Jun 02 1986 13:15

Does anyone have any clever algorithms for playing Mastermind?

 **  **  **  **  **  **  **  **  **  **  **  **  **  **  **  ** 

In Mastermind, one player creates a peg position to be guessed, and the
other player guesses peg positions until he/she guesses correctly.  Every
peg position is 4 pegs, each of which can be black, blue, green, red, white,
or yellow.  Each guess is scored by black markers (for right color in the
right place) and white markers (for right color in the wrong place).

Example game -- position to be guessed is (red, yellow, blue, red)

	Guess				Black markers	White markers
black  black  black  black			0		0
blue   blue   blue   blue 			1		0
blue   green  green  green			0		1
red    blue   red    red  			2		1
red    white  blue   red  			3		0
red    yellow blue   red  			4		0

 **  **  **  **  **  **  **  **  **  **  **  **  **  **  **  ** 

Peg positions map naturally onto the set of 4-digit, base-6 numbers.
Mastermind could be played with other bases (B) and other numbers of
digits (D).

Can you find the most effective guessing strategy for B=3 and D=2?  For
B=6 and D=4?

T.R	Title	User	Personal Name	Date	Lines
497.1	See SIGART journal	MODEL::YARBROUGH		`Mon Jun 02 1986 14:31`	3
	A number of articles on this topic have appeared in the ACM SIGART journal.
497.2		AURORA::HALLYB	Free the quarks!	`Tue Jun 03 1986 12:35`	12
	About 10 years ago, Chuck (PAXVAX::) O'Toole and John Xenakis wrote up Mastermind programs and had them play against the computer, to see who could write the better program. They both ended up with minimal-step solutions. The interesting thing was that you could go on from there and improve upon the solution! The idea was to out-guess the computer's random number generation algorithm, so that if RED and BLUE both appeared equally likely, then by building up a history file you might be able to make a better-than-even guess as to which was more likely. John
497.3	I programmed mastermind once	ROXIE::OSMAN	and silos to fill before I feep, and silos to fill before I feep	`Tue Jun 03 1986 12:36`	22
	Back on TOPS20, I wrote a program that fared as well as humans at the game. It was written in MACRO. The algorithm of the program was to weigh every possible guess according to the expected reduction in possible answer space. The guess that had the greatest expected reduction was guessed. This program only ONCE ever took six guesses. All the other times, it "won" in five or fewer guesses. The algorithm was interesting because the program might actually guess an already-known-to-be-wrong answer if the information gained was more than for any could-still-be-right answer. I never investigated under what circumstances this can happen. John Francis (anyone know where he went?) actually programmed a chart that said "First guess X". Then, according to the six or so possible responses you get , go to line N of the chart, which instructed you to "now guess Y". This reduced the entire algorithm to table lookup ! I don't know how he did it. /Eric
497.4	I have a Pascal source for the PRO; interested?	EAGLEA::BEST	R. D. Best, 32 bit sys. arch. & A.D., VAXBI	`Wed Jul 09 1986 22:49`	7
	I have a Pascal program running on a PRO/350 that I modified to play with a larger than standard number of pegs. The original source was taken from 'The BYTE book of Pascal'. If you are interested, I will PFT it onto our cluster and post it as a note. /R Best
497.5	Use words instead!	TSE::FONSECA	This message no verb.	`Fri Jul 25 1986 18:25`	11
	There is a fun car game based on the MasterMind idea. Instead of using configurations of colored pegs, players use words. Limiting words to four letters provides a sufficient level of difficulty, since you are now using 26 'colors' or the alphabet. Only real words are allowed as guesses, and more than two players can play, each taking their turn at guessing in order. I bet this would be an interesting game to try to program.
497.6	a.k.a. JOTTO	VIRTUE::HALLYB	Free the quarks!	`Sat Jul 26 1986 15:01`	8
	If you extend this to 5 letters you pretty much have the game of Jotto, which used to exist on the -10. The computer was very good. Playing the game with three players (each player gets one guess that simultaneously probes both opponents) is very mind-wrenching! John