Ing. David Milec

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 states -- for 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.

In zero-sum games, the optimal strategy is well-defined by the Nash equilibrium. However, it is overly conservative when playing against suboptimal opponents and it can not exploit their weaknesses. Limited look-ahead game solving in imperfect-information games allows superhuman play in massive real-world games such as Poker, Liar's Dice, and Scotland Yard. However, since they approximate Nash equilibrium, they tend to only win slightly against weak opponents. We propose theoretically sound methods combining limited look-ahead solving with an opponent model, in order to 1) approximate a best response in large games or 2) compute a robust response with control over the robustness of the response. Both methods can compute the response in real time to previously unseen strategies. We present theoretical guarantees of our methods. We show that existing robust response methods do not work combined with limited look-ahead solving of the shelf, and we propose a novel solution for the issue. Our algorithm performs significantly better than multiple baselines in smaller games and outperforms state-of-the-art methods against SlumBot.

Solution concepts of traditional game theory assume entirely rational players; therefore, their ability to exploit subrational opponents is limited. One type of subrationality that describes human behavior well is the quantal response. While there exist algorithms for computing solutions against quantal opponents, they either do not scale or may provide strategies that are even worse than the entirely-rational Nash strategies. This paper aims to analyze and propose scalable algorithms for computing effective and robust strategies against a quantal opponent in normal-form and extensive-form games. Our contributions are: (1) we define two different solution concepts related to exploiting quantal opponents and analyze their properties; (2) we prove that computing these solutions is computationally hard;(3) therefore, we evaluate several heuristic approximations based on scalable counterfactual regret minimization (CFR); and (4) we identify a CFR variant that exploits the bounded opponents better than the previously used variants while being less exploitable by the worst-case perfectly-rational opponent.