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;

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.

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.

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.

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;

References

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

javafx

Database Operations in JavaFX

By Onur Baskirt / Apr 1, 2016 / 56 Comments
Before started this section, please check the first article and learn How to Start JAVAFX! http://www.swtestacademy.com/getting-started-with-javafx/ At first, part of JavaFX tutorial series, we created a sample JavaFX project, designed the draft version of the UI and set up an...
rest assured

REST API Testing with Rest Assured

By Onur Baskirt / Mar 8, 2016 / 32 Comments
Outline In this post, I will explain what is API and API testing, what is the difference between SOAP and REST services, and how to test REST APIs with Rest Assured Library. What is API? API stands for Application Programming...
extentreports

How to Write Effective CSS Locators

By Onur Baskirt / Oct 1, 2017 / 0 Comments
Hi all, in this tutorial, I will describe you how to write effective CSS locators to interrogate web elements for your automation projects. As a rule of thumb, your interrogation strategy should be in below order: First try to use...
extentreports

Selenium-11: Execute JavaScript with JavascriptExecutor

By Onur Baskirt / Jan 27, 2016 / 15 Comments
Outline Sometimes we cannot handle some conditions or problems with Webdriver, web controls don't react well against selenium commands. In this kind of situations, we use Javascript. It is useful for custom synchronizations, hide or show the web elements, change...
javafx

Getting Started with JavaFX

By Onur Baskirt / Mar 25, 2016 / 0 Comments
When I started to work in my current position, one of my task is to do manual operations for campaign products  every week. After the second week, I thought that I have to automate this task using a GUI based...
extentreports

How to Write Smart XPath Locators

By Onur Baskirt / Sep 24, 2017 / 4 Comments
Hi all, in this tutorial, I will describe you how to write smart and non-brittle XPath locators. When we write our test scripts, we generally prefer to use id, name, class, etc. these kinds of locators. However, sometimes we could not...
extentreports

Selenium-1: Quick Start to Automation with Selenium WebDriver & JAVA & JUnit & Maven & IntelliJ

By Onur Baskirt / Sep 8, 2015 / 26 Comments
Outline Selenium Webdriver is the most popular open source web test automation framework across wide range of browsers and platforms. In this tutorial you will learn how to do web test automation with Selenium Webdriver and the related tools. Audience...
page object model

Page Object Model with C#

By Ege Aksoz / Jun 18, 2017 / 8 Comments
In the previous tutorial, we’ve taken the initial steps and entered the world of automated testing. We also wrote our first automated test. From this point on, since we are not just going to write one test, we need to...
extentreports

How to Select a Date From DatePicker Using Selenium

By Onur Baskirt / Aug 13, 2016 / 6 Comments
When you need to automate a airway, hotel, or similar websites you need to deal with Datepickers and some times it is a little bit cumbersome to select a specific date on the Datepicker or calendar.  In this post, I...
extentreports

Selenium Webdriver Performance testing with Jmeter and Selenium Grid

By Ozgur Kaya / Aug 9, 2016 / 2 Comments
In this post, we will complete Selenium Webdriver Performance testing scenario using Jmeter and Selenium Grid. 1- Install Java 7 or later If necessary https://java.com/tr/download/ 2- Download latest Jmeter version 3.0 or higher. http://jmeter.apache.org/download_jmeter.cgi 3- Download Jmeter PluginsManager JAR file and...
By | 2017-05-08T12:13:11+00:00 May 7th, 2017|Algorithms|0 Comments

About the Author:

Sinan Oz
Sinan Oz is an experienced IT professional who has a big passion on software science and algorithms since he attended International Olympiads in Informatics in his early ages. He finished Istanbul Technical University Computer Engineering Department. He worked at Garanti Technology, one of the biggest technology centres in the country for about 5 years. After that, he started Kariyer.net and takes some serious projects as a Lead Architect and he promoted as a Software Development Manager. Currently, he is working at Movie Star Planet Kopenhagen office as a Senior Backend Game Developer.

Leave A Comment