绝艺学会打麻将, 腾讯 AI Lab 提出全新策略优化算法 ACH

2022 年 4 月 26 日
本文字数：1714 字
阅读完需：约 6 分钟

“绝艺”是腾讯 AI Lab 研发的围棋 AI。自 2016 年面世后,已四次夺得世界顶级赛事冠军,包括 UEC 杯、AI 龙星战、腾讯世界人工智能围棋大赛、世界智能围棋公开赛等,并自 2018 年起无偿担任中国国家围棋队训练专用 AI。

在围棋以外,腾讯 AI Lab 绝艺团队持续深入研究大规模二人零和博弈问题,从完美信息游戏(围棋)逐步拓展至非完美信息游戏(例如麻将)。

4 月 25 日,腾讯 AI Lab 宣布棋牌类 AI“绝艺”取得新突破,在 1v1 麻将(二人雀神)测试中战胜职业冠军选手。团队在大规模强化学习算法框架下提出了一个新的策略优化算法 Actor-Critic Hedge (ACH),部分解决了大规模深度强化学习自博弈收敛不到纳什均衡最优解的问题。该算法及对应二人麻将 benchmark 已通过论文开源,并被机器学习顶会 ICLR 2022 收录。

论文链接:https://openreview.net/pdf?id=DTXZqTNV5nW

非完美信息博弈广泛存在于日常生活的方方面面,如智慧交通、网络安全、金融分析等。腾讯 AI Lab 以麻将 AI 为切入点研究非完美信息博弈,其目标不仅限于打造世界级的国粹麻将 AI,更多的在于探索非完美信息博弈在游戏领域,以及其他广阔的社会生活领域的实际应用价值。

研究背景

棋牌游戏一直以来都是 AI 技术的优质试验场,例如,在围棋上就诞生了 AlphaGo、绝艺等标杆性的 AI。相比于围棋这类“完美信息”游戏,德州扑克,桥牌,麻将这类“非完美信息”游戏存在着大量的隐藏信息,例如,玩家无法直接知道对手的手牌,这给游戏带来了更高的不确定性,对 AI 的博弈能力提出更高要求。

具体而言,在完美信息游戏中,始终存在确定性的最优解,即任何状态下都存在一个固定的最优动作。然而在非完美信息游戏中,最优策略往往是随机化的。例如,在二人石头-剪刀-布游戏中,最优策略(纳什均衡策略)不在是某一个固定的动作,而是关于每个动作的一个概率分布:等概率出石头,剪刀,和布。

二人石头-剪刀-布

近年来,反事实遗憾值最小化算法(CFR)在德州扑克游戏 AI 上取得了一些列突破性进展,例如 DeepStack(2017 Science 杂志),Libratus(冷扑大师,2017 Science 杂志),和 Pluribus(2019 Science 杂志)。CFR 具有收敛到纳什均衡解的理论保证。然而,由于 CFR 是一种基于表格的算法,并且需要对游戏树做全遍历,CFR 在德州扑克游戏上的应用需要大量的领域知识来对游戏树做剪枝。虽然后续有一些工作尝试将深度学习和 CFR 做结合,但目前还没有看到 CFR 在其他大规模非完美信息游戏上的成功应用。

另一方面,由于深度强化学习高效的可扩展性,深度强化学习结合自博弈广泛用于大规模非完美信息游戏中求解高强度 AI,例如星际 2,Dota2,和王者荣耀。

然而,基于深度强化学习的大部分 AI 的鲁棒性有待提高,集中表现为 AI 容易被针对,最坏情况下的性能没有保证。这些问题的根本原因在于深度强化学习结合自博弈缺乏收敛到纳什均衡解的理论保证。例如下图所示,在一个简单的二人石头-剪刀-布游戏中,自博弈 Proximal Policy Optimization 无法收敛到(红线为收敛过程)纳什均衡解(蓝点)。