对抗搜索

• 博弈问题
  博弈问题穷举有时可以获得必胜结果，但是稍微复杂一点的问题就很难穷举了。
• 极大极小过程
• alpha-beta剪枝
• Monte-Carlo博弈

极大极小过程

极大极小过程的想法非常直白，即：我方走步，则选择极大值；对方走步，则选择极小值。
极大极小过程是博弈问题的一个最基本的决策模式，alpha-beta剪枝法是建立在极大极小过程基础上的。

alpha-beta剪枝法

假如A和B博弈，不妨令局面估值函数为A的利益，那么A追求节点值极大，B追求节点值极小。
定义：极大节点的下界为alpha，极小节点的上界为beta。
剪枝：后辈节点的beta<=祖先节点的alpha，alpha剪枝；后辈节点的alpha>=祖先节点的beta，beta剪枝。
MyRemark
这个地方可能会给出一个树然后考手写求解过程，一个比较简单的手写方法是，先把每一层是极大还是极小标出来，然后标注这一行写alpha还是beta，之后从最后一层开始向上推。正常情况下一定是alpha小于beta的。如果出现alpha大于beta，就从中间剪开。这时候，被剪开上面是谁，就是谁剪枝。
实际实现的时候会发现，在ab剪枝法中，局面评价函数是非常重要的。深蓝能够依靠这个算法实现，很大程度上是因为成功构造出了一个局面评价函数。
在做大作业的时候，实在是没想出来合适的局面评价函数，效果特别差，所以最后用了蒙特卡洛。不过alpha-beta剪枝的效率真的是很好，现在想想假如用蒙特卡洛的结果训练神经网络，把这个作为估值函数，这样就相当于没有时间限制，算是一种cheat的方式吧（摊手）。

Monte-Carlo模拟

蒙特卡洛方法就很简单，就是不断地试，然后选择最优的。
主要就是UCT算法。每次模拟，假如没有拓展就拓展，每次拓展走子的时候，都选择UCB1最大的点走子。
最终选择被模拟次数最多的节点作为最佳走步。
AlphaGo用的是Monte-Carlo，显然是因为围棋比象棋复杂太多，局面估值函数实在是不好做。
AlphaGo在实际做的时候有以下几个操作：

• 利用策略网络缩小搜索范围
• 将估值网络的结果结合到信心上限的计算中
• 一个节点被模拟一定的次数之后才扩展（这个还是挺重要）
• 最终选择模拟次数最多的节点作为最佳走步
  这个部分做了一个大作业，可能就不考了吧（天真脸）