04-09-2012, 03:51 PM
A Heuristic Hillclimbing Algorithm for Mastermind
mastermind.ppt (Size: 140.5 KB / Downloads: 36)
Mastermind
A constraint optimisation problem
Studied from perspectives of:
combinatorics
information theory
game theory
artificial intelligence
evolutionary computation
Rules of Mastermind
A 2-player game:
code maker selects a secret code and score’s opponents guesses against it
code breaker attempts to find secret code with as few guesses as possible
Secret code is a sequence of 4 colours from the set {red, yellow, blue, green, black, white}
Objectives
1. Traditional objective is to minimise number of guesses needed to find secret code
2. For computer players also of interest to minimise number of codes considered as potential guesses
Our algorithm is similar to existing Genetic Algorithm players on (1) but better on (2)
General Strategies
Number of possible codes is finite
Each new guess rules out some possibilities
Strategically optimal strategies
make guesses we know are incorrect but which maximise number of possibilities ruled out
Stepwise optimal
make only guesses that could be correct
A Useful Property of Mastermind
Each guess is scored as 1 of 14 possible combinations of black and white pegs
So all guesses belong to 1 of 14 sets of guesses
If we score a potential guess against the last guess, the secret code will be in the set which scores the same as the last guess against the secret code
This lets us evaluate potential guesses against our last guess before making our next guess
Conclusions
Our method makes a similar number of guesses but considers far fewer potential guesses
Our method is less complex than GA methods
Further optimisation may be possible
A case where domain knowledge allows randomised hillclimbing to outperform GAs
Application to related constraint optimisation problems may be possible