# 一阶逻辑(FOL: First Order Logic)

一阶逻辑用下面的形式描述世界
- 对象：人、房屋、数字、颜色、游戏、战争、披萨
- 关系：可以是一元关系或属性, 如红色的、圆的、伪造的；更普适的是n元关系, 如大于、…和…是兄弟、在…里
- 函数:  有唯一值, 如…的父亲, …最好的朋友, …的左胳膊, …加1 等

关系又可称为**谓词**





# FOL的语法

- 常量/Constants: `KingJohn, 2, USTC, ...`
- 谓词/Predicates: `Brother, >, ...`
- 函数/Function: `Sqrt, LeftLegOf, ...`
- 变量/Variables: $x, y, a, b, \dots$

FOL还需要表示逻辑的符号（就跟命题逻辑一样）
- 联结词/Connectives: $\neg, \land, \lor, \Rightarrow, \Leftrightarrow$
- 等词/Equality: $=$
- 量词/Quantifiers: $\forall, \exists$

常量和变量称为**项**，即对象。对项应用函数也会得到项，称为**复合项**。如有$n$元函数$\varphi$
$$
\varphi(x_1,x_2,\cdots,x_n)
$$
将其作用到$n$个项$t_1,t_2,\cdots,t_n$上会得到复合项
$$
\varphi(t_1,t_2,\cdots,t_n)
$$

:::info{title="Note"}
所有项都是0次或有限次复合得到的
:::

谓词作用在项上形成**原子语句**，项也可以是复合项，如
$$
>(Length(LeftLegOf(Richard)), Length(LeftLegOf(KingJohn)))
$$

原子语句由逻辑词链接得到**复合语句**，如
$$
> (1,2) \land \neg >(1,2)
$$

# 一阶逻辑语句的真值与数据库语义
语句的真值是由一个**模型**和对句子符号的**解释**来判定，其中模型包含**对象域和对象的关系**，解释是指对FOL语句中的三类符号(常量符号、谓词符号、函数符号)指代的对象、关系和函数进行解释

如对于
$$
Brother (Richard, John) 
$$

根据`Brother`，`Richard`，`John`解释的不同，该语句的真值也不同。 FOL语言中，3类符号在模型中的对应数量可以从1到无穷大，**无法枚举**，因而需要引入**数据库**

**数据库语义**定义为
  - 唯一名称假设：每个常量符号指代一个唯一对象
  - 封闭世界假设：假设未知的所有原子语句均为假
  - 论域闭包：每个模型只包含常量符号指代的对象


# 全称量词与存在量词

- **量词**: 表示数量的词
- **全称量词 $\forall$**: 表示任意的，所有的，一切的
- **存在量词 $\exists$**: 表示存在，有的，至少有一个

量词的使用需要注意避免两类错误

:::warning{title="全称量词"}
全称量词$\forall$和`与`$\land$逻辑混合使用，如记$M(x)$表示`x是人`，$F(x)$表示`x爱美`
$$
\forall x(M(x)\land F(x))
$$
它的语义是任何事物$x$都是人并且任何事物$x$都爱美。事实上如果希望表达`人都爱美`，应当使用蕴含逻辑
$$
\forall x(M(x)\Rightarrow F(x))
$$
:::

:::warning{title="存在量词"}
存在量词$\exists$和`蕴含`$\Rightarrow$逻辑混合使用，如记$M(x)$表示`x是人`，$F(x)$表示`x爱美`
$$
\exists x(M(x)\Rightarrow F(x))
$$
它的语义是存在事物`x`，如果`x`是人`x`就爱美。事实上如果想表示`有的人爱美`应该使用与
$$
\exists x(M(x)\land F(x))
$$
:::

# 量词的性质
**两个相同的量词可以交换**
$$
\forall x\forall y,~\forall y \forall x
$$
它们是等价的，因而可以简写为$\forall x,y$。同样`存在量词`也有相同的等价关系
$$
\exists x\exists y,~\exists y \exists x
$$
它们是等价的，因而可以简写为$\exists x,y$。但是注意

:::warning{title="注意"}
$\forall x\exists y$ 和 $\exists y\forall x$ 不等价。随便找个函数试试就能发现了
:::

**量词否定等值式**

对含量词的逻辑表达式取反时应先将量词取反
$$
\neg \forall x A(x)\equiv \exists x\neg A(x)\\
\neg\exists x A(x)\equiv\forall x\neg A(x)
$$

**量词可以分配**

$\forall$对`与`$\land$可以分配，$\exists$对`或`$\lor$可以分配
$$
\forall x(A(x)\land B(x))\equiv \forall xA(x)\land\forall xB(x)\\
\exists x(A(x)\lor B(x))\equiv \exists xA(x)\lor\exists xB(x)\\
$$
反过来则不成立

# 等词`=`
等词`=`意为**相同的对象**而不是值相同，表征它俩就是同一个东西。例如可以用父母关系定义兄弟姐妹
$$
\forall x, y \, Sibling(x, y) \iff \\
[\neg(x = y) \land \exists m, f \, (\neg(m = f) \land Parent(m, x) \land Parent(f, x) \land Parent(m, y) \land Parent(f, y))]
$$

逻辑学（三）——一阶逻辑

# 推理的形式结构

推理有`前提`和`结论`。记前提为$A_1,A_2,\cdots,A_n$，结论为$B$，则由前提推出结论可以抽象地表示为一个逻辑表达式
$$
A_1\land A_2\land\cdots\land A_n\Rightarrow B
$$

该推理正确等价于上式无条件为真，也就是说

:::info{title="Note"}
前提为$A_1,A_2,\cdots,A_n$，结论为$B$的推理正确等价于表达式
$$
A_1\land A_2\land\cdots\land A_n\Rightarrow B
$$
为重言式
:::



推理有以下几种方法
- 真值表枚举法：对所有的变量枚举所有可能的取值，证明该表达式恒为真
- 等值演算法：根据逻辑学定理将该表达式变形，直到可以确定其为真
- 构造证明法: 从前提出发，严格按照推理规则构造命题序列，序列的最后一条是结论

包含蕴涵的重言式可以列举如下，供推理使用。`蕴含`符号的左侧为真就意味着右侧为真，欲证明右侧为真可以证明左侧为真

| 定律名称       | 表达式                                                                 |
| :-------------: | :------------------------------------------------------------------: |
| 附加律         | $A \vDash (A \lor B)$                                               |
| 化简律         | $(A \land B) \vDash A$                                              |
| 假言推理       | $(A \Rightarrow B) \land A \vDash B$                                |
| 拒取式         | $(A \Rightarrow B) \land \neg B \vDash \neg A$                      |
| 析取三段论     | $(A \lor B) \land \neg B \vDash A$                                  |
| 假言三段论     | $(A \Rightarrow B) \land (B \Rightarrow C) \vDash (A \Rightarrow C)$ |
| 等价三段论     | $(A \Leftrightarrow B) \land (B \Leftrightarrow C) \vDash (A \Leftrightarrow C)$ |
| 构造性二难     | $(A \Rightarrow B) \land (C \Rightarrow D) \land (A \lor C) \vDash (B \lor D)$ |
| 构造性二难(特殊) | $(A \Rightarrow B) \land (\neg A \Rightarrow B) \vDash B$          |
| 破坏性二难     | $(A \Rightarrow B) \land (C \Rightarrow D) \land (\neg B \lor \neg D) \vDash (\neg A \lor \neg C)$ |

# 推理规则
| 规则名称       | 表达式                                                         | 描述                         |
| -------------- | ------------------------------------------------------------ | ---------------------------- |
| 前提引入规则   | $\begin{aligned} A \\ \therefore A \end{aligned}$            | 一个命题可以直接推出自身     |
| 结论引入规则   | $\begin{aligned} \vdash B \\ \therefore A \vdash B \end{aligned}$ | 如果结论成立，则添加前提无影响 |
| 置换规则       | $\begin{aligned} A \iff B \\ \therefore B \iff A \end{aligned}$ | 等价命题可以交换位置         |
| 假言推理规则   | $\begin{aligned} A \Rightarrow B \\ A \\ \therefore B \end{aligned}$ | 前提成立则结论必然成立       |
| 附加规则       | $\begin{aligned} A \\ \therefore A \lor B \end{aligned}$     | 单个命题可以推出或关系       |
| 合取消去规则   | $\begin{aligned} A \land B \\ \therefore A \end{aligned}$    | 合取中的某一项可以被单独推出 |
| 拒取式规则     | $\begin{aligned} A \Rightarrow B \\ \neg B \\ \therefore \neg A \end{aligned}$ | 如果结论不成立，则前提必然不成立 |
| 假言三段规则   | $\begin{aligned} A \Rightarrow B \\ B \Rightarrow C \\ \therefore A \Rightarrow C \end{aligned}$ | 前提的传递性推导出最终结论   |

# 归结证明

:::tip{title="归结(消解)规则"}
若已知 $p\lor q$ 与 $\neg p \lor r$都为真，则$q\lor r$为真
:::
形式上看是消去了变量 $p$ ，利用它可以从条件中消去结论中不出现的变量进而完成证明

证明$A_1\land\cdots\land A_n\Rightarrow B$恒为真等价于证明下式为假
$$
A_1\land\cdots\land A_n\land \neg B
$$

利用反证法，假定它是真的，推出矛盾（0）即可。由此归结证明的过程可以描述如下
1. 将每个前提都转化为合取范式，即一些简单析取式以“或”的形式连接，进而得到一系列简单析取式形式的前提，记为$A_1,A_2,\cdots,A_t$
2. 将结论的反 $\neg B$ 转化为合取范式，即$\neg B=B_1\land B_2\land\cdots\land B_s$
3. 认为这些$B$都是真的，以$A_1,A_2\cdots A_t,B_1,\cdots B_s$为条件，使用归结推出矛盾（0）

一个证明的例子是
$$
前提：(p\Rightarrow q)\Rightarrow r,~r\Rightarrow s,~\neg s~~结论：p\land\neg q
$$

首先将前提转化为合取
$$
(p\lor r)\land(\neg q\lor r),~\neg r\lor s,~\neg s
$$

将结论转化为合取
$$
\neg p\lor q
$$

希望利用前提和结论推出0
$$
p\lor r,~\neg q\lor r,~\neg r\lor s,~\neg s,~\neg p\lor q
$$

先消去$p$
$$
p\lor r+~\neg p\lor q\rightarrow q\lor r
$$

那么就有$~\neg q\lor r,~\neg r\lor s,~\neg s,~q\lor r$，消去$q$
$$
~\neg q\lor r+~q\lor r\rightarrow r
$$

那么$~\neg r\lor s,~\neg s,~r$，再消去$r$
$$
~\neg r\lor s+r\lor 0\rightarrow s
$$

那么$s,~\neg s$。实际上到这里已经出现矛盾了，不过从程序上来说还是推导到$0$为止
$$
s\lor 0 + \neg s\lor 0\rightarrow 0
$$

即完成了证明。关于归结法有定理

:::info{title="Note"}
归结法是完备且可靠的
:::

不过它的时间复杂度是指数级的

# 前向链接与反向链接

逻辑学中将命题抽象为符号，称其为**正文字**，将其否定称为**负文字**。鉴于蕴含等值式

>$$
>A\Rightarrow B\equiv \neg A\lor B
>$$

若$A$是一些正文字的与，即简单合取式$A=a_1\land a_2\cdots \land a_n$，那么由于摩根定律有
$$
\neg A=\neg a_1\lor\neg a_2\lor\cdots\lor\neg a_n
$$
也就是说，如果一个析取式中只有一个正文字
$$
B\lor\neg a_1\lor\neg a_2\lor\cdots\lor\neg a_n
$$
它会等价于一个蕴含式
$$
a_1\land a_2\cdots \land a_n\Rightarrow B
$$

称其为**确定子句**

:::info{title="Note"}
**确定子句**：只有一个正文字的析取式
:::

若允许全是负文字，则得到了**霍恩子句**

:::info{title="Note"}
**霍恩子句**：最多一个正文字构成的析取式
:::

由于归结会消去两个子句中的一个正文字和对应负文字，因而**确定子句或霍恩子句的归结是封闭的**，即任意两个确定子句或霍恩子句归结，得到的仍是确定子句或霍恩子句

前向链接算法用于处理确定子句（即蕴涵式）构成的知识库推理问题。如果已知了一个知识库KB，其中是一系列的确定子句。为了描述方便，定义蕴涵式中
$$
a_1\land a_2\cdots \land a_n\Rightarrow B
$$

$a_1, a_2\cdots , a_n$为**前件**，$B$为结论。希望查询命题Q是否能被推理，可以依照下面的步骤

0. 初始化一个确定事件集合，用于保存已经确认为真的事实。对于知识库中每一个确定子句，维护其不在确定事件集合中的前件数目
1. 取出知识库中全部前件已知的确定子句（即不在确定事件集合中的前件数目为零），将其结论添加入已知事件集中，将其从知识库中删除
2. 重复`1`直到命题Q被添加入已知事件集或是知识库为空

也可以采取**反向链接**算法，它是自顶向下的，即查询以Q为结论的所有蕴涵式是否存在一个其前提都为真，尝试递归证明它们。反向链接算法是目标驱动的，适合解决明确的问题，有时复杂度会远远小于前向链接

逻辑学（二）——推理与证明

# 命题与联结词
命题是真假性唯一的陈述句，不能可真可假。若陈述句中存在悖论，或者分情况确定真假，也不构成命题

最简单的命题是**原子命题**，它是由简单陈述句构成的命题，将其抽象为符号，如`p`,`q`,`r`。它的作用和地位可以类比于单词，具有最基本的语义，也称为**原子语句**



由原子命题通过**联结词**联结而成的陈述句称为**复合命题**。逻辑联结词可以如下列出
- $\neg p$ ：**非**，否定联结词，称$\neg p$为**否定式**。$p$为正文字，$\neg p$为负文字
- $p\wedge q$：**与**，合取联结词，称$p\wedge q$为**合取式**
- $p\vee q$：**或**，析取联结词，称$p\vee q$为**析取式**
- $p\Rightarrow q$：**蕴含**，蕴含联结词，称$p\Rightarrow q$为**蕴含式**，$p$为前件，$q$为后件
- $p\Leftrightarrow q$：**双向蕴含**，等价联结词，当且仅当

规定联结词具有优先级
$$
()\to \neg\to\wedge,\vee\to\Rightarrow,\Leftrightarrow
$$
同级联结词从左到右结合。联结词的真假如下表

| $p,q$ | $\neg p$ | $p\wedge q$ | $p\vee q$ | $p\Rightarrow q$ | $p\Leftrightarrow q$ |
| :---: | :---: | :---: | :---: | :---: | :---: |
|啥啊|  $p$假时真   |  $pq$都真时真   |  $pq$都假时假   |  $p$真$q$假时假   |  $pq$真假相同时真   |
|0 0| 1|0|0|1|1|
|0 1| 1|0|1|1|0|
|1 0| 0|0|1|0|0|
|1 1| 0|1|1|1|1

比较难以理解的是蕴含联结词。可以这样理解：$p\Rightarrow q$为真意味着p蕴含q，即当p为真时q一定为真，而不要求p为假时q的真假性。也就是说p蕴含q不成立仅有一种可能，即p为真时q为假

# 逻辑等价
在所有的模型中两个语句真假相同称为**逻辑等价**。基本的逻辑等价可以列出如下表

| 定律         | 表达式1                                   | 表达式2                                   |
| ------------ | :----------------------------------------: | :----------------------------------------: |
| 双重否定律   | $\neg \neg A \equiv A$                   |                                          |
| 恒等律       | $A \lor A \equiv A$                      | $A \land A \equiv A$                     |
| 交换律       | $A \lor B \equiv B \lor A$               | $A \land B \equiv B \land A$             |
| 结合律       | $(A \lor B) \lor C \equiv A \lor (B \lor C)$ | $(A \land B) \land C \equiv A \land (B \land C)$ |
| 分配律       | $A \lor (B \land C) \equiv (A \lor B) \land (A \lor C)$ | $A \land (B \lor C) \equiv (A \land B) \lor (A \land C)$ |
| 德·摩根律    | $\neg (A \lor B) \equiv \neg A \land \neg B$ | $\neg (A \land B) \equiv \neg A \lor \neg B$ |

存在一些为常数的情况

| 定律   | 表达式1                  | 表达式2                  |
| ------ | :---------------------: | :----------------------: |
| 零律   | $A \lor 1 \equiv 1$      | $A \land 0 \equiv 0$     |
| 同一律 | $A \lor 0 \equiv A$      | $A \land 1 \equiv A$     |
| 排中律 | $A \lor \neg A \equiv 1$ |                          |
| 矛盾律 |                          | $A \land \neg A \equiv 0$|

此外还有一些常用的逻辑恒等式

| 定律             | 表达式                                  |
| ---------------- | --------------------------------------- |
| 蕴涵等值式       | $A \Rightarrow B \equiv \neg A \lor B$ |
| 等价等值式       | $A \Leftrightarrow B \equiv (A \Rightarrow B) \land (B \Rightarrow A)$ |
| 假言易位         | $A \Rightarrow B \equiv \neg B \Rightarrow \neg A$ |
| 等价否定等值式   | $A \Leftrightarrow B \equiv \neg A \Leftrightarrow \neg B$ |
| 归谬论           | $(A \Rightarrow B) \land (A \Rightarrow \neg B) \equiv \neg A$ |

# 合取范式与析取范式

首先需要定义**简单析取式**和**简单合取式**

:::tip{title="简单析取式"}
有限个文字用“或”连接形成的析取式
:::
简单析取式的例子可以列出如下
- $p$
- $\neg p$
- $p\lor q$
- $p\lor \neg q$
- ...


:::tip{title="简单合取式"}
有限个文字用“与”连接形成的合取式
:::
简单合取式的例子可以列出如下
- $p$
- $\neg p$
- $p\land q$
- $p\land \neg q$
- ...

进一步定义**析取范式**与**合取范式**

:::tip{title="析取范式DNF（与或式，先与再或）"}
有限个简单合取式用“或”连接形成的析取式
$$
A_1\lor A_2\lor\cdots\lor A_n
$$
其中$A_i$是简单合取式
:::

:::tip{title="合取范式CNF（或与式，先或再与）"}
有限个简单析取式用“与”连接形成的合取式
$$
A_1\land A_2\land\cdots\land A_n
$$
其中$A_i$是简单析取式
:::

可以利用逻辑等价将命题改为析取范式或是合取范式

# 有效性和可满足性

**重言式**：在所有模型都为真的语句，又称为**有效的**语句，如
$$
A\lor \neg A
$$

**矛盾式**：在所有模型都为假的语句，如
$$
A\land \neg A
$$

**可满足式**：非矛盾式的语句。重言式是可满足式，但是可满足式不是重言式

重言式的反是矛盾式，可以利用这个关系证明命题，即**反证法**
$$
A\Rightarrow B 等价于 A\land \neg B 矛盾
$$

逻辑学（一）——命题与逻辑

# 逻辑的基本概念
逻辑是用符合语法的语言来表示信息从而能够推理结论

1. 语法(Syntax) 定义语句所用的语言规范
2. 语义(Semantics) 定义语句的“含义”,即每个语句在每个可能世界的真值(True or False)

若定义语法为算数语法，那么合法的语句的一个例子是
$$
x+2\geq y
$$

而$x2+y$不符合算数语法，不是语句。在世界$x=7,y=1$中$x+2\geq y$为真，而在$x=0,y=6$的世界中该语句为假



# 模型
在逻辑学的描述中，变量是布尔的，也就是拥有两个取值，`1`和`0`，也即`真`和`假`

模型就是“可能的世界”的抽象描述，如三个布尔变量ABC，它们会构成8个可能的世界，也就是具有8个可能的模型
$$
\{A,B,C\}=\{0,0,0\}, \{0,0,1\}, \{0,1,0\}, \{0,1,1\}, \{1,0,0\}, \{1,0,1\}, \{1,1,0\}, \{1,1,1\}
$$

每个模型都代表着一个“世界”，即可能出现的情况（有点像随机事件发生的平行世界？）


# 蕴含

蕴含描述两个语句的关系

:::info{title="Note"}
A蕴含B：意为当A为真时B一定为真
:::

它的另一种解释是：在A为真的每个世界中B都为真。蕴含记为`|=`，A蕴含B即记为
$$
A|=B
$$

如果令$W(A)$为所有使得$A$为真的世界的集合，$W(B)$为所有使得$B$为真的世界的集合，那么这两个集合是包含的关系
$$
W(A)\subset W(B)
$$

# 推断

推断是针对推理算法的，对一个语句执行推理算法可以得到另一个语句。记推理算法为I,则记
$$
A|-_IB
$$

意为推理算法I从A导出了B。对于推理算法，我们关心的是它的**可靠性**与**完备性**

- 可靠性：假定算法I从A导出了B，经检验对于所有这样的A和B，都有A蕴含B（推导是对的）
    $$
    若A|-_IB则A|=B，称I可靠
    $$
- 完备性：若A蕴含B，则对A施加算法I一定能得到B
    $$
    若A|=B则A|-_IB，称I完备
    $$

逻辑学（零）——模型，蕴含与推断

# 双人零和博弈
双人零和博弈是两个玩家进行的**零和博弈**。零和博弈即
- 参与双方的效用相反，一个玩家的效用高就意为着另一个玩家的效用低
- 零和博弈是纯竞争而没有合作，不存在双赢

博弈双方可以采用同一效用值，一方使得效用最大，一方使得效用最小





可以给予双人零和博弈一个形式化的描述。将两个参与者分别称为`MIN`和`MAX`，`MAX`先移动，然后`MIN`移动，直到博弈结束

一个博弈中的状态需要有以下必要的属性：`将要移动的玩家`，`可以采取的动作`，`是否终止`。不妨给予定义
- $S_0$： 初始状态，即博弈开始时的状态
- To-Move(s)： 状态s下将要移动的玩家
- Action(s)： 状态s下全体合法移动的集合
- 转移模型Result(s,a)： 状态s下执行动作a产生的状态
- 中止测试Is-terminal(s)： 判断是否博弈结束
- 效用函数Utility(s)： 终止状态s下的效用函数


# 极小极大搜索(MiniMaxSearch)

极小极大算法适用于确定性的零和博弈，一方最小化结果，另一方最大化结果。假定所有参与者都最佳移动，极小极大算法期望中构造一棵**状态空间搜索树**，博弈双方轮流行动，如图

![image.png](/static/img/a6490ed19352ff04642a3c5131ea4e3f.image.webp)

在博弈中，双方都选择对自己最有利的行为，即`MAX`选择效用最大的状态进行转移，`MIN`选择效用最小的状态进行转移。但是对于非终止状态无法定义效用，因而对于状态`s`定义**极小极大值**
$$
MINMAX(s)=
\begin{cases}
Utility(s)&s是终止状态\\
所有可转移状态的最大MINMAX&MAX玩家将要移动\\
所有可转移状态的最小MINMAX&MIN玩家将要移动
\end{cases}
$$

即

:::info{title="Note"}
MIN节点的MINMAX是`MIN`玩家能确保获得的最小效用，MAX阶段的MINMAX是`MAX`玩家能确保获得的最大效用
:::

对于`MIN`玩家而言，最佳的行动策略就是选取拥有最小MINMAX的状态；对于`MAX`玩家而言，最佳的行动策略就是选取拥有最大MINMAX的状态

极小极大搜索是对博弈树进行完整的深度优先搜索。记博弈树的最大深度为`m`，每个节点的合法行动数为`b`，那么它的时间复杂度是指数级的
$$
O(b^m)
$$
由于是深度优先搜索，空间复杂度倒不大，为$O(bm)$。虽然它是完备的，但是需要的资源是非常难以满足的

# $\alpha-\beta$剪枝
$\alpha-\beta$剪枝是对博弈树进行修剪，剪去了对结果没有影响的部分。$\alpha$剪枝是针对`MAX`玩家而言的，$\beta$剪枝是针对`MIN`玩家而言的

定义$\alpha$


:::tip{title="定义"}
$\alpha$是到目前为止所有路径上所有`MAX`选择点的MINMAX最大值
:::

如果在执行极大极小搜素时发现某个`MAX`将行动的节点其MINMAX小于$\alpha$，那么该节点以及它所有的兄弟节点都不需要考虑。这是因为`MAX`玩家应该尽可能选择高MINMAX值的节点所在分支，而不会允许`MIN`玩家逼自己选择较低MINMAX值的分支

再清晰一些的说法是，记该节点为`n`，它的父节点是`MIN`玩家做选择，`MAX`玩家是处于`n`还是`n`的兄弟是由`MIN`玩家决定的。`MIN`玩家一定会选择最小的MINMAX，轮到`MAX`玩家选择时，能确保的效用一定小于等于`n`节点的MINMAX，因而`MAX`玩家不会给`MIN`玩家选择的机会，即不会选择`n`所在的分支

:::info{title="Note"}
$\alpha$剪枝：若某一个MAX节点的MINMAX小于$\alpha$，则将其兄弟全部剪枝
:::

这对于`MIN`玩家也是同理，定义$\beta$值

:::tip{title="定义"}
$\beta$是到目前为止所有路径上所有`MIN`选择点的MINMAX最小值
:::
$\beta$剪枝策略是

:::info{title="Note"}
$\beta$剪枝：若某一个MIN节点的MINMAX大于$\beta$，则将其兄弟全部剪枝
:::

$\alpha-\beta$剪枝的有效性依赖于节点的检查顺序。最坏的顺序是每次都考察最大的MAX和最小的MIN，无法减去任何的兄弟节点，最好顺序是考察最小的MAX和最大的MIN，可以剪去尽可能多的兄弟节点。在完美顺序下的时间复杂度为
$$
O(b^{m/2})
$$

# 启发式$\alpha-\beta$数搜索
在资源受限的情形下应使用**深度受限搜索**，即
- 截断测试(Cutoff-Test)代替终止测试
- 启发式评价函数EVAL代替效用函数Utility

评价函数评估非终止节点的分值，理想中应尽可能接近实际的MINMAX。由于深度受限，评价函数不可能完全与效用函数等同，会出现**视野效应**，即无法考虑搜索深度以外的情形

# 蒙特卡洛树搜索 (MCTS)
蒙特卡洛树搜索是基于概率模拟的结果构建启发式评价函数，一种常用的选择是Upper Confidence Bounder
$$
UCB(s)=\dfrac{U(s)}{N(s)}+C\cdot\sqrt{\dfrac{\log N(s的父亲)}{N(s)}}
$$
其中
- $U(s)$是经过$s$节点所有模拟效用值之和
- $N(s)$为经过$s$节点的所有模拟次数
- $C$是一个常数，常取$\sqrt2$，用于平衡利用和探索

前一项$\dfrac{U(s)}{N(s)}$代表“经验”，即该节点的平均效用；后一项是考虑到其父节点的效用对它效用的修正，代表“探索”

# 随机博弈
随机博弈即一方选择动作后状态的转移并不确定，即存在“机会节点”
<center>
    <img src="/static/img/cda106b45f9ad41c9862e5b384bf945a.image.webp" width=70%/>
</center>

此时极小极大搜索中的MINMAX就可以变为期望MINMAX
$$
ExpectMINMAX(s)=
\begin{cases}
Utility(s)&s终止状态\\
Max:ExpectMINMAX(s的所有后继)&MAX玩家将要移动\\
Min:ExpectMINMAX(s的所有后继)&MIN玩家将要移动\\
ExpectMINMAX(s的所有后继)的数学期望&下一步是机会节点
\end{cases}
$$