Lookahead
Lookahead Strategies in Games
In decision-making situations where there are sufficiently good models of all the relevant information, it is generally believed that looking ahead (to predict the possible results of one's actions) will help to produce better decisions. However, it was shown 30 years ago by Nau that there are "pathological" situations in which looking ahead is counterproductive. Two long-standing open questions are (a) what factors cause or prevent lookahead pathology, and (b) whether it occurs in real-world decision-making.
We have developed models of lookahead search that show the interplay between lookahead pathology and the three major factors affecting it. Experimental studies in three well-known board games (chess, kalah, and the 8-puzzle) confirm the trends predicted by these models, and show that lookahead pathology is more common than had been thought: all three games contain situations where it occurs.
We also are developing ways to recognize when pathological situations occur in arbitrary games, and modify the decision-making mechanism to overcome the pathology. Our preliminary results show that by doing this we can outperform ordinary minimax algorithms, sometimes substantially.
Project lead: Dr. Dana Nau.
For additional information, please contact Dr. Dana Nau or Dr. Inon Zuckerman.
Last updated: November 2009 by John Dickerson.
Publication links contingent upon publication!
This page will be updated as our work enters print. For information about receiving draft publications, technical reports, and conference presentations, please do not hesitate to contact team members.
The following sections may include links to restricted access material. Please do not hesitate to contact a group member for instructions regarding how to obtain a username and password.
Presentation links contingent upon publication!
The following sections may include links to restricted access material. Please do not hesitate to contact a group member for instructions regarding how to obtain a username and password.
Software links contingent upon publication!