Mastermind Algorithm

Hello, everybody.  As you know, I have just started to write these series which I want to share some interesting coding challenges and an example solutions to them.  Here is my first one, Teaching a Computer to play MasterMind.

Analytical thinking is very critical and desired skill of a tester and developer in the software world. In order to think more critical and analytical, you need to learn and you need to be the master at the computer science fundamentals. Most of the folks ignore the fundamentals and deep dive into the world of languages. It is generally more satisfying to reach their goals such as to build a mobile application or web application. However, underlying of that applications, there might be very low-level data structures and high order of complexity. In order to be exceptional, we need to learn fundamentals of computer sciences such as data structures and algorithms. These also provide us to write high-quality test automation scripts, help us to do more analytical and intuitive testing and we can solve challenging problems at work and also in life.

As the father of Linux Linus Torvalds says, “I will, in fact, claim that the difference between a bad programmer and a good one is whether he considers his code or his data structures more important. Bad programmers worry about the code. Good programmers worry about data structures and their relationships.”

Also, world class companies generally assess the engineers with tough technical and analytical thinking questions during interviews. This questions based on fundamentals of computer science and algorithms.

In my opinion, whatever job you work for, if you are good at algorithmic and analytical thinking, you will have high-quality outputs and resolutions at your work. In this way, you will be more exceptional and different.

That’s why we added “algorithms” section in swtestcademy.com and the first article is coming from Sinan Oz. He is a Lead Technical Architect and he loves computer science and algorithms. I hope you will enjoy the first article “Mastermind”. :) Enjoy it.

At last, I love this article at simpleprogrammer.com. If you have a time, it is worth to read it.

– Onur Baskirt

Thanks to Onur, for such a nice preface, now let’s start to teach our computer to play MASTERMIND ;) This is my algorithm and implementation of mastermind game. You can also find many mastermind algorithms on web and also in academic papers.

History of Mastermind

Mastermind is a code-breaking game that made popular in 1970 by an Israeli postmaster and telecommunications expert named Mordecai Meirowitz. After rejections by several leading toy makers, the rights were obtained by a small British firm, Invicta Plastics Ltd. The firm originally manufactured the game itself, but later licensed its manufacture to Hasbro in most of the world. Mastermind is actually just a readaptation of an all-time’s classic game called “Bulls and Cows” or “Cows and Bulls” in English and “Numerello” in Italian. It is also reported on a few web pages that in the late 1960s Ken Thompson of Bell Labs and J. M. Grochow of MIT wrote programs that played “Moo” (a version of Bulls and Cows) on Unix and Multics operating systems, respectively. Nevertheless, after over 50 million copies sold in around 80 countries, Mastermind board game is still on the store shelves today. [1]

Teaching a Computer to Play MasterMind

Let’s create a software that can play MasterMind game with you. And it should be very competitive as well.

For the one’s who has not heard about the game, MasterMind is a guessing game where both players hold a secret 4-distinct-digit key in their mind and try to find the others Secret key.

How is the Game Played?

At each turn,  one player makes a guess for his opponents secret key. And the other player response him with a clue according to his guess.  Let me give an example:

Player 1 Player 2 (Secret Key:  4163)
Guess :   5613 Answer :   +1  -2

Explanation:  +1 for 1 digit on the guess is found on the secret Key on the correct Digit order which is  “3”.  -2 for 2 digits on the guess found on the secret Key but they are not on the correct Digit order those are “6” and “1”.

The first player who guess his opponents secret key is the winner.

How do We approach to a Solution?

When you play this game with a paper and a pen on yourself, there are lots of heuristic strategies you can come up with. For example, you can choose some special numbers as initial moves for example 1234, 5678, or as Knuth’s algorithm you can start with 1122 etc.. To first get which numbers are on the secret key. This is the natural approach as a human brain.

Since our task is to write a program that can play this game smartly,  we should think about our tools strengths and skills. We know CPU which can handle millions of operations in a second and a good short term memory memorising thousands of numbers easily where a human player can not.

The algorithm which I am listing below focuses on these two strengths on the computer. That’s how we can achieve this with very small amount of lines and complexity.

If you interested in mastermind algorithms, you can check Shapiro’s, Knuth’s, and Kooi’s algorithms as well.

Algorithm

  1. Create a pool of possible numbers each can be the Secret of my Opponent. (In guess pool, each digit of the numbers should be distinct.)
  2. Make a random guess from these numbers.
  3. Take the answer such as (+1 -2) and eliminate all numbers in the pool that won’t give the same answer (+1 -2) for my guess at step 2.
  4. Go to Step 2 and make a new guess in updated number pool.

It is just simple but strong.

First, let’s define an Interface for a player;

    public interface IMastermindPlayer
    {
        string StartGame();
 	string MakeMove();
        
       void TakeAnswer(string answer);  //answer is in string format like +1-2 or +0-2 etc..
    }

Let’s write some member methods for each step in the algorithm.  You would realise some global state variables are used in the algorithm. I will list whole class at the end but you can also figure out what those mean looking at their names

1) Create a pool of possible numbers each can be the Secret of my Opponent

This is pretty straightforward. We want to generate All 4-digit numbers consisting of 4 distinct digits.

private List<string> GetAllPossibleTokens()
{
      List<string> tokens = new List<string>();
      for (int d1 = 0; d1 < _ValidDigits.Length; d1++)
       	for (int d2 = 0; d2 < _ValidDigits.Length; d2++)
                    for (int d3 = 0; d3 < _ValidDigits.Length; d3++)
                        for (int d4 = 0; d4 < _ValidDigits.Length; d4++)
                        {
                            if (d1 != d2 && d1 != d3 && d1 != d4
                                   && d2 != d3 && d2 != d4
                                    && d3 != d4)
                            {
                                tokens.Add((_ValidDigits[d1].ToString() + _ValidDigits[d2].ToString() + _ValidDigits[d3].ToString() + _ValidDigits[d4].ToString()));
                            }
                        }
            return tokens;
}

2) Make a random guess from these numbers.

This is the no-brain part of our AI. Actually, we do not need any Heuristic at all. Just pick a random number.

public string MakeMove()
{
      _LastMove =  _PossibleTokens[new Random(DateTime.Now.Millisecond).Next(_PossibleTokens.Count)];
      return _LastMove;
}

3) Take the answer and eliminate all numbers that won’t give that answer to my guess.

This part does it all. It is the Learning-Part of our software.  Each answer of our opponents actually gives us big information.  We test each member in the pool (PossibleTokens)  with the given answer. And remove the ones which won’t give us the same answer to the same guess.

private void PrunePossibleMovesForTheAnswer(string guess, string answer)
        {
            for (int i = 0; i < _PossibleTokens.Count; i++)
            {
                string token = _PossibleTokens[i];
                if (AnswerToGuess(token, guess) != answer)
                    _PossibleTokens.RemoveAt(i--);
            }
        }
        private string AnswerToGuess(string token, string guess)
        {
            int p = 0, m = 0;

            for (int i = 0; i < guess.Length; i++)
            {
                int pos = token.IndexOf(guess[i]);
                if (pos >= 0)
                {
                    if (pos == i) p++;
                    else m++;
                }
            }
            return "+" + p + "-" + m;
        }

I won’t write down the other stuff like game-engine or UI.  It is not the part of algorithm at all.

Let’s write down the whole class again;

public class MySmartPlayer : IMastermindPlayer
    {
        char[] _ValidDigits = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' };
        List<string> _PossibleTokens;
        string _LastMove;


        private List<string> GetAllPossibleTokens()
        {
            List<string> tokens = new List<string>();
            for (int d1 = 0; d1 < _ValidDigits.Length; d1++)
                for (int d2 = 0; d2 < _ValidDigits.Length; d2++)
                    for (int d3 = 0; d3 < _ValidDigits.Length; d3++)
                        for (int d4 = 0; d4 < _ValidDigits.Length; d4++)
                        {
                            if (d1 != d2 && d1 != d3 && d1 != d4
                                   && d2 != d3 && d2 != d4
                                    && d3 != d4)
                            {
                                tokens.Add((_ValidDigits[d1].ToString() + _ValidDigits[d2].ToString() + _ValidDigits[d3].ToString() + _ValidDigits[d4].ToString()));
                            }
                        }
            return tokens;
        }
        private void PrunePossibleMovesForTheAnswer(string guess, string answer)
        {
            for (int i = 0; i < _PossibleTokens.Count; i++)
            {
                string token = _PossibleTokens[i];
                if (AnswerToGuess(token, guess) != answer)
                    _PossibleTokens.RemoveAt(i--);
            }
        }
        private string AnswerToGuess(string token, string guess)
        {
            int p = 0, m = 0;

            for (int i = 0; i < guess.Length; i++)
            {
                int pos = token.IndexOf(guess[i]);
                if (pos >= 0)
                {
                    if (pos == i) p++;
                    else m++;
                }
            }
            return "+" + p + "-" + m;
        }
        

        public string MakeMove()
        {
            _LastMove =  _PossibleTokens[new Random(DateTime.Now.Millisecond).Next(_PossibleTokens.Count)];
            return _LastMove;
        }

        public string StartGame()
        {
            _PossibleTokens = GetAllPossibleTokens();
            _LastMove = String.Empty;
            return _PossibleTokens[new Random(DateTime.Now.Millisecond).Next(_PossibleTokens.Count)]; 
        }

        public void TakeAnswer(string answer)
        {
            if (!String.IsNullOrEmpty(_LastMove))
            {
                PrunePossibleMovesForTheAnswer(_LastMove, answer);
            }   
        }

        public string WhatIsYourName()
        {
            return "sharpshooter";
        }
    }

References

[1] https://www.computer.org/csdl/proceedings/ahs/2006/2614/00/26140237-abs.html 

1 thought on “Mastermind Algorithm”

  1. Hello Sinan,

    I know it’s been a while since your post, but I call your attention on the result of AnswertoGuess(“1234”, “1122”), as I believe it should be “+1 -1” , not “+1 -3”.

    The scoring method is described at the tips section at https://www.wikihow.com/Play-Mastermind:

    “If the codebreaker guesses multiple of the same color, the code maker still gives only one hint for each peg. For example, if the codebreaker guesses Yellow Yellow Blue Blue and the correct code is Yellow Blue Green Green, the code maker puts down one red peg (for the first yellow) and one white peg (for the first blue). The second yellow and second blue do not earn any hint pegs, because the code only has one yellow and one blue in it.”

    A guess “1112” for a code “1223” should then return “+1 -2”, while a guess “1223” for a code “1112” should return “+1 -1”.

    Cheers!

    Reply

Leave a Comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.