When is it better not to look ahead?
Title | When is it better not to look ahead? |
Publication Type | Journal Articles |
Year of Publication | 2010 |
Authors | Nau DS, Luštrek M, Parker A, Bratko I, Gams M |
Journal | Artificial Intelligence |
Volume | 174 |
Issue | 16–17 |
Pagination | 1323 - 1338 |
Date Published | 2010/11// |
ISBN Number | 0004-3702 |
Keywords | Game-tree search, Lookahead pathology, minimax |
Abstract | In situations where one needs to make a sequence of decisions, it is often believed that looking ahead will help produce better decisions. However, it was shown 30 years ago that there are “pathological” situations in which looking ahead is counterproductive. Two long-standing open questions are (a) what combinations of factors have the biggest influence on whether lookahead pathology occurs, and (b) whether it occurs in real-world decision-making.This paper includes simulation results for several synthetic game-tree models, and experimental results for three well-known board games: two chess endgames, kalah (with some modifications to facilitate experimentation), and the 8-puzzle. The simulations show the interplay between lookahead pathology and several factors that affect it; and the experiments confirm the trends predicted by the simulation models. The experiments also show that lookahead pathology is more common than has been thought: all three games contain situations where it occurs. |
URL | http://www.sciencedirect.com/science/article/pii/S0004370210001402 |
DOI | 10.1016/j.artint.2010.08.002 |