资源论文Limited Lookahead in Imperfect-Information Games

Limited Lookahead in Imperfect-Information Games

2019-11-18 | |  56 |   40 |   0

Abstract Limited lookahead has been studied for decades in perfect-information games. This paper initiates a new direction via two simultaneous deviation points: generalization to imperfect-information games and a game-theoretic approach. The question of how one should act when facing an opponent whose lookahead is limited is studied along multiple axes: lookahead depth, whether the opponent(s), too, have imperfect information, and how they break ties. We characterize the hardness of finding a Nash equilibrium or an optimal commitment 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) according to a fixed rule, or 3) adversarially. The impact of limited lookahead is then investigated experimentally. The limited-lookahead player often 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.

上一篇:A Characterization of n-Player Strongly Monotone Scheduling Mechanisms

下一篇:Impartial Peer Review

用户评价
全部评价

热门资源

  • Stratified Strate...

    In this paper we introduce Stratified Strategy ...

  • The Variational S...

    Unlike traditional images which do not offer in...

  • Learning to learn...

    The move from hand-designed features to learned...

  • A Mathematical Mo...

    Direct democracy, where each voter casts one vo...

  • Learning to Predi...

    Much of model-based reinforcement learning invo...