基于Python对抗 DQN 网络 Adversarial-DQN以及 MCTS 的结合【100011292】

# 对抗 DQN 网络 Adversarial-DQN”以及 MCTS 的结合 强化学习的本质是决策，根据当前的状态来决策应该采取什么动作。跟有监督学习不同的是，有监督学习是通过已有的数据和数据对应的正确标签，学习数据和标签对应逻辑；强化学习刚开始并没有标签，它是在尝试动作后才能获得结果，通过反馈的结果信息不断调整之前的策略。若将状态看作数据属性，动作看作标签，监督学习和强化学习都是在试图寻找一个映射，从已知属性/状态推断出标签/动作，强化学习中的策略相当于有监督学习中的分类/回归器。 ## Q-Learning Q-Learning 是强化学习里经典的算法之一。Q-Learning 主要有 R 表和 Q 表，两个表记录的都是各个状态下各个动作的得分。   在决策时，选择 Q 表中当前状态对应的得分最高的动作作为决策。在更新时，需要结合 R 表和当前 Q 表的信息，对 Q 表的更新是 Q-Learning 的关键，公式为：  R 表是固定不变的，这是固定的先验知识，需要人为引入。经过多轮的迭代更新之后，Q 表就会指引 agent 以更小的代价到达 reward 值最大的状态。 ## DQN Q-Learning 需要的 Q 表大小为 state*actin，当状态空间很大时，这个表将会变得非常大，想要构造出这么一个 Q 表几乎是不可能的事。所以后来转换了思想，Q-Learning 实际上是在寻找一个 state 到 actin 的映射，因为状态空间很大，所以这个映射应该是非常复杂的，所以可以借助深度学习来拟合这个映射。 DQN 的创新点有：通过经验池解决了训练数据的相关性及非静态分布问题；使用 TargetNet 作为延迟网络，解决了稳定性问题。 引用 Nature 中的 DQN 算法伪代码：  ## Adversarial-DQN 由于 DQN 算法设计是针对单一 agent 的，所以在连续的不同状态下，都是这一个 agent 执行动作，即连续的两个状态下 agent 的目标都是一样的最大化 reward 值，所以更新公式为：  但是现在的情景是下棋，是双方的博弈，这样相当于有两个 agent，对于他们各自而言目标都是最大化自己的 reward，这样就会相应的减小对方的 reward。 而且，连续两个状态下动作的执行者是不同的，这样存在 agent 的切换的情形不同于 DQN，所以我们提出了一种新的模型：Adversarial-DQN。 该模型由两个 DQN 组成，分别对应于，，2，并且训练时的经验池只记录属于自己的经验，即(s,a,r,s_)，s∈。在训练时，由于状态 s 对 应的后继状态 s_是属于对方的，所以当前值网络的更新公式修改为：  其中其中 1、1、2、2 分别对应于两个 DQN 网络的当前值网络和目标值网络。对 1 进行更新时，我们把后继状态′输入对方的目标值网络，而不像 DQN 那样输入到自身的目标值网络。而且因为对方的 DQN 网络的目标也是最大化自身的 reward，所以对方的目标值网络 2 输出的是对方的最大值得分，所以在更新自己的网络时应该是减去对方的网络输出。 A-DQN 结构如下：  训练时在 episde 中同时更新 DQN1 和 DQN2，分别在各自的经验池中随机抽选 minibatch 个样例，为了使梯度更新更加充分，在一个 episde 里还要反复训练 n 次，每一次都重新对经验池进行随机抽样。 ## DQN 网络结构 因为棋盘大小是 8*8，而状态 state 表示的就是当前棋盘的局面，所以可以用 1*64 大小的向量表示状态，对应位置上为 1 代表黑棋，为-1 代表白棋，为 0 代表空。而动作可以表示为在落子在棋盘的某个位置，所以也可以用一个 1*64 大小的向量表示 actin，但考虑到有可能当前状态下没有位置可以走，所以增加一个表示跳过的 actin，即表示为 1*65 大小的向量。 所以我们可以设计网络输入为 1*64 维的 tensr，输出为 1*65 维的 tensr，输出表示各个 actin 的得分，在合法位置集合中挑选得分最高的 actin 就是网络预测的决策。网络结构图如下：  #### 自博弈构造经验池 数据强化学习归根结底还是数据驱动的方法，所以想要训练出一个好的模型的话需要大量的数据。DQN 一个优点就是可以通过自博弈自动构造训练数据，我们只需要人工地加入 reward 值、或评价值即可。 游戏的初始状态是棋盘上共有 4 个棋，黑白各两个。游戏规定黑棋先手，所以把这个初始状态输入到 DQN1，网络输出一个动作 actin，并且游戏状态相应地转变为 s’。现在还差这一步的 reward 值，如果我们引入评价函数，就可以根据当前棋盘上的局面评价出这一步的得分，但是因为我们对黑白棋游戏并不熟悉，而且这个游戏比之前的五子棋复杂得多，所以不可能设计出一个合理的评价函数。如果评价函数设计得不好，反而会引入了错误的先验知识，这样反而会使得模型效果变差。所以我们的方法是，如果这一步使得游戏结束了，若是己方胜利则该步的 reward 值为 100，若是对方胜利则该步的 reward 值为-100，其余情况下 reward 值都为 0。这样设计 reward 值会存在反馈延迟的问题，这一步得到的经验需要在很久以后才能学习到它的反馈，相当于训练数据效率较低。但是如果数据足够多，训练时间足够的话，模型还是可以学习到这些数据的知识慢慢收敛的。 这样我们就构造完成了经验池中的数据，如前面所说的，如前面 A-DQN 中描述的，一个 DQN 的经验池只记录属于自己的数据，即(s,a,r,s_) ，s∈。 #### 蒙特卡罗树搜索： 在上一次实验的五子棋设计中，我们通过设计评价函数和使用博弈树的搜索方法来选择下一步的落子，取得了很好的效果，不过在五子棋中，我们就算使用了 alpha-beta 剪枝优化，下一步也有一定的延迟，而在本次实验的黑白棋中，我们自身对黑白棋就很不熟悉，自然很难去设计一个比较好的对当前棋局的评价函数，只能一直模拟对弈到棋局结束，再根据胜负回溯结果，不像五子棋的博弈树搜索可以限制搜索深度。如果每一步都这样搜索，解空间就会非常的大，落子速度非常的慢，没有实际的应用价值。 因此我们采用了蒙特卡罗 MCTS 的搜索方法，它本质上还是一种搜索的算法。对于黑白棋，MCTS 沿着博弈树不断的往下模拟，一直到叶子节点，也就是棋局无处可以落子，或者某一方被吃光，然后胜者评分为 +1，负者评分为-1，然后通过回溯的方法将棋局的结果信息一直往上传播，直到起始节点。反复进行多次模拟搜索，当搜索结束时（受限于时间或计算能�