Project Title: A Genetic Algorithms To Solve the Markov's Prison Puzzle
Student: Benjamin Humphrey
Course: MSci in Computer Science and Artificial Intelligence

Abstract:
Many puzzles and games exist in today's society, from old to new. Despite being easy 
to visualise and solve for humans, they are computationally difficult for computers to solve. 
While many puzzles have been solved a variety of times over, the core example of this 
being chess, there still exist new puzzles that are created, similar to pre-existing puzzles 
yet also with their own twists and rules that bind them.
The Markov's Puzzle is no different to many of these examples. It has rules that limit what 
can take place with each move and has states where it can win or loss at. What makes this 
puzzle quite unique is the randomness that the guards in this puzzle will always display, 
moving to areas based on probabilities with no certainty for moves in any situation.
As a result, the aim of this dissertation was to take this puzzle and build a system capable 
of producing paths of moves that one would be able to take from the start to the end. The moves 
would have to try to avoid the prisoner being caught by the guards in the puzzle, and as a 
result would mean that the path taken would have to have the highest chance that the method 
can nd to avoid the guards. Evaluation is done on the different effects that the population 
size of the genetic algorithm and the number of repeats that would take place within the genetic 
algorithm would have on the overall result, as well as comparing heuristics of significant 
different in order to determine and show the difference in effectiveness.