Ethan Burns, Matthew Hatem, Michale J. Leighton, and Wheeler Ruml, Implementing Fast Heuristic Search Code, Proceedings of the Fifth Annual Symposium on Combinatorial Search (SoCS-12), 2012. C++ source code


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.