虚拟网站,织梦网站做自适应,北京鲜花的网站建设,创建企业网站本文主要是将有关蒙特卡洛树搜索的文献#xff08;2011年之前#xff09;进行归纳#xff0c;概述了核心算法的推导#xff0c;给出了已经提出的许多变化和改进的一些结构#xff0c;并总结了MCTS方法已经应用于的博弈和其他领域的结果。
蒙特卡洛树搜索是一种通过在决策…本文主要是将有关蒙特卡洛树搜索的文献2011年之前进行归纳概述了核心算法的推导给出了已经提出的许多变化和改进的一些结构并总结了MCTS方法已经应用于的博弈和其他领域的结果。
蒙特卡洛树搜索是一种通过在决策空间中随机抽样并根据结果建立搜索树在给定域内寻找最优决策的方法它平衡了探索exploration和利用exploitation。
一、背景 二、蒙特卡洛树搜索
蒙特卡洛树搜索基于两个基本概念一个动作的真实值可以使用随机模拟来近似这些值可以有效地调整策略为最佳优先策略。
基本算法包括迭代地构建一个搜索树直到达到一些预定义的计算预算——通常是时间、内存或迭代约束——此时搜索停止并返回性能最好的根操作。搜索树中的每个节点表示域的一个状态指向子节点的定向链接表示导致后续状态的操作。
每次搜索迭代都将应用四个步骤
选择selection从根节点开始递归地应用子选择策略通过树向下移动直到到达最紧急的可扩展节点。如果节点表示非终端状态并且有未访问即未扩展子节点则节点是可扩展的。扩展expansion根据可用的操作添加一个或多个子节点以展开树。模拟simulation根据默认策略从新节点开始运行模拟以产生结果。反向传播backpropagated模拟结果通过选定的节点进行“备份”即反向传播以更新其统计信息。
这些步骤可以分为两种不同的策略
树策略tree policy从已包含在搜索树中的节点中选择或创建一个叶节点选择和扩展默认策略default policy从给定的非终端状态发挥域已产生值估计模拟 Upper Confidence Bounds for Trees (UCT
UCB1是解决MCTS中的探索-利用困境的一个很有前途的候选对象每当在现有的树中选择一个节点动作时该选择都可以被建模为一个独立的多武装强盗问题multiarmed bandit problem一个子节点 j 被选择去最大化 方程第一项是利用项第二项是探索项两项间有一个基本的平衡。当每个节点被访问时探索项的分母增加从而减少其贡献。另一方面如果访问了父节点的另一个子节点那么分子就会增加因此未访问的兄弟节点的探索值也会增加。探索项确保每个子节点都有一个非零的选择概率这是必要的随机性质。这也赋予了算法一个固有的重启属性因为即使是低奖励的子节点最终也能保证被选择如果给定足够的时间从而探索了不同的游戏路线。
参数可以进行调整以降低或增加探索的概率。一般取因为这个值能以范围为[0,1]的奖励满足Hoeffding ineqality。其他范围的奖励则需要不同的。 算法3展示了一种更有效的双人零和博弈交替移动的备份方法。 三、特点
1启发式MCTS最重要的好处之一就是缺乏对特定领域的知识的需求这使得它很容易适用于任何可以使用树建模的领域 。
2任何时间MCTS立即反向传播每个游戏的结果确保在算法的每次迭代后所有值都是最新的这允许算法在任何时候从根目录返回一个操作。
3不对称树的选择允许算法偏爱更有前途的节点但不允许其他节点的选择概率收敛到零导致随着时间的推移出现不对称的树也就是说部分树的构建倾向于更有前途即更重要的区域。
四、变化
传统的游戏AI研究集中于有两个玩家的零和游戏、交替回合、离散动作空间、确定性状态转换和完美信息。虽然MCTS已经广泛应用于此类游戏但它也被应用于其他领域类型如单人游戏和规划问题、多人游戏、实时游戏以及具有不确定性或同时移动的游戏。本节描述了MCTS适应这些领域的方法以及那些采用来自MCTS的想法而不严格遵守其大纲的算法。
我只选择部分可能与课题相关的算法进行学习
1.Learning in MCTS
MCTS可以被看作是一种强化学习算法因此考虑它与时间差异学习典型的RL算法之间的关系。
时间差异学习TDL时间差异学习TDL和MCTS都是学习基于状态或状态 - 行动对的值来采取行动的。在某些情况下算法甚至可能是等价的但TDL算法通常不构建树只有当所有状态值都可以直接存储在表中时这种等价才成立。MCTS估计临时状态值以决定下一步行动而TDL学习每个状态的长期值然后指导未来的行为。
时间差异与蒙特卡洛TDMC“一种新的方法使用获胜概率代替非终端位置的奖励” Bandit-Based Active Learner (BAAL)用来解决在数据稀疏的应用程序中的小训练集的问题。 2.多人 MCTS
极大极小搜索的中心假设是搜索玩家寻求最大化他们的奖励而对手则寻求最小化奖励。在双人零和游戏中这相当于说每个玩家都寻求最大化自己的奖励然而在两个以上玩家的游戏中这种等价性并不一定成立。
将MCTS应用于多人游戏的最简单的方法是采用这样的想法每个节点存储一个奖励向量并且选择过程寻求最大化使用奖励向量的适当成分计算出的UCB值。 3.多代理MCTS
考虑拥有多个代理即多个模拟策略的影响在这种情况下不同的代理是通过给程序中使用的启发式分配不同的优先级来获得的。然而寻找具有正确属性的代理集即那些增加游戏强度的代理是需要计算的。 集成UCT在该方法中多个UCT实例独立运行并将他们的根统计量组合起来得到最终结果。
