Mastermind

Solve Mastermind

A question was posted online recently about the best strategy for winning the game of Mastermind (https://en.wikipedia.org/wiki/Mastermind_(board_game)). Mastermind is a game played between two players, a Code Maker and a Code Breaker. The Maker makes a code of colored pegs, and the Breaker has to guess the code. After each guess, the Maker gives feedback of how many of the pegs were the right color in the right place and how many are the right color in the wrong place, indicated by black and white pegs in the board. The Breaker then makes another guess.

The parameters of the game are how many pegs are in the code, how many possible colors there are, and whether the same color is allowed to be repeated in the code, as in (4 of 6, repeats).

Donald Knuth wrote a paper (http://www.cs.uni.edu/~wallingf/teaching/cs3530/resources/knuth-mastermind.pdf) on optimal play for the Breaker and showed that in four pegs in the code of six possible colors with repeats, it can be solved in no more than five tries. Donald Knuth is a deity of Computer Science, having written The Art of Computer Programming (https://en.wikipedia.org/wiki/The_Art_of_Computer_Programming). I wrote a program to implement Knuth's algorithm in C#. It shows it playing all possible games and also creates a table at the end of how to make perfect play.

In my program, I replace colors with numerals since the colors are arbitrary. You can try the results, playing on this site (https://www.onlinespiele-sammlung.de/mastermind/mastermindgames/madglibs/index.html).

The program uses a MinMax algorithm (https://en.wikipedia.org/wiki/Minimax), which finds the code that will reduce the number of possible remaining codes on each play. Because of the way it works, sometimes it will make a code that might not actually solve it on the next play, but instead guarantee that it solves it in the least number of tries. There are some other algorithms that will solve it in a smaller average number of tries, but possibly having a larger maximum.

The algorithm shown here is not terribly efficient, playing rather loose with both execution speed and consumption of memory. It was meant as a fast demonstration rather than a necessarily optimal implementation.

Below is the table produced by the program for playing (4 of 6, with repeats). To use the table, let's assume Red=1, Blue=2, Yellow=3, Green=4, White=5, and Orange=6. Suppose the code is 2342 (or Blue, Yellow, Green, Blue). The first guess is always 1122 (Red, Red, Blue, Blue). This gives back 1 Black and 1 White, or B1W1. Scroll down so the first tab in reads B1W1, and it says after that to guess 1134 (Red, Red, Yellow, Green). This gives back 0 Black and 2 White, or B0W2. The next tab in says to guess 3521 (Yellow, White, Blue, Red). This gives back 0 Black and 2 White, or B0W2. Scroll down so the next tab in says to guess 4612 (Green, Orange, Red, Blue). This gives back 1 Black and 1 White. Scroll down so the next tab says to guess 2342 (Blue, Yellow, Green, Blue), which is the solution.

If the code is 2342 (Blue, Yellow, Green, Blue), this would be the sequence of guesses.

gregreddick / mastermind Goto Github PK

mastermind's Introduction

Mastermind

mastermind's People

Contributors

Watchers

Recommend Projects

React

Vue.js

Typescript

TensorFlow

Django

Laravel

D3

Recommend Topics

javascript

web

server

Machine learning

Visualization

Game

Recommend Org

Facebook

Microsoft

Google

Alibaba

D3

Tencent