Adapting Beyond the Depth Limit: Counter Strategies in Large Imperfect Information Games

We investigate how to adapt against known sub-optimal opponents while maintaining robustness against rational players in large imperfect-information zero-sum games. Previous approaches to large games use depth-limited search since examining the complete game tree is computationally infeasible. In computing a robust strategy against an opponent, the latest methods assume rational play beyond the search depth limit, restricting their ability to adapt to the opponent's behavior. To address this limitation, we introduce Adapting Beyond Depth-limit (ABD). This algorithm employs a strategy-portfolio approach-which is called matrix-valued statesfor depth-limited search. ABD is the first robust adaptation method capable of fully utilizing all available information about opponent models in large imperfect-information games. The matrix-valued states approach also simplifies the algorithm compared to previous methods that rely on optimal value functions. Our experiments demonstrate that ABD may double the utility when facing opponents who make mistakes beyond the depth and significantly improves utility against randomly generated opponents while maintaining safety against worst-case rational adversaries.