AAAI Publications, Ninth Annual Symposium on Combinatorial Search

Font Size: 
Optimal Solitaire Game Solutions Using A* Search and Deadlock Analysis
Gerald Paul, Malte Helmert

Last modified: 2016-06-20


We propose an efficient method for determining optimal solutions to such skill-based solitaire card games as Freecell. We use A* search with an admissible heuristic function based on analyzing a directed graph whose cycles represent deadlock situations in the game state. To the best of our knowledge, ours is the first algorithm that efficiently determines optimal solutions for Freecell games. We believe that the underlying ideas should be applicable not only to games but also to other classical planning problems which manifest deadlocks.

Full Text: PDF