RANDOMISED EVALUATIONS IN SINGLE-AGENT SEARCH

Article type: Research Article

Authors: Althöfer, Ingo^{a; 1} | Heuser, Susanne^{b; 2}

Affiliations: [a] Jena, Germany | [b] Cologne, Germany

Note: [1] Faculty of Mathematics and Computer Science, Friedrich-Schiller-University Jena, 07737 Jena, Germany. Email: [email protected].

Note: [2] ZAIK, University of Cologne, Weyertal 80, 50931 Cologne, Germany. Email: [email protected].

Note: [3] This article is based on the diploma thesis of Heuser (2003b).

Abstract: Heuristic tree search is a widely and successfully used principle in game-playing programs. Following an old investigation by Beal and Smith (1994) and a recent study by Sadikov, Bratko, and Konononenko (2003), we discuss depth-t search with randomised evaluation functions: the heuristic leaf evaluations at depth t of the game tree are artificially randomised before backing them up. Our experiments were performed for single-agent search, namely in the sliding tile puzzle SlideThree (Troyka, 2001). We construct six evaluation functions of different playing strength and compare them to their randomised versions. Furthermore we also study the perfect and the constant evaluation function and the dependence of the playing strength on the search depth. The main finding is that applying a random disturbance to the heuristic leaf values may considerably improve the playing strength of imperfect evaluation functions.3

DOI: 10.3233/ICG-2005-28106

Journal: ICGA Journal, vol. 28, no. 1, pp. 21-31, 2005