Improving sliding-block puzzle solving using meta-level reasoning

Abstract

In this thesis, we develop a meta-reasoning system based on CBR which solves sliding-block puzzles. The meta-reasoning system is built on top of a search-based sliding-block puzzle solving program which was developed as part of the specialization project at NTNU. As part of the thesis work, we study existing literature on automatic puzzle solving methods and state space search, as well as the use of reasoning and meta-level reasoning applied to puzzles and games. The literature study forms the theoretical foundation for the development of the meta-reasoning system. The meta-reasoning system is further enhanced by adding a meta-control cycle which uses randomized search to generate new cases to apply to puzzles. In addition, we explore several ways of improving the underlying solver program by trying to solve hard puzzles by using the solution for easier variants, and by developing a more memory-efficient way of representing puzzle configurations. We evaluate the results of our system, and shows that it offers a slight improvement compared to solving the puzzles with a set of general cases, as well as showing vast improvement for a few isolated test cases, but the performance is slightly behind the hand-tuned parameters we found in the specialization project. We conclude our work by identifying parts of our system where improvement can be done, as well as suggesting other promising areas for further research.