de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Datenschutzhinweis Impressum Kontakt
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Zeitschriftenartikel

Error Propagation in Game Trees

MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44338

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

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

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


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-000F-22BD-5
Zusammenfassung
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.