Automatic MasterMind Solver

For one of my university projects I had to find a way for automatically solving a mastermind game on a micro-controller in my case Arduino. There are several algorithms available on the internet, however most of them are very complicated or memory inefficient.


A very comon algorithm used to solve this problem is Knuth algorithm. Basically knuth algorithm stores all the possible cases in a array, and when the computer or the human makes the guess it eliminates all the cases which are not possible after the guess was made. It's a very good algorithm, however, it is very gready when it comes to memeory. It is physically impossible to put it on Arduino. So we had to find another solution.

 

After a lot of googling, I found Fran Van's gool algorithm, which was exactly what I was looking for. Simple, memory effiecient, fast in computation and reasonably low tries.

 

Bascially the algorithm just consists of a base 6 counter (depends on how many colors your version of game has). Initally you set the counter to something like 0000 or 0011 and make a guess. It will return you how many correct and misplaced pins you have. Save that result, and increment the counter. Afterwards check whether the new counter is consistent with all the previous guesses, if so save the result and increment the counter. You repeat this, until you find the code. If the counter overflows, goes back to 0000 or 0011, depends how you initialized, then there are no possible codes for the the correct and misplaced pins the user or someone else has given.

So if you want to read the original description click here.

Anyway here is my implementation in C/C++:

#include 
#include <time.h>
#include <stdio.h>
#include <stdlib.h>
 
using namespace std;
char input_code[4] = {0}; //Code which needs to be cracked
char g_code[4] = {0}; //code guessed by user or algorithm
char a_code[4] = {0}; //code guessed by user or algorithm
char solution[4] = {255}; //Holds the correct solutions
char checked[4] = {0}; //With bits, holds information which color has been checked in corresponding slot
char incorrect[4] = {255}; //Hold information which color was misplaced
char randNum; //just random number variable
 
//----------------------------------------------------------
// Function for returning the results of guess
//    0 - incorrect
//    1 - correct
//    2 - misplaced
//----------------------------------------------------------
void checkIfCorrect(char guess[], char result[], char code[])
{
 
    result[0] = 0;
    result[1] = 0;
    char blacks[4] = {0};
    char whites[4] = {0};
 
 
    for(int i=0; i<4; i++)
    {
        if(guess[i] == code[i])
            blacks[i]=1;
        else
            blacks[i]=0;
    }
 
    for(int i=0; i<4; i++)
    {
        if(blacks[i]!=1)
        {
            for(int f=0; f<4; f++)
            {
                if(f==i) continue;
                if((guess[i] == code[f] && blacks[f] != 1))
                    if(whites[f] == 0)
                    {
                        whites[f]=1;
                        break;
                    }
            }
        }
    }
 
    for(int i=0; i<4; i++)
    {
        result[0] += blacks[i];
        result[1] += whites[i];
    }
 
}
 
 
int scoreCalculator(int black, int white)
{
    if(black == 0 && white == 0) return 0;
    if(black == 0 && white == 1) return 1;
    if(black == 1 && white == 0) return 2;
    if(black == 0 && white == 2) return 3;
    if(black == 1 && white == 1) return 4;
    if(black == 2 && white == 0) return 5;
    if(black == 0 && white == 3) return 6;
    if(black == 1 && white == 2) return 7;
    if(black == 2 && white == 1) return 8;
    if(black == 3 && white == 0) return 9;
    if(black == 0 && white == 4) return 10;
    if(black == 1 && white == 3) return 11;
    if(black == 2 && white == 2) return 12;
    if(black == 4 && white == 0) return 13;
}
 
void base6counter(char num[4])
{
    num[3]++;
    if(num[3] == 6)
    {
        num[2]++;
        if(num[2] == 6)
        {
            num[1]++;
            if(num[1] == 6)
            {
                num[0]++;
                if(num[0]==6) num[0] = 0;
                num[1] = 0;
            }
            num[2] = 0;
        }
        num[3] = 0;
    }
}
 
int main()
{
    srand(time(NULL));
 
    //memset(g_code,0,4);
    memset(solution,255,4);
    memset(checked,0,4);
    memset(incorrect, 255, 4);
    cout << "Put 4 number code in with values from 0 to 5! (with spaces)" << endl << "For example: 0 3 4 2" << endl;
    scanf("%d%d%d%d", &input_code[0], &input_code[1], &input_code[2], &input_code[3]);
 
    int guesses = 0;
    char result[] = {0, 0};
 
    g_code[0] = 0; g_code[1] = 0; g_code[2] = 1; g_code[3] = 1;
    a_code[0] = 0; a_code[1] = 0; a_code[2] = 1; a_code[3] = 1;
    char previous_answers[10][4];
    char previous_scores[10];
    while(guesses < 15)
    {
        guesses++;
 
 
        cout << "Code: ";
        //scanf("%d%d%d%d", &g_code[0], &g_code[1], &g_code[2], &g_code[3]);
        printf("%d %d %d %d",g_code[0],g_code[1],g_code[2],g_code[3]);
        //reset the misplaced variables
 
        checkIfCorrect(g_code, result, input_code); //Check how if the guess was correct
        int score = scoreCalculator(result[0],result[1]);
 
        previous_answers[guesses-1][0] = g_code[0];
        previous_answers[guesses-1][1] = g_code[1];
        previous_answers[guesses-1][2] = g_code[2];
        previous_answers[guesses-1][3] = g_code[3];
 
        previous_scores[guesses-1] = score;
 
        if(result[0] == 4)
            break;
 
        bool anySolutions = true;
 
        while(anySolutions)
        {
            bool consistent = true;            
            for(int i=0; i<guesses; i++)
            {
                checkIfCorrect(a_code, result, previous_answers[i]);
                int test_score = scoreCalculator(result[0],result[1]);
                if(test_score != previous_scores[i])
                {
                    consistent = false;
                    break;
                }
            }
            if(consistent)
                break;
 
            base6counter(a_code);
            if(a_code[0] == 0 && a_code[1] == 0 && a_code[2] == 1 && a_code[3] == 1)
            {
                anySolutions = false;
                printf("ERROR: No solution possible!\n");
            }
        }
 
 
        g_code[0] = a_code[0];
        g_code[1] = a_code[1];
        g_code[2] = a_code[2];
        g_code[3] = a_code[3];
 
        printf("\n[ %d ; %d ]  ----  My best guess: [%d %d %d %d]\n", result[0],result[1],a_code[0],a_code[1],a_code[2],a_code[3]);
 
        if(guesses == 8)
            printf("\n-- %d %d %d %d -- \n",input_code[0],input_code[1],input_code[2],input_code[3]);
 
 
    }
 
    if(result[0] == 4)
    {
        cout << "\n\nI won the game, in " << guesses << " turns!" << endl << "Your code was: ";
        printf("[%d %d %d %d]\n", g_code[0],g_code[1],g_code[2],g_code[3]);
    }
    else
        cout << "\n\nI\'m are crap in this game!" << endl;
 
    return 0;
}

Some screen shots:

 

Download: mastermind.zip (21.97K)




ADVERTISEMENT

  • Chris Sparks

    Chris Sparks in Simple TLS/SSL SMTP client for Qt5

    qt.network.ssl: QSslSocket::connectToHostEncrypted: TLS initialization failed

    Edward Martin

    Edward Martin in Introduction to data encryption

    The introduction to the data encryption is very much helpful as you will get to know about the data encryption procedure which might help you to protect the files and folders. You can check the 

    bean

    bean in DIY 3D printer, AKA RepRap

    The 3D printer creates the dimensional object and with the features of the 3D printer, it executes the process if need further query then visit fix error code 0xc004f074...

    preter jack

    preter jack in Single Cycle MIPS CPU in VHDL

    Single-cycle CPU is more improved than the normal and usual CPUs and it has a lot of advantages and all you can get from fix

    henrydevid

    henrydevid in nRF51 Makefile with Qt Creator

    It is great for all, I have some different tricks if you want to know it then for that I have some different tricks, for that, you want to learn to code. For that, if you want to know it then for that you just visit some tutorial. And from there it is great for all. If you faced any type...

    Steve Rogger

    Steve Rogger in OpenCV on Raspberry Pi

    I have read the post and it is very much helpful because I have got to know about the open cv on the raspberry pi. The images and the screenshots provided here will guide you for your questions. The code you will get here is very unique and can be only used to run OpenCV. If you face any...

    preter jack

    preter jack in Programming micro-controller (Arduino) with cheap HC-06 Bluetooth

    This type of IC Bluetooth offers a lot of advantages and this type of Bluetooth are really very user-friendly and easy to use. It provides many unique features that are all mentioned over the