Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse




Journal Article

Error Propagation in Game Trees


Doerr,  Benjamin
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

There are no locators available
Fulltext (public)
There are no public fulltexts available
Supplementary Material (public)
There is no public supplementary material available

Doerr, B., & Lorenz, U. (2006). Error Propagation in Game Trees. Mathematical Methods of Operations Research, 64, 79-93.

Cite as:
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.