Item

Abstract

Game tree search is the core of most attempts to teach computers play games. We present a fairly general theoretical analysis on how evaluation error influence the value estimation of a game position. We extend the work of Lorenz and Monien [7] in two directions. Firstly, we allow arbitrary game values. By a different approach, we show that also in this setting the number of leaf-disjoint strategies proving a particular property is a key notion. This number precisely describes the order of growth of the heuristic game value in the terms of the quality of the leaf evaluation heuristics. Secondly, in allow random nodes (rolls of a die). Surprisingly, this changes the situation: Still the number of leaf-disjoint strategies ensures robustness against leaf evaulation errors, but the converse is not true. An average node may produce additional robustness like further leaf-disjoint strategies.