Expectiminimax AlgorithmEXPECTIMINIMAX gives perfect play for non-deterministicgamesLike MINIMAX, except add chance nodesFor max node return highest EXPECTIMINIMAX ofSUCCESSORSFor min node return lowest EXPECTIMINIMAX ofSUCCESSORSFor chance node return average of EXPECTIMINIMAXof SUCCESSORSHere exact values of evaluation function do matter(“probabilities”, “expected gain”, not just order)α-β pruning possible by taking weighted averages accord-ing to probabilitiesF. C. Langbein, CM0312 Artificial Intelligence – II Problem Solving by Searching; II.3 Adversarial Search 13*-Minimaxα-β pruning possible by taking weighted averages accord-ing to probabilities*-Minimax (B. Ballard, 1983)50% improvement with random node orderOrder of magnitude improvement with optimal orderAdd cut-offs to chance nodesMax and min nodes as in alpha-beta algorithmAssume that all branches not searched have the worst-case resultAssume range of evaluating values is bound by interval[L, U]F. C. Langbein, CM0312 Artificial Intelligence – II Problem Solving by Searching; II.3 Adversarial Search 14*-Minimax Cut-OffAlpha cut-off in chance node with N equally likely children1N((V1+ ···+ Vl−1) explored+ Vl current+ U ∗ (n − l) estimated future(worst case)) ≤ αBeta cut-off in chance node with N equally likely children1N((V1+ ···+ Vl−1) explored+ Vl current+ L ∗ (n − l) estimated future(worst case)) ≥ βBounds passed to C from A with[L, U]=[−10, 10]–13(2 + Vl+ L ∗ 1) ≥ β ⇒ Vl≥ 20–13(2+Vl+U∗1) ≤ α ⇒ Vl≥ −3F. C. Langbein, CM0312 Artificial Intelligence – II Problem Solving by Searching; II.3 Adversarial Search
View Full Document
Unlocking...