---
title: "Recent Progress in Heuristic Search: A Case Study of the Four-Peg Towers of Hanoi Problem"
authors:
  - "Richard E. Korf"
  - "Ariel Felner"
doi: ""
url: "https://ijcai.org/proceedings/2007/374"
pdf: "https://ijcai.org/proceedings/2007/0374.pdf"
venue: "Proceedings of the Twentieth International Joint Conference on Artificial Intelligence"
year: 2007
pages: "2324-2328"
track: ""
keywords:
---

# Recent Progress in Heuristic Search: A Case Study of the Four-Peg Towers of Hanoi Problem

Richard E. Korf, Ariel Felner

*Proceedings of the Twentieth International Joint Conference on Artificial Intelligence*, pages 2324-2328.

## Abstract

We integrate a number of new and recent advances in heuristic search, and apply them to the four-peg Towers of Hanoi problem. These include frontier search, disk-based search, parallel processing, multiple, compressed, disjoint, and additive pattern database heuristics, and breadth-first heuristic search. New ideas include pattern database heuristics based on multiple goal states, a method to reduce coordination among multiple parallel threads, and a method for reducing the number of heuristic calculations. We perform the first complete breadth-first searches of the 21 and 22-disc four-peg Towers of Hanoi problems, and extend the verification of presumed optimal solutions to this problem from 24 to 30 discs. Verification of the 31-disc problem is in progress.