The heuristic algorithm

     In playing mastermind, one tries to make the most of previous information and to use the information to narrow the possibilities in order to solve the code in as few steps as possible.   One way to do this is to always put guesses on the board that would make answers to previous guesses valid; e.g. if a guess receives no black or white pegs, we know that the code does not have any of the colors in the guess and therefore, using these colors in future guesses would be ineffective.

     With each guess that does not contradict previous ones, we at least have a minimal chance of guessing correctly and at the same time, we may get additional information.
     The procedure just described  is easily coded and follows the following structure:

     Below are some samples of using this algorithm to solve the 6 color, 4 positions code: 1 3 5 4 - the first guess is a random selection of two pairs.      In previous research this algorithm gave surprisingly good results.  It averaged 4.64 guesses for each {6,4} code solved, and in addition, it had a very good worst-case performance of  8 guesses per code.
 

Performance of the heuristic algorithm

     As stated in the introduction our purpose was to study the performance of this algorithm in games with more colors and more positions.  We performed this task for as wide a range of codes as the hardware available allowed (see technical notes).  The code sets tested ranged from 2 to 12 colors and 1 to 8 positions. This meant that our code spaces ranged from 2 ({2,1})  to 429,981,696 ({12,8})  possible codes.  A table with the results is shown below.

 
     The table shows results that are just as surprising as the results from the original research of the {6,4} case.  The algorithm performs just as well in higher dimensional spaces as in the smaller ones.  In fact, if we look at the graphical representation of the results (Figure 1) we see a simple linear evolution of the results.  The graph looks like a slightly crumpled piece of paper floating in space, the slight crumples coming from the natural statistical variation of the averages. This variation was at most 0.01.
 
 
Figure 1- Graph of guesses per code solved using heuristic algoritm 
Figure 1 - Guesses per code solved using heuristic algorithm.
 
     In contrast to the logical results of the heuristic algorithm, its time performance has exponential properties. This is due to the exponential nature of the problem at hand. As mentioned previously, the size of the code set is given by the formula colorspositions.  Therefore in the 12 color case, an increase of one position increased the code space by 12x. This property quickly depleted our computational resources.  Below is a table of times, and following it is a graphical representation of the performance data (Figure 2).  In addition we give a second interpretation of the results, graphing the time versus the code set size (Figure 3).  

     Figure 2, and 3 display the same results in graphical form.  Figure 2 displays the time taken on the z axis with Colors and Positions on the x and y axis, respectively.  Figure 3 displays the time taken in respect to the code set size.
 
Note: Click on images for a blown-up view.
Figure 2 - Heuristic algorithm - seconds per code solved  Figure 3 - Heuristic algorithm - Runtime / code set size
 
 

  Top Back  - Introduction  Definitions Forward - The deep search algorithm Forward - Conclusion