基于虚拟自我对局的非完备信息博弈策略研究
发布时间：2021-10-15 09:16
近年来机器博弈受到学术界和工业界的广泛关注,机器博弈领域的研究也取得了令人瞩目的成绩,例如Deep Mind的Alphago击败顶尖围棋选手、CMU的多人德扑智能体Pluribus击败顶级牌手以及Open AI的Open AI Five击败Dota职业队伍。机器博弈相关技术也正被应用于很多实际场景中,例如智能交通、智能推荐、多轮对话、量化交易等。根据参与者是否完全掌握博弈局面的所有信息可以把机器博弈分为完备信息博弈和非完备信息博弈。现实场景中的诸多决策问题都可以建模成非完备信息博弈中的策略求解问题,但目前的机器博弈算法需要对问题的状态空间进行抽象,在高维动作空间中表现不佳,且通常仅适用于二人博弈。因此研究能够应用于复杂状态空间、支持连续动作、适用于多人博弈的非完备信息博弈策略求解算法具有重大意义。本文在虚拟自我对局的算法框架下,结合深度强化学习、多智能体强化学习、蒙特卡洛树搜索等技术来解决策略优化问题,以德州扑克和炸弹人为实验平台,研究二人和多人博弈问题中的策略求解。针对复杂博弈问题通常需要利用先验知识进行状态空间抽象的问题,本文提出了利用深度强化学习和自适应的蒙特卡洛搜索树算法来求解...
【文章来源】：哈尔滨工业大学黑龙江省 211工程院校 985工程院校
【文章页数】：61 页
【学位级别】：硕士
【部分图文】：
扩展形式的博弈树
哈尔滨工业大学工程硕士学位论文弈游戏结束。（4）回溯（Backpropagation）：递归地向上访问父节点，并更新当前节点的统计信息。MCTS的搜索过程可以归纳为两种不同的策略，如图2-2所示，一种是树策略(TreePolicy),即是从搜索树中已经包含的节点中选择或创建叶节点(选择和扩展)。第二种是默认策略（DefaultPolicy），根据默认策略进行博弈直至博弈终端节点返回模拟结果。Alphogo中的快速走子策略就是第二种的默认策略。一旦树搜索中断或达到预设的计算时间，搜索就会终止，并且通过某种机制在根节点t0处选择动作a。Schadd[48]根据Chaslot等人[49]的工作，描述了选择最优子节点的四种方法：（1）Maxchild：选择收益最多的子节点。（2）Robustchild：选择访问次数最多的子节点。（3）Max-Robustchild:选择访问次数和收益均为最多的子节点，如果不存在则继续蒙特卡洛树搜索，直到达到可接受的访问次数为止。（4）Securechild：选择最大化置信区间下界的子节点。图2-2蒙特卡洛树搜索2.3.2置信上界树搜索MCTS的目标是近似当前状态可采取动作的真实博弈收益，这是通过迭代构建部分搜索树来实现的，而如何构建树取决于树策略。置信上界树搜索算法(UpperConfidenceBoundforTrees,UCT)是备受关注的蒙特卡洛树搜索算法，因为UCT算法可用来解决MCTS中的“探索和利用”问题，探索就是指对未访问节点的选择，利用则是指对迭代过程中的已知历史信息的利用，UCT算法就是在蒙特卡洛树搜索的子节点选择阶段采用了UCB算法。Kocsis[50]提出了利用上限置信区间(UpperConfidenceBounds,用UCB)来实现树搜索，通过蒙特卡洛模拟来近似子节点的预期奖励。UCB具有简单高效的优点，且可以保证在遗憾增长的情况下保持最优界限在一个恒定范围内，可以将迭代中选择子节点?
哈尔滨工业大学工程硕士学位论文Rainbow表现优异[57]。图2-3DQN算法框架2.4.3策略梯度策略梯度算法直接优化智能体的行为策略，相较于值迭代方法，通常具有更好的收敛性，在高维或连续动作空间中有效，并且可以学习随机策略。随机策略在博弈中比较重要，因为可以避免被对手过利用。对于可微策略，只要它不为零，就可以解析地计算策略梯度。Sutton[58]指出对于可微策略，其策略梯度可以表示为：Eπθ[θlogπ(a|s;θ)Qπθ(s,a)](2-15)策略梯度的前一项可以理解为一个描述智能体策略的方向向量，描述的是参数的更新方向，第二项则是一个标量，用来估计行动轨迹的预期收益Q值，相当于是对策略的评价项，因此结合前后两项策略梯度可以理解为通过降低低收益轨迹的出现概率，以及增加高收益轨迹的概率来实现策略的参数更新。策略梯度的第二项可以采用六种评价函数。传统的策略梯度算法则是采取轨迹总收益、动作收益以及引入基线的动作收益来作为评估指标，这三种方法因为是直接应用轨迹的真实奖励，类似蒙特卡洛的思想，因此不存在偏差，但是多步轨迹会导致样本数据方差大。而后文讲到的结合值迭代的策略梯度算法则是通过值函数来评估策略，可以直接利用Q函数来评价。或者引入一个状态值函数来作为基线奖励从而引出优势函数来评估智能体策略：A(at,st)=Q(at,st)V(st)(2-16)其中Q(at表示动作值函数，V(st表示状态值函数。此外，还可以利用状态值函数-16-
【参考文献】：
硕士论文
[1]基于状态抽象和残局解算的二人非限制性德州扑克策略的研究[D]. 胡开亮.哈尔滨工业大学 2017
本文编号：3437806
【文章来源】：哈尔滨工业大学黑龙江省 211工程院校 985工程院校
【文章页数】：61 页
【学位级别】：硕士
【部分图文】：
扩展形式的博弈树
哈尔滨工业大学工程硕士学位论文弈游戏结束。（4）回溯（Backpropagation）：递归地向上访问父节点，并更新当前节点的统计信息。MCTS的搜索过程可以归纳为两种不同的策略，如图2-2所示，一种是树策略(TreePolicy),即是从搜索树中已经包含的节点中选择或创建叶节点(选择和扩展)。第二种是默认策略（DefaultPolicy），根据默认策略进行博弈直至博弈终端节点返回模拟结果。Alphogo中的快速走子策略就是第二种的默认策略。一旦树搜索中断或达到预设的计算时间，搜索就会终止，并且通过某种机制在根节点t0处选择动作a。Schadd[48]根据Chaslot等人[49]的工作，描述了选择最优子节点的四种方法：（1）Maxchild：选择收益最多的子节点。（2）Robustchild：选择访问次数最多的子节点。（3）Max-Robustchild:选择访问次数和收益均为最多的子节点，如果不存在则继续蒙特卡洛树搜索，直到达到可接受的访问次数为止。（4）Securechild：选择最大化置信区间下界的子节点。图2-2蒙特卡洛树搜索2.3.2置信上界树搜索MCTS的目标是近似当前状态可采取动作的真实博弈收益，这是通过迭代构建部分搜索树来实现的，而如何构建树取决于树策略。置信上界树搜索算法(UpperConfidenceBoundforTrees,UCT)是备受关注的蒙特卡洛树搜索算法，因为UCT算法可用来解决MCTS中的“探索和利用”问题，探索就是指对未访问节点的选择，利用则是指对迭代过程中的已知历史信息的利用，UCT算法就是在蒙特卡洛树搜索的子节点选择阶段采用了UCB算法。Kocsis[50]提出了利用上限置信区间(UpperConfidenceBounds,用UCB)来实现树搜索，通过蒙特卡洛模拟来近似子节点的预期奖励。UCB具有简单高效的优点，且可以保证在遗憾增长的情况下保持最优界限在一个恒定范围内，可以将迭代中选择子节点?
哈尔滨工业大学工程硕士学位论文Rainbow表现优异[57]。图2-3DQN算法框架2.4.3策略梯度策略梯度算法直接优化智能体的行为策略，相较于值迭代方法，通常具有更好的收敛性，在高维或连续动作空间中有效，并且可以学习随机策略。随机策略在博弈中比较重要，因为可以避免被对手过利用。对于可微策略，只要它不为零，就可以解析地计算策略梯度。Sutton[58]指出对于可微策略，其策略梯度可以表示为：Eπθ[θlogπ(a|s;θ)Qπθ(s,a)](2-15)策略梯度的前一项可以理解为一个描述智能体策略的方向向量，描述的是参数的更新方向，第二项则是一个标量，用来估计行动轨迹的预期收益Q值，相当于是对策略的评价项，因此结合前后两项策略梯度可以理解为通过降低低收益轨迹的出现概率，以及增加高收益轨迹的概率来实现策略的参数更新。策略梯度的第二项可以采用六种评价函数。传统的策略梯度算法则是采取轨迹总收益、动作收益以及引入基线的动作收益来作为评估指标，这三种方法因为是直接应用轨迹的真实奖励，类似蒙特卡洛的思想，因此不存在偏差，但是多步轨迹会导致样本数据方差大。而后文讲到的结合值迭代的策略梯度算法则是通过值函数来评估策略，可以直接利用Q函数来评价。或者引入一个状态值函数来作为基线奖励从而引出优势函数来评估智能体策略：A(at,st)=Q(at,st)V(st)(2-16)其中Q(at表示动作值函数，V(st表示状态值函数。此外，还可以利用状态值函数-16-
【参考文献】：
硕士论文
[1]基于状态抽象和残局解算的二人非限制性德州扑克策略的研究[D]. 胡开亮.哈尔滨工业大学 2017
本文编号：3437806
本文链接：https://www.wllwen.com/kejilunwen/zidonghuakongzhilunwen/3437806.html
