Home > Artificial Intelligence > Mastermind: code guessing helper in Prolog

Mastermind: code guessing helper in Prolog

Mastermind Board

Mastermind board seen from the codemakers perspective.

You may know Mastermind, the 2 player board game where one player becomes the codemaker, who creates the code, and the other player becomes the codebreaker, who tries to guess/derive the code. A classic Mastermind board may look like the one shown on the left — seen from the perspective of the codemaker, with the code hidden in the first line. There are other layouts too, like I myself used to play Mastermind on a board with 8 colors (+1 more color, which was “empty”), and 6 code pegs per code line.

Game rules

One player becomes the codemaker, the other the codebreaker. At the start the codemaker secretly choses a code, which he sets with the colored code pegs on the hidden, first line on his side of the board. There are no limits on a valid code: color duplicates are allowed, in the version known to me even free slots are allowed (which simply increases the total amount of colors by 1). The color and position of each code peg matters — this is what the codebreaker tries to guess now: for each try, the codebreaker sets a code line with code pegs to the next free line, starting at his side of the board. After the guess has been set, the codemaker checks the following:

  1. how many code pegs in the guess and the actual code are equal in position and color. He sets this amount in black key pegs next to the line then. All code pegs equal that fit this criteria don’t get counted in 2. any more.
  2. how many code peg pairs (one peg in the guess, one in the code) share the same color, but not the same position. This does not include code pegs already counted for 1., and no duplicates: e.g. if the code contains 2 green code peg and the guess 3 green code pegs, which are not on the correct position, this counts for 2. The codemaker sets this amount in white key pegs next to the line then.

For the next round, the codebreaker shall use all information from the past code guesses to derive the actual code. Target of the game for the codemaker is to chose a code which the codebreaker will not guess/derive, and for the codebreaker, to guess/derive it in as least rounds as possible.

Deriving possible solutions from past guesses

As I played around a bit with Prolog the last few days and accidentally came across Mastermind again (and noticed, that it’s proven to be a NP-complete problem), I was interested in building a lightweight Mastermind helper for deriving those codes still possible from having seen the result of previous guesses. This would enable me to simply do some good code guess, type in the guess and it’s result and see which codes are still possible — which is basically what I find interesting about such games 😉 Mastermind further is a perfect example of what’s easy to solve in Prolog: there’s one exact solution we’re searching for, and we can conclude some facts from the results of previous guesses. The basic idea is easy:

  • We search for a code C where each position is a color.
  • We have results from known guesses, where we know for each guess a) the number B of code pegs in C and our guessed code G which are equal in position and color, and b) the number W of code pegs in C and G which share the same color, but are on wrong positions.

To code this in Prolog, we basically have to specify that:

  1. A guess unifies C, G, B and W. After multiply tries multiply guesses are valid, for which G, B and W will vary, but C will always be the same.
  2. C and G share the same amount B of code pegs with same position and color.
  3. C and G share the same amount W of code pegs with same color, but wrong positions. This can be unified with counting the amount of occurrences of each color in C and G and taking the minimum for each of those pairs. B+W unifies with the sum of those minimums then.

Implementation

% list of existing colors. to reduce colors change color(X) below!
color1(red).
color2(blue).
color3(green).
color4(yellow).
color5(orange).
color6(brown).
color7(black).
color8(white).
color9(none).

% how many code pegs can be set - how the layout looks. only change amount here!
layout(X) :- X=[_,_,_,_,_,_].

% color space - change amount of colors only here!
color(X) :- color1(X).
color(X) :- color2(X).
color(X) :- color3(X).
color(X) :- color4(X).
color(X) :- color5(X).
color(X) :- color6(X).
color(X) :- color7(X).
color(X) :- color8(X).
color(X) :- color9(X).

% check if all elements of a list fulfill certain criteria
all([],_).
all([H|T],Function) :- call(Function,H),all(T,Function).

% one guess that has the real code (C), the guessed code (G), the nr of correct pos+colors (B) and the nr of other correct colors (W).
guess(C,G,B,W) :-
%check code layout fits
layout(C),
all(C,color),
%check that correct amount of positions+colors fits
cnt_pos_equal(C,G,B),
%check that correct amount of colors only fits
color1(C1),color_cooccurrence(C,G,C1,Cnt1),
color2(C2),color_cooccurrence(C,G,C2,Cnt2),
color3(C3),color_cooccurrence(C,G,C3,Cnt3),
color4(C4),color_cooccurrence(C,G,C4,Cnt4),
color5(C5),color_cooccurrence(C,G,C5,Cnt5),
color6(C6),color_cooccurrence(C,G,C6,Cnt6),
color7(C7),color_cooccurrence(C,G,C7,Cnt7),
color8(C8),color_cooccurrence(C,G,C8,Cnt8),
color9(C9),color_cooccurrence(C,G,C9,Cnt9),
W is 0 - B + Cnt1 + Cnt2 + Cnt3 + Cnt4 + Cnt5 + Cnt6 + Cnt7 + Cnt8 + Cnt9.

% count color cooccurrences in C and G list
color_cooccurrence(C,G,Color,Cnt) :-
countall(C,Color,CCnt),
countall(G,Color,GCnt),
min(GCnt,CCnt,Cnt).

% count occurrence in list
count([],X,0).
count([X|T],X,Y):- count(T,X,Z), Y is 1+Z.
count([X1|T],X,Z):- X1\=X,count(T,X,Z).
countall(List,X,0) :-
sort(List,List1),
\+ member(X,List1),!.
countall(List,X,C) :-
sort(List,List1),
member(X,List1),
count(List,X,C).

% min of two objects
min(X,Y,X) :- X<Y,!.
min(X,Y,Y) :- X>=Y.

% count how many elements in 2 list are equal in position and object
cnt_pos_equal([],[],0).
cnt_pos_equal([H1|T1],[H2|T2],Cnt2) :- H1=H2,!,cnt_pos_equal(T1,T2,Cnt1),Cnt2 is Cnt1+1.
cnt_pos_equal([H1|T1],[H2|T2],Cnt) :- \+ H1=H2,!, cnt_pos_equal(T1,T2,Cnt).

Example game

An example game, showing how the game advances and which Prolog queries correspond to each guess is shown below. The guesses are actually pretty bad, but good for demonstration purposes.

  1. The codemaker secretly sets a code [yellow, none, green, yellow, orange, blue].
  2. The codebreaker (randomly) guesses [red,red,blue,blue,green,green]. This results in 0 black key pegs, 2 white key pegs. The codebreaker enters a Prolog query containing this information:
    guess(C,[red,red,blue,blue,green,green],0,2).

    and gets presented a very long list of possible codes.

  3. The codebreaker now (randomly) guesses [yellow,yellow,orange,orange,brown,brown]. This results in 1 black key pegs, 2 white key pegs. The codebreaker extends his Prolog query with this information:
    guess(C,[red,red,blue,blue,green,green],0,2),guess(C,[yellow,yellow,orange,orange,brown,brown],1,2).8

    . He still sees a very long list of possible codes.

  4. The codebreaker now (randomly) guesses [black,black,white,white,none,none]. This results in 0 black key pegs, 1 white key peg. The new Prolog query is:
    guess(C,[red,red,blue,blue,green,green],0,2),guess(C,[yellow,yellow,orange,orange,brown,brown],1,2),guess(C,[black,black,white,white,none,none],0,1).
  5. Next guess: [none,white,black,brown,orange,yellow], results in: 1 black key peg, 2 white key pegs. New Prolog query:
    guess(C,[red,red,blue,blue,green,green],0,2),guess(C,[yellow,yellow,orange,orange,brown,brown],1,2),guess(C,[black,black,white,white,none,none],0,1),guess(C,[none,white,black,brown,orange,yellow],1,2).
  6. Next guess: [brown,brown,red,red,red,yellow], results in: 0 black key pegs, 1 white key peg. New Prolog query:
    guess(C,[red,red,blue,blue,green,green],0,2),guess(C,[yellow,yellow,orange,orange,brown,brown],1,2),guess(C,[black,black,white,white,none,none],0,1),guess(C,[none,white,black,brown,orange,yellow],1,2),guess(C,[brown,brown,red,red,red,yellow],0,1)
  7. Next guess: [orange,orange,brown,brown,brown,green], results in: 0 black key pegs, 2 white key pegs. New prolog query:
    guess(C,[red,red,blue,blue,green,green],0,2),guess(C,[yellow,yellow,orange,orange,brown,brown],1,2),guess(C,[black,black,white,white,none,none],0,1),guess(C,[none,white,black,brown,orange,yellow],1,2),guess(C,[brown,brown,red,red,red,yellow],0,1),guess(C,[orange,orange,brown,brown,brown,green],0,2)
  8. Next guess: [brown,orange,yellow,green,blue,red], results in: 0 black key pegs, 4 white key pegs. New Prolog query:
    guess(C,[red,red,blue,blue,green,green],0,2),guess(C,[yellow,yellow,orange,orange,brown,brown],1,2),guess(C,[black,black,white,white,none,none],0,1),guess(C,[none,white,black,brown,orange,yellow],1,2),guess(C,[brown,brown,red,red,red,yellow],0,1),guess(C,[orange,orange,brown,brown,brown,green],0,2),guess(C,[brown,orange,yellow,green,blue,red],0,4)
  9. Finally, the codebreaker decides to guess a combination that’s still possible according to the output of his previous Prolog query: [yellow, green, none, yellow, orange, blue]. This results in: 4 black key pegs, 2 white key pegs. The new Prolog query now is:
    guess(C,[red,red,blue,blue,green,green],0,2),guess(C,[yellow,yellow,orange,orange,brown,brown],1,2),guess(C,[black,black,white,white,none,none],0,1),guess(C,[none,white,black,brown,orange,yellow],1,2),guess(C,[brown,brown,red,red,red,yellow],0,1),guess(C,[orange,orange,brown,brown,brown,green],0,2),guess(C,[brown,orange,yellow,green,blue,red],0,4),guess(C,[yellow, green, none, yellow, orange, blue],4,2).
  10. Executing this query reduces the amount of possible codes to 2. Now the codebreaker can do the rest on his own 😉 Btw: if the codebreaker would have guessed more wisely, he would have “cracked the code” most probably much earlier.
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: