Dr. Achiya Elyasaf

We evolve heuristics to guide staged deepening search for the hard game of FreeCell, obtaining top-notch solvers for this NP-Complete, human-challenging puzzle. We first devise several novel heuristic measures and then employ a Hillis-style coevolutionary genetic algorithm to find efficient combinations of these heuristics. Our results significantly surpass the best published solver to date by three distinct measures: 1) Number of search nodes is reduced by 87%; 2) time to solution is reduced by 93%; and 3) average solution length is reduced by 41%. Our top solver is the best published Free-Cell player to date, solving 98% of the standard Microsoft 32K problem set, and also able to beat high-ranking human players.