SIPPER

1) PAPER TITLE 

   Evolution of an Efficient Search Algorithm 

   for the Mate-In-N Problem in Chess


2) AUTHORS

   Ami Hauptpman
   Dept. of Computer Science
   Ben-Gurion University
   Be'er Sheva 84105, Israel
   amiha@cs.bgu.ac.il

   Moshe Sipper
   Dept. of Computer Science
   Ben-Gurion University
   Be'er Sheva 84105, Israel
   sipper@cs.bgu.ac.il


3) CORRESPONDING AUTHOR 

   Moshe Sipper


4) ABSTRACT
 
   We propose an approach for developing efficient search algorithms 
   through genetic programming.  Focusing on the game of chess we 
   evolve entire game-tree search algorithms to solve the 
   Mate-In-N problem: find a key move such that even with the 
   best possible counterplays, the opponent cannot avoid being mated 
   in (or before) move N. We show that our evolved search algorithms 
   successfully solve several instances of the Mate-In-N problem, for 
   the hardest ones developing 47% less game-tree nodes than 
   CRAFTYb --a state-of-the-art chess engine with a ranking of 2614 points. 
   Improvement is thus not over the basic alpha-beta algorithm, but over 
   a world-class program using all standard enhancements.


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) STATEMENT

   Our evolved search algorithms perform better than CRAFTY, 
   a world-class chess engine, in the task of finding mates-in-5 
   and less. This is a human-competitive achievement for several 
   reasons:

   O First, IMPROVEMENT IS OVER A WORLD-CLASS PROGRAM, DESIGNED BY HUMANS, 
     AND NOT OVER A STANDARD SEARCH ALGORITHM. While evolving search 
     algorithms has been done before to some small extent, results were  
     always compared to standard algorithms (such as alpha-beta or f-negascout). 
     Here, we competed against a far superior opponent, with state-of-the-art 
     search enhancements (including hash-tables, quiescence search, and other 
     powerful pruning heuristics). CRAFTY has been under development for over 
     a decade, and won second place in the Computer Speed-Chess Championship 
     held in Bar-Ilan in 2004. 
     THUS WE BEAT ONE OF THE TOP ENGINES IN THE WORLD.

   O Second, THE MATE-IN-N TASK, IN WHICH WE OUTPERFORMED CRAFTY, IS A 
     CRUCIAL TASK FOR CHESS ENGINES. Games may be won or lost for missing 
     a single mating combination (either the player's or the opponent's). 
     Therefore, considerable effort is put into finding mates in chess 
     engines (for example, in such positions, Deep Blue examines twice the 
     normal number of nodes [Campbell et al, 2002]). Moreover, since 
     competitive chess engines rely heavily on search, pruning the search 
     tree is the focus of developmental efforts, since viewing less nodes 
     leads to viewing nodes that are more important and thus better play. 
     In that sense, WE FAIRED BETTER ON THE CENTRAL TASK OF A CHESS ENGINE.

   O Third, we also outperformed previously evolved search algorithms. 
     As OUR ENTIRE SEARCH IS SUBJECT TO EVOLUTION (and not only parts of it, 
     as in [Gross et al., 2002], for example), evolution itself finds better 
     combinations of search and knowledge (and not the human GA/GP programmer 
     who designed scaffolding algorithms in previous experiments). Thus, 
     we applied evolution to a higher degree---to decide when to rely more 
     on search and when to rely more on knowledge. 
     Hence, the classical AI tradeoff of search vs. knowledge was not solved by 
     a human, but was left for evolution. As a result, we attained superb results.


7) CITATION

   A. Hauptman and M. Sipper.  
   "Evolution of an efficient search algorithm for the Mate-in-N 
   Problem in Chess." In M. Ebner, M. Ob Neill, A. Ekart, L. 
   Vanneschi, and A. I. Esparcia-Alcazar, editors, Proc. 10th 
   European Conf. on Genetic Programming (EuroGP 2007), vol. 4445 of 
   Lecture Notes in Computer Science, pages 78b 89, Valencia, Spain, 
   2007. Springer.


8) STATEMENT OF PRIZE DISTRIBUTION

   Any prize money, if any, is to be divided equally among the co-authors.


9) COMPARISON TO OTHER HUMAN-COMPETITIVE ENTRIES

   Why the judges should consider the entry as "best" in comparison to other 
   entries that may also be "human-competitive":

   O EVOLVING AN ENTIRE ALGORITHM, rather than a solution or solution blueprint, 
     is hard, arguably ONE OF THE HARDEST TASKS faced by EC practitioners, 
     with relatively few highly successful examples. We HAVE EVOLVED AN 
     ENTIRE SEARCH ALGORITHM in a truly ARDUOUS DOMAIN---chess---where man 
     and machine compete ferociously. Direct design of algorithms by humans 
     is itself no mean feat (to understate the caseb &), let alone evolving such 
     algorithms. 

   O Moreover, at the same time, WE SUCCESSFULLY COMPETE IN YET ANOTHER grueling 
     and time-honored domain of AI: search algorithms. 

   Thus we have demonstrated a DOUBLE STRIKE, as it were: SUCCESSFUL HUMAN 
   COMPETITIVENESS IN BOTH CHESS AND SEARCH.