自己制作网页的网站,WordPress网页加载时间,网络营销的理论基础,商城网站 价格蒙特卡洛树搜索又称随机抽样或统计试验方法#xff0c;属于计算数学的一个分支#xff0c;它是在上世纪四十年代中期为了适应当时原子能事业的发展而发展起来的。传统的经验方法由于不能逼近真实的物理过程#xff0c;很难得到满意的结果#xff0c;而蒙特卡洛树搜索方法由…蒙特卡洛树搜索又称随机抽样或统计试验方法属于计算数学的一个分支它是在上世纪四十年代中期为了适应当时原子能事业的发展而发展起来的。传统的经验方法由于不能逼近真实的物理过程很难得到满意的结果而蒙特卡洛树搜索方法由于能够真实地模拟实际物理过程故解决问题与实际非常符合可以得到很圆满的结果。这也是以概率和统计理论方法为基础的一种计算方法是使用随机数或更常见的伪随机数来解决很多计算问题的方法。将所求解的问题同一定的概率模型相联系用电子计算机实现统计模拟或抽样以获得问题的近似解。
在搜索空间巨大的情况下会比较有效
从全局来看其主要目标为给定一个游戏状态来选择最佳的下一步
经典应用alpha go
算法过程
选择:选择能够最大化UCB值的结点即UCB越大越有可能选择这条路径 该节点下的平均value大小
C:常数通常可以取2 N:总探索次数 ni:当前阶段的探索次数
扩展:创建一个或多个子节点 仿真在某一点用随机策略进行决策又称palyout或rollout 反向传播使用随机搜索的结果来更新整个搜索树
算法过程 流程图
算法的终结机制
1限定运行时间 2给固定的迭代次数
迭代完成后选择value更大的节点即可完成决策
示例: 左边搜索 在前面的基础上进行右边搜索 计算 左边再深一层搜索
计算
右边深一层搜索
蒙特卡洛树搜索与深度神经网络的结合
这是alpha go的计算原理
最初的解决方案是使用小型网络 即rollout policy 原理对棋盘的特征做新性组合再做softmax借此得到行动的概率 当时使用了8百万人类棋手的数据进行训练
这样做对局时每一步的准确率为24.2%
考虑到围棋变化的复杂度他们上了神经网络 效果3毫秒内完成计算落子准确率为57% 原理: 以输入棋盘状态S为输入数据 以选择不同行动的概率为输出 训练方法梯度下降
网络总体架构 分成两个网络策略网络给出决策与价值网络(评估胜率)
公式
现在将神经网络用到搜索树中
下面针对上面的UCT公式进行说明: 策略树 即UCT算法(Upper Confidence Bound Apply to Tree) 公式: 行动价值选择函数
c为常数c所乘公式用于表示不确定的项
s表示状态 a表示行动 Q(s,a):该函数表示状态行动对的价值。 N(s,a):状态行动对的访问次数没有采取过的行动的不确定性比较大潜力亦比较大。
最初的价值和访问次数都是0那么我们最初就要随机选择 即rollout policy(随机policy)方法(一般利用MC估计值函数的策略叫做rollout policy因为这个策略就是用来roll out出一个轨迹的而不是找到一个最优策略。经验表明rollout算法虽然简单但是在实际中十分有效。)
在反向传播的过程中如果这个决断使得棋局走向了胜利那么就标记为1反之标记为-1 故W表示的就是节点的总价值 这是基本结构 为了定制阈值的生长速度这里加以改进 有了这种网络我们一开始就能考虑那些高概率的行为而不必像UCT那样从0开始学习大大减少了计算负担。
总体来说alpha go具有以下优点: 神经网络rollout 构成快速决策系统 价值网络估计叶节点的价值→与rollout的价值做加权平均 反向传播
