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
Get full access to this article
View all access options for this article.