Automatic Move Pruning in General Single-Player Games Article Swipe

PDF

Related Concepts

Pruning Computer science Reduction (mathematics) Tree (set theory) Overhead (engineering) Class (philosophy) Search tree Range (aeronautics) Depth-first search State (computer science) Artificial intelligence Algorithm Machine learning Search algorithm Mathematics Engineering Biology Aerospace engineering Agronomy Mathematical analysis Geometry Operating system

Neil Burch , Robert C. Holte ·

YOU? · · 2021 · Open Access · · DOI: https://doi.org/10.1609/socs.v2i1.18187 · OA: W1591786641

Move pruning is a low-overhead technique for reducing the size of a depth first search tree. The existing algorithm for automatically discovering move pruning information is restricted to games where all moves can be applied to every state. This paper demonstrates an algorithm which handles a general class of single player games. It gives experimental results for our technique, demonstrating both the applicability to a range of games, and the reduction in search tree size. We also provide some conditions under which move pruning is safe, and when it may interfere with other search reduction techniques.