From: joe.taylor@argonet.co.uk Newsgroups: sci.math Subject: RE: mastermind algorithm Date: Thu, 07 Dec 1995 09:24:58 Someone asked for a program which solves mastermind. Here is a program written in BBC BASIC. Since this language is highly structured the program should be easily re-written in less powerful languages sucg as C, C++ etc. (Only joking, C fans! [No I'm not!!]) THE GAME OF MASTERMIND ********************** The game of mastermind involves a hidden set of coloured pegs placed in holes. (If memory serves, the "classical" game involves 6 colours and 4 holes.) The object of the game is to identify the colours of the pegs in each of the holes. This is achieved by guessing the solution and being given a score consisting of a number of smaller white or black 'peglets'. The number of black 'peglets' indicates the number of coloured pegs which have been correctly guessed and the number of white 'peglets' indicates the further number of colours guessed correctly but which are in the wrong place. CODING MASTERMIND - THE EQUIVALENT INTEGER GAME *********************************************** To code mastermind we convert it into a game involving integers as follows: Assign each of the available colours a value 0,1,2,... . Thus, assuming there are b colours for the choice of pegs then each peg represents one of the "digits" 0,1,2,...,b-1 . If there are n pegs then a set of colour pegs represents a unique integer with exactly n-digits when expressed in base b. E.g. consider the following "classical" game where the solution is 4204 : Guess W B ------------- 0000 0 1 1110 1 0 2202 0 2 3302 1 1 4204 0 4 ('W' is the number of white peglets in the score and 'B' the number of black peglets.). It is easy to write a string-valued function which is the "guess" which corresponds to the integer x. E.g. IN BBC BASIC : DEF FNMastermind(x) REM -------------------------------------------------------- REM The value of this function is the string containing the REM mastermind "guess" corresponding to the integer x. REM -------------------------------------------------------- LOCAL i,result$ FOR i=1 TO pegs result$=STR$(x MOD colours)+result$ x=x DIV colours NEXT =result$ **N.B.** The global variables 'colours' and 'pegs' are the numbers of colours available and the number of pegs used in the game. (In BBC BASIC x MOD y represents the remainder when x is divided by y. Also x DIV y is the quotient.) The "score" when comparing two integers x and y is calculated by: DEF FNScore(x,y) REM ------------------------------------------ REM Calculates the "score" in mastermind. REM This function has the string value "W B". REM 'B' is the number of digits (coloured pegs) REM which are the same in x and y (i.e. have REM the same colour and position) and 'W' are REM the numbers of remaining digits (colours) REM which are the same. REM N.B. x=y iff Score(x,y)="0 P" where REM P=# of pegs. E.g. for "classical" REM game "0 4" REM N.B. REM If colours>10 or pegs>10 then the last line REM would need to be altered. REM ------------------------------------------- LOCAL black_pegs,white_pegs,x_digit,y_digit,i,x_colour(),y_colour() DIM x_colour(colours-1),y_colour(colours-1) FOR i=1 TO pegs x_digit=x MOD colours : x_colour(x_digit)+=1 y_digit=y MOD colours : y_colour(y_digit)+=1 IF x_digit=y_digit THEN black_pegs+=1 x=x DIV colours : y=y DIV colours NEXT white_pegs-=black_pegs FOR i=0 TO colours-1 IF x_colour(i)<>0 AND y_colour(i)<>0 THEN IF x_colour(i)<=y_colour(i) THEN white_pegs+=x_colour(i) ELSE white_pegs+=y_colour(i) ENDIF ENDIF NEXT =STR$(white_pegs)+" "+STR$(black_pegs) *********************************** *********************************** AN ALGORITHM FOR SOLVING MASTERMIND *********************************** An obvious algorithm for solving mastermind is to start with the guess x=0 and then to choose the next highest integer which *could* be the solution. I.e. it gives the same score when compared with x=0. If this isn't the same solution then choose the next highest integer which is consistent (i.e. gives the same scores) as the previous choices. REM ------------------------------------------ REM A program for solving mastermind using the REM 'consistent' search method. REM ------------------------------------------ DIM guess(10),score$(10) DATA 6,4 READ colours,pegs : PerfectScore$="0 "+STR$(pegs) REM ++++++++++++++++++++++++++++++++++++++++++++++++++++++ REM Choose a random number as the "solution" to be guessed REM N.B. this number must be less than colours^pegs REM ++++++++++++++++++++++++++++++++++++++++++++++++++++++ solution=RND(colours^pegs) PRINT "Solution is ";FNMastermind(solution) PRINT'"Guess","W B" PRINT "-------------" REM +++++++++ REM Main loop REM +++++++++ i=-1 : guess(0)=0 REPEAT i+=1 score$(i)=FNScore(guess(i),solution) PRINT ;FNMastermind(guess(i)),score$(i) IF score$(i)<>PerfectScore$ THEN guess(i+1)=FNNext(i) UNTIL score$(i)=PerfectScore$ END DEF FNNext(i) REM ------------------------------------ REM Calculates the next consistent guess REM ------------------------------------ LOCAL x x=guess(i) REPEAT : x+=1 : UNTIL FNConsistent(x,i) =x DEF FNConsistent(x,i) REM ----------------------------------- REM Tests x against each previous guess REM ----------------------------------- LOCAL j : j=-1 REPEAT : j+=1 UNTIL j>i OR score$(j)<>FNScore(x,guess(j)) IF j>i THEN=TRUE ELSE=FALSE The above program can easily be improved in several directions. I have kept it simple for the sake of its being easier to understand. *********** SAMPLE RUNS *********** [deleted]