Multiple Symmetries in Sliding-Tile Puzzles: First Experiments

Contents

Since their introduction, symmetries have proven to be very powerful for the solution of different tasks related to heuristic search on sliding-tile puzzles. The most relevant being the boost of the heuristic values stored in Pattern Databases (PDBs), the construction time and storing size of PDBs, and the reduction in the number of written states in external search algorithms. Indeed, in the later, symmetries are almost a necessity in order to perform such complete search in acceptable time and space. All these applications only use single symmetries. As it turns out, multiple symmetries can also be utilized with very good results. In this paper, we explore the application of multiple symmetries on sliding puzzle problems and present some preliminary experimental results on complete explorations of state spaces using an external search algorithm. As it is shown, the net result is a 4-fold reduction in the number of written states with respect to an implementation that utilizes no symmetries.