Transcript A Heuristic Hillclimbing Algorithm for Mastermind

A Heuristic Hillclimbing
Algorithm for Mastermind
Alexandre Temporel and Tim Kovacs
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}
Feedback on Guesses
For each guess, code maker returns:
• a black peg for each correct colour in correct
position
• a white peg for each correct colour in incorrect
position
NB: each colour only scores 1 peg
Example: (using integers instead of colours)
Secret code: 2413
Guess:
1233
Score:
1 black peg, 2 white pegs
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
Example
Secret Code: 2413
Guess 1:
1233
Score:
1 black, 2 white
For guess 2, we should use a combination which
scores 1 back, 2 white against guess 1
Any combination which does not cannot be the
secret code
Selecting Potential Guesses
How to select potential guesses to score against
our last guess?
• at random (Rosu)
• using a Genetic Algorithm (Bento, Merelo)
• our new method
Our Method
1. Submit a random guess and call it CFG
2. Induce a New Potential Guess (NPG) from CFG
as described on next slide
3. If NPG does not score the same as previous
guesses go to (2), otherwise submit it as new guess
4. If new guess scores 0 black 0 white then prevent
its colours being used again and go to (1)
5. If new guess scores as good or better than CFG
then adopt it as CFG
6. If new guess is secret code stop, otherwise (2)
Induction of New Potential Guesses
1. Select as many characters from CFG as it has
black pegs (correct colours in correct position)
and add to NPG
2. Select as many characters from CFG as it has
white pegs and assign them to random empty
positions in NPG
3. Fill any remaining positions with random
colours (but give higher probability to colours
not already used in steps 1 and 2).
Number of guesses to find secret code
Random
GA (Bento)
GA (Merelo)
SHC Code Tracker
SHC without CT
Size of Game
(colours x positions)
4x6
5x8
6x8
4.66
5.88
6.86
4.132
5.904
4.661
5.888
6.308
4.64
5.834
6.289
Number of Potential Guesses
Evaluated
Random
GA (Bento)
GA (Merelo)
SHC Code Tracker
SHC without CT
Size of Game
4x6
5x8
1295
32515
1029.9
279
2171
76.3
835
41.2
480.1
6x8
258000
2800
2759
Number of Potential Guesses
Evaluated
1000000
SEARCH SPACE SIZE
100000
10000
Random
Bento
Merelo
1000
Our
Method
100
4x6
10
5x8
6x8
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