| Summary: | Decision makinq in larqe domains very often involves the necessity to handle unclear situations. So the ability to base ones decisions on estimates is important in real life as well as in complicated qames. Siqnificantly, even the analysis of chess positions by qrandmasters often results in the conclusion "unclear". The conventional methods in two-person qames (which are by far the most successful ones up to now) use point-values and depth-first (alpha-beta) minimax search (mostly in a brute-force manner). Unfortunately, this approach has a fundamental drawback in unclear situations: it iqnores the uncertainty of the values. Even refinements like quiescence search [4] or extendinq the horizon of the fUll-width search (e.q. by not-countinq certain moves as a ply of depth) [5] cannot completely resolve this defect. Another method proposed by Pearl [7] treats estimated values as probabilities and uses a product propaqation rule. This way the uncertainty of values is qiven too much emphasis and it seems not to be used in practical proqrams. Additionally, this method requires searchinq of the whole tree unlike alpha-beta minimax. Much more convenient for our problem are methods usinq ranqes U, 8] or even probability distributions [6] as values. Unfortunately, they are impracticable for a larqe domain up to now, because of the qreat difficulty in findinq valid bounds (parameters of the distribution). consequently, the converqence of such searches is very hard to quarantee
|
|---|