A Genetic Algorithm Approach to the Prisoners & Guards Puzzle : A Genetic Algorithm Approach to the Prisoners & Guards Puzzle
CPSC 5185 Intro to Artificial Intelligence
April 6, 2004
Description of Prisoners & Guards Puzzle : Description of Prisoners & Guards Puzzle
Adjacent Squares : Adjacent Squares
Sample 3x3 Board : Sample 3x3 Board
5 prisoners – can we do better?
A Better 3x3 Board : A Better 3x3 Board
6 prisoners – this is the maximum
Some 4x4 Boards : Some 4x4 Boards
An Optimal 4x4 Board : An Optimal 4x4 Board
Finding Maximum No. Prisoners : Finding Maximum No. Prisoners Characterize p(n), the max. no. prisoners on a valid n n board.
Larger Values of n : Larger Values of n
Brute force doesn’t work
Trying an evolutionary approach
Genetic Algorithm Overview : Genetic Algorithm Overview Each generation has 500 chromosomes
Spawn offspring through crossover and mutation operations
100 most fit in a generation retained in next generation
GA Overview, continued : GA Overview, continued Parents selected randomly, selection probabilities are proportional to fitness vals
Two parents always produce two offspring
Cataclysm prevents stagnation
Converting Boards to Chromosomes : Converting Boards to Chromosomes Treat each board configuration as a “chromosome” (ignore placement rule)
The Crossover Operation : The Crossover Operation
Crossover probability 0.7. Parents Children
Mutation : Mutation
Mutation probability 0.001 for each board square
Toggle value if mutation occurs
Survival of the fittest : Survival of the fittest Fitness function 1: fitness = total number of prisoners
Fitness function 2: fitness = (no. pris.) x (validity) validity = (# valid sqrs) / (total sqrs)
Fitness Comp. Example : Fitness Comp. Example F1 = 6 F2 = 6 ( 5 / 9 ) = 30 / 9
Outline of the Algorithm : Outline of the Algorithm
See handout sheet
Comparing Performances Using Two Fitness Functions : Comparing Performances Using Two Fitness Functions
See Excel printout
My Best 5x5 Example : My Best 5x5 Example
A 6x6 Example : A 6x6 Example
Lower Bounds for p(n) : Lower Bounds for p(n) For odd n, striping pattern yields
For even n, goose pattern yields
A Better 6x6 : A Better 6x6
Striping Not Best for 9x9 : Striping Not Best for 9x9
Questions : Questions Is there a better lower bound for p(n)?
What is a good upper bound for p(n)?