• Calendar

September 16, Wednesday
12:15 – 13:40

We evolve heuristics to aid search algorithms. The main method applied is Genetic Programming (GP), a sub-class of evolutionary algorithms, in which the individuals undergoing artificial evolution are (simple, yet large) LISP programs. In the domain of games, where search spaces are enormous, and the number of possible heuristics is even larger, the advantages of GP come to the fore, as an alternative to manually fine-tuning static evaluation functions. First, this method is demonstrated in the domain of Chess - both for endgames and the Mate-in-N problem. We further analyze the performance of evolved players and show that they demonstrate some emergent features. Second, we move to single-player games (puzzles) and show that a slightly-modified version of this methodology (using a form of policies), produces strong players for the 6x6 and 8x8 Rush-Hour puzzle, a PSPACE-Complete problem (for the nxn case). Some broader conclusions are drawn for the interplay between search and knowledge.