Error Propagation in Game Trees

Benjamin Doerr and Ulf Lorenz
Additional contact information
Benjamin Doerr: http://www.numerik.uni-kiel.de/~bed/

Mathematical Methods of Operations Research, 2006, vol. 64, issue 1, 79-93

Abstract: Game tree search is the core of most attempts to make computers play games. We present a fairly general theoretical analysis on how leaf evaluation errors influence the value estimation of a game position at the root. By an approach using prime factorization arguments in the ring of polynomials, we show that in this setting the maximum number of leaf-disjoint strategies proving a particular property is a key notion. This number precisely describes the quality of the heuristic game value in terms of the quality of the leaf evaluation heuristics. We extend this model to include random nodes (rolls of a die). Surprisingly, this changes the situation: utill the number of leaf-disjoint strategies ensures robustness against leaf evaluation errors, but the converse is not true. An average node may produce additional robustness similar to additional leaf-disjoint strategies. This work extends earlier ones which only deal with 0, 1 valued nodes, or without randomness. Copyright Springer-Verlag 2006

Date: 2006
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1007/s00186-006-0064-6 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:mathme:v:64:y:2006:i:1:p:79-93

Ordering information: This journal article can be ordered from
http://www.springer.com/economics/journal/00186

DOI: 10.1007/s00186-006-0064-6

Access Statistics for this article

Mathematical Methods of Operations Research is currently edited by Oliver Stein

More articles in Mathematical Methods of Operations Research from Springer, Gesellschaft für Operations Research (GOR), Nederlands Genootschap voor Besliskunde (NGB)
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().