浙大提出会打德扑的「自我博弈」AI,还会玩射击游戏

人工智能已在围棋这样的完美信息游戏上实现了远超人类的水平,但在信息未完全披露的多人对战游戏上还无法战胜人类。近年来,OpenAI 和 DeepMind 在 DOTA2 和星际争霸 2 上的尝试都难言成功。近日,来自浙江大学的研究人员提出了一种新方法,结合蒙特卡洛树搜索和 NFSP,大大提高了在信息不完整的大规模零和游戏上的表现。面对信息不完整的环境,浙大的研究人员提出了异步神经虚拟自我对弈(ANFSP)方法,让 AI 学会在多个虚拟环境中进行「自我博弈」,从而生成最优决策。他们的方法在德州扑克和多人 FPS 射击游戏中均取得了不错表现。

随着深度强化学习的快速发展,AI 已经在围棋等信息完整的游戏中战胜了人类专业玩家。然而,「星际争霸」等信息不完整游戏的研究还没有取得同样的进展。这类研究的一大问题是,它们很少从理论和量化的角度考虑对其训练和结果进行评估,因此效果难以保证。

博弈论是研究现实世界竞赛中人类行为模式的基石。该理论主要研究智能体如何通过竞争与合作实现其利益最大化并度量决策的质量。它已经成为计算机科学中一个颇具吸引力的研究任务。名为「算法博弈论」的交互研究课题已经确立,并随着人工智能的发展受到越来越多的关注。对于交易、交通管理等现实世界中的复杂问题,计算维度会急剧增加,因此有必要利用算法和人工智能的思想使其在实践中发挥作用,这也是该研究的主要动机之一。

博弈论中,纳什均衡是博弈的一个最优解决方案,即没有人可以通过缓和自己的策略获得额外收益。虚拟对弈(Fictitious Play)是求解正规博弈中纳什均衡的一种传统算法。虚拟对弈玩家反复根据对手的平均策略做出最佳反应。玩家的平均策略将收敛纳什均衡。Heinrich 等人提出了广泛的虚拟对弈(Extensive Fictitious Play),将虚拟对弈的概念扩展到了扩展式博弈。然而,状态在每个树节点中都以查找表的形式表示,因此(类似状态的)泛化训练是不切实际的,而且平均策略的更新需要遍历整个游戏树,这就给大型游戏带来了维数灾难

虚拟自我对弈(Fictitious Self-Play,FSP)通过引入基于样本的机器学习方法解决这些问题。对最佳反应的逼近是通过强化学习学到的,平均策略的更新是通过基于样本的监督学习进行的。但为了提高采样效率,智能体之间的交互由元控制器协调,并且与学习是异步的。

Heinrich 和 Silver 介绍了神经虚拟自我对弈(NFSP),将 FSP 与神经网络函数近似结合起来。一个玩家由 Q-学习网络和监督式学习网络组成。该算法通过贪婪深度Q学习(greedy deep Q-learning)计算一个「最佳反应」,通过对智能体历史行为的监督学习计算平均策略。它通过引入预期动态来解决协调问题——玩家根据它们的平均策略和最佳反应展开行动。这是第一个在不完全博弈中不需要任何先验知识就能学习近似纳什均衡的端到端强化学习方法。

然而,由于对手策略的复杂性和深度 Q 网络在离线模式下学习的特点,NFSP 在搜索空间和搜索深度规模较大的游戏中表现较差。本文提出了蒙特卡洛神经虚拟自我对弈(Monte Carlo Neural Fictitious Self Play,MC-NFSP),该算法结合了 NFSP 与蒙特卡洛树搜索(Monte Carlo Tree Search)。研究人员在双方零和的棋牌游戏中评估了该方法。实验表明,在奥赛罗棋中,MC-NFSP 将收敛到近似纳什均衡,但 NFSP 无法做到。

另一个缺点是在 NFSP 中,最佳反应依赖于深度 Q-学习的计算,这需要很长时间的计算直到收敛。在本文中,研究人员提出了异步神经虚拟自我对弈(ANFSP)方法,使用并行的 actor learner 来稳定和加速训练。多个玩家并行进行决策。玩家分享 Q 学习网络和监督学习网络,在 Q 学习中累积多个步骤的梯度,并在监督学习中计算小批量的梯度。与 NFSP 相比,这减少了数据存储所需的内存。研究人员在双人零和扑克游戏中评估了其方法。实验表明,与 NFSP 相比,ANFSP 可以更加稳定和快速地接近近似纳什均衡

为了展示 MC-NFSP 和 ANFSP 技术在复杂游戏中的优势,浙大研究人员还评估了算法在多人 FPS 对战游戏的有效性,其中 AI 智能体队伍和人类组成的队伍进行了比赛,新提出的系统提供了良好的策略和控制,帮助 AI 战胜了人类。

神经虚拟自我对弈

虚拟对弈(FP)是根据自我对弈学习纳什均衡的经典博弈论模型。在每次迭代的时候,玩家队伍根据对方的平均策略做出最佳回应,并更新其平均策略。在特定的游戏场景(如零和游戏)中,玩家在虚拟对弈中的平均策略可以达到纳什均衡。因为 FP 主要是针对正规博弈,Heinrish 等人将 FP 扩展为虚拟自我对弈,FSP 致力于遍历游戏扩展形式的游戏树,有可能在更大规模的游戏中找到纳什均衡。但是 FSP 方法需要玩家和对手遵循动作顺序,因此它不适合信息不完整的游戏。

玩家和对手需要遵循动作顺序的要求使得 FSP 不适用于信息不完整的游戏。神经虚拟自我对弈(NFSP)是一个在信息不完整的游戏上学习近似纳什均衡的模型。该模型结合了虚拟博弈和深度学习。在每一步,玩家会选择混合使用最佳反应和平均策略。玩家通过深度 Q 学习接近最佳反应,并通过监督学习更新平均策略。只有当玩家根据最佳反应决定动作时,状态-动作对(St, at)会被存储在监督学习记忆中。

图 1:FSP 和 NFSP 的训练效率

蒙特卡洛神经虚拟自我对弈(MC-NFSP)

该算法利用两种神经网络:蒙特卡洛树搜索的策略-估值网络(policy-value network)(如最佳反应网络,bestresponse network)和监督学习策略网络(如平均策略网络)。最佳反应网络如图 2 所示。神经网络的输入是边界状态。策略-估值网络有两种输出:策略 p(当前状态到动作概率的映射)和估值 v(指定状态的预测值)。估值范围为「0,1」,其中输掉比赛的对应估值 0,赢得比赛的对应估值 1。在浙大研究人员提出的网络中,relu 激活函数用于卷积层;dropout 用于全连接层以减少过拟合;softmax 用于策略概率。策略网络几乎与最佳反应网络相同,但前者仅输出策略 p 0(不会输出估值),而这也是玩家的平均策略。

图 2:MCTS 的最佳反应网络

实验

浙大研究人员在改进版无限制州扑克(Leduc Hold』em)中对 ANFSP 和 NFSP 进行比较。为了简化计算,浙大研究人员在无限制德州扑克中将每轮的最大赌注大小限制为 2。实验研究了改进版无限制德州扑克中 ANFSP 对纳什均衡收敛性,并以学得策略的可利用性作为比较标准。

图 5 显示在改进版无限制德州扑克中 ANFSP 接近纳什均衡。可利用性持续降低,并在 140w 个游戏片段后稳定在 0.64 左右。训练时间约 2 小时。

图 5:ANFSP 在改进版无限制德扑中的可利用性

在第一人称射击游戏(FPS)中的评估

为了在信息不完整的复杂游戏中评估本文算法的有效性,研究人员在一个 FPS 游戏上训练了该算法,并且让它与人类对战。本次实验中使用的 FPS 平台是由浙大研究人员设计的。游戏场景是两个队伍(10 VS 10)的攻防对抗。在训练过程中,一方是 MC-NFSP,另一方是由上千场人类游戏(SL-Human)训练的记忆。该实验在固定的封闭式 255 x 255 正方形地图上进行。整个地图被分为 12 x 12 个区域,每个区域有一个 20 x 20 的正方形。

图 7:FPS 游戏环境

与本文之前的研究不同,这两个网络是同时为外部队伍和内部队伍构建和训练的。图 8 显示了外部队伍的训练结果(内部队伍的训练结果与此类似)。从图中不难看出,训练收敛得非常快(少于 150 个片段,每个片段有 5 场游戏)。外部队伍对战 SL-Human 的胜率提高了 80%,而训练损失接近 0。

图 8:在 FPS 游戏上的评估结果

论文:Monte Carlo Neural Fictitious Self-Play: Achieve Approximate Nash equilibrium of Imperfect-Information Games

论文地址:https://arxiv.org/abs/1903.09569

摘要:人工智能领域的研究人员已经用 AI 在信息完整的大规模游戏上达到了人类水准,但要在信息不完整的大规模游戏(即战争游戏、足球教练或商业策略游戏)上实现最优结果(即近似纳什均衡)仍是一大挑战。神经虚拟自我对弈(NFSP)算法可以通过自我对弈,在没有先验领域知识的情况下有效学习信息不完整游戏的近似纳什均衡。但是,它依赖于深度 Q 网络,但这种网络是离线的而且很难融入对手策略不断变化的在线游戏,因此深度 Q 网络无法在游戏中用大规模搜索和深度搜索来达到近似纳什均衡。本文中,我们提出了蒙特卡洛神经虚拟自我对弈(MC-NFSP)算法,该方法结合了蒙特卡洛树搜索和 NFSP,大大提高了模型在信息不完整的大规模零和游戏中的表现。实验证明,该算法可以利用大规模深度搜索达到 NFSP 无法实现的近似纳什均衡。此外,我们开发了异步神经虚拟自我对弈(ANFSP)算法,该算法使用异步架构和并行架构来收集游戏经验。在实验中,我们发现并行 actor-learner 能够进一步加速和稳定训练。

理论蒙特卡洛树搜索完美信息博弈博弈机器学习游戏德州扑克浙江大学
4
相关数据
纳什均衡技术

纳什平衡,又称为非合作赛局博弈,是在非合作博弈状况下的一个概念解,在博弈论中有重要地位,以约翰·纳什命名。 如果某情况下无一参与者可以通过独自行动而增加收益,则此策略组合被称为纳什均衡点。

深度学习技术

深度学习(deep learning)是机器学习的分支,是一种试图使用包含复杂结构或由多重非线性变换构成的多个处理层对数据进行高层抽象的算法。 深度学习是机器学习中一种基于对数据进行表征学习的算法,至今已有数种深度学习框架,如卷积神经网络和深度置信网络和递归神经网络等已被应用在计算机视觉、语音识别、自然语言处理、音频识别与生物信息学等领域并获取了极好的效果。

深度强化学习技术

强化学习(Reinforcement Learning)是主体(agent)通过与周围环境的交互来进行学习。强化学习主体(RL agent)每采取一次动作(action)就会得到一个相应的数值奖励(numerical reward),这个奖励表示此次动作的好坏。通过与环境的交互,综合考虑过去的经验(exploitation)和未知的探索(exploration),强化学习主体通过试错的方式(trial and error)学会如何采取下一步的动作,而无需人类显性地告诉它该采取哪个动作。强化学习主体的目标是学习通过执行一系列的动作来最大化累积的奖励(accumulated reward)。 一般来说,真实世界中的强化学习问题包括巨大的状态空间(state spaces)和动作空间(action spaces),传统的强化学习方法会受限于维数灾难(curse of dimensionality)。借助于深度学习中的神经网络,强化学习主体可以直接从原始输入数据(如游戏图像)中提取和学习特征知识,然后根据提取出的特征信息再利用传统的强化学习算法(如TD Learning,SARSA,Q-Learnin)学习控制策略(如游戏策略),而无需人工提取或启发式学习特征。这种结合了深度学习的强化学习方法称为深度强化学习。

激活函数技术

在 计算网络中, 一个节点的激活函数定义了该节点在给定的输入或输入的集合下的输出。标准的计算机芯片电路可以看作是根据输入得到"开"(1)或"关"(0)输出的数字网络激活函数。这与神经网络中的线性感知机的行为类似。 一种函数(例如 ReLU 或 S 型函数),用于对上一层的所有输入求加权和,然后生成一个输出值(通常为非线性值),并将其传递给下一层。

机器学习技术

机器学习是人工智能的一个分支,是一门多领域交叉学科,涉及概率论、统计学、逼近论、凸分析、计算复杂性理论等多门学科。机器学习理论主要是设计和分析一些让计算机可以自动“学习”的算法。因为学习算法中涉及了大量的统计学理论,机器学习与推断统计学联系尤为密切,也被称为统计学习理论。算法设计方面,机器学习理论关注可以实现的,行之有效的学习算法。

维数灾难技术

维数灾难(英语:curse of dimensionality,又名维度的诅咒)是一个最早由理查德·贝尔曼(Richard E. Bellman)在考虑优化问题时首次提出来的术语,用来描述当(数学)空间维度增加时,分析和组织高维空间(通常有成百上千维),因体积指数增加而遇到各种问题场景。这样的难题在低维空间中不会遇到,如物理空间通常只用三维来建模。

人工智能技术

在学术研究领域,人工智能通常指能够感知周围环境并采取行动以实现最优的可能结果的智能体(intelligent agent)

收敛技术

在数学,计算机科学和逻辑学中,收敛指的是不同的变换序列在有限的时间内达到一个结论(变换终止),并且得出的结论是独立于达到它的路径(他们是融合的)。 通俗来说,收敛通常是指在训练期间达到的一种状态,即经过一定次数的迭代之后,训练损失和验证损失在每次迭代中的变化都非常小或根本没有变化。也就是说,如果采用当前数据进行额外的训练将无法改进模型,模型即达到收敛状态。在深度学习中,损失值有时会在最终下降之前的多次迭代中保持不变或几乎保持不变,暂时形成收敛的假象。

深度Q学习技术

Q学习是一种无模型(model-free)的强化学习方法,学习如何在给定(有限)马尔可夫决策过程(MDP)找到最优的动作选择策略。Q学习算法的核心是根据旧的Q值和新的Q值估计进行权重平均的一个值迭代更新(value iteration update)迭代更新的Q函数最终给出了主体在给定状态下采取给定行动的预期效用,当这种行动价值函数被学习时,主体可通过简单地选择在每个状态中具有最高价值的行为来构建最优策略(optimal policy)。

神经网络技术

(人工)神经网络是一种起源于 20 世纪 50 年代的监督式机器学习模型,那时候研究者构想了「感知器(perceptron)」的想法。这一领域的研究者通常被称为「联结主义者(Connectionist)」,因为这种模型模拟了人脑的功能。神经网络模型通常是通过反向传播算法应用梯度下降训练的。目前神经网络有两大主要类型,它们都是前馈神经网络:卷积神经网络(CNN)和循环神经网络(RNN),其中 RNN 又包含长短期记忆(LSTM)、门控循环单元(GRU)等等。深度学习是一种主要应用于神经网络帮助其取得更好结果的技术。尽管神经网络主要用于监督学习,但也有一些为无监督学习设计的变体,比如自动编码器和生成对抗网络(GAN)。

映射技术

映射指的是具有某种特殊结构的函数,或泛指类函数思想的范畴论中的态射。 逻辑和图论中也有一些不太常规的用法。其数学定义为:两个非空集合A与B间存在着对应关系f,而且对于A中的每一个元素x,B中总有有唯一的一个元素y与它对应,就这种对应为从A到B的映射,记作f:A→B。其中,y称为元素x在映射f下的象,记作:y=f(x)。x称为y关于映射f的原象*。*集合A中所有元素的象的集合称为映射f的值域,记作f(A)。同样的,在机器学习中,映射就是输入与输出之间的对应关系。

Q-learning技术

Q学习是一种用于机器学习的强化学习技术。 Q-Learning的目标是学习一种策略,告诉智能体在什么情况下要采取什么行动。 它不需要对环境建模,可以处理随机转换和奖励的问题,而无需进行调整。

监督学习技术

监督式学习(Supervised learning),是机器学习中的一个方法,可以由标记好的训练集中学到或建立一个模式(函数 / learning model),并依此模式推测新的实例。训练集是由一系列的训练范例组成,每个训练范例则由输入对象(通常是向量)和预期输出所组成。函数的输出可以是一个连续的值(称为回归分析),或是预测一个分类标签(称作分类)。

策略网络技术

在强化学习中,策略网络指一组相对稳定的关系,这些关系具有非等级和相互依赖的性质,将各个行为者(actor)联系起来。

先验知识技术

先验(apriori ;也译作 先天)在拉丁文中指“来自先前的东西”,或稍稍引申指“在经验之前”。近代西方传统中,认为先验指无需经验或先于经验获得的知识。先验知识不依赖于经验,比如,数学式子2+2=4;恒真命题“所有的单身汉一定没有结婚”;以及来自纯粹理性的推断“本体论证明”

过拟合技术

过拟合是指为了得到一致假设而使假设变得过度严格。避免过拟合是分类器设计中的一个核心任务。通常采用增大数据量和测试样本集的方法对分类器性能进行评价。

博弈论技术

博弈论,又译为对策论,或者赛局理论,应用数学的一个分支,1944年冯·诺伊曼与奥斯卡·摩根斯特恩合著《博弈论与经济行为》,标志着现代系统博弈理论的的初步形成,因此他被称为“博弈论之父”。博弈论被认为是20世纪经济学最伟大的成果之一

强化学习技术

强化学习是一种试错方法,其目标是让软件智能体在特定环境中能够采取回报最大化的行为。强化学习在马尔可夫决策过程环境中主要使用的技术是动态规划(Dynamic Programming)。流行的强化学习方法包括自适应动态规划(ADP)、时间差分(TD)学习、状态-动作-回报-状态-动作(SARSA)算法、Q 学习、深度强化学习(DQN);其应用包括下棋类游戏、机器人控制和工作调度等。

推荐文章
暂无评论
暂无评论~