Mastermind
Mastermind is a game where a player has to guess a code created by another player or a computer program. The classic version uses codes with four places, each of which can be occupied by one of six colors. This makes a total of 64 = 1296 possible codes.
The play starts with the codebreaker guessing a code. The codemaker then answers with black and white pins:
- Each correctly guessed position, the correct color in the correct place, awards a black pin.
- Then, each correctly guessed color awards a white pin, unless this position (code or guess) was already used in any other hit.
The goal for the codebreaker is to find the correct code in a minimal number of tries.
The Computer as Master Mind
Donald E. Knuth wrote a paper The Computer as Master Mind in the Journal of Recreational Mathematics 9, no. 1 (1976). He shows that every code can be guessed in at most 5 tries. Knuth gives constructive proof by providing a solution tree in his Figure 1: the codebreaker starts with the code AABB and then follows the edges of the tree depending on the answers of the codemaker. The tree has a height of 4, which leads to the mentioned maximum of 5 tries.
Knuth's Figure 1 is intriguing as it reminds of the intricacies of TeX programming and macro expansion. He released TeX a few years later.
An interactive Visualization of Knuth's Solution Tree
To make Knuth's Figure 1 more accessible, the Mastermind solution tree has been computed and different visualization options are provided.
The solution tree has been computed using the Python program The Computer as Master Mind.py provided in this repository. It seems to coincide with Knuth's tree. The tree can be visualized using GraphViz dot (see The Computer as Master Mind Vis.py in the same repository) as a static tree. Since it is rather large, an interactive tree visualization and navigation tool has been developed as well: