---
title: "Depth-bounded Discrepancy Search"
authors:
  - "Toby Walsh"
doi: ""
url: "https://ijcai.org/proceedings/1997/200"
pdf: "https://ijcai.org/proceedings/1997/0200.pdf"
venue: "Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence"
year: 1997
pages: "1388-1394"
track: "Search"
keywords:
---

# Depth-bounded Discrepancy Search

Toby Walsh

*Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence*, pages 1388-1394.

## Abstract

Many search trees are impractically large to explore exhaustivel y. Recently, techniques like limited discrepancy search have been proposed for improving the chance of finding a goal in a limited amount of search. Depth-bound ed discrepancy search offers such a hop e. The motivation behind depth-bounded discrepancy search is that branching heuristics are more likely to be wrong at the top of the tree than at the bottom . We therefore combine one of the best features of limited discrepancy search - the ability to undo early mistakes - with the completeness of iterative deepening search. We show theoretically and experimentally that this novel combination outperforms existing techniques.