大模型系列——AlphaZero/强化学习/MCTS

AlphaGo Zero无需任何人类历史棋谱，仅使用深度强化学习，从零开始训练三天的成就已远远超过了人类数千年积累的围棋知识。

1、围棋知识

（1）如何简单理解围棋知识

（2）数子法分胜负：https://zhuanlan.zhihu.com/p/37673325

（3）如何数目分胜负：https://www.zhihu.com/question/284822816/answer/2897667581

（4）3分钟围棋入门视频（总共近2小时）：b站 

2、强化学习

强化学习（Reinforcement Learning）是机器学习里面一个分支。如果说强化学习在AlphaGo之前版本里面还是初试牛刀的话，那在AlphaGo zero里面强就真正大显神威。根据deepmind的论文，新版本AlphaGo Zero经过三天的训练轻易达到对老版本的100:0的胜率，并且完全无需人类棋谱。可以说，AlphaGo Zero仅仅三天的成就就远远超过了人类数千年的围棋探索。

强化学习和传统机器学习的区别有如下几点：

• 传统机器学习假设算法本身对于环境无影响，强化学习破除了这个限制，能够考虑到了算法对于环境的影响, 这使得强化学习特别适合解决多回合博弈或者顺序决策问题。在传统机器学习中，如果你预测完了之后你根据据测去做多或着做空这个股票，那么其他的股票买家可能因为你的行为改变了自身行为，你原来的训练的模型便会失效，而强化学习可以考虑到这点。
• 在强化学习中，数据是在运行过程中自主收集。AlphaGo Zero之所以能够完全摒弃人类知识就是因为所有的数据都是通过机器互博生成。

用强化学习解决问题，我们需要首先把要解决的问题转化成为一个环境（environment）。环境需要如下的要素：

• 状态空间（state space）：对于围棋来说，每一个棋盘布局（记为s）就是一个状态。所有可能的棋盘布局就是状态空间。
• 动作空间 （action space）：对于围棋来说，所有可能落子的位置就是一个动作空间
• 可行动作 （allowable action）： 在给定状态下，什么动作是可行，什么是不可以的。在围棋里，就是给定一个棋盘，哪里可以落子，哪里不可以。
• 状态转化：你落子之后，对手可能会下的子。如果是两台alpha zero互搏的话，相互是对方环境的一个部分。
• 奖励函数：你落子之后得到的信号。在围棋里面，就是胜率的一个正函数。胜率越大，奖赏越大。

在强化学习里面，知识可以通过一个称为状态－动作值函数（state-action value function) 的结构的存储。通常大家用符号Q(s,a)来表示这个函数，这就是所谓Q-learning的来历。简而言之，Q(s,a)是对于状态s，采取动作a的期望奖励(expected reward)。

强化学习知识（理论）：https://zhuanlan.zhihu.com/p/25319023

3、AlphaZero实战

AlphaZero实战：从零学下五子棋（附代码）：https://zhuanlan.zhihu.com/p/32089487

3.1 模型训练

本节参考：https://zhuanlan.zhihu.com/p/30339643

训练步骤如下：

（1）构造MCTSPlayer self_play一些轮次后（批量进行），收集构造批次训练数据（包括当前状态，可能的行动概率，胜率），其中winners_z为1或者-1，如下：

zip(states, mcts_probs, winners_z)

（2）利用self_play数据训练策略价值网络。

（2）构造MCTSPlayer和MCTS_Pure（每个子节点的概率都一样）两个玩家，对战n_games次，返回胜率。

（3）若胜率为最佳，则保存当前模型。

（4）重复以上步骤game_batch_num次。

注意：这里MCTS是AlphaZero能够通过self_play不断变强的最重要的原因，相当于用能力不这么强的模型尝试多次后取更有可能胜利的判断。刚开始模型准确率基本为0，但让其仿真模拟N次后，知道哪些落子路径有一定的胜率。将这些路径作为训练数据，训练模型后，模型有一定准确率，MCTS仿真N次后，得到更佳的路径，最终不断变强。

3.2 实际对战

整体步骤如下：

（1）构造Human和MCTSPlayer两个玩家，进入start_play方法的while循环中

（2）交替出子

（3）若判断有人胜出则结束。

1、MCTSPlayer计算出子流程（Play）

（1）利用MCTS策略模拟执行500次，获取子节点访问次数。注意：本代码中_n_playout为500，每一个playout中敌我双方走了N步（不超过当前树的最大深度），直到产生了新的路径节点才结束本次仿真。

（2）所有仿真结束后，根据父节点下所有一级子节点的访问次数构造概率，获得下一步落子位置。

这里面T为温度参数，T越大，表示温度越高，落子位置越随机，否则位置越确定，代码中temp参数为0.01。公式实验如下：

visits = [2,10, 8, 4, 1]

softmax(1.0/0.001*np.log(np.array(visits)))
array([0.00000000e+00, 1.00000000e+00, 1.23023192e-97, 0.00000000e+00,
       0.00000000e+00])
>>> softmax(1.0/0.01*np.log(np.array(visits)))
array([1.26765060e-070, 1.00000000e+000, 2.03703598e-010, 1.60693804e-040,
       1.00000000e-100])
>>> softmax(1.0/0.1*np.log(np.array(visits)))
array([9.24622380e-08, 9.02951542e-01, 9.69536836e-02, 9.46813317e-05,
       9.02951542e-11])
>>> softmax(1.0/1*np.log(np.array(visits)))
array([0.08, 0.4 , 0.32, 0.16, 0.04])

可以看出，当temp为1时，概率就比较均匀了。否则为0.001时，虽然10和8差距小，但概率都集中到了10这个为止。

最后说下最终落子的采样逻辑，按概率随机选择一个：

random.choice说明如下：
If an ndarray, a random sample is generated from its elements.
>>> aa_milne_arr = ['pooh', 'rabbit', 'piglet', 'Christopher']
>>> np.random.choice(aa_milne_arr, 5, p=[0.5, 0.1, 0.1, 0.3])
array(['pooh', 'pooh', 'pooh', 'Christopher', 'piglet'], # randomdtype='<U11')

2、MCTS推演落子规则-(Select)

在每一个节点s，AlphaGo Zero会根据如下的公式来选择下一次落子位置：

其中Q(s, a)是对于状态动值函数的估计值。U(s,a)是一个confidence interval 的upbound。决定探索（exploration）的程度。

代码实现如下：

 从代码中可以看出U由P、当前节点访问次数、父节点访问次数组成，当前节点访问次数越低，值越高，结合c_puct（代码中为5）赋予探索权重。

2、MCTS推演落子规则-(Expand and Evaluate)

 （1）当棋局没有结束且仿真到叶子节点时（select参考上述步骤），则需要Expand操作添加新的行为策略节点，并将本次仿真后的胜率更新到Q值，继续下一次仿真。

3、MCTS更新Q值-(Backup)

（1）更新节点和父节点Q值

一次仿真结束后，调用_policy进行策略和胜率评估，这里的胜率是node节点对手的胜率，因此当前节点的Q值更新是-leaf_value。另外由于是交替进行，父节点是leaf_value。

这里leaf_value是最终盘面的胜率，相当于最终的奖励。用于更新Q，根据访问次数平均权重 

4、alphago和alphazero对比

4.1 AlphaGo 和 AlphaZero 的区别

本段参考：https://zhuanlan.zhihu.com/p/634880256

（1） Policy network 和 Value network 的神经网络 前几层参数是共享的

（2）一开始没有 Supervised Learning of Policy Network (SL policy network) 的环节，也就是说完全没有加入任何人类先验知识在里边，直接暴力上强化学习。

。这一点 AlphaZero 就是完全颠覆了人类传统棋理，可见 AlphaZero 在没有人类先验知识的情况下，不仅仅可以学习到人类的走棋模式，也可以创造出自己的走棋模式，而且这种走棋模式还更加合理。

其他较好文章：https://zhuanlan.zhihu.com/p/30339643

minigo解读：https://zhuanlan.zhihu.com/p/352536850 

minigo实现：https://github.com/tensorflow/minigo

5、问题

 （1）大模型中若使用MCTS，那么策略和价值如何定义？

在数学题中，可以分解子问题作为action