Implementing Fast Heuristic Search Code

Proceedings of the International Symposium on Combinatorial Search, 5

Volume

Vol. 5 No. 1 (2012): Fifth Annual Symposium on Combinatorial Search

Full Papers

Published papers rarely disclose implementation details. In this paper we show how such details can account for speedups of up to a factor of 28 for different implementations of the same algorithm. We perform an in-depth analysis of the most popular benchmark in heuristic search: the 15-puzzle. We study implementation choices in C++ for both IDA* and A* using the Manhattan distance heuristic. Results suggest that several optimizations deemed critical in folklore provide only small improvements while seemingly innocuous choices can play a large role. These results are important for ensuring that the correct conclusions are drawn from empirical comparisons

10.1609/socs.v3i1.18245