The report presents the work done to investigate search tree algorithms used to solve puzzles and games. Then the algorithms are applied to solve the Blocks-World puzzle .
The method used is building a search tree and exploring it to find the solution. The algorithms used are mixture of blind search and heuristic search. For the blind search, the algorithms used are depth-first, breadth-first and iterative deepening. Different ways of calculating the heuristic values are discussed but only one was used in the implementation.
The key results are, despite the game may look trivial at the first glance; blind search techniques were not able to find the solution in a reasonable time. On the other hand, involving heuristic estimates in the search tree resulted in notable outcomes. A solution for the puzzle was found. Nevertheless, the blind search algorithms were able to find the solution when reducing the puzzle conditions (reduce world size or the number of blocks to be moved).
This project was built as a coursework for the ‘Artificial Intelligence’, 1st semester in MSc Artificial Intelligence at the University of Southampton.