So I read about this neat hat problem that's been going around, and decided to try to find an optimal solution for the 7 person problem. The code to run these strategies is below.
The found strategies are presented in the form of a string of characters - "R" indicates guessing a red hat, "B" indicates guessing a blue hat, and "N" indicates guessing neither. The strategies for each player is presented in order, and within each the order is as follows: the first character is what to do if you see all blue hats, the second character is what to do if you see all blue hats except the last person has a red hat. This continues on in the manner of incrementing binary numbers (where a 0 digit is seeing a blue hat and a 1 digit is seeing a red hat) until the last character which is seeing all red hats. Then the strategy continues with what player #2 should do, etc. For 7 players, this leads to strings of length 2^6*7=448.
Note that the strategy of one person picking blue and everyone else picking nothing all the time will get a score of .5, so this is the benchmark for a reasonably good result.
Technique: Random (score .171875) - This technique just picks 10000000
strategies at random and selects the one with the highest score. I did this
technique first as a sort of baseline, and to see if "good" strategies
are very very common over the solution space. They are not, as .171875 is a
pretty bad score. The gene that produces this is:
BRNNRRNRRRBRBRRNBNNBNNBNRNBNRNNRRRBBBRNRNNBNNNNBNNBNRRNNRNNNNRNBBNNNRNBRNNRRNRNNRBRBNBBRBNRNRRRBRRNBBBNNBBNBNRNRBNRBNRRRNBRRRNNBRRBRBNNBBRRBBNNBRRBRBBNBBRNNRNNBNBRNNRBBNBRRNBNBNRRBRNRRBRRRRBRBRRNRNBNBBBNBNRBNBBBRNNRNBNRRRBNNNRRNBRBRNNNNNNNNBNRBNBBBBNNRBNNNRRNRNBBNBBNNNRNRRRRRNNNNNRNNRRNBBRNNNBNBBRBRBBNBNRRRBRNBNRNNNRNNRRNRBRNBRBRNBRNRBRNRNNNBBNNBNNNBRNRRNNNRNRBBBBRRNNNNRNBNNBNRNBNBBRBNBBBNRNRNBNRNNRNNRNNBBNNBNRNRBNBBNNRRRNNNNBRNNRRRRRRBBNBBBNRB This method is
implemented in findBestStrategyExhaustive(7, 10000000).
Technique:
Hill-climbing with random restart (scores .273438, .28125) - This
technique starts at a random strategy, and finds the best strategy achievable
by changing only one character. It then continues, restarting randomly with a
new random strategy. (for simplicity, my code restarts after 20 changes -
perhaps increasing this value would lead to better results) These scores are
better but still nowhere near our baseline of .5. The best gene was:
BRRBBBNNBNNRBRNRNNRNNRNBBRNBRRNRNRBNNNNBNNNBBRBNRNNRRBRNNRNBBNNNRNNBNNRNRRNRBNNNRRRBNNBNBNNRNNRRNNBRRNRRRRNNRNNBNBRRBBBRRRBNBBBRNBNRBRBRNBRRBRNNNRRNNNNBBNBRNRNNNRNBBNBRBRNRRNRBBBRBBBNRBNBRBNBRNBRBBRRRRNBNRNBBNRBBNNNNNNNRNNRNRBNNNNBBBNNNRNBBNRRNBBBBBNNBBBNNRBRRNBRBNNBNNRRRNNRRBBNRRNNNNNRNBBBNRRBBBRBBBNBRNRRBRBNBNNBNNNRNBRNRRBRNNNRRBRNRBNBRBNNNNNNNNRNNRRRNNBNBNBRNRRRBNRRNNBBRNNNRBBNRRRBBNRRNRNRRNBRRNBBRNRRNRBRNRRNNBBRNNNRRBRNNNRRRNNRNRNRNBBNNNRNN This method is
implemented in findBestStrategyHillClimbRestart(7, 10000000, 20).
Technique:
Genetic algorithm with mutation (scores .387438, .671875, .367188,
.359375, .632812, .664062) - This techniques starts with a generation of
strategies, scores them, and creates a new generation by breeding the current
generation (weighting by fitness) and randomly mutating. The scores here
greatly depended on the size of the generations - they were 1000, 10000, 100000,
100000, 10000, 10000 respectively, showing that 10000 (perhaps because it's
close to sqrt(10000000)?) does clearly better. We've broken through the magic
.5 score, although still not near the theoretical maximum score of 7/8=.875.
The best gene was:
BNNNRBNRRNBBNNNBNRNRNNBNNNNNNNNNNNBNRNNNRRBRNNNNNNNBNNBRNNNBBNNRNNNNBNNRRBRBNNNNNRRRRNNBNNNNNRBBRNNNNRNNNNRRNBNNNRNBRNBNBRNNBNNNNBBBBNNRRNNRNBNNNBNNNNNBRNNNNNBNRBNNBRBNNBBRRNNRNRRBNNNNNNRBBRNRBNNBRNNNNRRRRBNNBBNBRBNBNRNNNNBBNNBBNNNNNBBNNNRNNRBNNNNBBNNRBNRNNNNNNNRRBRNNNNNNBNNNNBNBNRNBNNBNNBNNNNNBBNBNNRRNNRRNNNRBNBBRBNNNNNRNBNNNNRRNNNNRNNRNRNNBNNNBNNBBNNNNBBNBNNRNNNNNNRNNBNNRNBNNNNRNNNRNRBNNNNNNNNBNNNNNBBNBBNNNNNNNNNNNNNNBNNNRBRNNNNNNNNBBNBNNRBNN This method is
implemented in findBestStrategyGenetic(7, 10000000, 10000, .01).
Conclusion: The genetic algorithm was the clear winner - even with non-optimal generation sizes it did better than both of the other strategies. It's always neat to see how, without any knowledge of how to pick a good strategy encoded in the program, we can get a good strategy that's certainly better than we could do by hand.
Source code: The code is written in C++ for speed. Here are the source files: