1) PAPER TITLE Evolutionary Design of FreeCell Solvers 2) AUTHORS Achiya Elyasaf, achiya.e@gmail.com Ami Hauptman, 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 human-challenging puzzle. We first devise several novel heuristic measures using minimal domain knowledge and then use them as building blocks in two evolutionary setups involving a standard genetic algorithm and policy-based, genetic programming. Our evolved solvers outperform the best FreeCell solver to date by three distinct measures: 1) number of search nodes is reduced by over 78%; 2) time to solution is reduced by over 94%; and 3) average solution length is reduced by over 30%. Our top solver is the best published FreeCell player to date, solving 99.65% of the standard Microsoft 32K problem set. Moreover, it is able to convincingly 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 (B) We were able to evolve a killer application for the game of FreeCell, a highly challenging game for humans. Our evolved strategy is faster and better than ALL humans at a major FreeCell website (freecell.net). (D,F,G) FreeCell is considered to be one of the most difficult domains for classical planning. Our evolved solvers are the most successful reported ones to solve this difficult problem with search. Our solvers are evolved using policy-based GP and are publishable in their own right. Our policy-based GP is better than other methods both in terms of scalability and performance. (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. 7) CITATION A. Elyasaf, A. Hauptman and M. Sipper. "Evolutionary Design of FreeCell Solvers" IEEE Transactions on Computational Intelligence and AI Games, (conditionally accepted, revision submitted) 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 Last year we used a simple GA and a number of heuristics we designed to evolve GA-FreeCell, which we compared to humans whose statistics are available at a major FreeCell online website (freecell.net). As noted in last year's paper: "Sorted according to number of games played, the no. 1 player played 147,219 games, achieving a win rate of 97.61%. This human is therefore pushed to the second position, with our top player (98.36% win rate) taking the first place... If the statistics are sorted according to win rate then our player assumes the no. 9 position." Last year's GA-FreeCell is therefore a top performer, but it is still at a distance of a few humans from the very top. Try as we did, tweaking the GA did not improve performance. So we went back to the drawing board and dumped the GA entirely, in favor of a far more sophisticated approach, involving policies (a form of rule-based systems) evolved through GP. One major advantage of this setup is its allowing evolved solvers to behave differently at different stages of the game, something we could not achieve with the GA. This feature proved of immense value. Our significant improvement is documented in this year's paper: "The site statistics, which we downloaded on December 13, 2011, included results for 83 humans who met the minimal game requirement -- all but two of whom exhibited a win rate greater than 91%. Sorted according to the number of games played, the no. 1 player played 160,237 games, achieving a win rate of 96.02%. This human is therefore pushed to the fourth position, with our top player (99.65% win rate) taking the first place, our GA-FreeCell taking the second place... When sorted according to average solving time, the fastest human player with win rate above 90% solved deals in an average time of 104 seconds and achieved a win rate of 96.56%. This human is therefore pushed to the fourth position, with... GA-FreeCell in the second place and Policy-FreeCell taking the first place. If the statistics are sorted according to win rate then our Policy-FreeCell player takes the first place with a win rate of 99.65%, while GA-FreeCell attains the respectable 11th place." Policy-FreeCell is now #1 any which way the statistics are examined. It is significantly better than last year's GA-FreeCell. We were also able to defeat previous top algorithmic approaches quite convincingly. The result was recently conditionally accepted by the major journal in the field of CI & Games, namely, the IEEE Transactions on Computational Intelligence and AI in Games (IEEE TCIAIG). One reviewer wrote: "The results are strong, well analysed, and may be highly applicable to other domains." Another opined that, "The idea is seemingly novel, intuitive, and significant." FreeCell 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. 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.