3 博弈问题
3.1 与或图
问题归约：复杂问题不断分解和变换得到子问题，最后转化为若干本原问题。
- 初始问题描述、将问题化为子问题的操作符、本原问题描述
与图 & 或图：
- 与图：将原问题分解为若干子问题的与\(\rightarrow\)与节点
- 或图：将原问题变换为若干子问题的或\(\rightarrow\)或节点
与或图：如果原问题既需要分解有需要变换才能得到本原问题，则归约过程可使用与或图表示
- 端节点：没有子节点的节点
- 终止节点：本原问题对应的节点（终止节点一定是端节点）
（不）可解节点：
- 终止节点是可解节点，不为终止节点的端节点是不可解节点
- 对于或节点，若子节点（不）存在可解节点，则该或节点为（不）可解节点
- 对于与节点，若子节点（不）都是可解节点，则该与节点为（不）可解节点
解图（解树）：由可解节点构成的，并且由这些可解节点可以推出初始节点为可解节点的子图
状态空间法与问题归约法：
| 状态空间法 | 问题空间法 | |
|---|---|---|
| 问题求解 | 状态变换 | 问题分解 |
| 搜索过程 | 普通有向图 | 与或图 |
| 节点 | 状态 | 问题 |
| 边 | 状态变换规则（操作） | 问题分解规则（操作） |
| 求解 | 解径 | 解图（解树） |
一般搜索过程：
- 将原始问题作为初始节点，将其作为当前节点
- 应用分解和变换对当前节点进行扩展，为子节点设置指向父节点的指针
- 选择合适的子节点作为当前节点，反复执行（2）步，反复执行（不）可解标记过程，直到初始节点被标记为（不）可解节点为止
3.2 与或图的盲目搜索
与或树的广度优先搜索：
- 算法
- 把初始节点放入open表
- 将open表的第一个节点取出放入closed表，记为n
- 如果节点n可扩展，则：
- 扩展节点n，将子节点设置父指针并放入open表尾部
- 考察子节点中是否有终止节点。若有，则标记为可解节点并放入closed表，并用可解标记过程对先辈节点进行标记
- 如果初始节点被标记为可解节点，则搜索成功并退出
- 从open表删除具有可解先辈的节点，转（2）步
- 如果节点n不可扩展，则：
- 标记节点n为不可扩展节点
- 用不可标记过程对节点n的先辈节点进行标记。如果初始节点标记为不可解节点，则搜索失败并退出
- 从open表删除具有不可解先辈的节点，转（2）步
与或树的深度优先搜索：
- 扩展节点的子节点放在open表的首部
3.3 与或图的启发式搜索
最优解树：代价最小的解树
- 解树的代价是自下而上逐层计算的
- 与状态空间搜索的代价计算不同
- 节点的代价：
- 终止节点的代价：\(h(n)=0\)
- 或节点的代价：\(h(n)=\min\{c(n,n_i)+h(n_i)\}\)，\(n_i\)为\(n\)的子节点
- 与节点的代价：
- 最大代价法：\(h(n)=\max\{c(n,n_i)+h(n_i)\}\)，\(n_i\)为\(n\)的子节点
- 和代价法：\(h(n)=\sum{(c(n,n_i)+h(n_i))}\)
- 非终止节点的端节点：\(h(n)=\infty\)
- 解树的代价：初始节点的代价
希望树：任何时候都选择最有希望成为最有解树一部分的节点进行扩展
- 初始节点在希望树中
- 如果节点在希望树中，则：
- 若节点为或节点，则子节点中代价最小的在希望树中
- 与节点为与节点，则所有子节点在希望树中
希望树的代价：除非节点的全部子节点都是端节点，否则子节点的代价是不可知的
- 根据问题本身提供的启发性信息定义启发函数，用启发函数估算节点代价
- 每当有新一代节点生成，都要自下而上地重新计算先辈节点的代价
启发式搜索过程：
- 把初始节点放入open表中
- 计算希望树
- 依次将open表中希望树的端节点取出并放入closed表，记为n
- 如果节点n为终止节点，则：
- 标记n为可解节点
- 对希望树使用可解标记过程，对节点n的先辈节点进行标记
- 如果初始节点标记为可解节点，则找到最优解树并退出
- 从open表中删除具有可解先辈的所有节点，转（2）步
- 如果节点n不为终止节点，且不可扩展，则：
- 标记n为不可解节点
- 对希望树使用不可解标记过程，对节点n的先辈节点进行标记
- 如果初始节点标记为不可解节点，则搜索失败并退出
- 从open表中删除具有不可解先辈的所有节点，转（2）步
- 如果节点n不为终止节点，但可扩展，则：
- 扩展节点n，将子节点设置父指针并放入open表
- 计算这些子节点及其先辈节点的代价，转（2）步
3.4 博弈树搜索
博弈树：任何一方的每一步都是对自己最有利、对对手最不利的方案，站在某一方将上述博弈过程表示为与或图，即博弈树
- 博弈树的初始格局为初始节点
- 博弈树中，或节点和与节点是逐层交替出现的，己方扩展的节点之间为或关系，对方扩展的节点之间为与关系
- 所有使自己获胜的终局都是本原问题，对应的节点为可解节点；所有使 对方获胜的终局都是不可解节点
极大极小分析法：
- 基本思想：
- 设为博弈双方中的一方寻找一个最优行动方案
- 为了找到当前最优行动方案，需要考虑每一方案实施后对方要采取的行动，计算可能的得分
- 为了计算得分，需要根据问题的特性定义估价函数，用于估算端节点的得分（静态估值）
- 端节点的估值计算出来后，计算父节点的得分：
- 或节点：选择子节点中最大得分作为父节点得分
- 与节点：选择子节点中最小得分作为父节点得分
- 若一个方案能获得较大倒推值，则它就是当前最佳行动方案
- 局限性：
- 对于十分复杂的问题，利用完整的博弈树进行极大极小分析是困难的
- 可行的方法：只生成一定深度的博弈树，使用极大极小分析法找出当前最好方案，然后在已选分支上继续扩展，如此反复
\(\alpha-\beta\)剪枝
- 基本思想：边生成博弈树边计算各节点的倒推值，根据评估出的倒推值范围及时停止扩展已无必要扩展的子节点
- 剪枝方法：
- 定义：与节点倒推值的上确界为\(\beta\)，或节点倒推值的下确界为\(\alpha\)
- \(\alpha\)剪枝：对于与节点及其父节点（一定是或节点），若\(\alpha\geq \beta\)，则不必再扩展该与节点的其余子节点
- \(\beta\)剪枝：对于或节点及其父节点（一定是与节点），若\(\alpha\geq \beta\)，则不必再扩展该与节点的其余子节点
- 简记：
- 极小\(\leq\)极大，剪枝，\(\alpha\)永不下降
- 极大\(\geq\)极小，剪枝，\(\beta\)永不上升
- 要进行\(\alpha-\beta\)剪枝，则至少必须使某一部分的搜索树生长到最大深度
- 采用\(\alpha-\beta\)过程都要使用某种深度优先的搜索算法