Using Knuth's Mastermind Algorithm for NetHack


Opposed to the naive attempt attempted by a friend, this one actually tries something intelligent.

The basic idea of this algorithm is to make a guess, and then delete entries that would not return the same result if applied to the guess.

Examples

Example One:

AAAAD AAABB,AAAAA,AAAAC,AAAAD 4

This (terse) output is it trying to solve for the pattern "AAAAD". The first guess is the hardcoded AAABB, which would return three gears and no tumblers. It then eliminates all possibilities that would not return three gears and no tumblers for the pattern "AAABB". Thus, the second guess is "AAAAA" with a result of four gears. From here it's mostly a matter of going through all of the guesses, starting with "C".

Example Two:

FFCDE AAABB,CCCCC,CDDDD,ECDEE,EDCFF,EFFCD,FCEFD,FDFEC,FEDCF 9

This is the most interesting of the nine turn solutions (both of the worst cases, ten turns, are uninteresting). Again, an initial guess of "AAABB", except this time it returns nothing, eliminating "A" and "B". "CCCCC" returns a gear and one is included in the next guess, "CDDDD". This time one gear and one tumbler is the result. This continues as it picks out that there's only one "E" and two "F" notes with guess five. From here it needs to get them in the right order. Note that the last guess does not match the desired pattern, this is because there's only one possibility left.

Improvements

The biggest improvement is to use what I've seen deemed as a "minmax" function. The point of this function is to get the guess that has the best worst case, or minimizes the maximum guesses left after getting the result. This was deliberately not implemented due to how slow this implementation is. Although running for just one solution isn't particularly slow, no more than a second; running it over all possible tunes took 9800 seconds, or about 2:45.

Results

Running over all 16,807 possible tunes took 93103 turns for an average of 5.5395 turns per tune. Worst case was 10, happened twice: "GFEDG" and "GGDEF".

Distribution of results:

 turns | number
----------------
     1 | 1
     2 | 19
     3 | 260
     4 | 1337
     5 | 6975
     6 | 5812
     7 | 2052
     8 | 336
     9 | 13
    10 | 2