Superhuman AI for Stratego Using Self-Play Reinforcement Learning and Test-Time Search
Samuel Sokota, Eugene Vinitsky, Hengyuan Hu, J. Zico Kolter, Gabriele Farina
cs.LG, cs.AI
2025-11-11
CMU、NYU、斯坦福、MIT 团队用自博弈 RL 加测试时搜索训出 Ataraxos,20 局 15 胜 1 负击败史上最伟大的 Stratego 棋手，训练成本只要几千美元。
Stratego 是 10×10 棋盘上的军棋类游戏：双方各把 40 个棋子秘密布置在自己一侧，子力身份互不可见，之后像 chess 一样轮流行棋，捕获对方军旗获胜。在被视为 AI 主要 benchmark 的经典游戏里，它的隐藏信息量最突出：德州扑克只有 1326 种起手牌，少到可以显式枚举；Stratego 的布阵超过 10^33 种。Libratus、DeepStack 这类基于公共信息的问题变换是不完美信息博弈的最成功打法，但成本随隐藏信息量增长，到这个量级直接用不了。2022 年登上 Science 的那轮研究(Perolat 等)烧掉商业成本以百万美元计的算力，仍没打到顶尖人类水平，Stratego 因此成了经典游戏里几乎唯一一个重金投入仍未超人类的 benchmark。
Ataraxos 从零自博弈训练，不用人类棋谱，核心是三块。
训练数据直接从策略网络采样，没走 AlphaZero 式的搜索造数据，作者试过，搜索拖慢数据生成的代价超过了收益。走子样本按优势幅度过滤，只训幅度最大的那部分，单次迭代墙钟省 2.5 倍，样本效率和最终棋力反而更高。布阵侧用 Monte Carlo 回报估计优势，这在 RL 里少见，作者指出 LLM 推理训练中也有同样的观察。工程侧自研 CUDA C++ GPU 模拟器，单张 H100 每秒约 1000 万次状态更新，replay buffer 整个住在 GPU 显存里，bfloat16 再提速约 3 倍。
| 设置 | 指标 | 结果 |
| 对 Pim Niemeijer,20 局 | 战绩 | 15 胜 4 和 1 负，有效胜率 85% |
| 2025 世锦赛表演赛，40 局 | 战绩 | 38 胜 2 负 0 和，有效胜率 95% |
| 纯策略网络 | Elo | 2095 |
| 40 层深、1000 rollout 搜索 | Elo | 2218,每步约 1.26 秒 |
Pim Niemeijer 拿过 4 次世界冠军、15 次荷兰全国冠军，世界第一累计 600 多周，被同行称为「史上最佳 Stratego 棋手」。有效胜率把和棋记半胜，85% 这个差距在人类最高水平的对抗里前所未有；而且赛制不对等，只有 Pim 能跨局适应，Ataraxos 不适应，三届世界冠军 Vincent de Boer 认为这本身就是很大的让子。按独立同分布算 p < 0.00026;作者另做了 betting 分析，全程押 Ataraxos 的赌徒最终财富是对手的 2000 多倍。
训练成本：两个策略网络用 16 张 H100 训一周，belief 网络 4 张 H100 训 4 天，论文口径几千美元。总训练量 1.63 亿局完赛对局、2080 亿环境步。搜索消融里，去掉对 move network 的 reverse KL 约束后 Elo 掉到 1733,比不做搜索还低：搜索会过拟合自家策略的怪癖，换个对手就失灵。
直接含义是成本：对任何能造出快速模拟器的策略决策场景(谈判、拍卖、情报不全的对抗)，超人类 AI 的算力门槛从工业级降到了学术实验室级。组件全是通用的，动态阻尼不依赖 Stratego 的任何特殊性，搜索也只是一次带正则的策略更新，不是一套独立的搜索算法。做 RL 的人有两个可直接搬的点：按优势幅度过滤训练样本；把决策时搜索实现成一次阻尼更新。冷水也要泼：这是单游戏验证，「许多策略场景现在都能低成本超人类」目前是作者的推测，实验没有覆盖。
作者自述的：用 Elo 衡量 Stratego 棋力「有用但有缺陷」，随机化会压缩分差；20 局的 p 值依赖独立同分布假设，而人类会跨局适应，假设不成立；搜索造数据为什么失败只有猜测，对局数量可能比质量更重要；优势过滤反而涨点这件事需要进一步研究；消融全是单种子。
读下来的补充疑点：顶级人类样本只有一人，20 局加 40 局都算不上大样本；表演赛输掉的 2 局说明系统并非不可击败；belief 网络面对偏离自博弈分布的人类下法，泛化全靠 dropout 硬扛；「几千美元」是作者口径，给了算力配置但没有账单明细。