Limited Lookahead in Imperfect-Information Games

Limited lookahead has been studied for decades in perfect-information games. This paper initi-ates a new direction via two simultaneous devia-tion points: generalization to imperfect-information games and a game-theoretic approach. The ques-tion of how one should act when facing an oppo-nent whose lookahead is limited is studied along multiple axes: lookahead depth, whether the oppo-nent(s), too, have imperfect information, and how they break ties. We characterize the hardness of finding a Nash equilibrium or an optimal commit-ment strategy for either player, showing that in some of these variations the problem can be solved in polynomial time while in others it is PPAD-hard or NP-hard. We proceed to design algorithms for computing optimal commitment strategies for when the opponent breaks ties 1) favorably, 2) ac-cording to a fixed rule, or 3) adversarially. The impact of limited lookahead is then investigated experimentally. The limited-lookahead player of-ten obtains the value of the game if she knows the expected values of nodes in the game tree for some equilibrium, but we prove this is not sufficient in general. Finally, we study the impact of noise in those estimates and different lookahead depths. This uncovers a lookahead pathology.