Abstract

Sokoban-type puzzles and their variants involve complex planning and decision-making challenges in wide and deep search spaces. Such scenarios are interesting for testing path-planning algorithms. This document uses A ∗ and IDA ∗ (Iterative Deepening A *) algorithms to solve Zen Puzzle Garden game boards; a Sokoban-type puzzle where you need rake the sandy area completely. The algorithms are evaluated in terms of speed and node expansion in moderately complex boards. Additionally, we implement three improvements: transposition tables, move ordering, and deadlock tables. The results show that IDA ∗ with the three proposed improvements is on average faster than A *. Although its strength is its low memory usage, it can be seen that it is very competitive versus A ∗ in terms of time usage. Transposition tables and deadlocks tables reduce by 500 times the number of nodes expanded by the IDA ∗ without improvements. On the other hand, the ordering of nodes is not very effective for some boards, which causes a worse performance of the IDA ∗ algorithm, giving rise to greater exploration in boards that do not lead to the solution. Studying these algorithms can be beneficial in the field of path-finding for Sokoban-type game domains or solver-based procedural content generators.