第3章：约束满足与博弈搜索

约束满足问题

CSP 用变量、取值域和约束描述合法配置。图着色中，变量是顶点颜色，域是可用颜色，相邻顶点不同色是二元约束。目标是找到满足赋值，不一定存在自然的路径代价。

回溯为变量逐个赋值，违反约束时撤销。最少剩余值启发式优先选择域最小的变量，尽早暴露冲突；前向检查在赋值后删除邻居不可能的取值。

弧一致性要求：对约束 $C(X,Y)$ ， $X$ 域中每个值都能在 $Y$ 域中找到支持。删去无支持值后可能影响其他弧，因此需要反复传播。

三个变量组成三角形，每个域为红、蓝，两两要求异色。任一变量的红都能在相邻变量找到蓝作为支持，蓝也有红支持，因而可保持弧一致；整个三角形却不能二着色。

约束传播减少搜索，不普遍代替搜索。它检查局部关系，不能据此推断所有局部选择能同时组合。

双人零和、完全信息、轮流行动的有限博弈，终局给定效用。己方节点取子节点值的最大值，对方节点取最小值：

V(s)=\begin{cases}\max_aV(T(s,a)),&\text{己方};\\\min_aV(T(s,a)),&\text{对方}.\end{cases}

该策略针对按同一零和效用最优行动的对手。若对手行为服从已知概率模型，可在相应节点取期望，而不能继续把概率当作最坏情况。

$\alpha$ 表示当前已知的己方下界， $\beta$ 表示对方上界。当某分支已不可能改善祖先的选择时，可停止展开，不改变完整 minimax 值。

根为 MAX，第一子树值为 5，故根已有下界 5。第二子树为 MIN，看到一个叶值 3 后，该子树最终值至多为 3，剩余叶子不影响根选择，可以剪掉。

搜索截断后需要评价函数估计未到终局的局面。剪枝对所搜索树保持精确，但评价误差、截断深度与地平线效应仍会影响真实棋力。