In order to gauge  the performance of  the heuristic algorithm,  an algorithm that deduced the best possible average performance had to be developed.  This entails finding a strategy 's' such that when all codes are deduced using 's', the sum of guesses made is minimized.  In order to develop such a strategy, a deep search procedure has to be applied to each code set, that is: an algorithm that searches all the possible paths and finds the shortest one.  As for Mastermind, this entails trying all possible codes as the first guess, and then choosing the one that leads to guessing the rest of the codes the quickest. To better understand what this involves, a detailed study of the 4 color and 3 positions game is given in Figure 4.  For this example we have chosen 112 as the initial code.

Figure -4 - Detailed description of the {4,3} case.
 
For demostration purposes we start with 112 as the initial code.
Colors: 4; Positions: 3; Guess path: 112
Results: (Blacks, Whites)
 
(0,0)     (0,1)     (0,2)     (0,3)     (1,0)     (1,1)     (1,2)     (2,0)     (3,0)
333        233      221                   133       131      121       111      112
334        244      231                   144       141      211       113
344        223      241                   134       311       114
343        224      321                   143       411       122
433        234      421                   313       123       132
434        243                              414       124       142
444        323                              314       213       212
             324                              413        214       312
             423                              332                    412
             424                              442
             331                              342
             441                              432
             341                              232
             431                              242
                                                222
                                                322
                                                422

     We continue searching on the set of codes that gave the (2,0) result and display several of the 9 guesses that could be made (on the left we have the guess, and in the table we have the corresponding answer -- whet it is compared to the rest).
 

Colors: 4;     Positions: 3;    Guess path: 112 (2,0)
        111       113       114      122       132      142       212       312       412
111  (3,0)     (2,0)     (2,0)     (1,0)     (1,0)     (1,0)     (1,0)     (1,0)     (1,0)
113  (2,0)     (3,0)     (2,0)     (1,0)     (1,1)     (1,0)     (1,0)     (1,1)     (1,0)
132  (1,0)     (1,1)     (1,0)     (2,0)     (3,0)     (2,0)     (1,1)     (0,3)     (1,1)

     Looking at the results in the table we see that the guess of 111 splits the set of 9 into sets of 1,2,6 elements. 113 splits the set into sets of 1,2,2,4 members. 132 splits the set into sets of 1,1,2,2,3.
     Now, in each case one of the sets created contains of the guess itself,  which we can ignore. If there are other sets of 1 element, we know that we need an additional guess to get it. If there are 2 elements in the set, we know that we need 3 additional guesses - one for the first element, and two for the second. If we have more than two, we must do a deep search on the set.
     In our cases this leads to the following sums of guesses
     111: 1 (the guess itself) + 5(3 from the set {113,114} plus one for each element of the set in order to take into account the 111 guess) + 21 (from an other deep search done on the       {122,132,142,212,312,412} set)  = 27.
     113: 1+5+5+11 = 22
     132: 1+2+5+5+8 = 21
     From this we see that the 132 guess is best when we receive an answer of  (2,0) to the guess of 112.
     The same procedure is applied to the different sets created by the different answers.

     In the case of {4,3} the code set is of size 64, and this algorithm leads to a minimum number of guesses, 206. This gives an optimum average of 206/64 = 3.21.

Optimization of the deep search algorithm

     After beginning to run the above algorithm on the {4,3} case it became clear that doing a pure depth search (i.e. searching every possible path) was an unfeasible task with any larger case. Below, we outline some of the optimizations made.
 
     The first optimization made concerned the top level of the search tree. It was clear that several first guesses led to equal results and therefore, testing each one was wasteful.  With any color - position combination one can come up with the minimum set of codes that have the essential characteristics of all the others.  In the 4x3 case these are 111, 112, 123. All other codes are just permutations of these three.  By permutations we mean a switch of color and/or position. Therefore, by reducing the first level search space from 64 to 3, we improved our performance drastically.  This however was not enough. While reducing the number of  guesses, the computer had to try from the topmost level down, and  it did not allow us to follow the same procedure for lower levels.  At lower levels one cannot assume that all codes of a certain structure (ones that can be converted into others by a set of permutations)  achieve the same minimum of guesses

     The second optimization we made involved stopping a search on a branch as soon as the optimum was found. For example: in the 4x3 case outlined in Figure 1, we can follow the path: 112->(2,0)->132->(1,1).  This leaves us with three remaining possibilities, namely 212, 113, 412.
If we now try 212 we distinguish the rest as shown below.
        212       113      412
212  (3,0)     (1,0)     (2,0)

     The fact that each answer we received appears only once ensures that this guess (212) gives the shortest path.  We do not need to consider the other two (113 and 412).  We have already discovered the optimum path at this point and can disregard the rest.
     This optimization significantly reduces the number of times that the deep search function is called.
 
     The optimization allowed us to do deep searches for standard cases up to {6,4}, for which the algorithm took approximately 15 hours.  Below is a table of the achieved results.
 

    c      1          2         3          4        5         6
p
1        1.0      1.50     2.00     2.50     3.00    3.50
2        1.0      2.00     2.33     2.80     3.24    3.89     
3        1.0      2.25     2.70     3.21     3.64    4.25
4        1.0      2.75     3.02     3.54     3.96    4.34