Mastermind for the computer player
Most computer games provide a 'demo mode'. Getting the computer to play against itself and win, however, is far trickier. (If the game is not compromised, that is.) Achieving that for a game like invaders or snapper is not a trivial exercise, in the site's view. (Of course, at high speed when the game becomes unplayable by a human, almost any computer code will do better.) This page provides a computer program which plays mastermind- if you do not know the game, this section will refresh your memory.
Mastermind is about guessing a 4- digit number within say, 12 moves, all digits being different. For each guess, the number of correct digits is given, as well as how many of them are in the proper place, too.
The program finds how many right digits are in the range 0-3, 4-7 and 8-9. Then the digits are determined precisely by changing one digit at a time. At most ten tries are needed, though typically only 7.
Also, the program shuffles the digits under test before trying them, so that positional data is acquired at the same time. It is more demanding to get the digits in the right order, too. Whenever the number of properly placed digits is zero, clearly these digits can be excluded from the corresponding positions. Additional information is easily obtained when the number of right digits is the same as the number of digits in their rightful place. This gets the program success rate close to 90%. Subsequent improvements, have to be won hard, though:
Once the proper digits have been found, it is seen that the best practice is to permute them randomly for the tests following. Comparison with past tests to avoid duplication does not seem to be much use. When the proper position of one digit is known, it may be seen to be misplaced in a specific test. If correctly guessed digits exceed rightfully placed digits by one, the exact locations for the remaining digits can be deduced. Regrettably, this doesn't happen often, either.
Eventually, the number of times a digit has been placed in a column and the corresponding number of properly positioned digits are recorded. They can be combined to yield a probability of the digit being correctly assumed in that location. Of course any number can be guessed correctly within 17 tries at most, but this will only worsen the average number of guesses needed. It is startling that this performance is procured without scanning past guesses again, in order to milk additional data from them.
By now though, the program is probably no worse than the average human player, and sooner or later, the law of diminishing returns sets in. Of course, claims of optimality would be out of place- they usually are.
By the standards of this site, the code is easily the longest so far provided: It has been written by looking at different cases, which is not good programming practice, if somebody decided to switch, say, to guessing 5 digits instead of four. Too many If clauses are used, as well. No doubt a language offering extensive list processing facilities, like Prolog would have been more appropriate. (The program borders on artificial intelligence). However, the site has scant experience of it.
The code is shown after the usual substitution of hopefully more meaningful names for variables.