人智导第三章笔记

notes › iAi

第三章:对抗搜索

image-20230615212012526

α-β剪枝

基于max-min

根本思想是如果知道这条路很差,那么不需要知道这条路究竟有多差

所以当一个max结点发现自己找到了一条路,这条路比它祖先的任意一个(已经有值的)min结点的值($\beta$)要好,就直接放弃继续搜索.这叫(因为)$\beta$剪枝

因为作为max结点我肯定会选择这条看上去的比较好的路,可是他的这个min祖先一定不会最终选择这条路.(如果真的选择了,这条路的最终值会一直传上去,直到在和那个坏蛋min结点的另一个孩子竞争时失败)

模拟算法实现时的注意事项

其实α-β剪枝理解起来是很直观的,就和人类对局面的思考差不多.不知道为什么看了ppt什么极大节点的下界为a。极小节点的上界为b。反而变糊涂了

主要是注意一下结点发生剪枝时至少进行了一次搜索,所谓的剪枝实际上是剪掉了剩下的所有儿子,而不是直接剪掉了自己

在祖先没有已经计算过的另一种结点时,不会发生剪枝,所以左起这个2不应该被剪掉,同时父亲也应该更新

image-20230615215559423

但是更新到爷爷时,应该在箭头位置进行$\beta$剪枝

image-20230615215720463

定义

  1. 蒙特卡洛算法: 这是一种统计模拟方法，通过从概率分布中随机抽样或使用随机数来近似复杂过程的结果。蒙特卡洛方法广泛应用于各种领域，从物理学到金融，当然还有游戏。

  2. 蒙特卡洛树搜索 (MCTS): 这是一种在很多游戏和决策过程中使用的搜索算法，它使用蒙特卡洛方法来评估每个动作的潜在价值。它通过重复模拟游戏的玩法来构建一个搜索树，并使用统计数据来选择最有希望的移动。MCTS 主要包括四个步骤：选择(Selection)、扩展(Expansion)、模拟(Simulation)和回传(Backpropagation)。

  3. UCT (Upper Confidence Bounds for Trees) 算法: 这是 MCTS 的一个变种，它在选择步骤中使用 UCB 策略。UCB 考虑了两个因素：一个节点的平均奖励和该节点被访问的次数。通过使用 UCB，UCT 在探索（搜索未知的部分）和利用（聚焦于已知的好动作）之间找到平衡。

简单说来,MCTS就是选择-拓展-模拟-回传,而UCT是MCTS的一个特例

UCT 主要包括以下四个步骤：

  1. 选择(Selection): 从根节点开始，使用 UCB 公式选择子节点，直到找到一个可以扩展的节点（即没有完全展开或游戏结束的节点）。UCB 公式是这样的：

    UCB = X + C * sqrt(2ln(n) / ni)

    其中 X 是节点的平均奖励值(比如胜率)，n 是总的访问次数，ni 是当前节点的访问次数，C 是一个常数，控制探索与利用的平衡。较高的值会增加探索，而较低的值会强调利用。

    利用就是X,探索就是sqrt(2ln(n) / ni),如果当前访问次数较小,探索值就会偏大

  2. 扩展(Expansion): 如果找到的节点不是一个游戏结束的状态，那么创建一个或多个子节点并选择其中一个。通常，这一步是随机地选择一个尚未尝试过的动作。

  3. 模拟(Simulation): 从选定的节点开始，通过随机地选择动作，模拟游戏直到达到游戏结束状态.

  4. 回传(Backpropagation): 一旦模拟结束，根据模拟的结果（赢、输或平局），更新从所选节点一直到根节点的所有节点的统计数据。

阿尔法狗

使用神经网络+MCTS

其中神经网络包括策略神经网络和估值神经网络

MCTS的问题

  • 生成所有子节点

  • 模拟具有盲目性

就是说:盲目

策略网络

损失函数L(w)=$-t_a log(p_a)$

​ $t_a$：当前棋局下棋手落子在a处时为1，否则为0

​ $p_a$：策略网络在a出落子的概率

就是说,如果棋手落在a位置,希望策略网络也在a处落子

估值网络

损失函数L(w)=$(R-V)^2$

R为棋局的胜负

V为估值网络的输出(-1,1)

与MCTS融合

AlphaGo增加了第三个原则经验：落子概率高的节点

image-20230616005919473

上面的图不用记.只需要知道最后选择的点是根子节点中被拓展过最多次的点.

还有一个要注意的点是最后回传的价值:奇数层和偶数层之间正负号要切换.因为一方得利就是另一方失利

强化学习

强化学习就是监督学习的反义词

强化学习是机器学习的一个子领域，它关注的是如何基于环境反馈来采取最优的行动。

在强化学习中，我们设有一个智能体（Agent），它在某个环境（Environment）中进行行动。每一次行动之后，环境都会对智能体的状态造成变化，并给予一定的回馈（Reward）。智能体的目标就是通过学习，寻找一种策略，使得随着时间的推移，其能获取最多的回馈。

为了实现这个目标，智能体需要通过探索（Exploration）和利用（Exploitation）之间进行平衡。探索是指尝试新的行动以获取更多信息，利用是指根据已有的知识采取最佳行动。如果智能体只是利用当前的知识，可能会错过那些长远看有更大回馈的行动；但是如果过多地探索新的行动，也可能会付出更多代价。

深度强化学习

基于神经网络的强化学习方法

三个方法

  • 基于策略梯度

    • 假设获胜者的行为都是正确的，负者行为都是不正确的

    • 假设获负时对权重的修改量大小与获胜时一样，方向相反

    • 流程

      1. 自己和自己下棋
      2. 下完棋的数据用来训练新模型
      3. 新的自己和过去的自己下棋
      4. 如果赢了则更新自己的版本
      5. jump to 1

  • 基于价值评估

实际上前两种方法就是把监督学习的MCTS的策略网络和估值网络迁移过来给出了一个深度学习的版本而已

  • 演员评价方法

image-20230616012023947

实际上演员评价方法就是把上面两个网络变成两个通道,最后再通过一定的权重组合

AlphaGo Zero

在第三步的模拟过程中,用估值网络的输出取代模拟过程

引入多样性:人为引入噪声.



本文总阅读量次