Learning from Heuristics in Search Domains

Contents

Heuristic functions for single-agent search applications estimate the cost of the optimal solution. When multiple heuristics exist, taking their maximum is an effective way to combine them. A new technique is introduced for combining multiple heuristic values. Inspired by the evaluation functions used in two-player games, the different heuristics in a singleagent application are treated as features of the problem domain. An ANN is used to combine these features into a single heuristic value. This idea has been implemented for the sliding-tile puzzle and the 4-peg Towers of Hanoi, two classic single-agent search domains. Experimental results show that this technique can lead to a large reduction in the search effort at a small cost in the quality of the solution obtained. To show the applicability of our learning approach we have also implemented it on the game of chess as a benchmark of two players games. Our experimental results show that the proposed learning strategy is effective in winning against an opponent who offers its best survival defense using Nalimov database of best endgame moves.