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.