Adapting Beyond the Depth Limit: Counter Strategies in Large Imperfect Information Games
This addresses a key limitation in robust adaptation for large imperfect-information games like poker, enabling better performance against non-rational opponents, though it is incremental as it builds on depth-limited search methods.
The paper tackles the problem of adapting to sub-rational opponents in large imperfect-information games, where existing methods fail due to assumptions of rational play beyond depth limits, and proposes the ABD algorithm, which yields more than a twofold increase in utility against such opponents in poker and battleship.
We study the problem of adapting to a known sub-rational opponent during online play while remaining robust to rational opponents. We focus on large imperfect-information (zero-sum) games, which makes it impossible to inspect the whole game tree at once and necessitates the use of depth-limited search. However, all existing methods assume rational play beyond the depth-limit, which only allows them to adapt a very limited portion of the opponent's behaviour. We propose an algorithm Adapting Beyond Depth-limit (ABD) that uses a strategy-portfolio approach - which we refer to as matrix-valued states - for depth-limited search. This allows the algorithm to fully utilise all information about the opponent model, making it the first robust-adaptation method to be able to do so in large imperfect-information games. As an additional benefit, the use of matrix-valued states makes the algorithm simpler than traditional methods based on optimal value functions. Our experimental results in poker and battleship show that ABD yields more than a twofold increase in utility when facing opponents who make mistakes beyond the depth limit and also delivers significant improvements in utility and safety against randomly generated opponents.