hide
Free keywords:
-
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.
