1) PAPER TITLE GA-FreeCell: Evolving Solvers for the Game of FreeCell 2) AUTHORS Achiya Elyasaf, achiya.e@gmail.com Ami Hauptpman, amihau@gmail.com Moshe Sipper, sipper@cs.bgu.ac.il Physical address for all: Department of Computer Science, Ben-Gurion University of the Negev, Beer-Sheva 84105, ISRAEL 3) CORRESPONDING AUTHOR Moshe Sipper 4) ABSTRACT 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 FreeCell player to date, solving 98% of the standard Microsoft 32K problem set, and also able to beat high-ranking human players. 5) CRITERIA (B) The result is equal to or better than a result that was accepted as a new scientific result at the time when it was published in a peer-reviewed scientific journal. (D) The result is publishable in its own right as a new scientific result---independent of the fact that the result was mechanically created. (F) The result is equal to or better than a result that was considered an achievement in its field at the time it was first discovered. (G) The result solves a problem of indisputable difficulty in its field. (H) The result holds its own or wins a regulated competition involving human contestants (in the form of either live human players or human-written computer programs). 6) WHY THE RESULT SATISFIES THE CRITERIA Why the result satisfies criterion (B) -------------------------------------- We were able to evolve a true killer application for the game of FreeCell, a highly challenging game for humans, which was also proven to be NP-complete. Our evolved strategy requires far less search AND less time to solve the most difficult known instances, as compared to any other published, unpublished, or breathing method, including: (a) Novel hand-crafted heuristics, (b) human-designed solvers, (c) humans. (The reader is welcome to try their hand at http://www.freeonlinegames.com/game/freecell-solitaire.html) Why the result satisfies criteria (D,F,G) ----------------------------------------- FreeCell is considered to be one of the most difficult domains for classical planning (F. Bacchus), evidenced by the poor performance of planners in regulated International Planning Competitions (IPCs). Our evolved solvers for the game of FreeCell are the most successful reported ones to solve this difficult problem with search, and thus the result is publishable in its own right. Our method is better than other method for several reasons: (1) Scalability: Our algorithm is combined from low-level heuristics that are not dependent on board size. This is in contrast to other methods, such as PDBs (pattern databases), which are not scalable and consume a large amount of memory. (2) Search quality: Our results significantly surpass the best published solver to date by three distinct measures: a) Number of search nodes is reduced by 87%; b) time to solution is reduced by 93%; and c) average solution length is reduced by 41%. (3) Percentage of solved problems: Our top solver manages to solve 98% of the standard Microsoft 32K problem set, compared to 96% solved by the best human-designed solver to date. Why the result satisfies criterion (H) -------------------------------------- Victory over humans is two-fold: (1) We have developed the best algorithm for the hard FreeCell game, better than any algorithm designed by humans. (2) Our evolved solver's performance far surpasses that of human players, in terms of game time: Over 70 times faster. This is important because it means that the algorithm is efficient in every way, both using less nodes during the search AND running in less time. In addition, our evolved solver solves 98.36% of the problem instances, compared to 97.61% solved by the top human player. 7) CITATION A. Elyasaf, A. Hauptman and M. Sipper. "GA-FreeCell: Evolving Solvers for the Game of FreeCell", Genetic and Evolutionary Computation Conference (GECCO 2011), July 2011, Dublin, Ireland. 8) STATEMENT OF PRIZE DISTRIBUTION Any prize money, if any, is to be divided equally among the three co-authors. 9) COMPARISON TO OTHER HUMAN-COMPETITIVE ENTRIES PUSHING EVOLUTION FURTHER ------------------------- This is the most difficult single-player search (i.e., *planning*) problem solved (so successfully) with evolution thus far. FreeCell requires an enormous amount of search, due both to long solutions and to large branching factors. SEVERAL DEGREES (AND MODALITIES) OF IMPROVEMENT ----------------------------------------------- The popular Enhanced Iterative Deepening algorithm was outperformed by the HSD algorithm, all of which were beaten by our evolved solvers. Evolution managed to take our best designed ingredients of limited performance and transform them into HIGHLY successful strategies. Our EA not only beat human AI researchers but also all human players of FreeCell on record. SOLVING A DIFFICULT PROBLEM WITH A LONG HISTORY ----------------------------------------------- Difficult puzzles---involving search and planning problems---have a longstanding tradition in the AI community. Among them, FreeCell was used as such a domain both in several International Planning Competitions (the first of them in 2000), and in numerous attempts to construct state-of-the-art planners reported in the literature. Yet, in all competitions, all of the general-purpose planners performed poorly on this domain. In 2009, Heineman published the best FreeCell solver to date. Our evolutionary algorithm beats Heineman's algorithm in all measures by a wide margin. FreeCell is not only challenging to AI researchers aiming to design winning strategies, it is indeed highly challenging for humans who "merely" wish to *play* the game. We have shown that we are able to convincingly beat top-ranking humans.