Is there an elegant way of grouping sequences in the game Mastermind by a certain rule?

Question

I'm not sure if this is a combinatorics question, I'm not a mathematician so pardon me if I've tagged this wrong.

Some context: the game Mastermind is a codebreaking game where you have to guess a hidden sequence of colours based on hints given after each guess. For every colour you guess in the right position, you get a Black token, and for every colour you guess that is in the hidden code but not in the right position, you get a White token (unless it has previously been considered for another Black or White token). As a side note, Donald Knuth wrote a paper proving that it is possible to win within 5 moves (in the original version with code length of 4 and 6 colours).

Imagine a game of Mastermind where you have narrowed down the code to 4 possibilities: 3525, 4542, 5244, 5352 (Why did I choose to use 2-5? Who knows.). What’s the best move? Let’s take a look at the hints you get for all possible entries and all possible answers (Black, White): https://i.imgur.com/RpydgBS.png

If your entry is 4542 or 5352, in the worst case you will get a 1, 1 response which narrows the number of possible solutions to 2. However if your entry is 3525 or 5244, in the worst case you get a response which narrows the number of possible solutions to 1, which guarantees you winning on the next move. Thus, 3525 and 5244 would be in one group, and 4542 and 5352 would be in another group.

Now the question: is there a more elegant way of grouping an arbitrarily large set of sequences like this, without needing to brute-force through all sequences? Just looking at the 4 sequences, can you tell at a glance which are the best solutions?

I’m teaching myself Python, currently trying my hand at making a python program which runs Mastermind, both for human players and for computer analysis. The program is fast enough to analyse the original Mastermind in a reasonable time, but as I try higher numbers of code lengths and colours (e.g. 5, 10), it gets a lot slower. If there is a general rule which I can use to know which sequences will return a certain number of worst-case scenarios and skip sequences which repeat, it will really cut computation time.

There is a way to narrow down the first move of the game: count the number of times each different colour repeats in the sequence. There are only 5 opening moves for code length of 4: 0000, 0001, 0011, 0012 and 0123. It works because the list of possible solutions is "uniform", so any other sequence with the same "profile" will return the same worst-case scenario. The problem comes when some possible sequences are eliminated. (EDIT: As a general rule, as long as all the guesses you have made returned 0 Black 0 White, you can apply this method, because it simply means eliminating whatever colours were guessed.) And of course permutations of sequences will not return the same worst-case scenarios, as shown in the example above.

My guess is it’s mathematically impossible, but I’m not a mathematician, that’s why I’m here.

Answer 1

(I'm not a mathematician so maybe my explanation won't be very precise in jargon.)

After much experimentation with different methods, the answer is no; you have to analyse a certain number of moves the hard way. The worst-case (and average-case, i.e. average possible solutions on the next move) scenario is intrinsically tied to the hints given, therefore there is no shortcut. However, the good news is it is possible to prune the number of moves you have to analyse down to a minimum, if you know what previous moves were.

The minimum amount of moves you have to analyse is equal to the amount of "unique" moves which exist in the list of moves not tried before. By a "unique move" I mean that moves which return the same amounts of each "x Black, y White" hint when checked against every possible solution are functionally the same move.

This is why the "profile method" above works for the first move of the game; moves of the same "profile" will always return the same list of hints. However, a correction: the general rule of applying this method if all hints so far has been 0 Black, 0 White is wrong, because the best move (i.e. move which gives the most information) may not always be a possible solution.

Using my example above, each move returns a unique list of hints when checked against every possible solution, so while it seems that 3525 and 5244 are "the same", in reality the way they arrive at the worst-case scenario of 1 is completely different, and same goes for 4542 and 5352, so one cannot tell which are the best moves just by looking at them.

However, let's say you're in a game of Mastermind and have made 1 move: 0011 (0-5 representing 6 colours), which can be generalised as "aabb".

1. First, categorise potential moves into unique combinations of the move and hint received, e.g. aaaa and 2*a Black; aaab and 2*a Black, 1*b Black; aaab and 1*a Black, 1*a White, 1*b White; cdef (signifying numbers not in the move) and so on. Thus, 0000 and 1111 are the same, 0001, 0010, 1011, 0111 are the same, 0100, 1000, 1110, 1101 are the same, permutations of 2345 are the same, and so on (I don't know how to formally describe this).

Note: Depending on the hint you received for the move made, the number of unique moves may actually be less than the number of categories, as moves of different categories may produce the same hints; e.g. moves 0000 and 0001 will produce the same hints if the hint to 0011 was 0 Black, 0 White (i.e. all colours are neither 0 or 1, both will always return 0 Black, 0 White as well).

2. Include one occurrence of each category to the list of moves to be analysed, and skip the rest (all moves have to be categorised, even those not in the list of possible solutions, because as mentioned above, the best move is not necessarily a possible solution).

3. After making n moves, do step 1 for each move, and the upper limit of unique moves is the product of the number of categories of all moves (although it will not likely be that high, as there will be certain combinations of categories which no move will fulfil).

4. For each move not tried before, check it against every move's categories. If it is the first occurrence to fulfil a certain combination of categories (e.g. category 3 of move 1, category 5 of move 2, etc.), add it to the list of moves to be analysed, otherwise skip it.

To implement this in the program is pretty hard and may even increase runtime, but that's another story.