这次继续介绍几个凸包算法，包括 Graham scan 和快速凸包算法。

Graham scan​

Graham scan 是一个表达起来很简洁的算法，而且也没有涉及到复杂的数据结构，它仅仅需要两个栈 $S$ 和 $T$。

首先遍历所有点，选出 lowest-then-leftmost 的点 $p_{1}$，并以该点为参照，将所有其余点按照极角排序，分别为 $p_{2},p_{3},\cdots ,p_{n}$。

两个栈初始化为（方括号代表栈底）： $S=[\ p_{1},p_{2}>$ $T=< p_{3},p_{4},\cdots ,p_{n}\ ]$

扫描算法流程：当栈 $T$ 非空时，如果栈 $T$ 的栈顶在栈 $S$ 的栈顶与次栈顶组成的有向边的左侧，则将栈 $T$ 的栈顶压入栈 $S$；否则弹出栈 $S$ 的栈顶元素。伪代码如下：

while (!T.empty())
    toLeft(S[1], S[0], T[0]) ? S.push(T.pop()) : S.pop();

有兴趣的读者可以在下图所示的点集上运行一遍算法流程，我就不赘述了。

扫描效率​

这一节讨论扫描一步的效率。粗浅来看，点集中除了参照点的每个点都可能被做 $\Omega(n)$ toLeft 比较，那么扫描效率就是 $O(n)\times O(n)=O(n^{2})$。但这种估计方法明显太松了，接下来用两种方法求更紧的上界。

平面图​

先来复习一下图论中平面图的概念：

在图论中，平面图是可以画在平面上并且使得不同的边可以互不交叠的图。而如果一个图无论怎样都无法画在平面上，并使得不同的边互不交叠，那么这样的图不是平面图，或者称为非平面图。

而在扫描一步中，遍历的所有边都不会相交（如下图）。也就是说，这一步的搜索空间构成了一个平面图。根据欧拉定理，得知平面图中边数 $E=O(3n)$，从而说明了扫描效率为 $O(n)$。

均摊分析​

我们从另一方面看待这个问题，考虑变量 $A=|S|+2|T|$。显而易见地，每次循环中 $A$ 都会减少 $1$。扫描开始时，$A=2n-2$；扫描结束时，$A\ge 3$。则循环执行了 $O(2n-5)=O(n)$ 次，也即扫描效率为 $O(n)$。

简化​

仔细想想，算法中的排序一步是不需要 toLeft 作为比较器的。

假如在点集中增加一个点作为参考点，并把它无限拉低，直到 $(0,-\infty)$，则点集中其余点与参考点连成的线就是竖直的，也就是说，我们只需要对其余点的横轴坐标排序即可。

但由于引入了一个新的点，所以也会导致求得的凸包与原点集凸包不符。幸运的是，如果我们将新凸包中与参考点有关的两条边删掉，就可以得到原凸包的上半部分，称之为上半凸包（upper hull）。

同理，可以在点集中增加参考点 $(0,+\infty)$，就可以求出下半凸包（lower hull）。将两者合并，就得到了原凸包。

极点个数期望​

令 $P$ 是平面上的点集，假设点的个数是 $n$，这一节将讨论 $CH(P)$（P的凸包）上点个数的量级。

值得注意的是，不同的采样方式会得出不同的结果。考虑在单位正方形内均匀且独立地采样（单位正方形与任意长方形是相同的，因为两者可以通过仿射变换至彼此）。

取凸包的最上/下/左/右四个点，可以将凸包分成四个部分，不失一般性，我们只考虑凸包的右上角 $CH_{UR}(P)$，如下图。

在右上角区域，可以定义「极大点」：

以点 $P$ 为原点建立坐标系，如果第一象限没有点集中的其余点，则称点 $P$ 为极大点。

称极大点集为 $MAX(P)$，则 $|CH_{UR}(P)|\le |MAX(P)|$，接下来考虑 $|MAX(P)|$ 的期望。

从右到左，将点集中的点称之为 $\{p_{1},p_{2},\cdots ,p_{n}\}$。对于点 $p_{k}$ 来讲，它是极大点当且仅当它是 $\{p_{1}, p_{2}\cdots ,p_{k}\}$ 中最高的。由于点是在单位正方形内均匀独立采样得到的，则 $p_{k}$ 是极大点的概率为 $\frac{1}{k}$。故

$E[|MAX(P)|]=\sum_{i=1}^{n} \frac{1}{n}=O(\log(n))$

经过上述推导，得知当在单位正方形内均匀独立采样时，凸包上点个数的期望为 $O(\log(n))$。

除了在单位正方形内采样以外，在其他几何形状内采样则会得到不同的结果：

• 单位圆 —— $O(n^{\frac{1}{3}})$；
• 三角形 —— $O(\log(n))$；
• 凸 $k$ 多边形 —— $O(k\log(n))$。

快速凸包（Quickhull）​

首先找出点集中 leftmost-then-lowest 的点 $s$，以及 rightmost-then-highest 的点 $t$。则求解凸包就可以分为求解上半凸包和下半凸包，如下图。

由于求解上下半凸包是对称的，所以只讨论上半凸包的求解过程。

与快速排序类似，在每次求解凸包时，都将当前点集分为三部分：

• $P_{0}$ 区域是需要被剪掉的部分，这其中的点之后无需考虑；
• $P_{1},P_{2}$ 区域为左、右子区域，原凸包可以由这两个子区域的凸包组合而成。

具体来说，取距离线段 $st$ 最远的点 $r$ 作为哨兵。那么 $\triangle srt$ 包围的区域则为 $P_{0}$，$sr$ 左侧的区域是 $P_{1}$，$rt$ 右侧的区域是 $P_{2}$，如下图。

当然快速凸包算法的最差情况也是 $O(n^{2})$ 的，考虑这种情况：在单位圆的直径上取两个点，随后在圆心角为 $\frac{90^{\circ}}{2^{k}},k=0,1,2,\cdots$ 的位置加入点，如下图。那么每次选择哨兵时都会造成左右极不均匀，从而导致最坏情况。

先来说两个简单的计算几何小问题：

给定两个二维线段，判定它们是否相交？

当然最笨的办法就是求出两个线段方程，判断解是否满足要求。但这会引入除法操作，这不是我们希望的结果。

如上图，考虑 $P_{3}, P_{4}$ 是否在线段 $a$ 的异侧（toLeft 返回值不同则表示在异侧）。当然只做这一次异侧判断是不行的，对称地考虑 $P_{1}, P_{2}$ 是否在线段 $b$ 的异侧。如果两次异侧判断都成功，则说明两个线段相交。这种方法只需要进行 $4$ 次 toLeft 判断，提高了效率。

用极点法求出若干极点后，如何将其排成环？

假设 leftmost-then-lowest 的极点为 $P_0$，定义 $P_{1} < P_{2} \Leftrightarrow toLeft(P_{0}P_{1}, P_{2})==false$。按照上述定义的偏序关系就可以对所有极点排序，排序后从小到大即可。

从上面两道小题能够看出 toLeft 判定的重要性，这个判定函数将会贯穿计算几何的学习历程。

极边法（Extreme Edges）​

从极点法我们可以自然而然地想到，如果遍历点集中所有可能成为凸包边界（极边）的线段，也能达到求解凸包的目的。事实上，我们也只需要对点集中每两个点相连的线段判断其余点是否都处于它的一侧即可。

所以极边法的时间复杂度相对极点法要低一些，遍历所有线段（$C_{n}^{2}=O(n^2)$）$\times$ $O(n)$ 个 toLeft 判断 $=O(n^3)$ 的复杂度，虽然好一些但还不够。

增量法（Incremental Construction）​

顾名思义，增量法的主要思路就是遍历点集中的所有点，每次都更新当前已遍历点集的凸包，最后得到对于所有点的凸包。

如上图，在添加新点时会发生三种情况：

• 该点作为新凸包上的点，且不影响原凸包上的点；
• 该点在目前凸多边形的内部；
• 该点作为新凸包上的点，并删除一些原凸包上的点。

那么怎么判断新加入的点属于上面哪种情况呢？我们一点一点看，先来判断新点是否属于原凸包内，也即判断点是否属于凸多边形的内部。

线性解法 —— 逆时针遍历凸多边形的所有边，执行 toLeft 判定。优势是可以应用于链表等动态内存结构，劣势是慢；

二分查找 —— 二分地判定点是否属于两条射线张成的区域之内，如下图。优势是快，劣势是只能应用于数组等静态内存结构。

在增量法中，由于我们需要保证能够在常数时间内删除点，所以需要采用链表等结构，那么还是需要使用线性解法。

那么怎么应对刚刚说的第三种情况呢？我们将原凸包分成四部分：

• 上、下切点（$t,s$）；
• $ts$ 段，需要被删除的部分；
• $st$ 段，需要保留的部分。

那么怎么判断点属于哪种类别呢？如上图，

• 若 $v$ 的两个邻域点都分布在 $xv$ 的左侧，则 $v$ 是下切点；
• 若 $v$ 的两个邻域点都分布在 $xv$ 的右侧，则 $v$ 是上切点；
• 若 $v$ 的两个邻域点（逆时针上、逆时针下）分布在 $xv$ 的左右侧，则 $v$ 属于 $ts$ 段；
• 若 $v$ 的两个邻域点（逆时针上、逆时针下）分布在 $xv$ 的右左侧，则 $v$ 属于 $st$ 段；

幸运的是，可以用类似的方法判断点是否在凸多边形内，也即判断其余点是否都属于 $st$ 段。

Jarvis March​

该算法的大致思想是逐条选出极边并加入到凸包中，如下图。

如下图，在算法运行中，怎样选取下个点，使得它与当前点 $k$ 组成的边是下一条极边（$ks$）呢？

对于极点 $k$，只要找到点 $s$ ，使得 $ks$ 的右侧没有任何其他点。与本文一开始提出的第二个小问题类似，以 toLeft 测试为比较函数，找出其余点中最大的那个即可。

不失一般性，第一个极点 $o$ 可以按照 lowest-than-leftmost 的规则选取。

凸包算法的下界​

使用归约法（reduction）说明。关于归约法，维基百科有如下说明：

以直觉观之，如果存在能有效解决问题 B 的算法，也可以作为解决问题 A 的子程序，则将问题 A 称为“可归约”到问题 B，因此求解 A 并不会比求解 B 更困难。

上图表示了一个线性归约，如果对于问题 A 的任意输入都可以在线性时间内转换为某个 B 的输入，且对于问题 B 的输出都可以在线性时间内转换为 A 的输出，那么称问题 A 可以线性归约至问题 B。且问题 A 的下界也是问题 B 的下界。

考虑基于比较的排序问题，对于一维上的所有输入，可以在线性时间内投影到抛物线 $y=x^2$ 上。而投影过后的点集的凸包投影回一维上就是排序后的结果。则基于比较的排序问题可以线性归约为二维凸包问题，那么二维凸包问题的下界就是 $O(n\log(n))$。

下次将介绍几个 $O(n\log(n))$ 的凸包算法。

这学期有幸选到了贵系邓俊辉老师的《计算几何》，这学期会随着课程进度更新一些笔记。

凸包​

用邓老师的话来说，所谓凸包就是

把点集看作钉在桌子上的若干钉子，这时撑开一个橡皮筋，让它能够囊括所有钉子，松手后橡皮筋围成的多边形就是该点集的凸包

当然这只是一个凸包在二维上的解释，但通俗易懂，如下图。

那么给定一个点集 $P$，如何计算出其凸包 $CH(P)$ 呢？接下来将介绍第一个计算凸包的算法 —— 极点法。

极点法（Extreme Points）​

极点​

如下图，对于点集中的某个点，若存在一条经过该点的直线，使得点集中的其余点均处于该直线的一侧，则称该点为极点（Extreme Point）。

但根据上述定义很难实现凸包的构建算法，因为对于每个点都要遍历经过它的所有直线，而这些直线是无限的。

对于非极点来说，它必然会被点集中某三个点组成的三角形完全包围（不包括边界），而极点不满足该性质，如下图。

所以就可以遍历点集中的所有三角形，将其覆盖的所有点设置为非极点。通过排除所有的非极点就可以得到点集中的所有极点。 该算法的时间复杂度是 $O(C_{n}^{3}\cdot n)=O(n^4)$ 的。

那么如何判断点是否在三角形内呢？当然，可以使用射线法或累计角度法判定，但未免有些「杀鸡用牛刀」的意味。考虑边按逆时针排列的三角形，对于这三条有向边，若某点处于它们的左侧（toLeft 判断），则该点被该三角形覆盖，如下图。

通过计算有向面积（$\times 2$）的符号能够判定某点是否在有向边的左侧：

在得到点集中的所有极点后，再对它们进行排序（$O(n\log(n))$）就可以得到最终结果。

极点法虽然能够计算凸包，但还存在问题，其中最不能使人接受的是其较高的时间复杂度，之后将会介绍一些复杂度相对较低的算法。

这次的笔记包括马尔科夫决策过程以及增强学习的相关内容。

马尔科夫决策过程​

马尔科夫决策过程（Markov Decision Processes，简称MDP）的定义：

• 状态集合 $s\in S$
• 动作集合 $a\in A$
• 转移函数 $T(s,a,s^{\prime})$，表示从状态 $s$ 执行动作 $a$ 后达到状态 $s^{\prime}$ 的概率
• 收益函数 $R(s,a,s^{\prime})$，表示转移对应的收益
• 初始状态
• 终止状态（不必须）

举个例子，在一个网格迷宫中，我们操纵的 agent 将会在迷宫中进行游走。

区别于一般的游戏，它并不会完全按照我们给他的指令进行移动，它有 80% 的概率正确地移动，其余 20% 的概率将会向正确移动方向的左边或者右边（各 10%）进行移动，如果移动方向前方有墙，那么它待在原地不动。为了敦促 agent 尽快找到宝物，在游戏结束前，走的每一步都会略微扣一些分数，当找到宝物后，将会有较大的奖励；反之，如果不幸掉进陷阱，将会有较大惩罚。

在这个 MDP 中，我们可以对 MDP 定义中的一些抽象概念进行具体化，比如转移函数可以写成：

$T((3,1),North,(3,2))=0.8$ $T((3,1),North,(2,1))=0.1$ $T((3,1),North,(4,1))=0.1$

值得注意的是，终止状态并不是可见的，也就是说，当 agent 达到 $(4,3)$ 时，不会马上得到分数，而是需要经过一个动作 exit 后达到终止状态。

在 MDP 中，我们需要找出一个最佳策略（policy）$\pi^{*}:S\rightarrow A$：

• 对于每个状态，策略 $\pi$ 都会给出一个动作
• 使得效益（utilities）最大化的策略被称之为最佳策略

收益（reward）函数对最佳策略的影响见下图：

比较有趣的是，当每一步的收益亏损很大时（右下角），在陷阱附近的 agent 将会倾向于自杀，因为自杀也只不过扣1分，而继续活着将扣2分。

值得一提的是，马尔科夫通常代表，针对当前状态来讲，未来以及过往都是独立的。在MDP中具体来说，可以用下面这个式子来表达：

$P(S_{t+1}=s^{\prime}|S_{t}=s_{t},A_{t}=a_{t},S_{t-1}=s_{t-1},A_{t-1}=a_{t-1},\cdots,S_{0}=s_{0})=P(S_{t+1}=s^{\prime}|S_{t}=s_{t},A_{t}=a_{t})$

接下来介绍折扣（discounting）概念。在我们最大化收益的同时，我们倾向于更早地获得收益，以及更晚地获得负收益。所以可以考虑将收益进行指数性减小，每经过一步，收益都会乘以一个因子 $\gamma\in(0,1)$。

现在考虑对 MDP 的求解。首先定义几个概念：

• $V^{*}(s)=$ 在状态 $s$ 下开始，进行最优操作所获得的收益期望
• $Q^{*}(s,a)=$ 从状态 $s$ 进行动作 $a$ 后，进行最优操作所获得的收益期望
• $\pi^{*}(s)=$ 状态 $s$ 的最优操作

可以类比之前学过的 Expectimax Search ，通过构造出类似的搜索树，可以得到如下几个公式（Bellman 等式）：

• $V^{*}(s)=\max\limits_{a} Q^{*}(s,a)$
• $Q^{*}(s,a)=\sum\limits_{s^{'}}T(s,a,s^{'})[R(s,a,s^{'})+\gamma V^{*}(s^{'})]$ $\Rightarrow V^{*}(s)=\max\limits_{a} \sum\limits_{s^{'}}T(s,a,s^{'})[R(s,a,s^{'})+\gamma V^{*}(s^{'})]$

但如果还用之前的搜索法来对这个问题进行求解，速度就太慢了。所以引入新的算法：价值迭代（value iteration）：

• $\forall s\in S\quad V_{0}(s)=0$
• $\forall s\in S\quad V_{k+1}(s)\leftarrow \max\limits_{a}\sum\limits_{s^{'}}T(s,a,s^{'})[R(s,a,s^{'})+\gamma V_{k}(s^{'})]$
• 重做第二步，直到收敛

价值迭代法每一步的时间复杂度为 $O(S^{2}A)$，而且当 $\gamma\in (0,1)$ 时，算法必然收敛。

在使用价值迭代法得到每个状态的 $V^{*}$ 值后，怎么得到某个状态下的最佳策略呢？这时我们需要在该状态下计算其所有 $Q^{*}$ 值，并取使 $Q^{*}$ 最大的动作作为在该状态下的最佳动作。

价值迭代算法存在着一些问题：

• 时间复杂度较高
• 每个状态的最佳策略往往在 $V$ 值收敛前就已经收敛了

针对上列问题，我们可以对策略进行迭代，该方法称为策略迭代（policy iteration）：

• 策略评估：针对固定策略 $\pi$ 计算出所有状态的 $V$ 值
• 策略改进：对于每个状态，都找出当前的最优动作，更新策略
• 重复上两步，直到策略收敛

其中策略评估可以使用迭代法（利用 Bellman 等式，时间复杂度：$O(S^{2})$ 每步），也可以将Bellman等式看做一个线性系统进行求解。

策略迭代方法的运行速度比价值迭代方法快了不少，并且也会收敛到最优策略。

强化学习​

强化学习的基本思想如下：

• 环境会以收益的形式给出反馈
• agent 的效益由收益函数定义
• 学习能够最大化收益期望的策略
• 所有学习过程都基于在游戏探索得到的样本

之所以我们需要探索游戏，是因为游戏（MDP）中的 $T$（转移函数）和 $R$（收益函数）是未知的。

基于模型的学习​

基本思想：

• 根据经验学习一个大概的模型（估计 $T$ 和 $R$）
• 对这个学习出的 MDP 进行求解

看个例子，

根据输入的策略 $\pi$，可以得到若干遍历结果，从而可以对 $T,R$ 进行估计。

无模型学习​

被动强化学习（passive reinforcement learning），类似于之前介绍的策略迭代，首先对一个输入的固定策略进行评估，之后对策略进行优化改进。那么问题就是，我们没有 $T,R$，无法使用之前的方法直接进行策略评估，所以需要尝试新的方法。

直接评估，针对固定策略 $\pi$，按照该策略进行游戏，并记录每一步的收益，并最终通过取平均来获得每个状态的 $V$ 值。看个例子，

比如 $V(B)$，由于样本中从状态 $B$ 出发，只有向东走的情况，所以 $V(B)=\frac{(-1-1+10)+(-1-1+10)}{2}=8$，其余类似。这个方法很直观，也不需要 $T,R$ 的任何信息，但忽略了状态间的关系，且每个状态必须分开学习，所以需要较长时间去学习。

既然这个方法不行，那么我们又想回上一节策略评估的方法：通过下式进行迭代，

$V_{k+1}^{\pi}(s)\leftarrow\sum\limits_{s^{'}}T(s,\pi (s),s^{'})[R(s,\pi (s),s^{'})+\gamma V_{k}^{\pi}(s^{'})]$

虽然没有 $T,R$ 也就无法使用上式，但我们可以在游戏中进行一系列采样：

$sample_{i}=R(s,\pi (s),s_{i}^{'})+\gamma V_{k}^{\pi}(s_{i}^{'})\\ V_{k+1}^{\pi}(s)\leftarrow \frac{1}{n}\sum\limits_{i}sample_{i}$

通过对采样进行平均，从而得到每个状态的 $V$ 值。

进一步，我们需要将算法调节成迭代算法，这样就不用针对每个状态单独进行估值，而是每次进行游戏都可以使路径中的状态 $V$ 值迭代逼近真正的值。这种方法被称为时间差分学习（temporal difference learning）。以固定策略进行游戏的情况下，每次迭代都将更新状态的 $V$ 值，公式如下：

• $sample=R(s,\pi (s),s^{'})+\gamma V^{\pi}(s^{'})$
• $V^{\pi}(s)\leftarrow (1-\alpha)V^{\pi}(s)+\alpha sample$

这个方法很好，但我们不能忘了目标，我们需要找到每个状态的最优动作，也即对于状态 $s$，需要找到

$\pi (s)=\operatorname*{argmax}\limits_{a} Q(s,a)=\operatorname*{argmax}\limits_{a}\sum\limits_{s^{'}}T(s,a,s^{'})[R(s,a,s^{'})+\gamma V(s^{'})]$

由于对 $T,R$ 的缺失，导致无法从已有的 $V$ 值中榨取出最优动作，所以我们应该考虑对 $Q$ 值进行学习。

主动增强学习（active reinforcement learning），其与被动增强学习的区别在于，学习者需要自己选择策略对游戏进行探索，而不是之前的按照既定策略进行探索然后更新。

Q-Learning，通过自定的策略对游戏进行探索，并更新状态 $s$ 及对应动作 $a$ 的 $Q$ 值：

• 探索得到一个样本：$(s,a,s^{'},r)$
• 考虑旧的估计值 $Q(s,a)$
• 考虑新样本的估计值 $sample=R(s,a,s^{'})+\gamma\max_{a^{'}}Q(s^{'},a^{'})$
• 将新旧估计值做加权平均：$Q(s,a)\leftarrow (1-\alpha)Q(s,a)+\alpha\cdot sample$

Q-Learning将会收敛至最优策略，但也有几个附加说明：

• 需要足够多的探索
• 学习率 $\alpha$ 需要逐渐变小（比如 $\frac{1}{n}$，但也不能减小得太快）

在Q-Learning中，比较重要的一点是在exploration和exploitation中做一个 trade-off 。

一种比较简单的做法就是设定一个阈值 $\epsilon$，随后每次做选择时 roll 一个 0 到 1 之间的随机数，如果小于 $\epsilon$，则随机选择动作（exploration）；否则，选择当前的最优决策（exploitation）。

稍微复杂些的做法是设置一个 exploration function，比如：$f(u,n)=u+\frac{k}{n}$ ，其中 $u,n$ 分别代表估计值和探索次数，那么改良后的 Q-Learning 中每个样本估计值的表达式将变为：

$sample=R(s,a,s^{'})+\gamma\max_{a^{'}}f(Q(s^{'},a^{'}),N(s^{'},a^{'}))$

这样一来，当 agent 进行探索时，也会更倾向于考虑探索次数少的动作，而且当 $n$ 越来越大时，$\frac{k}{n}$ 一项对 $Q$ 的影响也越来越小，最终将不会影响最优策略的选择。

然而在实际问题中，会有很多很多的状态，当状态足够多时，我们不可能存储所有的 $Q$ 值。而且某些状态比较相近，但我们的 Q-Learning 方法仍然将它们视为完全不同的状态。举个例子，

前两个状态，pacman 都是被两只鬼堵在角落里，实质上 pacman 所处的情形差不多。一、三两个状态更是几乎完全相同，只是右上角的一块食物在第三个状态中被吃掉。然而它们都被视为了完全不同的状态，这一点可以被我们用来优化算法。

这样看来，优化方法也可以比较容易想到，也即将状态用特征向量表示出来：$f_{i}(s,a),i\in [1,n]$。这里特征的设计就显得尤为重要，好的特征可以将状态空间较好地映射到特征空间。考虑将这些特征进行线性组合：

$Q(s,a)=\sum\limits_{i=1}^{n} w_{i}f_{i}(s,a)$

经过这样的处理，Q-Learning 算法也将变为 Approximate Q-Learning ：

$difference=[r+\gamma\max_{a^{'}}Q(s^{'},a^{'})]-Q(s,a)\\ w_{i}\leftarrow w_{i}+\alpha\cdot difference\cdot f_{i}(s,a)$

至此，课程的第一部分也就结束了。由于学校这边即将开学，所以博文也要停更一段时间，之后的部分随后有时间再填坑吧。。

这次笔记将会总结对抗性游戏中游戏策略的决策方法。

在研究决策策略之前，我们需要对游戏的类型做一个限制。首先，这种游戏需要是确定性的，也就是说，任意一个动作都可以让玩家从某一个状态确定地转移至另一个状态。以及，这种游戏需要是一个零和游戏，即，玩家的效益是相反的。

在之前的决策搜索中，状态树一般是长成这样的：

由于只有一名玩家，所以我们只需要最大化节点的值即可。但在对抗性游戏当中，至少有两位玩家，所以对抗性游戏的状态树一般是这样的：

考虑这样一种策略，当自己控制 pacman 时，总是希望选取能让自己效益最大化的那个动作；而对方控制 ghost 时，自己总是做好最坏打算（也就是对面会选取一种让自己的效益最小化的那个动作）。这种策略被称为 Minimax Search 。用数学表达式来说明每个节点的 Minimax Value ，如下：

$V(s)=$

• $\max_{s^{\prime}\in successor(s)}V(s^{\prime})$ , if under user's control
• $\min_{s^{\prime}\in successor(s)}V(s^{\prime})$ , if under opponent's control
• known value, if terminal state

只要理解了原理，实现起来也比较简单。伪代码：

这就像一个彻底的 DFS，把状态树彻彻底底地搜索一遍。所以复杂度也与DFS相同。但在实际情况中，几乎不可能把整个状态树全部搜索完，所以需要考虑限制搜索深度。如果搜索一定深度后，仍然没有到达树的底部，那么就需要评估当前状态是好还是坏，这就是评估函数。评估函数好坏与否对于解决问题是很重要的。

在限制搜索深度的同时，还可以对状态树进行剪枝，被称作 Alpha-Beta 剪枝。看一个例子：

当我们在计算节点 $n$ 的值时，将会遍历其所有子节点，计算它们的值并从中选出一个最小的值作为$n$ 的值。这时令 $a$ 为从根节点到 $n$ 路径中所有选项中最小的那个，如果 $n$ 的某个子节点的值小于 $a$，那么我们将不再考虑 $n$ 的其他任何子节点，也即将 $n$ 剪掉。另外一种情况是对称的。根据这个原理，可以将 Alpha-Beta 剪枝的伪代码表示成如下形式：

经过剪枝后的搜索算法的时间复杂度从 $O(b^{m})$ 降至 $O(b^{\frac{m}{2}})$，也就是说，可以搜索的深度相较于之前的 naive 算法多了一倍！

之前讨论的情况都是在对方也是一个出色的玩家（总是选择最大化自己的效益）下进行的。另外还有可能对方只是采取随机游走或者采取固定策略，如果是这种情况，使用 Minimax Search 就不是一个好的选择。所以考虑引入 Expectimax Search ，思路很简单，就是将 Minimax Search 算法中状态树中的最小值节点（min node）替换成概率节点（chance node），这种节点的值等于子节点值的期望。伪代码如下：

注，本文系从 https://web.archive.org 抢救而恢复，可能会丢失一些信息。

UCB 的 CS188 课程名为 Introduce to AI，人工智能导论，在 edX 网站中可以进行在线学习，链接：CS188

本文主要是对 Lecture2&3 做一个总结，这两次课着重介绍了对搜索问题的建模方法以及搜索方法。

Search Problem​

一个搜索问题由几个部分组成：状态空间（state space）、继承函数（successor function）、开始状态（start state）以及结束测试（goal test）。解决方案则是由一系列动作（action）组成，这些动作可以使开始状态变化至结束状态。

举个例子，先来看这个地图：

对于一个旅游问题，比如某人想从城市 Arad 移动至城市 Bucharest 来说，以上提到的几个要素的建模方法如下：

• 状态空间：地图中所有城市；
• 继承函数：假设旅行者现在所在的城市为 $T$，则继承函数为 $S(T)=$ 所有与 $T$ 邻接的城市；
• 开始状态：城市 Arad；
• 结束测试：旅行者是否身处于城市 Bucharest。

进而，对于搜索问题，我们可以构建一个状态空间图，其中每个状态至多只在图中出现一次，继承关系可以用有向边来表示。但对很多问题来说，把整个图存放在内存中是一件几乎不可能的事情（太大），所以转而考虑构建状态空间树，从而进行搜索。

Uninformed Search​

先来看一下搜索算法的框架：

接下来的三种搜索方法都是以上面这个框架为基础。在该算法框架中，closed 是一个 set，以保证已经扩展过的状态不会再次被遍历到；fringe 则是一个容器，用来存储搜索中遍历到的状态；而 strategy 则是会影响容器 fringe 的排列方式。

如果说刚刚介绍的那套算法流程看起来比较陌生的话，那么深度优先搜索和广度优先搜索我们就比较熟悉了。对于DFS（Depth First Search）来讲，fringe 和 strategy 所组成的数据结构就是栈，而对BFS（Breadth First Search）来说，其对应的数据结构则是队列。在 Uninformed Search 中，还有一种搜索方法 UCS（Uniform Cost Search），这种方法与 Dijkstra 算法比较相似，只不过是在这个算法框架内缺少了 relax 操作，也即 UCS 比 Dijkstra 算法略逊一筹。对 Dijkstra 算法比较熟悉的同学可以看出，优先级队列是在这套算法框架中需要使用的数据结构。

这三种搜索方法的一些性质可以罗列如下：

• DFS
  • 扩张节点个数复杂度
    • $O(b^{m})$，$m$ 为搜索树的高度，$b$ 为树中所有节点的最大子节点数
  • 空间复杂度
    • $O(bm)$
  • 能否搜索到任意一个解？
    • 如果 $m$ 有限，则可以
  • 搜索到的解是否最优？
    • 不一定
• BFS
  • 扩张节点个数复杂度
    • $O(b^{s})$，$s$ 为最浅解在树中的搜索深度
  • 空间复杂度
    • $O(b^{s})$
  • 能否搜索到任意一个解？
    • 可以
  • 搜索到的解是否最优？
    • 除非 cost 均为固定常数，否则不一定
• UCS
  • 扩张节点个数复杂度
    • $O(b^{C^{*}/\epsilon})$，$C^{*}$ 为最优解的cost，$\epsilon$ 为边的最小cost
  • 空间复杂度
    • $O(b^{C^{*}/\epsilon})$
  • 能否搜索到任意一个解？
    • 如果 $C^{*}$ 有限且 $\epsilon$ 为正数，就可以
  • 搜索到的解是否最优？
    • 可以

Informed Search​

之前所介绍的搜索方法完全没有考虑当前搜索到的状态与最终解的状态之间的距离，比如说某人想去东边的一座城市，在搜索时可能会将西方的城市也进行扩张搜索，然而这是完全没有意义的，这是南辕北辙。所以我们需要人为引入启发式函数来引导搜索方向。

一个启发式函数对当前状态与解状态之间的距离进行估计，具体函数的表达需要每个人自己去估计，比如在寻路问题中可以利用曼哈顿距离、欧氏距离等等。

在A*（A-star）算法中，将边的 cost 与启发式函数相加，得到函数 $f=g+h$。使用 $f$ 作为优先级队列的key，就能够使用上一节所介绍的搜索算法框架来实现 A* 算法。

为保证 A* 算法的最优性，启发式函数 $h$ 需要满足性质：启发式函数所估计出的 cost≤ 实际 cost，用数学表达出来即，

$0\le h(n)\le h^{*}(n)$

其中 $h^{*}$ 是从当前状态到最近解状态的真实 cost。（admissible）以及，

$h(A)-h(C)\le cost(A\rightarrow C)$

（consistency）

A* 算法将会在扩张更少节点的情况下搜索到最优解，在Pacman游戏中的寻路问题上，A* 算法与贪心法、UCS 的比较如下图：

可以看到，贪心法虽然扩张的节点较少，但并没有找到最优解；UCS 虽然找到了最优解，但几乎搜索了整张地图；而 A* 算法在找到了最优解的情况下，只搜索了大概半张地图。

简单说一下上个学期图形学课程做的一些东西，主要是实现了 Ray Tracing 以及 Monte Carlo Path Tracing 的一部分，以及实现了一篇通过神经网络训练辐射度函数的论文。这里就先谈一谈光线追踪的相关东西吧。

我在去年这个时间自己实现了一个光线追踪的 demo，只实现了几个简单的模型，并没有纹理、景深等特性，而且代码结构比较差，不是很 OOP。上个学期我拜读了一下 ppwwyyxx 的code，从代码结构以及各种 C++11 的特性运用上，感觉自己相比于这位贵系同学在大二时的水准差的还是太多了，还是需要再学习一个。这次光线追踪程序的架构很大程度上也是参考了他的架构，但类的内部实现基本还是自己写的，在之前的基础之上增加了比如折射、纹理、景深、软阴影等等特性。效果大概是这样

这里着重说一下景深，这个特性从视觉上理解就是在对焦平面上的物体最清晰，距对焦平面越远，物体越模糊的一种现象。所谓对焦平面即满足如下条件的平面：从成像平面上的一点向光圈追踪的所有光线在经过光圈折射后都会在对焦平面上的某一点相交。也就是说，如果想要模拟这种现象，就需要利用上述性质。首先我们需要在光圈上进行采样（我直接用的随机采样，貌似pbrt有更高级些的采样方法），得到采样点 $P_{i}$，作为跟踪光线的起点。再从光圈中点与虚拟屏幕上需要渲染的像素点位置进行连线并延长，找到其与对焦平面的交点 $Q$，则 $P_{i}Q$ 即为跟踪光线的方向。

蒙特卡洛路径追踪这一部分呢，主要还是对算法的理解以及重要性采样比较重要（对我来讲）。理解了渲染方程会对算法的实现有很大的帮助。由于我只实现了Lambertian和Phong模型，所以重要性采样也只涉及了针对这两种模型的方法。

先来看 Phong 模型的 BRDF 函数：

$f_{r}(x,\theta_{i},\theta_{o})=\frac{k_{d}}{\pi}+k_{s}\frac{n+2}{2\pi}cos^{n}(\alpha)$

其中 $\alpha$ 是镜面反射方向与出射方向所成的夹角，$n$ 是材质的 shininess。以及满足约束 $k_{d}+k_{s}\le 1$

那么可以分成两步，先根据俄罗斯轮盘赌法则确定光线接下来的采样方式（漫反射/高光反射/被吸收），之后根据不同情况进行重要性采样。对于漫反射部分，概率分布函数以及采样方法如下：

$pdf(\theta_{i})=\frac{1}{\pi}cos(\theta_{i})$

$w_{i}=(\theta,\phi)=(arccos(\sqrt{u_{1}},2\pi u_{2}))$

其中 $u_{1},u_{2}$ 为属于 $[0,1]$ 区间的随机数。对于高光反射部分，pdf 以及采样方法：

$pdf(\theta_{i})=\frac{n+1}{2\pi}cos^{n}(\alpha)$

$w_{i}=(\alpha,\phi)=(arccos(u_{1}^{\frac{1}{n+1}}),2\pi u_{2})$

MCPT的效果如下：

github地址：https://www.github.com/nero19960329/RayTracer