提出新算法让AI在复杂博弈中更聪明地应对对手失误
Adapting Beyond the Depth Limit: Counter Strategies in Large Imperfect Information Games
- 用矩阵状态代替传统值函数，实现深度限制下的完整对手建模
- 对犯错对手的收益提升超2倍，对随机对手也更安全
- 适用于扑克、战舰等大型不完美信息博弈，适合实战对抗场景
我们研究在在线博弈中适应已知非理性对手的同时，仍能抵御理性对手的策略。聚焦于大型不完美信息（零和）博弈，由于无法一次性遍历整个博弈树，必须采用深度受限搜索。然而，现有方法均假设深度限制之外为理性博弈，仅能适应对手极小部分行为。我们提出自适应超越深度限制（ABD）算法，采用策略组合方法——即矩阵值状态——进行深度受限搜索。这使算法能充分利用所有对手模型信息，成为首个在大型不完美信息博弈中实现完全鲁棒性适应的方法。此外，矩阵值状态使算法比基于最优值函数的传统方法更简洁。实验结果表明，在扑克和战舰游戏中，面对深度限制外犯错的对手，ABD收益提升超过两倍；对随机生成对手也显著提升收益与安全性。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。